Java HashMap 源代码学习

注：这里使用的是java 1.6版本。

1.HashMap继承AbstractMap，实现Map、Cloneable、Serializable接口；

2.HashMap的内部是通过数组实现的；
    2-1 HashMap的内部结构

    /**
     * The table, resized as necessary. Length MUST Always be a power of two.
     */
    transient Entry[] table;

 
    2-2 Entry的定义：

    static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        final int hash;

        /**
         * Creates new entry.
         */
        Entry(int h, K k, V v, Entry<K,V> n) {
            value = v;
            next = n;
            key = k;
            hash = h;
        }

 
    Entry是一个链表结构；
    对于一个Map中的对象，对应一个Entry；
    默认初始的table大小为16，最大为1<<30，即1073741824。

 

3. HashMap的初始化方法。

一共有四种：

    HashMap (int initiaCapacity, float loadFactor);

    HashMap (int initialCapacity);

    HashMap();

    HashMap (Map<? Extends K, ? extends V> map);

    前面三个仅仅是指定HashMap的基本参数，比如容量（capacity），扩展因子（loadFactor）；第四种是通过一个已经定义的Map对HashMap进行初始化，具体的方法是通过putAllForCreate()完成。

    3-1 HashMap的Map初始化

    public HashMap(Map<? extends K, ? extends V> m) {
        this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1,
                      DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR);
        putAllForCreate(m);
    }

 
    这里首先是申请新的内存空间，新建对象；
    然后在putAllForCreate()方法中，通过迭代器的循环，将参数map中的结果写入；
    结果的写入通过putForCreate(K k, V v)方法完成。
    3-2 HashMap的Entry插入方法

    private void putForCreate(K key, V value) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);

        /**
         * Look for preexisting entry for key.  This will never happen for
         * clone or deserialize.  It will only happen for construction if the
         * input Map is a sorted map whose ordering is inconsistent w/ equals.
         */
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                e.value = value;
                return;
            }
        }

        createEntry(hash, key, value, i);
    }

 
    在putForCreate(K k, V v)方法中，首先获取新对象的hash值，计算该hash在table数组中的位置；然后检查该对象是否已经存在，如果存在，则插入失败；否则进行插入。
    插入方法在createEntry中进行：
    3-3 createEntry方法

    void createEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        size++;
    }

 
    可以看到，新的元素将在链表的头部被插入。
    同时，注意到HashMap中，size表示的是Entry对象的数量；而不是table数组的长度，即table.length。

4.这里有个比较巧妙的地方，即hash方法的实现以及通过hash和table长度快速定位Entry在table数组中的位置。
    Hash方法是通过移位操作完成的。如下：
    4-1 HashMap的hash方法

    /**
     * Applies a supplemental hash function to a given hashCode, which
     * defends against poor quality hash functions.  This is critical
     * because HashMap uses power-of-two length hash tables, that
     * otherwise encounter collisions for hashCodes that do not differ
     * in lower bits. Note: Null keys always map to hash 0, thus index 0.
     */
    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

    /**
     * Returns index for hash code h.
     */
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

 
5.Get方法
    很简单，如下：

    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

 
    当输入的key为null时，从table[0]中返回key为null时的结果；（getForNullKey()）。
    当key为非null时，遍历对应的链表，直到找到符合条件的Entry；如果链表遍历完成之后还没有找到，则返回空结果null。
    需要说明的是，对于hash方法，不同的入参，有可能得到相同的结果，这就是所谓的“hash碰撞”。理想地，hash算法设计的目的，就是尽量减少碰撞的现象，使经过hash计算之后，结果尽量地分散，这样才能保证hash的效率最好。一种极端的情况是，所有的对象，hash的结果都相同，这种情况下，Map就退化成了链表，查询效率将大大下降。

6.containsKey方法
    public boolean containsKey(Object key)；
    这其实也就是一种查询，除了对key进行检查之外，执行的方法和get方法一致。

7.put方法
    代码如下：

    public V put(K key, V value) {
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key.hashCode());
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

 
    对于key为null的情况，将更新table[0]链表中，key为null的Entry；如果已经存在一个key为入参的entry，则更新这个entry，然后将旧的值返回；如果不存在这样的Entry，则插入一个。插入的方法为addEntry，后续马上进行说明；（putForNullKey()）。
    当key不为null的时候，先进行查找。通过key查找Entry，如果找到，则更新Entry的value，然后将旧的value返回；如果没有找到，则新增一个Entry。
    新增Entry通过addEntry方法完成。同样是通过头部插入，新的结果被放在链表的头部。与createEntry方法不同的是，这里需要进行一次扩容判断，如果满足要求，则进行一次扩容。
    addEntry方法如下：

    void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

 
    扩容的条件是，当前HashMap的大小达到了阈值的设置（阈值的计算：threshold=capacity*loadFactor）；扩容是将table的长度扩展为原来的两倍。
    Resize方法如下：

    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }

 
    Resize方法，会重新申请新的内存保存新的结果，老的table数组将会被回收。
    这里，如果旧的table的容量已经达到了设置的上限（2<<30），则新的table的threshold将会设置为最大整数值，这意味着，后续不能进行扩容了。

    将旧的结果重新设置到新的table中的过程在transfer中完成。

    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry<K,V> next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

 

    整个过程相当于，遍历一次所有的旧的table，以及table中每个链表的元素；然后重新写入新的table中——同样是头部插入。

    这是个非常耗时的操作，所以为了性能考虑，尽量在初始化的时候，设置好合理的capacity和loadFactor，尽量避免这个方法的执行。

    在最后，modCount完成一次自增操作；modCount用来记录HashMap的结构性变化的次数；在同步操作的时候用到，使失败尽可能早的发生（ConcurrentModificationException）。

    同时，在put的时候，返回结果为旧的value；如果旧的value不存在，直接返回null。

 

8. putAll方法

    public void putAll (Map<? Extends K, ? extends V> map);

    将入参的map的结果全部插入HashMap中。

    主要的做法就是检查容量，是否需要进行扩容；

    然后通过循环，将map中的Entry对象通过循环写入。

9.remove方法
    将一个元素HashMap中删除。
    返回结果是被删除的Entry的值（value）。
    通过removeEntryForKey方法完成。

    final Entry<K,V> removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry<K,V> prev = table[i];
        Entry<K,V> e = prev;

        while (e != null) {
            Entry<K,V> next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }

 
    这是一个简单的链表删除的操作；这里就不进行赘述了。
    不过需要注意，在HashMap的范围中进行变量的操作，比如modCount和size。

10.removeMapping
    删除一个映射；相当于删除一个Entry，不过这个Entry传入的时候，类型进行了向上扩展，变成了Object。
    操作的方法和removeEntryForKey一致。

11.clear方法
    清理HashMap中Entry。
    clear方法

    public void clear() {
        modCount++;
        Entry[] tab = table;
        for (int i = 0; i < tab.length; i++)
            tab[i] = null;
        size = 0;
    }

 
    主要是将所有的引用置空，除了modCount和size，其他的参数设置不变。

12.containsValue方法
    判断HashMap中是否含有value。

    public boolean containsValue(Object value) {
	if (value == null)
            return containsNullValue();

	Entry[] tab = table;
        for (int i = 0; i < tab.length ; i++)
            for (Entry e = tab[i] ; e != null ; e = e.next)
                if (value.equals(e.value))
                    return true;
	return false;
    }

 
    这也相当于一次遍历，如果HashMap的Entry很多的话，效率会很差；慎用。

13.其他辅助访问对象
    为了便于HashMap的遍历，在HashMap的类中，还定义了一些辅助的访问类。比如ValueIterator、KeyIterator、EntryIterator、HashIterator、entrySet、KeySet等等，这里就不一一列举了。
    同时，为了支持序列化，HashMap也实现了readObject和writeObject方法。