基于JDK1.7的HashMap源码详解

如有不对的地方，请指出，谢谢！

一、HashMap概述

HashMap是基于哈希表的Map接口实现，此实现提供所有可选的映射操作，并允许使用null值和null键。HashMap与HashTable的作用大致相同，但是它不是线程安全的。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

遍历HashMap的时间复杂度与其的容量(capacity)和现有元素的个数（size）成正比。如果要保证遍历的高效性，初始容量（capacity)不能设置太高或者平衡因子（load factor）不能设置太低。

二、HashMap的结构

HashMap是基于数据结构哈希表实现的，哈希表使用数组来存储元素，并使用链地址法来处理冲突（有多种方式处理冲突）。

从上图可以看出，数组中每一项都是一个单向链表。

源码如下：

//存放链表的数组
transient Entry[] table;  
//键值对，持有指向下一个Entry的引用，由此构成单向链表
static class Entry<K,V> implements Map.Entry<K,V> {  
    final K key;  
    V value;  
    //指向下一节点
    Entry<K,V> next;  
    final int hash;  
    ……  
}

三、构造器与属性

先来看看HashMap有哪些属性

    /**
     * 默认的初始化桶数量，HashMap中桶数量的值必须是2的N次幂
     */
    static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * HashMap中散列桶数量的最大值，1073741824
     */
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     * 默认的负载因子，当HashMap中元素的数量达到容量的75%时，进行扩容。
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /**
     * HashMap的存储结构
     */
    transient Entry<K,V>[] table;

    /**
     * HashMap中条目（即键-值对）的数量
     */
    transient int size;

    /**
     * HashMap的重构阈值，它的值为容量和负载因子的乘积。在HashMap中所有桶中元素的总数量达到了这个重构阈值之后，HashMap将进行resize操作以自动扩容。
     */
    int threshold;

    /**
     * 负载因子，它和容量一样都是HashMap扩容的决定性因素。    
     */
    final float loadFactor;

    /**
     * 表示HashMap被结构化更新的次数，比如插入、删除等会更新HashMap结构的操作次数，用于实现迭代器快速失败行为。
     */
    transient int modCount;

    /**
     * 默认的阀值 
     */
    static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;

    /**
     * 表示是否要对字符串键使用备选哈希函数      
     */   
     transient boolean useAltHashing;

    /**
     * 一个与当前实例关联并且可以减少哈希碰撞概率，应用于键的哈希码计算的随机种子。     
     */
    transient final int hashSeed = sun.misc.Hashing.randomHashSeed(this);

构造器：

public HashMap(int initialCapacity, float loadFactor) {
        //校验初始化容量大小
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //初始化容量是否大于容量的最大值
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        //校验加载因子
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        // Find a power of 2 >= initialCapacity
        int capacity = 1;
        //使容量为2的N次方
        while (capacity < initialCapacity)
            capacity <<= 1;

        //加载因子
        this.loadFactor = loadFactor;
        //重构阈值
        threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1);
        table = new Entry[capacity];
        //跟hash值的计算相关
        useAltHashing = sun.misc.VM.isBooted() &&
                (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        init();
    }

四、HashMap的基本操作

PUT方法

 public V put(K key, V value) {
        //如果键是NULL，调用putForNullKey方法。
        if (key == null)
            return putForNullKey(value);
        //计算hash值
        int hash = hash(key);
        //根据hash值计算桶号
        int i = indexFor(hash, table.length);
        //遍历该桶中的链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //如果其hash值相等且键相等，将新值替换旧值，并返回旧值
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        //用于Fail-Fast机制
        modCount++;
        //该桶中没有存放元素，或者没有元素的键与要PUT元素的键匹配，插入新节点
        addEntry(hash, key, value, i);
        return null;
    }

putForNullKey方法：

    private V putForNullKey(V value) {
        //遍历第一个桶中的链表
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            //如果链表中有元素的键为NULL，将新值替换旧值，并返回旧值
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //第一个桶中没有存放元素或没有节点的键为null的，插入新节点
        addEntry(0, null, value, 0);
        return null;
    }

hash方法：

    final int hash(Object k) {
        int h = 0;
        if (useAltHashing) {
            if (k instanceof String) {
                //对字符串键使用备选哈希函数
                return sun.misc.Hashing.stringHash32((String) k);
            }
            //随机种子,用来降低冲突发生的几率
            h = hashSeed;
        }

        h ^= k.hashCode();

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

该方法是“扰乱函数”，使高位和低位混合，以此来加大低位的随机性，避免低位相同而高位不同的两个数产生冲突。

indexFor方法：

    static int indexFor(int h, int length) {
        //把hash值和数组的长度进行“与”操作
        return h & (length-1);
    }

该方法用于确定元素存放于数组的位置，但是参数h是一个由hash方法计算而来的int类型数据，如果直接拿h作为下标访问HashMap主数组的话，考虑到2进制32位带符号的int值范围从-2147483648到2147483648，该值可能会很大，所以这个值不能直接使用，要用它对数组的长度进行取模运算，得到的余数才能用来当做数组的下标，这就是indexFor方法做的事情。（因为length总是为2的N次方，所以h & (length-1)操作等价于hash % length操作， 但&操作性能更优）

该方法也是HashMap的数组长度为什么总是2的N次方的原因。2的N次方 - 1的二进制码是一个“低位掩码”，“与”操作后会把hash值的高位置零，只保留低位的值，使用这种方法使值缩小。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。

    10100101 11000100 00100101
&   00000000 00000000 00001111
----------------------------------
    00000000 00000000 00000101 //高位全部归零，只保留末四位

这样，就算差距很大的两个数，只要低位相同，那么就会产生冲突，会对性能造成很大的影响，于是，hash方法的作用就体现出来了。

        h ^= k.hashCode();

        // 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);

h ^= k.hashCode(): 0101 1101 0010 1111 1100 0110 0011 0101
------------------------------------------------------------
h >>> 20：       : 0000 0000 0000 0000 0000 0101 1101 0010
h >>> 12         : 0000 0000 0000 0101 1101 0010 1111 1100 
------------------------------------------------------------
(h >>> 20) ^ (h >>> 12)
                 : 0000 0000 0000 0101 1101 0111 0010 1110
-----------------------------------------------------------
h ^= (h >>> 20) ^ (h >>> 12)
                 : 0101 1101 0010 1010 0001 0001 0001 1011
-----------------------------------------------------------
(h >>> 7)        : 0000 0000 1011 1010 0101 0100 0010 0010
(h >>> 4)        : 0000 0101 1101 0010 1010 0001 0001 0001 
-----------------------------------------------------------
(h >>> 7) ^ (h >>> 4)
                 ：0000 0101 0110 1000 1111 0101 0011 0011
-----------------------------------------------------------
h ^ (h >>> 7) ^ (h >>> 4)
                 ：0101 1000 0100 0010 1110 0100 0010 1000
-----------------------------------------------------------
h & (length-1)   ：0000 0000 0000 0000 0000 0000 0000 1000   = 8  

就这样，通过高低位之间进行异以此来加大低位的随机性，以减少冲突的几率。

addEntry方法：

void addEntry(int hash, K key, V value, int bucketIndex) {
        //如果尺寸已将超过了阈值并且桶中索引处不为null
        if ((size >= threshold) && (null != table[bucketIndex])) {
            //扩容2倍
            resize(2 * table.length);
            //重新计算哈希值
            hash = (null != key) ? hash(key) : 0;
            //重新计算桶号
            bucketIndex = indexFor(hash, table.length);
        }
        //创建节点
        createEntry(hash, key, value, bucketIndex);
    }

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];
        boolean oldAltHashing = useAltHashing;
        //计算是否需要对键重新进行哈希码的计算
        useAltHashing |= sun.misc.VM.isBooted() &&
                (newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
        boolean rehash = oldAltHashing ^ useAltHashing;
        /**
         * 将原有所有的桶迁移至新的桶数组中
         * 在迁移时，桶在桶数组中的绝对位置可能会发生变化
         * 这就是为什么HashMap不能保证存储条目的顺序不能恒久不变的原因
         */
        transfer(newTable, rehash);
        table = newTable;
        //重新计算重构阈值
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }

transfer方法：

 void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        //遍历当前的table，将里面的元素添加到新的newTable中
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    //重新计算hash值
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                //计算桶号
                int i = indexFor(e.hash, newCapacity);
                //插入到链表头部
                e.next = newTable[i];
                //存放在数组下标i中,所以扩容后链表的顺序与原来相反
                newTable[i] = e;
                e = next;
            }
        }
    }

createEntry方法：

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        //把该节点插到链表头部
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

GET方法

    public V get(Object key) {
        //如果键为null，调用getForNullKey方法
        if (key == null)
            return getForNullKey();
        //键不为null，调用getEntry方法
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

getForNullKey方法：

    private V getForNullKey() {
        //遍历第一个桶中的链表，因为putForNullKey是把NULL键存放到第一个桶中。
        for (Entry<K,V> e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

getEntry方法：

final Entry<K,V> getEntry(Object key) {

        //计算键的hash值
        int hash = (key == null) ? 0 : hash(key);
        //遍历对应桶中的链表
        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 != null && key.equals(k))))
                return e;
        }
        return null;
    }

REMOVE方法

    public V remove(Object key) {
        Entry<K,V> e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }

removeEntryForKey方法：

    final Entry<K,V> removeEntryForKey(Object key) {
        //计算键的hash值
        int hash = (key == null) ? 0 : hash(key);
        //计算桶号
        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
                    //上一节点的NEXT为将要删除节点的下一节点
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }

        return e;
    }