概要
我们在上一篇对HashTable进行了原理解析，再加上之前我们对HashMap的原理解析，这篇对ConcurrentHashMap的解析可称为数据结构解析三步曲了。
在这里我们也来总结一下他们的特点:
- HashMap采用数组+链表+红黑树方式实现,提高查找效率;它永远长度是2的整倍数，可能出现hash冲突造成get出现死循环，在多线程下无法保证数据安全。
- HashTable采用数组+链表的方式实现,采用Synchronized关键字锁方法的方式锁住了整个table来保证在多线程下的数据安全,但这样无疑使执行效率变得低下
- ConcurrentHashMap采用数组+链表+红黑树的方式实现,采用Synchronized关键字实现分段锁技术降低锁的颗粒度，利用多个锁控制多个私有的小table,来保证多线程下的数据安全,提高执行效率.
让你能清晰的了解三者的区别:
| 散列表 | 实现方式 | 数据安全 | 数据安全实现方式 | key\value是否可为Null |
|---|---|---|---|---|
| HashMap | 数组+单向链表+红黑树 | 不安全 | 无 | 可为Null |
| HashTable | 数组+单向链表 | 安全 | Synchronized | 不可为 Null |
| ConcurrentHashMap | 数组+单向链表+红黑树 | 安全 | Synchronized实现分段锁技术 | 不可为 Null |
ConcurrentHashMap
1.继承关系
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable
2.常量&构造方法
//ConcurrentHashMap容量极限
private static final int MAXIMUM_CAPACITY = 1 << 30;
//ConcurrentHashMap容量初始大小
private static final int DEFAULT_CAPACITY = 16;
//数组容量极限
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//默认并发级别
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
//默认负载因子大小
private static final float LOAD_FACTOR = 0.75f;
//链表转红黑树的阈值
static final int TREEIFY_THRESHOLD = 8;
//节点数小于等6保持单向链表状态
static final int UNTREEIFY_THRESHOLD = 6;
//红黑树容量最小64
static final int MIN_TREEIFY_CAPACITY = 64;
//每个转移步骤的最小复归数
private static final int MIN_TRANSFER_STRIDE = 16;
private static final int RESIZE_STAMP_BITS = 16;
//可以帮助调整大小的最大线程数
private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;
//记录生成戳的偏移位
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
//控制table初始化和扩容的标记量
//-1时 表示 正在初始化或正在扩容
//-(1+n) 表示 活动调整的线程数量
private transient volatile int sizeCtl;
//节点hash字段编码
static final int MOVED = -1; // 转发节点的hash
static final int TREEBIN = -2; // hash树的根
static final int RESERVED = -3; // 临时保留的hash
static final int HASH_BITS = 0x7fffffff; //普通节点hash的可用位
//默认构造方法
public ConcurrentHashMap() {
}
//指定初始化容量大小
public ConcurrentHashMap(int initialCapacity) {
//若指定的容量小于0 则抛出IllegalArgumentException异常
if (initialCapacity < 0)
throw new IllegalArgumentException();
//获取table容量
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
this.sizeCtl = cap;
}
//指定初始容量大小 & 指定负载因子大小
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
//指定初始容量大小 & 指定负载因子大小 & 估算更新线程的并发数目
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
this.sizeCtl = cap;
}
//传入一个Map集合,将Map集合中元素Map.Entry全部添加进HashMap实例中
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
3.Node单向链表的实现
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
Node(int hash, K key, V val, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return val; }
public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
public final String toString() {
return Helpers.mapEntryToString(key, val);
}
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
public final boolean equals(Object o) {
Object k, v, u; Map.Entry<?,?> e;
return ((o instanceof Map.Entry) &&
(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&
(v = e.getValue()) != null &&
(k == key || k.equals(key)) &&
(v == (u = val) || v.equals(u)));
}
/**
* Virtualized support for map.get(); overridden in subclasses.
*/
Node<K,V> find(int h, Object k) {
Node<K,V> e = this;
if (k != null) {
do {
K ek;
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
} while ((e = e.next) != null);
}
return null;
}
}
4.TreeNode红黑树实现
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next,
TreeNode<K,V> parent) {
super(hash, key, val, next);
this.parent = parent;
}
Node<K,V> find(int h, Object k) {
return findTreeNode(h, k, null);
}
/**
* Returns the TreeNode (or null if not found) for the given key
* starting at given root.
*/
final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {
if (k != null) {
TreeNode<K,V> p = this;
do {
int ph, dir; K pk; TreeNode<K,V> q;
TreeNode<K,V> pl = p.left, pr = p.right;
if ((ph = p.hash) > h)
p = pl;
else if (ph < h)
p = pr;
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
else if ((q = pr.findTreeNode(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
}
return null;
}
}
5.spread的计算实现
将(XORs)较高的哈希值向较低的哈希值扩展(XORs)，并强制执行将最高位置0
static final int spread(int h) {
return (h ^ (h >>> 16)) & HASH_BITS;
}
6.ConcurrentHashMap put的源码实现
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
//key 和 value 不可为Null,若为null则将抛出 NullPointerException异常
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;
//判定tab为Null 或 长度为0
if (tab == null || (n = tab.length) == 0)
//初始化tab
tab = initTable();
//通过执行tabAt函数寻找tab索引下的Entry
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) { //对tab中一个节点加锁，这个锁锁在Entry的根节点上的
if (tabAt(tab, i) == f) { //做判定 若tab中第i个元素 等于 f节点
//此判定若成功 说明f节点下是一个普通节点 即链表节点
if (fh >= 0) {
binCount = 1;
//遍历整个链表
for (Node<K,V> e = f;; ++binCount) {
K ek;
//判定若成功则修改节点下的value值
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;
//若指向的下一个节点为null
if ((e = e.next) == null) {
//new出一个新节点进行插入 此处即我们存储put进来的值的新索引位置
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
//若 f类型TreeBin 黑红树
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
//执行putTreeValue方法进行添加或查询节点操作
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
else if (f instanceof ReservationNode)
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
//当节点长度大于等于8时
if (binCount >= TREEIFY_THRESHOLD)
//将原来的链表存储方式转换为黑红树存储
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
梳理以下ConcurrentHashTable put函数的执行过程
- 1.key 和 value 不可为Null,若为null则将抛出 NullPointerException异常
- 2.判定tab为Null 或 长度为0 判定成功则初始化table
- 3.否则 通过执行tabAt函数寻找tab索引下的Entry若为空 则判定是否需要比较并进行交换
- 4.若tabAt函数寻找tab索引下的Entry不为空 则判定f.hash是否为MOVE 若判定成功 则在调整tab大小过程中帮助转移
- 5.1.若以上条件都不成立 则 对tab中一个节点加锁，这个锁锁在Entry的根节点上的
- 5.1.1 做判定 若tab中第i个元素 等于 f节点 此判定若成功 说明f节点下是一个普通节点 即链表节点
- 5.1.1.1 遍历整个链表,查找符合条件的节点修改节点下的值
- 5.1.2 若 f类型TreeBin 黑红树 则执行putTreeValue方法进行添加或查询节点操作
- 5.2 当节点长度大于等于8时 将原来的链表存储方式转换为黑红树存储
- 6.添加到总数中,若容量小则进行扩容
7.ConcurrentHashMap get的源码实现
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//计算hash值
int h = spread(key.hashCode());
//table 不为null & table长度大于0 & table索引位置下的Entry不为null
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
//做判定Hash匹配成功
if ((eh = e.hash) == h) {
//key的匹配成功
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
//返回节点下的vlaue
return e.val;
}
else if (eh < 0) //hash节点小于0
//使用find函数在单向链表中查找value
return (p = e.find(h, key)) != null ? p.val : null;
//通过while循环,遍历e下的子节点查找value
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
8.ConcurrentHashMap treeifyBin的源码实现
单向链表转为黑红树
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n;
//判定单向链表不为null
if (tab != null) {
//判定tab长度若小于黑红树最小长度
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
//对黑红树进行扩容
tryPresize(n << 1);
//tab指定索引下数据不为null & hash值大于0
//这里将tab赋给b 原因是为下面Synchronized准备的
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
//加锁 锁住了b 是为了降低锁的颗粒度
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
//遍历b下的节点
for (Node<K,V> e = b; e != null; e = e.next) {
//声明黑红树
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
//将上一个子节点设置成下一个节点的父节点
hd = p;
else
//设置下一个节点
tl.next = p;
//设置子节点
tl = p;
}
//将tab指定的索引设置进以hd为头部节点的TreeBin中
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}
梳理以下ConcurrentHashTable treeifyBin函数的执行过程
- 1.判定黑红树是否需要扩容
- tab指定索引下数据不为null & hash值大于0，这里将tab赋给b 原因是为下面Synchronized准备的
- 2.1加锁 锁住了b 是为了降低锁的颗粒度
- 2.3 遍历b下的节点，新建黑红树节点
- 2.4 将上一个子节点设置成下一个节点的父节点，设置下一个节点，设置子节点
- 2.5 将tab指定的索引设置进以hd为头部节点的TreeBin中
9.ConcurrentHashMap 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(); // 让出线程执行资源
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;
}
