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()) && 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) & 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 的值，高低位更加均匀地混到一起，结合上面数组脚标(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.用位运算，效率更高

2. 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

　　但是，我们不能光看这个常量值就说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 && 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()方法里调用了这个方法

　　截图中的代码已经很清楚了，就是当 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值，所以这种做法是不是不合理？

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

　　那么这个阈值具体是多少呢？下面我们来探究源码，既然要找到扩容的阈值，那我们不外乎要从两个方法入手去找，一个就是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) & hash]) == null) tab[i] = newNode(hash, key, value, null); //这一步其实也很清楚了，就是根据hash值计算出数组的脚标，然后判断数组的该脚标的元素是否为空，为空的话就把put进来的数据封装成节点赋值进数组 else { //根据上面的两个判断，那么走到这里的代码就是说，数组不为空，而且put进来的key计算所得的脚标节点也不为空，走这一块逻辑（实际上这块逻辑也跟扩容的阈值无关，只是单纯的判断然后加节点的操作，但是我还是解释下这里的代码） Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && 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 && ((k = e.key) == key || (key != null && 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()方法处，

/** * 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

　　当 HashMap 数组为 null 或长度为 0 时，初始化threshold的值，DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY，DEFAULT_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 && 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 && 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 && 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 & (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 & oldCap) == 0) { //这个判断是理解这整个链表遍历的关键，这里也涉及到了前面讲到的2^n-1对应二进制是0111xxxx的内容，我们知道数组的长度总是2^n，所以oldCap的值实际上就是1000xxxx，然后hash & 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新设计）

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

链表的“扩容”

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

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

单链表–>红黑树

　　在前面“数组扩容的阈值”章节的时候，我曾解读过 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) & 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，此时就进行转红黑树的操作，那红黑树又是什么呢？

　　我们知道链表的查询时间复杂度最坏的情况有可能是 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 & 0x7FFFFFFF) % tab.length; //get方法 public synchronized V get(Object key) { Entry<?,?> tab[] = table; int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length; for (Entry<?,?> e = tab[index] ; e != null ; e = e.next) { if ((e.hash == hash) && e.key.equals(key)) { return (V)e.value; } } return null; }

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

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

　　这里有几个场景：

（1）若 key 不存在，则添加元素

（2）若 key 存在，则删除元素

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

　　存在这样问题的原因是复合操作的场景下，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中维护着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 的各个构造方法，但是实际上只有 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) & 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 && ((ek = e.key) == key || (ek != null && 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 的源码解读就到这里啦。

作者：金发只是水一下

原文链接：https://blog.csdn.net/qq_25940921/article/details/81263784