I often found myself thinking in clojure's PersistentHashMap, this data structure is indeed marvel. I also often need this data structure in some project, and have to include the whole clojure.jar in project even if I didn't need any other functionality provided by clojure. So I clean some unnecessary code of PersistentHashMap from clojure and a…

ImmutableMap.java

/**
 *   Copyright (c) Rich Hickey. All rights reserved.
 *   The use and distribution terms for this software are covered by the
 *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
 *   which can be found in the file epl-v10.html at the root of this distribution.
 *   By using this software in any fashion, you are agreeing to be bound by
 * 	 the terms of this license.
 *   You must not remove this notice, or any other, from this software.
 **/

import java.io.Serializable;
import java.util.Iterator;
import java.util.NoSuchElementException;

// http://lampwww.epfl.ch/papers/idealhashtrees.pdf
public class ImmutableMap<K, V> {
    final int count;
    final INode<K, V> root;

    final public static ImmutableMap EMPTY = new ImmutableMap(0, null);

    public static class Entry<K, V> {
        public final K key;
        public final V value;

        public Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    static final Iterator EMPTY_ITER = new Iterator(){
        public boolean hasNext(){
            return false;
        }

        public Object next(){
            throw new NoSuchElementException();
        }
    };

    interface INode<K, V> extends Serializable {
        INode<K, V> assoc(int shift, int hash, K key, V val);

        INode<K, V> without(int shift, int hash, K key);

        V find(int shift, int hash, K key);

        // returns the result of (f [k v]) for each iterated element
        Iterator<Entry<K, V>> iterator();
    }

    private static int bitpos(int hash, int shift) {
        return 1 << mask(hash, shift);
    }

    private static int mask(int hash, int shift) {
        return (hash >>> shift) & 0x01f;
    }

    private static INode[] cloneAndSet(INode[] array, int i, INode a) {
        INode[] clone = array.clone();
        clone[i] = a;
        return clone;
    }

    private static Object[] cloneAndSet(Object[] array, int i, Object a) {
        Object[] clone = array.clone();
        clone[i] = a;
        return clone;
    }

    private static Object[] cloneAndSet(Object[] array, int i, Object a, int j, Object b) {
        Object[] clone = array.clone();
        clone[i] = a;
        clone[j] = b;
        return clone;
    }

    private static Object[] removePair(Object[] array, int i) {
        Object[] newArray = new Object[array.length - 2];
        System.arraycopy(array, 0, newArray, 0, 2 * i);
        System.arraycopy(array, 2 * (i + 1), newArray, 2 * i, newArray.length - 2 * i);
        return newArray;
    }

    private static INode createNode(int shift, Object key1, Object val1, int key2hash, Object key2, Object val2) {
        int key1hash = key1.hashCode();
        if (key1hash == key2hash)
            return new HashCollisionNode(key1hash, 2, key1, val1, key2, val2);
        return BitmapIndexedNode.EMPTY
                .assoc(shift, key1hash, key1, val1)
                .assoc(shift, key2hash, key2, val2);
    }

    private static class NodeIter implements Iterator {
        private static final Entry NULL = new Entry(null, null);
        final Object[] array;
        private int i = 0;
        private Entry nextEntry = NULL;
        private Iterator nextIter;

        NodeIter(Object[] array){
            this.array = array;
        }

        private boolean advance(){
            while (i < array.length) {
                Object key = array[i];
                Object nodeOrVal = array[i + 1];
                i += 2;
                if (key != null) {
                    nextEntry = new Entry(key, nodeOrVal);
                    return true;
                } else if (nodeOrVal != null) {
                    Iterator iter = ((INode) nodeOrVal).iterator();
                    if (iter != null && iter.hasNext()) {
                        nextIter = iter;
                        return true;
                    }
                }
            }
            return false;
        }

        public boolean hasNext(){
            if (nextEntry != NULL || nextIter != null) {
                return true;
            }
            return advance();
        }

        public Object next(){
            Object ret = nextEntry;
            if (ret != NULL) {
                nextEntry = NULL;
                return ret;
            } else if (nextIter != null) {
                ret = nextIter.next();
                if (!nextIter.hasNext())
                    nextIter = null;
                return ret;
            } else if (advance()) {
                return next();
            }
            throw new NoSuchElementException();
        }

        public void remove(){
            throw new UnsupportedOperationException();
        }
    }

    private static class Iter implements Iterator {
        private final INode[] array;
        private int i = 0;
        private Iterator nestedIter;

        private Iter(INode[] array){
            this.array = array;
        }

        public boolean hasNext(){
            while(true) {
                if (nestedIter != null) {
                    if (nestedIter.hasNext()) {
                        return true;
                    } else {
                        nestedIter = null;
                    }
                }

                if (i < array.length) {
                    INode node = array[i++];
                    if (node != null) {
                        nestedIter = node.iterator();
                    }
                } else {
                    return false;
                }
            }
        }

        public Object next(){
            if (hasNext()) {
                return nestedIter.next();
            } else {
                throw new NoSuchElementException();
            }
        }
    }

    final static class ArrayNode<K, V> implements INode<K, V> {
        final int count;
        final INode<K, V>[] array;

        ArrayNode(int count, INode<K, V>[] array) {
            this.array = array;
            this.count = count;
        }

        @Override
        public INode<K, V> assoc(int shift, int hash, K key, V val) {
            int idx = mask(hash, shift);
            INode<K, V> node = array[idx];
            if (node == null) {
                return new ArrayNode(count + 1, cloneAndSet(array, idx, BitmapIndexedNode.EMPTY.assoc(shift + 5, hash, key, val)));
            }
            INode<K, V> n = node.assoc(shift + 5, hash, key, val);
            if (n == node) {
                return this;
            }
            return new ArrayNode(count, cloneAndSet(array, idx, n));
        }

        @Override
        public INode<K, V> without(int shift, int hash, K key) {
            int idx = mask(hash, shift);
            INode<K, V> node = array[idx];
            if (node == null) {
                return this;
            }
            INode<K, V> n = node.without(shift + 5, hash, key);
            if (n == node) {
                return this;
            }
            if (n == null) {
                if (count <= 8) {// shrink
                    return pack(idx);
                }
                return new ArrayNode(count - 1, cloneAndSet(array, idx, n));
            } else {
                return new ArrayNode(count, cloneAndSet(array, idx, n));
            }
        }

        @Override
        public V find(int shift, int hash, K key) {
            int idx = mask(hash, shift);
            INode<K, V> node = array[idx];
            if (node == null) {
                return null;
            }
            return node.find(shift + 5, hash, key);
        }

        @Override
        public Iterator iterator() {
            return new Iter(array);
        }

        private INode<K, V> pack(int idx) {
            Object[] newArray = new Object[2*(count - 1)];
            int j = 1;
            int bitmap = 0;
            for (int i = 0; i < idx; i++) {
                if (array[i] != null) {
                    newArray[j] = array[i];
                    bitmap |= 1 << i;
                    j += 2;
                }
            }
            for (int i = idx + 1; i < array.length; i++) {
                if (array[i] != null) {
                    newArray[j] = array[i];
                    bitmap |= 1 << i;
                    j += 2;
                }
            }
            return new BitmapIndexedNode(bitmap, newArray);
        }
    }

    final static class BitmapIndexedNode<K, V> implements INode<K, V> {
        static final BitmapIndexedNode EMPTY = new BitmapIndexedNode(0, new Object[0]);

        final int bitmap;
        final Object[] array;

        final int index(int bit) {
            return Integer.bitCount(bitmap & (bit - 1));
        }

        BitmapIndexedNode(int bitmap, Object[] array) {
            this.bitmap = bitmap;
            this.array = array;
        }

        @Override
        public INode<K, V> assoc(int shift, int hash, K key, V val) {
            int bit = bitpos(hash, shift);
            int idx = index(bit);
            if ((bitmap & bit) != 0) {
                Object keyOrNull = array[2 * idx];
                Object valOrNode = array[2 * idx + 1];
                if (keyOrNull == null) {
                    INode<K, V> n = ((INode<K, V>) valOrNode).assoc(shift + 5, hash, key, val);
                    if (n == valOrNode) {
                        return this;
                    }
                    return new BitmapIndexedNode(bitmap, cloneAndSet(array, 2 * idx + 1, n));
                }
                if (key.equals(keyOrNull)) {
                    if (val == valOrNode) {
                        return this;
                    }
                    return new BitmapIndexedNode(bitmap, cloneAndSet(array, 2 * idx + 1, val));
                }
                return new BitmapIndexedNode(bitmap,
                        cloneAndSet(array,
                                2 * idx, null,
                                2 * idx + 1, createNode(shift + 5, keyOrNull, valOrNode, hash, key, val)));
            } else {
                int n = Integer.bitCount(bitmap);
                if (n >= 16) {
                    INode<K, V>[] nodes = new INode[32];
                    int jdx = mask(hash, shift);
                    nodes[jdx] = EMPTY.assoc(shift + 5, hash, key, val);
                    int j = 0;
                    for (int i = 0; i < 32; i++) {
                        if (((bitmap >>> i) & 1) != 0) {
                            if (array[j] == null)
                                nodes[i] = (INode<K, V>) array[j + 1];
                            else
                                nodes[i] = EMPTY.assoc(shift + 5, array[j].hashCode(), array[j], array[j + 1]);
                            j += 2;
                        }
                    }
                    return new ArrayNode(n + 1, nodes);
                } else {
                    Object[] newArray = new Object[2 * (n + 1)];
                    System.arraycopy(array, 0, newArray, 0, 2 * idx);
                    newArray[2 * idx] = key;
                    newArray[2 * idx + 1] = val;
                    System.arraycopy(array, 2 * idx, newArray, 2 * (idx + 1), 2 * (n - idx));
                    return new BitmapIndexedNode(bitmap | bit, newArray);
                }
            }
        }

        @Override
        public INode<K, V> without(int shift, int hash, K key) {
            int bit = bitpos(hash, shift);
            if ((bitmap & bit) == 0) {
                return this;
            }
            int idx = index(bit);
            Object keyOrNull = array[2 * idx];
            Object valOrNode = array[2 * idx + 1];
            if (keyOrNull == null) {
                INode<K, V> n = ((INode<K, V>) valOrNode).without(shift + 5, hash, key);
                if (n == valOrNode) {
                    return this;
                }
                if (n != null) {
                    return new BitmapIndexedNode(bitmap, cloneAndSet(array, 2 * idx + 1, n));
                }
                if (bitmap == bit) {
                    return null;
                }
                return new BitmapIndexedNode(bitmap ^ bit, removePair(array, idx));
            }
            if (key.equals(keyOrNull)) {
                // TODO: collapse
                return new BitmapIndexedNode(bitmap ^ bit, removePair(array, idx));
            }
            return this;
        }

        @Override
        public V find(int shift, int hash, K key) {
            int bit = bitpos(hash, shift);
            if ((bitmap & bit) == 0) {
                return null;
            }
            int idx = index(bit);
            K keyOrNull = (K) array[2 * idx];
            V valOrNode = (V) array[2 * idx + 1];
            if (keyOrNull == null) {
                return ((INode<K, V>) valOrNode).find(shift + 5, hash, key);
            }
            if (key.equals(keyOrNull)) {
                return valOrNode;
            }
            return null;
        }

        @Override
        public Iterator iterator() {
            return new NodeIter(array);
        }
    }

    final static class HashCollisionNode<K, V> implements INode<K, V>{
        final int hash;
        final int count;
        final Object[] array;

        HashCollisionNode(int hash, int count, Object... array) {
            this.hash = hash;
            this.count = count;
            this.array = array;
        }

        @Override
        public INode<K, V> assoc(int shift, int hash, Object key, Object val) {
            if (hash == this.hash) {
                int idx = findIndex(key);
                if (idx != -1) {
                    if (array[idx + 1] == val) {
                        return this;
                    }
                    return new HashCollisionNode(hash, count, cloneAndSet(array, idx + 1, val));
                }
                Object[] newArray = new Object[2 * (count + 1)];
                System.arraycopy(array, 0, newArray, 0, 2 * count);
                newArray[2 * count] = key;
                newArray[2 * count + 1] = val;
                return new HashCollisionNode(hash, count + 1, newArray);
            }
            // nest it in a bitmap node
            return new BitmapIndexedNode(bitpos(this.hash, shift), new Object[] {null, this})
                    .assoc(shift, hash, key, val);
        }

        @Override
        public INode<K, V> without(int shift, int hash, Object key) {
            int idx = findIndex(key);
            if (idx == -1) {
                return this;
            }
            if (count == 1) {
                return null;
            }
            return new HashCollisionNode(hash, count - 1, removePair(array, idx/2));
        }

        @Override
        public Object find(int shift, int hash, Object key) {
            int idx = findIndex(key);
            if (idx < 0) {
                return null;
            }
            if (key.equals(array[idx])) {
                return array[idx + 1];
            }
            return null;
        }

        public int findIndex(Object key) {
            for (int i = 0; i < 2 * count; i += 2) {
                if (key.equals(array[i])) {
                    return i;
                }
            }
            return -1;
        }

        @Override
        public Iterator iterator() {
            return new NodeIter(array);
        }
    }

    public ImmutableMap(int count, INode<K, V> root) {
        this.count = count;
        this.root = root;
    }

    public ImmutableMap assoc(K key, V val) {
        INode<K, V> newroot = (root == null ? BitmapIndexedNode.EMPTY : root)
                .assoc(0, key.hashCode(), key, val);
        if (newroot == root) {
            return this;
        }
        return new ImmutableMap(val == null ? count : count + 1, newroot);
    }

    public ImmutableMap without(K key) {
        if (root == null) {
            return this;
        }
        INode<K, V> newroot = root.without(0, key.hashCode(), key);
        if (newroot == root) {
            return this;
        }
        return new ImmutableMap(count - 1, newroot);
    }

    public Iterator<Entry<K, V>> iterator() {
        return (root == null) ? EMPTY_ITER : root.iterator();
    }

    public V valAt(K key) {
        return root != null ? root.find(0, key.hashCode(), key) : null;
    }
}