Mutable Map implementation with small memory footprint.

SmallMap.java

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;
        }
    }

}