前言
HashMap和ConcurrentHashMap是我们十分常用的Map下的数据结构，本文整理了一些常用的api源码分析，希望对于学习数据结构和集合能有帮助~
HashMap
1.HashMap概述
在JDK1.8之前，HashMap采用数组加链表来实现，一个table数组中存放一个entry，entry是一个链表，就像是一个桶。使用拉链法来处理hash冲突，同一hash值的节点都存储在一个链表里。当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key一次查找的效率较低。在JDK1.8中，HashMap采用数组+链表+红黑树的实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。（转换为数组+链表+红黑树是为了提高查找效率）。
下图中代表jdk1.8之前的hashmap结构，左边部分即代表哈希表，也称为哈希数组，数组的每个元素都是一个单链表的头节点，链表是用来解决冲突的，如果不同的key映射到了数组的同一位置处，就将其放入单链表中。
jdk1.8之前的hashmap都采用上图的结构，都是基于一个数组和多个单链表，hash值冲突的时候，就将对应节点以链表的形式存储。如果在一个链表中查找其中一个节点时，将会花费O（n）的查找时间，会有很大的性能损失。到了jdk1.8，当同一个hash值的节点数不小于8时，不再采用单链表形式存储，而是采用红黑树，如下图所示。
上图很形象的展示了HashMap的数据结构（数组+链表+红黑树），桶中的结构可能是链表，也可能是红黑树，红黑树的引入是为了提高效率。
2 涉及到的数据结构：处理hash冲突的链表和红黑树以及位桶
- 链表的实现
Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V 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;
}
}这里不难看出，node中包含一个next变量，这个就是链表的关键点，hash结果相同的元素就是通过这个next进行关联的。
- 红黑树
TreeNode是Map中的内部类，比链表多了四个变量，parent父节点、left左节点，right右节点、prev上一个同级节点。
static final class TreeNode extends LinkedHashMap.Entry {
TreeNode parent; // red-black tree links
TreeNode left;
TreeNode right;
TreeNode prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node next) {
super(hash, key, val, next);
}
/**
* Returns root of tree containing this node.
*/
final TreeNode root() {
for (TreeNode r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
} - 位桶
transient Node<K,V>[] table; HashMap类中有一个非常重要的字段，就是 Node[] table，即哈希桶数组，明显它是一个Node的数组。使用transient修饰是为了不讲整个数组进行序列化，只序列化有值的那一部分。
这样其实HashMap的实现流程就一目了然了，首先有一个每个元素都是链表（可能表述不准确）的数组，当添加一个元素（key-value）时，就首先计算元素key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这时就添加到同一hash值的元素的后面，他们在数组的同一位置，但是形成了链表，所以说数组存放的是链表。而当链表长度太长时，链表就转换为红黑树，这样大大提高了查找的效率。
3 HashMap源码分析
- 类的继承关系
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable 继承自AbstractMap，实现了Map、Cloneable, Serializable接口。Map接口定义了一组通用的操作；Cloneable接口表示可以进行拷贝，在HashMap中，实现的是浅层次拷贝，即对拷贝对象的改变会影响被拷贝的对象；Serializable接口表示HashMap实现了序列化，即可以将HashMap对象保存至本地，之后可以恢复状态。
- 类的属性
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
// 序列号，serialVersionUID适用于java序列化机制。简单来说，JAVA序列化的机制是通过判断类的
//serialVersionUID来验证的版本一致的。
private static final long serialVersionUID = 362498820763181265L;
//默认的初始容量为16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//数组的最大容量为2^30
static final int MAXIMUM_CAPACITY = 1 << 30;
//默认的填充因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//当桶上的节点数大于这个数的时候转成红黑树
static final int TREEIFY_THRESHOLD = 8;
//当桶上的节点数小于这个数的时候会转成链表
static final int UNTREEIFY_THRESHOLD = 6;
//桶中结构转化为红黑树对应的table的最小大小
static final int MIN_TREEIFY_CAPACITY = 64;
//存储元素的数组，总是2的n次幂
transient Node<K,V>[] table;
//存放具体元素的集
transient Set<Map.Entry<K,V>> entrySet;
//存放元素的个数，注意这个不等于数组长度
transient int size;
//每次扩容和更改map结构的计数器
transient int modCount;
//临界值，当实际大小(容量*填充因子）超过临界值时，会进行扩容
int threshold;
//填充因子
final float loadFactor;- 构造函数
- Hash(int float)型构造函数
public HashMap(int initialCapacity, float loadFactor) {
//初始容量不能小于0
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量不能大于最大值，否则为最大值
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//填充因子不能不能小于或等于0，不能为非数字
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
//初始化填充因子
this.loadFactor = loadFactor;
//初始化threshold的大小
this.threshold = tableSizeFor(initialCapacity);tableSizeFor(initialCapacity)返回大于initialCapacity的最小二次幂函数。>>>表示无符号右移，高位取0
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;
}todo:为什么一定要是2的n次幂。这样在计算计算桶下标的时候才能用hashcode&2^n-1来进行计算
- HashMap(int)型构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}- HashMap()型构造函数
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}- HashMap<Map<? extends K>型构造函数
public HashMap(Map<? extends K, ? extends V> m) {
//初始化填充因子
this.loadFactor = DEFAULT_LOAD_FACTOR;
//将所有元素添加至HashMap中
putMapEntries(m, false);
}
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
int s = m.size();
if (s > 0) {
//判断table是否已经初始化
if (table == null) { // pre-size
//未初始化，s为m的实际元素个数
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//计算得到的t大于阈值，则初始化阈值
if (t > threshold)
threshold = tableSizeFor(t);
}
//已初始化，并且m元素个数大于阈值，进行扩容处理
else if (s > threshold)
resize();
//将所有元素添加至HashMap中
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
- hash算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}在putVal源码中，我们通过(n-1)&hash获取该对象的键在hashMap中的位置。（其中hash的值就是（1）中获得的值），其中n表示的是hash桶数组的长度，并且该长度为2的n次方，这样(n-1)&hash就等价于hash%n。因为&运算的效率高于%运算
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
if ((p = tab[i = (n - 1) & hash]) == null)//获取位置
tab[i] = newNode(hash, key, value, null);
...
}
tab即table，n是map集合的容量大小，hash是上面方法的返回值。因为通常声明map时不会指定大小，或者初始化的时候就创建一个很大的map对象，所以通过容量大小与hash值运算的时候最开始只会在低位运算，虽然容量位2进制高位一开始都是0，但是key的2进制高位通常是有值的，因此先在hash方法中将key的hashCode右移16位在与自身异或，使得高位也可以参与hash，更大程度上减少了碰撞率。（理解：table容量不会很大，高位都为0.但是hash的高位有信息，为了利用高位信息，将hash右移16位进行异或，可以减小碰撞率）
- 重要方法分析
- putVal方法
HashMap并没有直接提供putVal接口给用户调用，而是提供的put方法，而put方法就是通过putVal来插入元素的。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}- 判断键值对数组table是否为空或者为null，否则执行resize()进行扩容(按照默认的threshold和loadfactor初始化数组)
- 根据key计算hash值得到插入数据的数组索引（桶下标），如果该桶table[i]==null,直接将新节点添加，转向6，如果table[i]!=null转向3
- 判断table[i]的首个是否和key一样，若一样就直接覆盖转向4，这里的相同指的是hashCode以及equals；
- 判断table[i]是否为TreeNode，即table[i]是否为红黑树，如果是红黑树，则直接在树中插入键值对，否则转向⑤；
- 遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，，否则进行链表的插在红黑树中执行插入操作入操作；遍历过程中若发现key已经存在直接覆盖value即可；
- 插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容（每次扩大为原来的两倍。
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没有进行初始化，按照默认值初始化table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果通过key的hashcode计算处的下标位置不存在元素，直接将节点插入该位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
//桶中元素已经存在
else {
Node<K,V> e; K k;
//如果要插入位置为首节点与要插入的key相同，直接覆盖
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
//如果要插入的桶是红黑树结构，直接插入红黑树
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//在链表末尾插入节点
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;
}
//若与链表中某个元素key相同，直接覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//表示在桶中找到key值、hash值与插入元素相等的结点
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//结构性修改
++modCount;
if (++size > threshold)
//每次扩容为原来的两倍
resize();
afterNodeInsertion(evict);
return null;
}HashMap数据存储实现原理
流程：
- 根据key计算得到key.hash = (h = k.hashCode()) ^ (h >>> 16)；
- 根据key.hash计算得到桶数组的索引index = key.hash & (table.length - 1)，这样就找到该key的存放位置了：
如果该位置没有数据，用该数据新生成一个节点保存新数据，返回null；
② 如果该位置有数据是一个红黑树，那么执行相应的插入 / 更新操作；
③ 如果该位置有数据是一个链表，分两种情况一是该链表没有这个节点，另一个是该链表上有这个节点，注意这里判断的依据是key.hash是否一样：
如果该链表没有这个节点，那么采用尾插法新增节点保存新数据，返回null；如果该链表已经有这个节点了，那么找到该节点并更新新数据，返回老数据。
- getNode方法
HashMap同样并没有直接提供getNode接口给用户调用，而是提供的get方法，而get方法就是通过getNode来取得元素的。判断一个节点是否在红黑树中first instanceof TreeNode。使用instanceof关键字
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//数组已经初始化，长度大于0，计算的桶下标也存在
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//和第一个节点对比
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
//红黑树中查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//链表中查找
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
- resize方法
- 在jdk1.8中，resize方法是在hashmap中的键值对大于阀值时或者初始化时，就调用resize方法进行扩容；
- 每次扩展的时候，都是扩展2倍；
- 扩展后Node对象的位置要么在原位置，要么移动到原偏移量两倍的位置。
final Node<K,V>[] resize() {
//oldTab指向hash数组桶
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//这一部分都是重新计算新的容量和阈值。
//在旧容量大于0的时候，如果就容量超过了容量最大值，新的阈值设为整数的最大值。
if (oldCap > 0) {//如果oldCap不为空的话，就是hash桶数组不为空
if (oldCap >= MAXIMUM_CAPACITY) {//如果大于最大容量，就赋值为整数最大的阀值
threshold = Integer.MAX_VALUE;
return oldTab;
}//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
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;
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 = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//新建hash数组桶
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {//进行扩容操作，复制Node对象到新的hash桶
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {//如果旧的hash桶数组在j结点处不为空，复制给e
oldTab[j] = null;//将旧的hash桶数组在j结点处设置为空，方便gc
if (e.next == null)
//直接对e的hash值对新的数组长度求模获得存储位置
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)//如果e是红黑树类型，那么添加到红黑树中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//链式情况，将原来的链表拆分为两个链表，一个索引不变，一个索引变化。
Node<K,V> loHead = null, loTail = null;//索引不变
Node<K,V> hiHead = null, hiTail = null;//索引变化
Node<K,V> next;
do {
next = e.next;//将Node节点的Next值赋给next
if ((e.hash & oldCap) == 0) {
//如果节点e的hash值与原hash数组桶的长度做与运算为0
if (loTail == null)//如果loTail为null
loHead = e;//将e结点赋值给loHead
else
loTail.next = e;//否则将e赋值给loTail.next
loTail = e;///然后将e复制给loTail
}
else {//如果结点e的hash值与原hash桶数组的长度作与运算不为0
if (hiTail == null)//如果hiTail为null
hiHead = e;//将e赋值给hiHead
else
//如果hiTail不为空，将e复制给hiTail.next
hiTail.next = e;
hiTail = e;//将e复制个hiTail
}
} while ((e = next) != null);////直到e为空
if (loTail != null) {//如果loTail不为空
loTail.next = null;//将loTail.next设置为空
newTab[j] = loHead;//将loHead赋值给新的hash桶数组[j]处
}
if (hiTail != null) {//如果hiTail不为空
hiTail.next = null;//将hiTail.next赋值为空
////将hiTail.next赋值为空
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
什么时候会resize():
- 初始化数组的时候，如果要将元素插入table，但是table==null;而且，table.length==null,进行resize操作初始数组。如果在构造函数中传入了cap参数，那么thr不为0，使用传入的参数进行初始化。如果构造函数中没有传入参数，使用默认值进行初始化，默认容量为16，默认填充因子为0.75。（初始化数组，若存在参数则按参数进行初始化，若不存在参数按照默认值进行初始化）
- 如果map的长度>threshold的时候，就需要进行扩容， 如果原始的容量大于最大的容量2^30次方，就将阈值设为Integer.MAX_VALUE，这样就永远不用进行扩容。如果原来的容量小于最大容量，大于默认容量，将容量扩大为2倍。（就是大于最大值时设置为最大值，小于最大值大于默认值扩大两倍，小于默认值设定为默认值）
resize()过程总体理解：将hashcode与原来的cap长度相与，若为0则位于原本的位置，若不为0，则位于原索引加old数组容量的位置。
ConcurrentHashMap
采用CAS+synchornized实现多线程下的并发安全。
重要的属性
transient volatile Node<K,V>[] table;和hashMap一样代表整个hash表
private transient volatile Node<K,V>[] nextTable;这是一个连接表，用于哈希表扩容，扩容后会被置成null
private transient volatile long baseCount;该属性保存着整个hash表中存储的所有节点的个数总和，有点类似与hashMap的size属性
private transient volatile int sizeCtl;这是一个重要的属性，无论是初始化哈希表，还是扩容 rehash 的过程，都是需要依赖这个关键属性的。该属性有以下几种取值：
0：默认值
-1：代表哈希表正在进行初始化
大于0：相当于 HashMap 中的 threshold，表示阈值
小于-1：代表有多个线程正在进行扩容
构造函数与hashmap类似
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}put方法
public V put(K key, V value) {
return putVal(key, value, false);
}putVal方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
//不允许插入空值
if (key == null || value == null) throw new NullPointerException();
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();
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
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
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;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
分成两个部分进行分析
- 第一 部分
final V putVal(K key, V value, boolean onlyIfAbsent) {
//对传入的参数进行合法性判断
if (key == null || value == null) throw new NullPointerException();
//计算键所对应的hashcode
int hash = spread(key.hashCode());
//bincount为hash表中节点数
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//如果hash表还没有初始化，那么初始化它
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//根据键的hash值找到hash数组对应的索引位置
//如果该位置为null，那么以CAS无锁式方式向该位置添加一个节点（比较并交换）
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
}
总结来说，若没有初始化哈希表进行初始化，若通过hash找到的桶为null，使用CAS的compareAndSwapObject（比较并交换）将值插入对应的位置。
计算hashcode方法
static final int spread(int h) {
//在hashcode结果中与了一个常量
return (h ^ (h >>> 16)) & HASH_BITS;
}initTable方法
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
//当表为空的时候才进行初始化操作
while ((tab = table) == null || tab.length == 0) {
//sizeCtl 小于零说明已经有线程正在进行初始化操作
if ((sc = sizeCtl) < 0)
//当前线程放弃cpu的使用
Thread.yield(); // lost initialization race; just spin
//获取初始化线程的权力，并将sizectl置为-1，告诉其它线程我正在初始化数组
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//保险起见，再校验一下表是否为空
if ((tab = table) == null || tab.length == 0) {
//如果sizectl>0表示阈值也就是初始化容量
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
//根据容量构建数组
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
//计算阈值=容量*填充因子（默认0.75）
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
总结来说，若检测到有其它线程（sizectl=-1）在初始化哈希表，放弃初始化，若没有其它线程初始化，根据sc（=sizectl)的值进行初始化，初始化之前通过CAS操作将标志位置为-1，防止其它线程再进行初始化.并设置阈值。保证hash表只被初始化一次。
- 第二部分：
//检测到桶节点是ForwardingNode 类型，协助扩容，见下面分析。
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
//桶结点是普通的结点，锁住该桶头结点并试图在该链表的尾部添加一个节点
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) {
//向普通链表中添加元素
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
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;
}
}
}
//向红黑树中添加元素，TreeBin 结点的hash值为TREEBIN（-2）
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 说明向链表或者红黑树中添加或修改一个节点成功
//binCount == 0 说明put操作将一个新节点添加成为某个桶的首节点
if (binCount != 0) {
////链表深度超过 8 转换为红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
//oldVal != null 说明此次操作是修改操作
//直接返回旧值即可，无需做下面的扩容边界检查
if (oldVal != null)
return oldVal;
break;
}
}
}
//CAS式更新binCount，并判断是否需要扩容。bincount是增加的节点数
addCount(1L, binCount);
return null;
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);分析
首先，看一下ForwardingNode 这个节点类型
static final class ForwardingNode<K,V> extends Node<K,V> {
final Node<K,V>[] nextTable;
ForwardingNode(Node<K,V>[] tab) {
super(MOVED, null, null, null);
this.nextTable = tab;
}
//省略find方法
Node<K,V> find(int h, Object k) {
}这个节点内部保存了一 nextTable 引用，它指向一张 hash 表。在扩容操作中，我们需要对每个桶中的结点进行分离和转移，如果某个桶结点中所有节点都已经迁移完成了（已经被转移到新表 nextTable 中了），那么会在原 table 表的该位置挂上一个 ForwardingNode 结点，说明此桶已经完成迁移。
ForwardingNode 继承自 Node 结点，并且它唯一的构造函数将构建一个键，值，next 都为 null 的结点，反正它就是个标识，无需那些属性。但是 hash 值却为 MOVED。
所以，我们在 putVal 方法中遍历整个 hash 表的桶结点，如果遇到 hash 值等于 MOVED，说明已经有线程正在扩容 rehash 操作，整体上还未完成，不过我们要插入的桶的位置已经完成了所有节点的迁移。
由于检测到当前哈希表正在扩容，于是让当前线程去协助扩容。
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
boolean finishing = false; // to ensure sweep before committing nextTab
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
while (advance) {
int nextIndex, nextBound;
if (--i >= bound || finishing)
advance = false;
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
Remove方法
public V remove(Object key) {
return replaceNode(key, null, null);
}final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
V oldVal = null;
boolean validated = false;
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
validated = true;
for (Node<K,V> e = f, pred = null;;) {
K ek;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
V ev = e.val;
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
e.val = value;
else if (pred != null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
}
else if (f instanceof TreeBin) {
validated = true;
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
oldVal = pv;
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (validated) {
if (oldVal != null) {
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}
过程：遍历整张表的桶节点，如果表还未初始化或者无法根据参数的hash值定位到桶节点，返回null。如果定位到桶节点类型是ForawdingNode，则去帮助扩容。否则就给桶加锁，删除一个节点。最后会调用 addCount 方法 CAS 更新 baseCount 的值。
size方法
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
final long sumCount() {
CounterCell[] as = counterCells; CounterCell a;
long sum = baseCount;
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
ConcurrentHashMap 中的 baseCount 属性不就是记录的所有键值对的总数吗？直接返回它不就行了吗？
之所以没有这么做，是因为我们的 addCount 方法用于 CAS 更新 baseCount，但很有可能在高并发的情况下，更新失败，那么这些节点虽然已经被添加到哈希表中了，但是数量却没有被统计。
还好，addCount 方法在更新 baseCount 失败的时候，会调用 fullAddCount 将这些失败的结点包装成一个 CounterCell 对象，保存在 CounterCell 数组中。那么整张表实际的 size 其实是 baseCount 加上 CounterCell 数组中元素的个数。
