1 前言
前几节我们分析了一些并发安全的数据结构，分别是CopyOnWrite系列的CopyOnWriteArrayList、BlockingQueue阻塞队列系列的LinkedBlockingQueue、ArrayBlockingQueue、DelayQueue。接下来我们要讲解一个很重要的并发安全的数据结构，ConcurrentHashMap。在Java的数据结构里面平时我们最常使用的数据结构就是List、Map、Set这几种数据结构了。List类的并发安全的数据结构之前讲解了CopyOnWriteArrayList，而Set类型的数据结构是基于Map类来进行构建的，所以我们下面的重点是看看Map类型并发安全数据结构。由于ConcurrentHashMap和HashMap这两个数据结构很相似，在用法、特性、底层原理上有很多共同之处，所以我们本章先来详细讲解一下HashMap这个数据结构。然后再来讲解并发安全版本的Map数据结构ConcurrentHashMap，它是怎么做到并发安全的，是怎么基于分段锁的机制来并发过程的锁冲突来提高并发性能的。
2 HashMap介绍
HashMap底层采用数组+链表+红黑树的形式来存储数据，如下图所示：
（1）首先插入数据之前，会对使用一个hash算法计算key的hash值，然后根据此hash值对数组长度进行取模，得出该key存储在数组的第几个元素上。
（2）如上图黄色部分k = 1，v = 2，刚开始数组的此位置未存储元素，则此时不存在hash冲突，直接存储在此数组的位置即可。
（3）加入存在hash冲突，如上红色部分所示，则首先使用链表来解决hash冲突，新存入的元素放在链表末尾
（4）如果hash冲突变多，此时使用链表查询数据时间复杂度是O(n)，为了提高查询性能，而将链表进行树化，将转化成一颗红黑树，此时查询性能为O(logN)，另外链表转成红黑树的条件是，当链表上的节点数量不少于8个的时候。
3 HashMap内部源码
接下来继续分析一下它内部的源码是怎么实现这个设计的。
3.1 内部属性
// 默认的初始化容量16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 // 最大容量2的30次方 static final int MAXIMUM_CAPACITY = 1 << 30; // 负载因子0.75，比如数组的长度是16，当数组里元素的个数打到了数组大小的这个0.75比率， // 也就是12个的时候，就会进行数组的扩容 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 链表红黑树化的条件，长度是8 static final int TREEIFY_THRESHOLD = 8; // 非树化的添加，长度小于等于6 static final int UNTREEIFY_THRESHOLD = 6; // 数化之前的最小容量必须打到64，否则优先进行扩容而不是进行树化 static final int MIN_TREEIFY_CAPACITY = 64; // HashMap内部的基础数组，HashMap是使用数组+聊表+红黑树的方式来存储数据 transient Node<K,V>[] table;
3.2 构造方法
public HashMap() { // 默认构造函数，只是初始化了一个负载因子，其它啥都没干 this.loadFactor = DEFAULT_LOAD_FACTOR; } // 设置容量的构造方法 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } // 设置容量和负载因子的构造方法 public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 容量不可超过最大允许值 MAXIMUM_CAPACITY if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; // 调用tableSizeFor方法，根据传入的容量再进行一轮计算，算出应该分配的容量多少 this.threshold = tableSizeFor(initialCapacity); }
3.2.1 tableSizeFor(int cap)方法
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; }
这个方法看起来很多位运算，其实没什么，也就是保证传入一个cap的值，最会返回的值一定是2的n次方，因为HashMap要保证底层的数组长度必须是2的N次方。
比如传入cap为7，则返回的是8；传入13得到的是16等，根据传入的cap值取得一个靠近cap的2的N次方的结果。同时确保得到的结果不能大于限定的MAXIMUM_CAPACITY 最大容量。
3.3 put方法
public V put(K key, V value) { // 1. 首先使用hash(key)方法进行hash计算得到一个hash值 // 2. 然后在调用putVal方法插入元素 return putVal(hash(key), key, value, false, true); }
3.3.1 hash方法
static final int hash(Object key) { int h; // 1. 如果key == null直接返回0，这也就是为啥HashMap能使用null作为key的原因 // 2. (h = key.hashCode()) 获取key的hashCode保存在h变量中 // 3. h ^ (h >>> 16) 这个代码的意思是将一个32位的高16位和低16位进行异或运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
我们画个图理解一下：
相当于高16位不变，低的16位变成了原先的高16位和低16位的异或结果。
这里可能有个疑问：为什么不直接取key的hashCode，而是要进行这样的运算，这样做的好处是什么？
假如有72、40：
进行了高4位和低4位异或运算之后，76 % 8 = 4， 42 % 8 = 2 ，此时不存在hash冲突了。
假如不进行高4位和低4位的异或运算，假设此时数组长度是8，72 % 8 = 0，40%5 = 0 ，此时就存在hash冲突了。
上面只是列举了4位异或的情况，同样的道理HashMap中的高16位和低16位进行异或运算也是一样的，结果都是让得到的hash值中让高16位和低16位都参与运算，这样得到的结果更加随机一点，能更加有效的减少hash冲突了。
3.3.2 hash方法
接下来继续看下putVal方法的源码：
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数组是null，获取数组长度是0，说明还没进行初始化，需要先进行数组的初始化 if ((tab = table) == null || (n = tab.length) == 0) // 进行数组的初始化 n = (tab = resize()).length; // n 为数组的长度，当n为2的x次方时候（n - 1） & hash 的结果与 hash % n 相等 // 这也就是为什么数组的长度要是2的x次方的原因，使用 & 位运算 代替 % 取模运算提高性能 if ((p = tab[i = (n - 1) & hash]) == null) // 这里根据(n-1) & hash定位到数组的i位元素 // 如果tab[i] == null，说明之前此下标的数组没存储过元素，直接将k、v存储在此数组位置即可 tab[i] = newNode(hash, key, value, null); else { // 当tab[i] != null，走到这里，说明存在hash冲突 Node<K,V> e; K k; // 判断一下此节点的Key和传入的Key是否一样，如果一样，直接替换value的值即可 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 如果p节点是一个红黑树，按照红黑树的方式插入或者替换一个节点 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { // 走到这里说明p是一个链表，使用链表的方式插入或者替换一个节点 // 这里从链表头结点开始遍历整个链表 for (int binCount = 0; ; ++binCount) { // 这里是走到链表的尾部，未发现该链表的任何节点的Key与传入的key一致 // 说明需要新插入一个节点 if ((e = p.next) == null) { // 这里就是新插入一个节点 p.next = newNode(hash, key, value, null); // 如果插入一个节点后，该链表长度达到了8，需要将链表转化成红黑树，提升搜索性能 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } // 这里就是遍历链表过程中发现有节点的Key跟传入的Key一直 // 此时直接替换该节点的Value值即可 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } if (e != null) { // existing mapping for key // 获取修改前旧节点的value值，返回旧的值 V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } // modCount记录HashMap修改的次数，每次put方法之后修改次数自增1 ++modCount; // size表示HashMap中元素个数，threshould表示HashMap扩容的阈值 // 插入元素之后size > threshould表示达到扩容阈值了，此时HashMap触发扩容操作 if (++size > threshold) // 进行扩容 resize(); // afterNodeInsertion(evict); return null; }
我们画个图理解一下：
（1）首先查看用来存储数据的基础数组，table是否为空或者长度length是否为0；如果是则先需要对数组进行初始化。
（2）根据寻址算法，（n-1）& hash ，其实也就是 hash % n，定位到数组的某个元素tab[i]，如果tab[i]位置不存在元素，可以直接存储在tab[i]位置
（3）如果tab[i] !=null，说明存在hash冲突，此时需要解决hash冲突。判断tab[i]位置节点是链表节点还是红黑树节点。
（4）如果是红黑树节点，则调用putTreeVal对红黑树遍历，查找是否有Key与传入Key一致，有则替换该节点Value值即可，没有则插入新节点
（5）如果是链表节点，则从头开始遍历链表，对比链表的每个节点的Key是否与传入的Key一致，如果一致直接替换该节点的Value节点即可
（6）如果不一致，则在链表尾部插入一个新的节点，Key和Value存储在该节点中。同时判断新插入一个节点之后，该链表的长度是否达到8，如果是则需要将链表转成红黑树，提高查询效率。
（7）插入新的元素之后，HashMap的大小size自增1，同时判断size > threshould是否成立，也就是HashMap是否达到了扩容的阈值，如果是则需要调用resize()方法进行HashMap的扩容
3.3.3 resize方法
我们继续看看HashMap如何初始化以及容量达到扩容阈值的时候，是怎么进行扩容的：
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) { // 如果当前数组长度已经MAXIMUM_CAPACITY，说明数组长度非常大了 if (oldCap >= MAXIMUM_CAPACITY) { // 此时再进行扩容，直接就赋予Integer的最大长度 threshold = Integer.MAX_VALUE; return oldTab; } // 扩容一倍之后长度 < MAXIMUM_CAPACITY 且大于初始化长度 // 那么此种情况，基础数组长度扩容一倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } // 走到这里说明oldCap == 0，oldThr > 0 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // 走到这里说明oldCap == 0 && oldThr == 0，此时就是设置长度为初始化长度 // 也就是16 newCap = DEFAULT_INITIAL_CAPACITY; // 新的达到扩容的阈值为 长度 * 负载因子 = 长度 * 0.75 newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果扩容阈值为0，需要重新计算 if (newThr == 0) { float ft = (float)newCap * loadFactor; // 计算扩容阈值，结合容量限制等情况 newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } // 赋值扩容阈值 threshold = newThr; // 新创建一个基础数组，长度为上面的新容量长度newCap 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; // 获取oldTab[j] 位置元素，赋值给e if ((e = oldTab[j]) != null) { // 将旧数组此位置引用置位null，方便进行垃圾回收 oldTab[j] = null; // 如果e == null，说明此位置是一个单元素，既不是链表也不是红黑树 if (e.next == null) // 这种情况就好办，直接使用寻址算法移动到新数组上即可 newTab[e.hash & (newCap - 1)] = e; // 如果是一个红黑树 else if (e instanceof TreeNode) // 调用split方法将红黑树拆散移动到新数组上 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 如果是一个链表，则执行一下方式进行数据移动 else { // preserve order // 这里是先生成两个链表 // 链表lo的头节点是loHead，尾节点是loTail Node<K,V> loHead = null, loTail = null; // 链表hi的头结点是hiHead，尾节点是hiTail Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; // 如果旧链表上元素Key.hash & oldCap == 0 // 则将此节点放入到链表lo中 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } // 如果旧链表上元素Key.hash & oldCap != 0 // 则将次节点放入hi链表中 else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); // 上面就将旧数组tab[j]位置的链表平均拆成了两个聊表lo和hi // 新数组的newTab[j]位置存放lo链表 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 新数组的newTab[j+oldCap]位置存放链表hi if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
我们画个图来理解一下：
（1）首先就是计算需要扩容的容量是多少，计算得到新的容量为newCap
（2）然后就是创建一个新的数组了，新数组长度为newCap
（3）然后就是遍历旧的数组，将数据移动到新数组长度了
（4）如果旧的数组tab[j]位置只有一个元素，那么直接移动到新数组即可，移动到新数组的位置使用寻址算法(newCap -1) & hash计算得到
（5）如果旧的数组tab[j]位置是一个链表，则需要将这个链表拆成两个，分别为lo和hi链表。旧链表元素的 hash & oldCap == 0 则移动到lo链表，如果hash & oldCap ！= 0 则移动到hi链表。
（6）lo链表存放入新数组newTable[j]的位置，hi链表存放入newTable[j+oldCap]的位置
（7）如果旧数组的tab[j]位置是一个红黑树，也需要将这颗红黑树拆成两个链表，也是根据hash & oldCap 是否为0的方式，跟链表的迁移方式是一样的，不同的是，迁移完成之后，需要判断一下，如果迁移后链表长度还是大于等于8，需要将链表再次转成红黑树。
（8）至此一个一个按照上述的方式迁移旧数组的每个元素，扩容就完成了。
3.4 remove方法
public V remove(Object key) { Node<K,V> e; return (e = removeNode(hash(key), key, null, false, true)) == null ? null : e.value; }
remove跟put方法是一样的，也是通过hash & (n - 1)的寻址方法找到位于数组的第几个元素。然后如果是链表则遍历链表，对比Key是否一样，如果找到则删除这个节点。如果是红黑树也是需要在红黑树中查找，对比Key是一样，如果一样删除这个节点，基本都是一样的，这里就不具体看了哈。
4 小结
好了，本节我们HashMap基本就到这里了，下一节我们就要开始研究ConcurrentHashMap了，有理解不对的地方欢迎指正哈。
- 数据结构 ConcurrentHashMap 原理 HashMap 结构数据结构concurrenthashmap原理hashmap concurrenthashmap原理hashmap 数据结构concurrenthashmap原理 结构 concurrenthashmap hashmap null concurrenthashmap底层hashmap concurrenthashmap hashmap concurrenthashmap amp hashmap concurrenthashmap arraylist hashmap concurrenthashmap hashtable之间hashmap hashmap concurrenthashmap线程hashtable