Skip to content

Instantly share code, notes, and snippets.

@zhong-j-yu zhong-j-yu/SmallMap.java
Last active Aug 29, 2015

Embed
What would you like to do?
Mutable Map implementation with small memory footprint.
package bayou.util;
import java.util.*;
/**
* Mutable Map implementation with small memory footprint.
* <p>
* This class is suitable for maps with small number of entries.
* The implementation stores keys and values in an array;
* searching a key will be a linear operation.
* </p>
*/
@SuppressWarnings("unchecked")
class SmallMap<K,V> extends AbstractMap<K,V>
{
// keys and values
Object[] kvs; // k1,v1,k2,v2,...
int size;
// return -1 if not found
int index(K key)
{
int h = key.hashCode();
// we compare hash codes of 2 keys, to fail fast if they are not equal (the usual case)
for(int i=0; i< size; i++)
{
K n = (K) kvs[2*i]; // kvs!=null, because size>0 here
if(h==n.hashCode() && key.equals(n))
return i;
}
return -1;
}
@Override
public V put(K key, V value)
{
int index = index(key);
if(index!=-1)
{
V old = (V) kvs[2*index+1];
kvs[2*index+1] = value;
return old;
}
// new key
if(kvs ==null)
kvs = new Object[2*4]; // usually not many keys
else if(kvs.length==2* size) // full
kvs = Arrays.copyOf(kvs, 2*(size +4)); // we don't expect many more keys
kvs[2* size] = key;
kvs[2* size +1] = value;
size++;
return null;
}
// AbstractMap does get() by linear search thru entrySet, which is generally not good.
// but it works for us, since we store entries as an array (reasoning that there aren't many entries)
@Override
public Set<Entry<K, V>> entrySet()
{
return new EntrySet();
}
class EntrySet extends AbstractSet<Entry<K, V>>
{
@Override
public Iterator<Entry<K, V>> iterator()
{
return new EntryIterator();
}
@Override
public int size()
{
return size;
}
}
class EntryIterator implements Iterator<Entry<K, V>>
{
int x;
MyEntry current;
@Override
public boolean hasNext()
{
return x < size;
}
@Override
public Entry<K, V> next()
{
if(!hasNext())
throw new NoSuchElementException();
return current = new MyEntry(x++);
}
@Override
public void remove()
{
if(current==null)
throw new IllegalStateException();
current.remove();
current = null;
x--; // adjust pointer
}
}
class MyEntry extends SimpleEntry<K, V>
{
int index; // -1 if removed
MyEntry(int index)
{
super( (K) kvs[2*index], (V) kvs[2*index+1] );
this.index = index;
}
void remove()
{
validateIndex();
int remain = size - index - 1;
if(remain>0)
System.arraycopy(kvs, 2*index+2, kvs, 2*index, 2*remain);
kvs[2* size -2]=null;
kvs[2* size -1]=null;
size--;
index = -1;
}
// the table cell pointed to by the index may no longer represent this entry
void validateIndex() throws ConcurrentModificationException
{
if(index>= size) // likely some attrs were removed by someone else.
throw new ConcurrentModificationException();
Object prevKey = this.getKey(); // as seen in the constructor
Object currKey = kvs[2* index];
if(prevKey!=currKey) // identity comparison!
throw new ConcurrentModificationException();
// even if prevKey==currKey, table might have been modified.
// we cannot detect that case, but it's not harmful.
// we could also do prevKey.equals(currKey) to be more lenient, since it's not harmful either.
}
// getKey()/getValue() still works after remove(). but setValue() does not.
@Override
public V setValue(V value)
{
if(index==-1)
throw new IllegalStateException("this entry has been removed from the map");
// setValue() after remove() is very likely a programming error.
validateIndex();
V old = super.setValue(value); // local copy
kvs[2* index +1] = value; // write through
return old;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.