HashTable、HashMap与ConCurrentHashMap源码解读

HashMap 的数据结构

hashMap 初始的数据结构如下图所示,内部维护一个数组,然后数组上维护一个单链表,有个形象的比喻就是想挂钩一样,数组脚标一样的,一个一个的节点往下挂。

hashMap初始数据结构图

我们可以看源码来验证下,HashMap 的数据结构是不是真的是像上面所说是数组加链表的形式:

//此处略过其他代码,只截取出了hashMap的数组结构相关的数组与链表
public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {

    private static final long serialVersionUID = 362498820763181265L;
    
    /* ---------------- Fields -------------- */

    /**
     * The table, initialized on first use, and resized as
     * necessary. When allocated, length is always a power of two.
     * (We also tolerate length zero in some operations to allow
     * bootstrapping mechanics that are currently not needed.)
     */
     //这个是hashMap内部维护的数组
    transient Node<K,V>[] table;
    
    
    /**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
     //这个是数组元素的节点类,next的属性表示下一个节点,即数组的节点元素维护的下一个节点的元素,那不是就是链表吗
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash; //数组的脚标值,下面会详细描述这个内容
        final K key; //map的key
        V value; //map的value
        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()) &amp;&amp;
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

通过源码可知,HashMap 的数据结构正如上文所述,是一个数组加链表的形式存储数组,那么数组的角标是怎么计算的呢?如果是你来设计,你会怎么去设计这个角标的计算方式呢?

在没看源码之前,我做了一个猜想,就是数组的角标我猜想是按照下面的计算方式计算的:

  • 既然是 HashMap,那肯定有个 hashCode
  • 然后通过 key 值的 hashCode 与数组的长度取模
  • 取模之后,数值一样的,就往数组的节点上面往下挂 上面是我的猜想,但是 HashMap 的数组角标的实现真的是这样吗?我们进入下一节去探究

hash 值的计算

既然要看脚标值的计算,那我们肯定要看 HashMap 的 put 方法,因为在 put 方法里面肯定要计算出脚标的值,然后才能把数据存放到数组里面去嘛,所以我们直接看 put 的源码:

    /**
     * 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>.)
     */
    //此处是HashMap的put方法的源码,这个put方法又调了另一个putVal的方法,我们看一下putVal的方法
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    /**
     * 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;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) &amp; hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {

这里我们关注 tab[i] = newNode(hash, key, value, null); 这句代码,前面我们看到了tab就是数组,那说明这句代码就是给节点赋值,那么 i 就是数组的角标那这个 i 是怎么计算的呢?

看他上面的一句判断 (p = tab[i = (n - 1) & hash] 即这个 i 是通过 (n - 1) & hash 计算出来的, n = tab.length 这个 n 是数组的长度,就是说数组的角标是通过数组的长度-1与上这个 hash ,这个跟我们之前猜想的然后通过hashCode与数组的长度取模就不一致了,那这里我们先保留着这个问题,先看一下 hash 的计算,从上面代码中,可以知道, hash 值是通过调用 hash(key) 方法调用得到。

这里我将计算 hash 的方法,单独抽离出来外面写,如下:

    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

key 就是 map 调用 put 方法,put 进来的 key 值,看上面这个方法,前面判空之后返回0的大家一眼就看明白了,主要关注后面的内容, (h = key.hashCode()) ^ (h >>> 16) 这句代码前半部分很明白,就是取key的hashCode值赋给h,( ^ 这个符号表示异或, >>> 表示无符号右移),然后与h右移16位后的值进行异或操作。

为什么要这样计算去计算 hash 呢?这样计算 hash 又最终与数组的脚标有什么联系呢?

下面我来画张图,来理顺这一块的计算,看下图:

hashCode异或运算计算hash

这样做可以实现 hashCode 的值,高低位更加均匀地混到一起,结合上面数组脚标 (n - 1) & hash 的运算,由于 HashMap 数组的大小总是 2^n,即 (2^n-1) 得到的值转化为二进制,如: 00001111、00011111 (舍弃前面高位)等,与 hash 的值进行与运算,这样又保证每一个脚标 i 值都能在数组的长度内。这里可能有点难理解,举个例子来说明一下。

就是 hashMap 的数组初始大小是 16,那 length-1 的值就为 15,15 的二进制值是.... 0000 1111,此时上面hash 值 363766277 的二进制位 0001 0101 1010 1110 1010 0010 0000 0101,这两个数进行与运算时,由于 15 的前面高位都为 0,所以进行与运算的值最终都不可能大于15,像这个例子,最终的值为 0101 为 9,这样就保证了每一个脚标 i 值都能在数组的长度内。

那么这里就有一个疑问了,为什么不直接采用与数组长度取模的方式,直接取得脚标值,而是先去异或,再与运算去计算脚标值?

主要有两个原因:

1.用位运算,效率更高

  1. hashCode 的高低位异或运算,让高低位更加均匀的混合到一起,可以使得在 put 元素时,可以减少哈希碰撞

减少哈希碰撞才是最主要的原因。那什么是哈希碰撞呢?

我们知道 HashMap 的数组结构不是数组加链表吗?那数组跟链表有什么特点?我们都知道数组是查询快、增删慢,链表是查询慢、增删快。

这也很容易理解,链表嘛,只记录着下一个节点的值,又没有脚标,如果你这个链表很长(虽然在这里最长不会超过8,后面会讲到),你查找的一个元素刚好在最后一个,那不是在定位到数组脚标以后找到链表的第一个节点,然后往下一直遍历查找到最后一个才找到我们要的元素,这样效率不就很慢了吗,所以如果我们直接对 hashCode 跟数组的长度进行取模,计算出的 hash 值可能会碰撞高,就会使得数组单个节点的链表很长很长,而这样子 HashMap 的查询效率就很差,而 hashCode 的高低位异或运算,可以让高低位更加均匀的混合到一起,减少哈希碰撞,从而提高 HashMap 的查询效率。

一句话总结,失败的 hashCode 算法会导致 HashMap 的性能由数组下降为链表,所以想要避免发生碰撞,就要提高 hashCode 结果的均匀性。

数组的扩容

数组的初始化长度

在上一节的时候,我们讲到了 HashMap 的长度总是 2^n 这句话,我们怎么知道呢,我们可以从源码中找到这一设定,那么我们首先先看一下,HashMap 数组初始的默认大小是多少呢,源码中有这一句代码

    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

但是,我们不能光看这个常量值就说HashMap内数组的默认常量值就是 16 啊,我们要继续找到初始化的方法代码,看他是不是初始值为 16

    /**
     * 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
     */
    //上面的英文中说到,初始化或者翻倍数组的大小
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &amp;&amp;
                     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; //当oldTab即为table数组的长度,当oldTab长度为0时,将DEFAULT_INITIAL_CAPACITY赋值给newCap,newCap即为数组的新长度
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }

我们可以查询下 resize() 方法的调用者,发现 putVal() 方法里调用了这个方法

putVal方法调用resize()

截图中的代码已经很清楚了,就是当 table 数组的长度为 null 或长度为 0 时,调用初始化 resize() 方法,然后在 resize() 方法中也做了判断,当table数组的长度为 0 时,将新数组的长度赋值为 DEFAULT_INITIAL_CAPACITY

所以 HashMap 中数组的初始化长度就是 DEFAULT_INITIAL_CAPACITY ,等于 1 << 4 ,等于 16

数组扩容的阈值

上一节我们知道数组的初始长度是 16,然而 16 的长度显然不能满足我们普通应用的开发,所以这里就涉及到了数组的扩容。那要什么时候扩容,怎么扩呢?

我们知道,链表的查询效率肯定比数组的查询效率低,所以要提高 HashMap 的查询效率,我们肯定要数据尽可能多的往数组上存数据,而不是延长链表的长度。那是不是存满之后再做扩容呢?比方说数组初始化 16,等到存满 16 的时候或者第 17 个进来的时候,开始扩容呢?

我们可以先分析一下,然后再来看源码。当数组的元素都放满了,然后这时候来扩容,扩容之后,数组元素的脚标值就得重新计算,即 rehash ,比如原来是计算hash用的数组长度 16,扩容之后数组长度变成了 32,这时候 (n - 1) & hash 计算脚标的值就不正确了,那你数组都存满了,那不是数组的每个元素都得重新计算脚标 i 值,所以这种做法是不是不合理?

hashMap初始数据结构图

所以这里就有一个数组扩容的阈值,就是说,当数组的长度达到某个值或某个条件时,数组就开始扩容,而这里的某个值或某个条件就是我们所说的数组扩容的阈值。

那么这个阈值具体是多少呢?下面我们来探究源码,既然要找到扩容的阈值,那我们不外乎要从两个方法入手去找,一个就是 put() 操作的时候,一个就是扩容 resize() 的时候。因为我已经找过了,我就直接去 put() 方法里面找了, resize() 方法后面会细讲,这里就讲 put() 方法。

    //这里put方法只调用了putVal方法,那我们就直接看putVal方法
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    //我解释下这个方法里面,大概的操作
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length; //这一步之前分析过了,就是判断数组为null或长度为0时,对数组进行扩容
        if ((p = tab[i = (n - 1) &amp; hash]) == null)
            tab[i] = newNode(hash, key, value, null); //这一步其实也很清楚了,就是根据hash值计算出数组的脚标,然后判断数组的该脚标的元素是否为空,为空的话就把put进来的数据封装成节点赋值进数组
        else {
            //根据上面的两个判断,那么走到这里的代码就是说,数组不为空,而且put进来的key计算所得的脚标节点也不为空,走这一块逻辑(实际上这块逻辑也跟扩容的阈值无关,只是单纯的判断然后加节点的操作,但是我还是解释下这里的代码)
            Node<K,V> e; K k;
            if (p.hash == hash &amp;&amp;
                ((k = p.key) == key || (key != null &amp;&amp; key.equals(k))))
                e = p;//这里的意思是说,如果hash值相同,key值也相同,那么就说明此时put操作的元素在数组从存在,这覆盖该节点
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //这里是判断节点类型是否是树类型,为什么会是树类型呢?不是说是HashMap是数组加链表吗?后面的章节会详细讲到,这里暂且跳过
            else {
                //代码走到这里,就说明此时put进来的元素,对应的数组脚标是个链表
                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;
                    }
                    //这里判断hash值与key值是否都相同,如果是即说明map中存在该key-value,此时跳出循环
                    if (e.hash == hash &amp;&amp;
                        ((k = e.key) == key || (key != null &amp;&amp; key.equals(k))))
                        break;
                    p = e;
                }
            }
            //此逻辑是判断hash值与key值是否都相同跳出循环后,将新值覆盖旧值,然后将旧值返回出去
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;//hashMap内部维护的一个修改的次数,有兴趣了解的话可以看源码里面对这个属性的翻译
        if (++size > threshold)
            resize();//扩容,在此之前的代码,都是判断之后进行添加覆盖节点的操作,此处是插入新节点之后判断是否扩容,所以这里的条件就是我们找了这么久的扩容的阈值!!!
        afterNodeInsertion(evict);
        return null;
    }

走读完上面的代码,我们可以得知 if (++size > threshold) ,如下代码可知 size 实际上就是HashMap集合的键值对数,即长度,所以就是说,当 size 的大小超过 threshold 时,开始进行扩容,也即 threshold 就是进行扩容的阈值。那么这个阈值的大小是多少呢?

    /**
     * The number of key-value mappings contained in this map.
     */
    transient int size;

    /**
     * Returns the number of key-value mappings in this map.
     *
     * @return the number of key-value mappings in this map
     */
    public int size() {
        return size;
    }

继续走读源码,找到 resize() 方法处,

resize方法初始化数组长度与阈值

    /**
     * The load factor used when none specified in constructor.
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

当 HashMap 数组为 null 或长度为 0 时,初始化 threshold 的值, DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITYDEFAULT_INITIAL_CAPACITY 为数组的初始长度, DEFAULT_LOAD_FACTOR 是阈值的计算因子,他的值是 0.75f,意思就是当 HashMap 的 size 超过数组长度的75%的时候,就进行扩容。

我们可以继续走读源码来验证是否数组长度超过 75% 就进行扩容,还是上面那张图的源码,我把其中一段给抽离出来,如下:

        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //此处的意思是说,当数组的长度是大于0的时候,而且数组扩容一倍之后,小于默认配置的最大值时,并且大于初始化数组的长度,则执行if下面的代码,那就是说,扩容之后如果没超过最大值,就走这个逻辑
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &amp;&amp;
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //而这个逻辑的代码意思,就是阈值threshold增大一倍(左移一位)
                newThr = oldThr << 1; // double threshold
        }

那么,我们就知道了,当数组扩容时, threshold 的值也会增大一倍,那么下一次扩容时,也是HashMap的 size 超过数组长度的 75% 的时候,就进行扩容。

扩容

HashMap 内数组的扩容是将数组的长度左移一位,在二进制运算中,左移一位实际上就是将数值扩大一倍。而且我们也知道,扩容的源码就是 resize() 这个方法,所以这一章节就来重点解读 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
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table; //oldTab就是扩容前数组对象
        int oldCap = (oldTab == null) ? 0 : oldTab.length; //oldCap就是扩容前数组的长度
        int oldThr = threshold; //oldThr就是扩容前的阈值
        int newCap, newThr = 0; //声明newCap-扩容后的数组长度,newThr-扩容后的阈值
        if (oldCap > 0) {
            //这一部分逻辑其实上一节已经讲过了,在这里我就大致说一下,就是如果这是扩容前数组长度已经达到了默认配置的最大值时,那么就不扩容了,直接返回原数组,否则,数组扩容一倍,阈值也增大一倍
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &amp;&amp;
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr; //这个判断不是正常创建Map集合走的逻辑,这里可以跳过这句代码
        else {               // zero initial threshold signifies using defaults
            //这一步的代码前面也解释过了,就是当数组长度为0,初始化数组长度与扩容的阈值
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY &amp;&amp; ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //将新的扩容后的阈值赋值给threshold
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //创建新的数组
        table = newTab;
        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 &amp; (newCap - 1)] = e; //根据hash值与新数组的长度进行与操作,获取新数组的脚标值,将节点存储到新数组
                    else if (e instanceof TreeNode) //如果节点是树节点,走这个逻辑,后面讲链表的红黑树的时候会做解释,这里先跳过
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { //所以这一部分的逻辑,就是如果节点是链表,走这里
                        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 &amp; oldCap) == 0) {
                                //这个判断是理解这整个链表遍历的关键,这里也涉及到了前面讲到的2^n-1对应二进制是0111xxxx的内容,我们知道数组的长度总是2^n,所以oldCap的值实际上就是1000xxxx,然后hash &amp; oldCap的操作,就是判断oldCap高位的1与对应hash那一位的值是否是1,如果是0走这个逻辑,如果是1走下面的else代码
                                //这里,前面声明的4个变量loHead, loTail, hiHead, hiTail中,lo的指的是低位,hi的指的是高位,走完这个do里面的逻辑,就是将oldCap高位的1与对应hash那一位的值是0的存到loTail这个链表中,高位是1的存到hiTail这个链表中!!!!
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            //将上面遍历之后低位的loTail存放到新数组的原脚标处
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            //将上面遍历之后高位的hiTail存放到新数组的扩容后的脚标处
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

在上面的源码解读中,我们可能会留有一个问题,就是为什么扩容后,对数组中的链表还要做 (e.hash & oldCap) == 0 的判断?

实际上这部分逻辑是为了提高HashMap的查询性能,因为数组扩容后,节点要重新散列,那么节点上面的链表当然也最好要做到均匀的分布,减少单个数组节点上的链表长度,变相的提高了查询性能。所以,源码的逻辑是在扩容后将低位的 loTail 存放到新数组的原脚标处,高位的 hiTail 存放到新数组的扩容后的脚标处(jdk1.8新设计)

jdk1.8 hashMap扩容例图

注:有同学可能会纠结于,为什么代码中高位的链表是直接 j + oldCap 的脚标,不需要重新计算hash与上新数组长度计算吗?其实这是一个简单的数学问题而已,你自己举个例子计算一下就可以明白,结果是一样的

链表的“扩容”

前面的章节已经对 HashMap 数组的扩容及其重新散列的内容讲完了,这一章节的内容来讲一讲链表的"扩容"。根据前面的内容,我们了解到,如果链表的长度越来越长,HashMap 的查询效率也会随之降低。所以单纯的对链表长度的增加,显然是不可取的。

所以在 HashMap 中,对于链表实际上并没有扩容操作。在本文开头列出的 Node 节点的源码中也可以看到,内部并没有维护一个size或者length的属性,也没有一个去获取 length 或 size 相关的方法,所以本章节主要阐述的内容,是链表结构向树状结构的转化。

单链表-->红黑树

在前面“数组扩容的阈值”章节的时候,我曾解读过 putVal 方法的代码,在解读过程中,我跳过了两次代码逻辑,在这一章节我就来详细的解读这两处逻辑

putVal方法未解读的两处逻辑

我们先看 for 循环遍历处的代码,此处的遍历的内容是 HashMap 是 put 操作节点是为链表时的逻辑:首先这里先判断链表的 next 节点是否为空,为空则将 put 操作的 key-value 封装为 node 对象,赋值给 next 节点,然后下一步的判断 if (binCount >= TREEIFY_THRESHOLD - 1) 是这里的关键, TREEIFY_THRESHOLD 这个是什么呢? THRESHOLD 这个单词是不是看着有点眼熟,在前面将数组扩容的阈值的时候,是不是用的这个单词,那在这里的 TREEIFY_THRESHOLD 会不会就是链表结构转树状结构的阈值呢?

通过上面这段代码的上下文,我们知道 binCount 就是链表的长度(注意:这里是从 0 开始的),而 TREEIFY_THRESHOLD 看下面的源码,默认值是 8,意思就是说当链表的长度,大于等于 8 时,就执行 treeifyBin(tab, hash);

    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     */
    static final int TREEIFY_THRESHOLD = 8;

treeifyBin(tab, hash); 方法的内容是做什么呢?

    /**
     * Replaces all linked nodes in bin at index for given hash unless
     * table is too small, in which case resizes instead.
     */
    //翻译大概的意思就是,在给定hash的节点处替换节点类型,除非是数组的长度太小了,才进行resize操作
    //总结就是说,并不是链表的长度超过了默认的阈值8时,就一定转树状结构,还要判断数组的长度是否已经经过了扩容
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //这里就是上面翻译说的判断,MIN_TREEIFY_CAPACITY的值是64,就是说如果你的数组没有经过扩容操作的情况下,如果链表长度已经超过8了,此时不转树状结构,而是进行数组扩容,数组扩容时会重新散列,将链表的节点均匀的分布,查询效率对比转树状结构也要好,不得不佩服设计者的设计。
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        else if ((e = tab[index = (n - 1) &amp; hash]) != null) {
            //此处代码就是找到给定的hash的节点,将此节点的链表转为红黑树,下面的代码主要是数据结构代码的内容,有兴趣的同学可以自己解读,由于时间原因,我就不解读这部分转红黑树的代码了
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

在上面的源码解读中,我们知道,并不是链表的长度超过了默认的阈值 8 时,就一定转树状结构,还要判断数组的长度是否已经经过了扩容,就是说如果你的数组没有经过扩容操作的情况下,如果链表长度已经超过 8 了,此时不转树状结构,而是进行数组扩容,数组扩容时会重新散列,将链表的节点均匀的分布,查询效率对比转树状结构也要好。

那么在数组扩容后,链表长度也超过了 8,此时就进行转红黑树的操作,那红黑树又是什么呢?

hashMap链表转红黑树

我们知道链表的查询时间复杂度最坏的情况有可能是 O(n) ,当你想要找到节点刚好是在链表的最后一个时,你就必须得遍历完链表中所有的节点才能找到你要的值,查找效率太低。而红黑树的本质其实是一棵平衡二叉查找树,平衡二叉查找树的特点就是左子节点小于等于父节点,右子节点大于等于父节点,所以他的查询时间复杂度是 O(Log2n) ,比链表的 O(n) 效率就要高很多了。

本章开头说到的另一处未解读的putVal源码,其实只是判断是树状结构时,将节点按照红黑树的规则,put进树中而已。

e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

HashTable 的数据结构

在前面解读的 HashMap 中,已经将HashMap的数据结构,还有put操作、扩容做了详细的解读,而其实 HashTable,只是在 HashMap 的基础上,给各个操作都加上了synchronized关键字而已,这就是我们常说的 HashTable 是线程安全的,而 HashMap 是线程不安全的,如下代码。

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable {

    private transient Entry<?,?>[] table; //数组
    private int threshold; //数组扩容阈值
    private float loadFactor;
    
//链表实体类
private static class Entry<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Entry<K,V> next;
    
//put方法
public synchronized V put(K key, V value) {
        // Make sure the value is not null
        if (value == null) {
            throw new NullPointerException();
        }

 //remove方法
 public synchronized V remove(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash &amp; 0x7FFFFFFF) % tab.length;
 
 //get方法
 public synchronized V get(Object key) {
        Entry<?,?> tab[] = table;
        int hash = key.hashCode();
        int index = (hash &amp; 0x7FFFFFFF) % tab.length;
        for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) {
            if ((e.hash == hash) &amp;&amp; e.key.equals(key)) {
                return (V)e.value;
            }
        }
        return null;
    }

内部也是维护了一个数组与链表,然后在 put、get 等方法上都加上 synchronized 关键字,那这样就能确保 HashTable 在任何场景都是线程安全的吗?

HashTable 是否在任何场景都是线程安全的?

这里有几个场景:

(1)若 key 不存在,则添加元素

(2)若 key 存在,则删除元素

我在这里画张图来描述下多线程环境下的这两个场景

hashtable在复合操作下的线程安全问题

存在这样问题的原因是复合操作的场景下,HashTable不是线程安全的,因为 HashTable 只是保证单个方法操作是原子性的,但在不保证原子性的复合操作下,HashTable 也存在线程安全问题。

ConCurrentHashMap 的数据结构

我们知道 HashTable 的性能比 HashMap 的差很多,因为 HashTable 在每个操作方法上面都加了 synchronized 关键字,而且在复合场景下还存在线程安全问题,所以 HashTable 算是旧版本遗留下来的问题了,现在的实际开发中一般也不会去使用到 HashTable,但是在 jdk1.5 以后新增了 java.util.concurrent 包,在这个包下提供了很多线程安全又高性能的集合,其中就包含了本章的主角ConCurrentHashMap

jdk1.7 分段锁

在 jdk1.5 以后到 jdk1.7 ,ConCurrentHashMap 在解决多线程场景下的线程安全问题,采用的是分段锁的技术。

我们知道 HashTable 之所以性能低下,是因为其在 public 方法的实现上都加上了 synchronized 的关键字,即当任意一个 put 或 get 操作,都将整个 map 对象锁住,只有等待持有锁的线程操作结束,才有机会获得锁进行操作。

这里有一种场景,在 Map 的数组 table 中,线程1对 table[0] 进行 put 操作,而此时有线程2想对 table[1] 进行 put 操作,实际上两者的 put 操作互不干涉,而在 HashTable 的实现下,线程2只能等待线程1操作完成之后才能执行。那么,我们是否可以这样实现,当线程1对 table[0] 进行 put 操作时,对 table[0] 下的链表进行加锁,而操作 table[1] 时,对 table[1] 的链表进行加锁,各自那各自的锁,这样线程1在操作 table[0] 时,线程2也可以操作 table[1]。

ConcurrentHashMap分段锁结构图

分段锁采用的就是这种思想,在ConCurrentHashMap中维护着Segment[]的数组,这种实现方式把原本 HashTable 粗粒度的锁实现,拆分成一段一段的Segment锁。

//jdk1.7的ConcurrentHashMap的源码
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>
        implements ConcurrentMap<K, V>, Serializable {  
    /**
     * Mask value for indexing into segments. The upper bits of a
     * key's hash code are used to choose the segment.
     */
    final int segmentMask;

    /**
     * Shift value for indexing within segments.
     */
    final int segmentShift;

    /**
     * The segments, each of which is a specialized hash table.
     */
    //Segment是继承了可重入锁的子类,所以在Segment的操作方法中,包含了tryLock、unLock等方法
    final Segment<K,V>[] segments;
    
    /**
     * Segments are specialized versions of hash tables.  This
     * subclasses from ReentrantLock opportunistically, just to
     * simplify some locking and avoid separate construction.
     */
    static final class Segment<K,V> extends ReentrantLock implements Serializable {
        
        /**
         * The per-segment table. Elements are accessed via
         * entryAt/setEntryAt providing volatile semantics.
         */
        transient volatile HashEntry<K,V>[] table;
    }
}

简单理解就是,ConcurrentHashMap 维护一个 Segment 数组,Segment 通过继承 ReentrantLock 来进行加锁,所以每次需要加锁的操作锁住的是一个 Segment,这样只要保证每个 Segment 是线程安全的,也就实现了全局的线程安全。

ConcurrentHashMap的Segment结构

如下,是 ConcurrentHashMap 的各个构造方法,但是实际上只有 public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) 该构造方法是真正完成初始化的方法,其他的都是方法重载

public ConcurrentHashMap(int initialCapacity,
                         float loadFactor, int concurrencyLevel) {
        if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
            throw new IllegalArgumentException();
        if (concurrencyLevel > MAX_SEGMENTS)
            concurrencyLevel = MAX_SEGMENTS;
        // Find power-of-two sizes best matching arguments
        int sshift = 0;
        int ssize = 1;
        // 计算并行级别 ssize,因为要保持并行级别是 2 的 n 次方
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        // 我们这里先不要那么烧脑,用默认值,concurrencyLevel 为 16,sshift 为 4
        // 那么计算出 segmentShift 为 28,segmentMask 为 15,后面会用到这两个值
        this.segmentShift = 32 - sshift;
        this.segmentMask = ssize - 1;

        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;

        // initialCapacity 是设置整个 map 初始的大小,
        // 这里根据 initialCapacity 计算 Segment 数组中每个位置可以分到的大小
        // 如 initialCapacity 为 64,那么每个 Segment 或称之为"槽"可以分到 4 个
        int c = initialCapacity / ssize;
        if (c * ssize < initialCapacity)
            ++c;
        // 默认 MIN_SEGMENT_TABLE_CAPACITY 是 2,这个值也是有讲究的,因为这样的话,对于具体的槽上,
        // 插入一个元素不至于扩容,插入第二个的时候才会扩容
        int cap = MIN_SEGMENT_TABLE_CAPACITY; 
        while (cap < c)
            cap <<= 1;

        // 创建 Segment 数组,
        // 并创建数组的第一个元素 segment[0]
        Segment<K,V> s0 =
            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                             (HashEntry<K,V>[])new HashEntry[cap]);
        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
        // 往数组写入 segment[0]
        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
        this.segments = ss;
    }

    public ConcurrentHashMap(int initialCapacity, float loadFactor) {
        this(initialCapacity, loadFactor, DEFAULT_CONCURRENCY_LEVEL);
    }

  
    public ConcurrentHashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
    }

    public ConcurrentHashMap() {
        this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, DEFAULT_CONCURRENCY_LEVEL);
    }

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

concurrencyLevel:并行级别、并发数、Segment 数,怎么翻译不重要,理解它。默认是 16,也就是说 ConcurrentHashMap 有 16 个 Segments,所以理论上,这个时候,最多可以同时支持 16 个线程并发写,只要它们的操作分别分布在不同的 Segment 上。这个值可以在初始化的时候设置为其他值,但是一旦初始化以后,它是不可以扩容的。

再具体到每个 Segment 内部,其实每个 Segment 很像前面介绍的 HashMap,不过它要保证线程安全,所以处理起来要麻烦些。

initialCapacity:初始容量,这个值指的是整个 ConcurrentHashMap 的初始容量,实际操作的时候需要平均分给每个 Segment。

loadFactor:负载因子,之前我们说了,Segment 数组不可以扩容,所以这个负载因子是给每个 Segment 内部使用的。

jdk1.8 的新特性:CAS

在 jdk1.8 以下版本的 ConcurrentHashMap 为了保证线程安全又要提供高性能的情况下,采用锁分段的技术,而在java8中对于 ConcurrentHashMap 的实现又变成了另外一种方式----CAS

CAS的全称是compare and swap,直译过来就是比较与替换。CAS的机制就相当于这种(非阻塞算法),CAS是由CPU硬件实现,所以执行相当快.CAS有三个操作参数:内存地址,期望值,要修改的新值,当期望值和内存当中的值进行比较不相等的时候,表示内存中的值已经被别线程改动过,这时候失败返回,当相等的时候,将内存中的值改为新的值,并返回成功。

这里也不去细讲多线程、锁、CAS这些内容,后续等有空再整理一篇文档出来做详细点的笔记,这里只当做体会精神,理解思想即可。

下面的代码是摘自网上一篇文章的对 java8 中 ConcurrentHashMap 的源码分析,也是为了方便自己后续当笔记学习来看。

public V put(K key, V value) {
    return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (key == null || value == null) throw new NullPointerException();
    // 得到 hash 值
    int hash = spread(key.hashCode());
    // 用于记录相应链表的长度
    int binCount = 0;
    for (Node<K,V>[] tab = table;;) {
        Node<K,V> f; int n, i, fh;
        // 如果数组"空",进行数组初始化
        if (tab == null || (n = tab.length) == 0)
            // 初始化数组,后面会详细介绍
            tab = initTable();
 
        // 找该 hash 值对应的数组下标,得到第一个节点 f
        else if ((f = tabAt(tab, i = (n - 1) &amp; hash)) == null) {
            // 如果数组该位置为空,
            // 用一次 CAS 操作将这个新值放入其中即可,这个 put 操作差不多就结束了,可以拉到最后面了
            // 如果 CAS 失败,那就是有并发操作,进到下一个循环就好了
            if (casTabAt(tab, i, null,
                         new Node<K,V>(hash, key, value, null)))
                break;                   // no lock when adding to empty bin
        }
        // hash 居然可以等于 MOVED,这个需要到后面才能看明白,不过从名字上也能猜到,肯定是因为在扩容
        else if ((fh = f.hash) == MOVED)
            // 帮助数据迁移,这个等到看完数据迁移部分的介绍后,再理解这个就很简单了
            tab = helpTransfer(tab, f);
 
        else { // 到这里就是说,f 是该位置的头结点,而且不为空
 
            V oldVal = null;
            // 获取数组该位置的头结点的监视器锁
            synchronized (f) {
                if (tabAt(tab, i) == f) {
                    if (fh >= 0) { // 头结点的 hash 值大于 0,说明是链表
                        // 用于累加,记录链表的长度
                        binCount = 1;
                        // 遍历链表
                        for (Node<K,V> e = f;; ++binCount) {
                            K ek;
                            // 如果发现了"相等"的 key,判断是否要进行值覆盖,然后也就可以 break 了
                            if (e.hash == hash &amp;&amp;
                                ((ek = e.key) == key ||
                                 (ek != null &amp;&amp; key.equals(ek)))) {
                                oldVal = e.val;
                                if (!onlyIfAbsent)
                                    e.val = value;
                                break;
                            }
                            // 到了链表的最末端,将这个新值放到链表的最后面
                            Node<K,V> pred = e;
                            if ((e = e.next) == null) {
                                pred.next = new Node<K,V>(hash, key,
                                                          value, null);
                                break;
                            }
                        }
                    }
                    else if (f instanceof TreeBin) { // 红黑树
                        Node<K,V> p;
                        binCount = 2;
                        // 调用红黑树的插值方法插入新节点
                        if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
                                                       value)) != null) {
                            oldVal = p.val;
                            if (!onlyIfAbsent)
                                p.val = value;
                        }
                    }
                }
            }
            // binCount != 0 说明上面在做链表操作
            if (binCount != 0) {
                // 判断是否要将链表转换为红黑树,临界值和 HashMap 一样,也是 8
                if (binCount >= TREEIFY_THRESHOLD)
                    // 这个方法和 HashMap 中稍微有一点点不同,那就是它不是一定会进行红黑树转换,
                    // 如果当前数组的长度小于 64,那么会选择进行数组扩容,而不是转换为红黑树
                    //    具体源码我们就不看了,扩容部分后面说
                    treeifyBin(tab, i);
                if (oldVal != null)
                    return oldVal;
                break;
            }
        }
    }
    // 
    addCount(1L, binCount);
    return null;
}

对于 ConcurrentHashMap 的源码解读就到这里,详细的源码解读,可以看这篇很牛的文章,我也是在写本分析的情况下,发现了Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析这篇文章,发现写的比我还写的详细的多的多,所以如果觉得意犹未尽的同学可以去读读这篇源码解读。