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.用位运算，效率更高
- 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 &&
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 16
当 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 的源码解读就到这里，详细的源码解读，可以看这篇很牛的文章，我也是在写本分析的情况下，发现了Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析这篇文章，发现写的比我还写的详细的多的多，所以如果觉得意犹未尽的同学可以去读读这篇源码解读。