Разреженный массив

Есть Map – известно что ключи последовательные и работают по принципу плавающего окна, чисто в теории эту структуру можно заменить на набор из N массивов, что приведет к ускорению работы. Ниже прототип, идея думаю понятная. Но дописывать вам.


import java.util.Iterator;

import org.apache.commons.lang.NotImplementedException;

/**
* Разреженная Map, в качестве ключа Long, эффективна только для алгоритма с плавающим окном, иначе перерасход памяти. Оптимазция по памяти и времени доступа,
* удаление достаточно медленное
*
* @author Квиринг А.В. May 20, 2010
* @param
*/
public class SparseLongMap implements Iterable {

private final Object[][] buckets;

private final int[] nullsCount;

private final int windowSize;

private final int modSize;

private final int countBucked;

/**
*
* @param windowSize
* размер окна (2^x)
* @param max
* максимальный размер
*/
public SparseLongMap(int windowSize, long max) {
this.windowSize = windowSize;
this.modSize = (1 << windowSize) - 1; this.countBucked = (int) (max >> windowSize);
buckets = new Object[countBucked][];
nullsCount = new int[countBucked];
}

public void put(long id, T object) {
int lo = (int) (id & modSize);
int hi = (int) (id >> windowSize);

if (buckets[hi] == null) {
buckets[hi] = new Object[1 << windowSize]; } buckets[hi][lo] = object; if (object != null) nullsCount[hi]++; } public void remove(long id) { int lo = (int) (id & modSize); int hi = (int) (id >> windowSize);

if (buckets[hi][lo] != null)
nullsCount[hi]--;

if (nullsCount[hi] == 0) {
buckets[hi] = null;
}

}

public T get(long id) {
int lo = (int) (id & modSize);
int hi = (int) (id >> windowSize);
return (T) buckets[hi][lo];
}

public boolean containKey(long id) {
return get(id) != null;
}

@Override
public Iterator iterator() {
return new Iterator() {

private int lo = -1;
private int hi = 0;
private T current;

@Override
public boolean hasNext() {
if (hi >= countBucked)
return false;

// смотрим есть ли bucked - если нет - идем далее
if (buckets[hi] != null) {
while (lo < (1 << windowSize)-1) { lo++; if (buckets[hi][lo] != null) { current = (T) buckets[hi][lo]; return true; } } } hi++; lo = -1; return hasNext(); } @Override public T next() { return current; } @Override public void remove() { throw new NotImplementedException(); } }; } }