Java源码阅读之HashMap

@author StormMa

@date 2017-05-31

生命不息，奋斗不止！

基于jdk1.8的HashMap源码分析。

前期准备

什么是HashMap

官方解释

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

基于哈希表的Map接口实现，此实现提供了可选的映射操作，并且允许null的key和null的value。（HashMap类大致等价于HashTable，除过它不是同步的并且允许nulls）。HashMap类也无法保证元素的顺序, 特别是，它更不能保证在一段时间之内元素的顺序不变。

总之，官方的解释说明了HashMap基于什么样的数据结构，与HashTable的区别，以及它是无序的。

什么是哈希表

既然官方已经说了HashMap是基于哈希表的Map接口实现，我想我们需要看一下哈希表是个什么玩意儿!

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。

一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则F()，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。

上面的文字节选自维基百科。我想我们得用一张图看一下哈希表究竟是个多么神奇的数据结构。

我想我得对这个图做一点解释。上图就是哈希表，当然也可以叫做链表的数组。很显然，上图中的数据结构其实就是一个数组，而数组的元素又是一个链表，这就很巧妙的结合了数组和链表的全部优点。在开始学习HashMap之前，我想我有必要说两个概念，一个是Hash冲突, 为什么会发生Hash冲突呢？在说Hash冲突之前，我想要说一下HashMap的table数组下标是怎么确定的，他有确定的计算公式，先得到key的hashcode值，然后进行二次hash之后和table数组的(length-1)做与运算得到数组的下标。但是这个数组的下标有可能会发生冲突，这个冲突就叫做Hash冲突。有了Hash冲突，才会出现上图中链状的形状的结构。链式的东西我们暂且称为bucket(桶)。我想我有必要说一下jdk1.8中和jdk1.7做了一些变化。jdk1.8中，如果一个bucket中的元素大于8个，那么会把链表转换成红黑树来提高效率。

HashMap实现内探

HashMap声明

HashMap继承了AbstractMap类并且实现了Map、Cloneable、和Serializable接口。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    ...

    //哈希表中的数组(HashMap中称为table数组), 元素是Node<K, V>，在jdk1.8之前应该是HashMapEntry<K,V>[]//Entry[K, V]初始化大小为1<<4=16
    transient Node<K,V>[] table;

    /**
     * Holds cached entrySet(). Note that AbstractMap fields are used
     * for keySet() and values().
     */
    transient Set<Map.Entry<K,V>> entrySet;

    //也就是HashMap所有的Key=>Value的个数
    transient int size; 

    //记录HashMap内部结构发生变化的次数,例如put新键值对，但是某个key对应的value值被覆盖不属于结构变化。
    transient int modCount;

    //所能容纳的key-value对极限 
    int threshold;

    //加载因子
    final float loadFactor;
    ...

}

Node[] table的初始化长度length(默认值是16)，Load factor为负载因子(默认值是0.75)，threshold是HashMap所能容纳的最大数据量的Node(键值对)个数。threshold = length * Load factor。也就是说，在数组定义好长度之后，负载因子越大，所能容纳的键值对个数越多。这里存在一个问题，即使负载因子和Hash算法设计的再合理，也免不了会出现拉链过长的情况，一旦出现拉链过长，则会严重影响HashMap的性能。于是，在JDK1.8版本中，对数据结构做了进一步的优化，引入了红黑树。而当链表长度太长（默认超过8）时，链表就转换为红黑树，利用红黑树快速增删改查的特点提高HashMap的性能，其中会用到红黑树的插入、删除、查找等算法。接下来我们先看一下Node[K, V]的声明

/**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        //下一个Node[K, V]的指针，链表的实现
        Node<K,V> next;

        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

在看HashMap存储之前，我想应该先看一下怎么确定确定哈希桶数组索引位置，即table数组的索引位置

//方法一：
static final int hash(Object key) {   //jdk1.8 & jdk1.7
     int h;
     // h = key.hashCode() 为第一步 取hashCode值
     // h ^ (h >>> 16)  为第二步 高位参与运算
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//方法二：
static int indexFor(int h, int length) {  //jdk1.7的源码，jdk1.8没有这个方法，但是代码里面的实现是一样的。
     return h & (length-1);  //第三步 取模运算
}

对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用方法一所计算得到的Hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，模运算的消耗还是比较大的，在HashMap中是这样做的：调用方法二来计算该对象应该保存在table数组的哪个索引处。

这个方法非常巧妙，它通过h & (table.length -1)来得到该对象的保存位，而HashMap底层数组的长度总是2的n次方，这是HashMap在速度上的优化。当length总是2的n次方时，h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

在JDK1.8的实现中，优化了高位运算的算法，通过hashCode()的高16位异或低16位实现的：(h = k.hashCode()) ^ (h >>> 16)，主要是从速度、功效、质量来考虑的，这么做可以在数组table的length比较小的时候，也能保证考虑到高低Bit都参与到Hash的计算中，同时不会有太大的开销。

put方法实现

put方法实现的大致思路:

1. 对key的hashCode()做hash，然后再计算index;
2. 如果没碰撞直接放到bucket里；
3. 如果碰撞了，以链表的形式存在buckets后；
4. 如果碰撞导致链表过长(大于等于TREEIFY_THRESHOLD)，就把链表转换成红黑树；
5. 如果节点已经存在就替换old value(保证key的唯一性)
6. 如果bucket满了(超过load factor*current capacity)，就要resize。

/**
     * Associates the specified value with the specified key in this map.
     * If the map previously contained a mapping for the key, the old
     * value is replaced.
     *
     * @param key key with which the specified value is to be associated
     * @param value value to be associated with the specified key
     * @return the previous value associated with <tt>key</tt>, or
     *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
     *         (A <tt>null</tt> return can also indicate that the map
     *         previously associated <tt>null</tt> with <tt>key</tt>.)
     */
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

putVal()

/**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //判断table数组是否为空
        if ((tab = table) == null || (n = tab.length) == 0)
            //创建一个新的table数组，并且获取该数组的长度 
            n = (tab = resize()).length;
        //根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加 
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {//如果对应的节点存在, 那么就是bucket冲突
            Node<K,V> e; K k;
            //判断table[i]的首个元素是否和key一样，如果相同直接覆盖value
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;

            //判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {//链表
                    //遍历table[i]，判断链表长度是否大于TREEIFY_THRESHOLD(默认值为8)，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        // 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

简单地说put时候先判断table数组是不是一个空数组，如果不是，根据hash(key)&(table.length-1)来得到table的index,然后判断table[index]是否为空节点，如果不是那么判断table[index]的首元素的key值和要put的key是否相等，如果是就覆盖value，保证key的唯一性

，如果不相等，先判断节点是否是treeNode，如果是调用红黑树的putVal方法，如果不是那么就是链表，判断链表的长度是否大于8，如果是转换成红黑树进行插入。

get的实现

大致思路:

1. bucket里的第一个节点，直接命中；
2. 如果有冲突，则通过key.equals(k)去查找对应的entry
   若为树，则在树中通过key.equals(k)查找，O(logn)；
   若为链表，则在链表中通过key.equals(k)查找，O(n)。

/**
     * Returns the value to which the specified key is mapped,
     * or {@code null} if this map contains no mapping for the key.
     *
     * <p>More formally, if this map contains a mapping from a key
     * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
     * key.equals(k))}, then this method returns {@code v}; otherwise
     * it returns {@code null}.  (There can be at most one such mapping.)
     *
     * <p>A return value of {@code null} does not <i>necessarily</i>
     * indicate that the map contains no mapping for the key; it's also
     * possible that the map explicitly maps the key to {@code null}.
     * The {@link #containsKey containsKey} operation may be used to
     * distinguish these two cases.
     *
     * @see #put(Object, Object)
     */
    public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

getNode()

/**
     * Implements Map.get and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @return the node, or null if none
     */
    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //直接找到
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //第一次未命中
            if ((e = first.next) != null) {
                    //如果是树的实现
                if (first instanceof TreeNode)
                // 树中获取
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {// 链表中获取
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

扩容机制

扩容(resize)就是重新计算容量，向HashMap对象里不停的添加元素，而HashMap对象内部的数组无法装载更多的元素时，对象就需要扩大数组的长度，以便能装入更多的元素。当然 Java 里的数组是无法自动扩容的，方法是使用一个新的数组代替已有的容量小的数组。我要补充一点就是，jdk1.8的resize方法比较jdk1.8之前的resize方法有了很多的变化，这些变化不仅仅是红黑树，还有rehash的实现。我不想直接拿着jdk1.8的resize方法来啃，我们还是先来看看jdk1.7的resize方法吧。在阅读resize方法源码的时候，刚开始我是看不懂的，然后找了几篇博客学习了一下，较之前来说好多了。

jdk1.7 resize()

/**
 * @param newCapacity 新的容量值
 */
void resize(int newCapacity) {
    //引用扩容前的Entry数组(因为jdk1.7HashMap的table元素都是Entry而不是Node)
    Entry[] oldTable = table;      
    int oldCapacity = oldTable.length;  
    //扩容前的数组大小如果已经达到最大(2^30)了
    if (oldCapacity == MAXIMUM_CAPACITY) {  
        //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了  
        threshold = Integer.MAX_VALUE;   
        return;  
    }  
    //初始化一个新的Entry数组 
    Entry[] newTable = new Entry[newCapacity];
    //将数据转移到新的Entry数组里    
    transfer(newTable);            
    //HashMap的table属性引用新的Entry数组               
    table = newTable;                            
    threshold = (int) (newCapacity * loadFactor);//修改阈值
}

transfer()方法用于把元素移动到新的table数组中去

void transfer(Entry[] newTable) {  
    //旧数组
    Entry[] src = table;
    //新容量
    int newCapacity = newTable.length; 
    //遍历旧的table数组 
    for (int j = 0; j < src.length; j++) {  
        //Entry的第一个元素
        Entry<K, V> e = src[j]; 
        if (e != null) {  
            //释放旧table数组的引用
            src[j] = null; 
            do {  
                Entry<K, V> next = e.next;  
                //重新计算新table数组中应该插在哪个位置，这一步就是rehash操作
                int i = indexFor(e.hash, newCapacity);
                //e.next = null
                e.next = newTable[i];  
                //table[i]引用e（其实就是链表头插法，和当年 c语言 写链表操作没啥区别）
                newTable[i] = e;   
                //访问这个Entry链上的下一个元素
                e = next;   
            } while (e != null);  
        }  
    }  
}

我上面所说的table数组和Entry数组其实就是一个东西，在jdk1.8中的生命是Node[K, V] [] table形式，在jdk1.7有点不一样，但是实际差不多，就更改了一下命名而已。基于上面的那个transfer方法，用一句话来概括…先放在一个索引上的元素终会被放到Entry链的尾部,,为什么呢，因为上面是采用链表的头插法，第一个引用的元素肯定就是尾部的元素了。[嘿哈]..

jdk1.8 resize()

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */

     //上面的javadoc，翻译之后得到
初始化或加倍table数组大小。如果为null，则根据在场阈值中保持的初始容量目标进行分配。否则，因为我们使用的是二次幂扩展(就是扩容的新容量值是旧的2倍)，所以每个bin中的元素必须保持相同的索引，或者在新表中以两个偏移量的方式移动。

    //其实上句话的意思就是经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。
    final Node<K,V>[] resize()

看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1和key2两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希值(也就是根据key1算出来的hashcode值)与高位与运算的结果。（注：这部门来源于别人的博客讲解，感觉讲得挺好的，所以引用来以助于自己理解!）

元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        //旧table的容量
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
                //扩容前的数组大小如果已经达到最大(2^30)了
            if (oldCap >= MAXIMUM_CAPACITY) {
            //修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            // 没超过最大值，就扩充为原来的2倍, 印证javadoc所述
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        // 计算新的resize上限
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        // 把每个bucket都移动到新的buckets中
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                    // 链表优化重hash的代码块
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // 原索引， 就是扩容之后不变的
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            // 原索引+oldCap,对应上图看
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        // 原索引放到bucket里
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        // 原索引+oldCap放到bucket里
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

jdk1.7的resize方法还算简单，但是jdk1.8的扩容必须好好研究一下。HashMap源码阅读就写到这里了，写博客真的能学习到很多，之前对HashMap的认识只停留到不同步允许null的key和value无序并且会用的层次上，但是这远远不够，还是应该多看看源码，了解一下设计者的初心。原文章来自我的个人站点: http://blog.stormma.me ，转载请注明出处!