Java源码解读 --- HashMap&ConcurrentHashMap

贪挽懒月

发布于 2019-04-22 10:24:16

5540

发布于 2019-04-22 10:24:16

文章被收录于专栏：JavaEEJavaEE

HashMap是一个常用的集合，日常使用可能我们并不关心它是如何实现的，不过它是面试中的常客。所以为了弄懂它，不妨看一看源码，同时也可以学习一下大牛的编程思想。

一、HashMap的宏观实现

1、HashMap数据结构: HashMap采用数组 + 链表的方式来实现数据的存储。为什么使用这种方式呢？链表什么时候产生呢？

首先HashMap主要还是用数组来存储元素的。它通过key的hash来计算元素应该放在数组中的哪个位置。如果有两个key的hash都一样，该怎么处理呢？这时候会去判断这两个key是否相等，如果相等，那就直接用新的value覆盖旧的value；如果这两个key不相等，那么就连接在第一个key的后面，用头插法形成链表(JDK1.8开始用尾插法)。由此链表就诞生了。

JDK1.8开始，又对HashMap进行了优化。我们知道链表读取数据不方便，所以为了避免链表太长，又加入了红黑树结构。当链表长度达到阈值时，就会将链表转成红黑树。

所以宏观的来说，JDK1.8开始，HashMap是由(数组 + 链表 + 红黑树)实现的。首先是用hash去判断元素应该放到数组中的哪个位置，如果该位置已有元素，就判断这两个元素的key是否相同，相同就覆盖，不同就生成链表，接在后面。当链表达到一定长度时，就转成红黑树。同时数组的元素个数达到一定值时，就会进行扩容。扩容之后再将数据转移到新的数组。

二、HashMap实现细节

1、用什么存储元素？ 根据上面的宏观描述，可以知道，我们需要一个Node类，里面有四个属性，分别是 key、value、hash、next。其中next是Node类型，表示下一个节点，用于生成链表。同时需要一个Node[ ] 数组，用来存储每个节点。如下代码所示：

// 这是源码中的节点内部类。
 static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
}
// 源码中的节点数组
 transient Node<K,V>[] table;

2、数组如何初始化？ 从上面我们可以看到，这个数组并没有初始化，那么当我们put元素的时候，这个数组是如何初始化的呢？通过源码可以发现，put方法里面调用了一个putVal方法，在putVal方法中，首先判断数组长度是不是没有初始化，如果是，就调用resize方法进行初始化。

 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;
        ...
}

接下来看看resize方法是怎么初始化数组的。

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

这个是数组初始化默认的大小。

 ...
 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 table = newTab;
 ...
 return newTab;

在这个方法中，其他的先不用看，就看这几行代码，其中newCap的值就是与上面数组默认初始化大小值一样，也就是16。也就是说，使用HashMap的时候，首先会初始化一个长度为16的数组，用来存储元素。

3、如何将元素放入数组？ 初始化了一个长度为16的数组，那么索引就是 0 ~ 15，当put元素的时候，如何知晓元素是放入哪个位置呢？Node内部类的hash属性就起作用了。首先来看看这个hash属性是怎么来的。

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

在HasnMap中有一个hash方法，该方法返回key的hashCode值的高16与低16位进行异或运算(科普一下：异或运算，将运算数转成二进制，1^1=0，1^0=1，0^0=0 ，0^1=1，也就是说，相等为0，不等为1；与运算，将运算数转成二进制，1&1=1，1&0=0，0&1=0，0&0=0；或运算，将运算数转成二进制，1|1=1，1|0=1，0|1=1，0|0=0)，该值就是hash。为什么要这样计算hash的值，而不直接使用hashCode方法计算的值？hashCode方法返回值是一个32位的二进制数，等下在计算元素索引的时候，这32位并没有都参与运算，这样的话，两个key计算出来的索引一致的概率就更大，所以要让这32位充分利用起来，都参与计算，所以先用hashCode值的高16位与低16位进行异或运算。那么为什么是异或，而不是其他运算呢？从上面括号内的说明可以知道，只有异或运算，得到1和0的概率都是0.5。为了不影响计算结果，所以选择了异或。

有了hash后，如何计算出索引？

...
 if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

...
}

在putVal方法中，有这样一段代码。索引 i 就是 hash 和 n ( n是数组长度 - 1) 进行与运算得来的。为什么这样算呢？上面说了，数组默认初始化长度为16，二进制就是 10000，减一后结果就是 01111。再用 hash 和 01111 进行与运算，其结果一定是在 0 到 01111 这个范围的，也就是 0 到 15 之间。而数组索引也是 0 到 15，这样便达到了目的。计算出来的结果是 n，那就放入数组索引为 n 的位置。

问题来了，因为数组默认初始化长度是16，是2的n次幂。(length - 1) 就是奇数，最后一位是1。这样就保证了 hash & (length - 1) 的计算结果可能为奇数也可能为偶数，保证了散列的均匀性。

4、如果我们给的初始化大小不是2的n次幂怎么办？ HashMap还有个构造方法，我们可以自己传入一个数组初始化容量。如下：

HashMap<Integer,String> map = new HashMap<>(20);

根据上面的分析，我们知道数组的大小一定得是2的n次幂，才能保证散列均匀分布。如果我传入不是2的n次幂，比如是20，那么如何处理？

通过源码我们可以发现如下的一个方法：

static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
 }

这个方法的作用就是，如果用户传入的不是2的n次幂，那么就会return一个大于和用户传入的数最接近的2的n次幂的数。比如传入20，那么实际上数组的大小将会是32。

5、数组何时进行扩容？如何扩容？ resize方法不仅是用来初始化的，也是用来扩容的。那么什么时候进行扩容？是数组中的元素满了才扩容的吗？当然不是。

 static final float DEFAULT_LOAD_FACTOR = 0.75f;

在源码中有这么一个常量，暂且称作扩容因子。当数组中元素个数达到了数组长度的四分之三的时候，就会进行扩容。上面也说了，数组长度必须是2的n次幂，所以扩容就会扩成两倍。原来长度为16，当数组中有12个元素了，就会进行扩容，扩成32。那么旧数组的数据如何移动到新数组呢？有三种情况：

如果是单个元素，那就用 hash & (newLength - 1 )；
如果是链表，那么就用看 hash & oldLength 的计算结果是否为0(oldLength表示旧数组的容量)，如果为0，放在原位置，如果不为0，放在 (原来的index + 旧数组容量) 的位置。
如果是红黑树，那么将树打散，根据 hash & (newLength - 1 ) 重新分配位置。

所以总结起来就是，要么在原来的位置，要么在原来索引加上原数组容量的位置。

6、什么时候会生成链表？ 上面说了HashMap通过计算 hash & (数组长度 - 1 ) 的值来确定元素放入数组中哪个位置。当两个元素计算出来的值一样时，如何处理？那么就会继续通过equals方法方法判断这两个元素的key是否一样，如果一样，那么新的value就会覆盖旧的value；如果不一样，就会生成链表。在jdk 1.7的时候，用头插法生成链表，jdk1.8开始，用尾插法生成链表。

7、为什么要有红黑树？什么时候生成红黑树？ 上面说了什么时候生成链表，我们知道链表读取数据很慢，如果链表太长，会导致读取性能不好。所以就出现了红黑树。在源码中，有如下常量：

 static final int TREEIFY_THRESHOLD = 8;

也就是说，当链表的长度达到了8，就会将链表转成红黑树，以提高读取效率。还有一个常量：

static final int UNTREEIFY_THRESHOLD = 6;

也就是说，当树中元素个数少于6个时，那就将树变回链表。

红黑树的平均查找长度为log(n)，链表的平均查找长度为 n/2。当元素个数为8时，使用链表平均查找长度为4，而使用红黑树的话平均查找长度为3，所以有必要转成红黑树。当元素个数小于等于6时，用链表平均查找长度是3，速度已经很快了，所以没必要转红黑树。

小结：往HashMap中put元素主要分为以下几个步骤：

1. hash(key)，计算key的hash，用key的hashCode值的高16位和低16位进行异或运算；
1. 调用resize方法初始化数组，默认初始化大小为 16 ，如果自定义的初始化大小x不是2的n次幂，就会转成比x大的最接近x的2的n次幂；
1. hash和数组长度减一的值进行与运算，判断元素在数组中的存储位置，如果这个位置没有其他key，直接存入该位置，如果有其他的key，那么又有三种情况： --- ：如果key相等，直接替换 --- ：如果key不等，生成链表 --- ：如果链表长度达到 8 了，那就转成红黑树
1. 当数组中元素个数达到容量的 0.75 时，调用resize方法将容量扩为当前的两倍。
1. 扩容后数据的转移有两种情况： --- ：如果是单个元素或者是红黑树，根据 hash ^ （newLength - 1）的方式存储； ---：如果是链表，判断 hash ^ oldLength 的值是否为0，如果是，放在原位置，不为0，放在 (原index + 旧数组容量) 的位置。

三、ConcurrentHashMap

1、为什么要有ConcurrentHashMap？ 看了HashMap的源码之后，可以发现HashMap并不是同步的。如果在多线程环境中同时对一个HashMap进行读写操作，肯定是会出问题的。那么如何保证在多线程中的安全问题呢？加锁！没错，最熟悉的就是 synchronized 了。只要在HashMap的每个方法中都加上 synchronized 关键字，就安全了。确实可以，HashTable就是这样做的，所以它被淘汰了，因为这样性能很低。接下来就该ConcurrentHashMap上场表演了。

2、ConcurrentHashMap如何保证线程安全？ 说这个问题之前，先回到HashMap的小结中的5个过程，看看5个过程哪几个过程在多线程环境中可能出现线程安全问题。

1. hash(key)，这个过程不管多少个线程同时操作，计算出的hash都是一样的，不会有线程安全问题。所以ConcurrentHashMap中这个过程没做处理。
1. 初始化数组，这个过程肯定会有问题。比如一个线程要初始化容量为16，另一个线程要初始化容量为32，那么怎么办？ConcurrentHashMap采用了CAS算法来保证线程的安全性。当有线程初始化map了，其他线程就yield，礼让一下。初始化数组的 initTable 方法如下：

private final Node<K,V>[] initTable() {
        Node<K,V>[] tab; int sc;
        while ((tab = table) == null || tab.length == 0) {
            if ((sc = sizeCtl) < 0)
                Thread.yield(); // lost initialization race; just spin
            else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
                try {
                    if ((tab = table) == null || tab.length == 0) {
                        int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
                        @SuppressWarnings("unchecked")
                        Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
                        table = tab = nt;
                        sc = n - (n >>> 2);
                    }
                } finally {
                    sizeCtl = sc;
                }
                break;
            }
        }
        return tab;
    }

关于CAS算法的工作原理，它如何保证线程安全，以后再写个文章详细说明，此处不多说。

3、存放元素，这个过程肯定也会有线程安全问题。

 if (tab == null || (n = tab.length) == 0)
         tab = initTable();
 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
         if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))
               break;                   // no lock when adding to empty bin
 }

先看这段代码，首先判断数组是否为空，为空，那么就调用initTable进行初始化。如果不为空，并且要插入的位置没有元素，就执行casTabAt方法。下面来看一个这个方法：

 static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i, Node<K,V> c, Node<K,V> v) {
        return U.compareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);
 }

这个方法也是使用了CAS算法，也就是说，当要插入的位置没有其他key时，也是用CAS保证线程的安全性的。如果要插入的位置有key存在呢，看接下来的代码：

 else {
       synchronized (f) {
       ......
       }
}

如果要插入的位置有key了，那么要判断是替换还是生成链表还是生成红黑树，情况比较复杂。所以直接用synchronized代码块。锁对象是当前操作的node节点，缩小了锁的粒度也就是说，其他线程只是不能对当前节点进行操作，但可以对其他节点进行操作。

4、扩容和转移数据：这个过程也会有线程安全问题。只能有一个线程进行扩容，当一个线程进行扩容的时候，其他线程也别闲着，其他线程就帮忙将旧数组的数据转移到新数组。扩容的addCount方法也是通过CAS来保证线程安全的。在putVal方法中，好友一个判断条件如下：

else if ((fh = f.hash) == MOVED) // -1
        tab = helpTransfer(tab, f);

当那个值等于-1时，那么就调用helpTransfer方法去帮忙进行数据的转移。

小结：ConcurrentHashMap在put元素时主要逻辑如下：

 if (tab == null || (n = tab.length) == 0) // 数组为空
         tab = initTable(); // 初始化，CAS保证线程安全
 else if ((f = tabAt(tab, i = (n - 1) & h)) == null) { // 要插入的位置key为null 
         // casTabAt 方法用CAS保证线程安全
         if (casTabAt(tab, i, null, new Node<K,V>(h, key, value, null))) { 
             delta = 1;
             val = value;
             break;
          }
 }
 else if ((fh = f.hash) == MOVED) // f.hash == MOVED(-1)
          tab = helpTransfer(tab, f); // 帮忙转移元素到扩容后的数组，CAS保证安全性
 else { // 要插入的位置key不为null 
          synchronized (f) { // 同步代码块保证线程安全
                   ......
          }
 }
 if (delta != 0) 
          addCount((long)delta, binCount); // 扩容，CAS保证安全性

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2019.04.13 ，如有侵权请联系 cloudcommunity@tencent.com 删除

hashmap

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

hashmap

编程算法

登录后参与评论

0 条评论

热度