承接上篇《Java 深入研究 Collection 汇合框架》文章中的 HashMap、ConcurrentHashMap 源码剖析, 在 Java 中罕用的四个实现 Map 接口的类，别离是 HashMap、TreeMap、LinkedHashMap 以及继承自 Dictionary 抽象类的 Hashtable，上面简略概述下各实现类的特点 :
HashMap
依据键的 hashcode 存储数据，容许 null 键 / 值(null 键只容许一条，value 能够有多条 null)，非 synchronized、元素无序，程序也可能随时扭转，底层基于链表 + 红黑树实现【JDK1.8】
TreeMap
实现 SortedMap 接口，能够依据键排序，默认按键值升序排序，也能够指定排序的比拟器，在应用时 key 必须实现 Comparable 接口，TreeMap 在 Iterator 遍历是排过序的
LinkedHashMap
属于 HashMap 的一个子类，保留了记录的插入程序，在用 Iterator 遍历 LinkedHashMap 时，先失去的记录必定是先插入的，也能够在结构时带参数，依照拜访秩序排序
Hashtable
罕用性能跟 HashMap 相似，不反对 null 键 / 值,synchronized 线程平安，Hashtable 默认的初始大小为 11，之后每次裁减，容量变为原来的 2n+1.HashMap 默认的初始化大小为 16. 之后每次裁减，容量变为原来的 2 倍，并发性不如 ConcurrentHashMap，因为 ConcurrentHashMap 引入了分段锁
HashMap 重要的常量定义
DEFAULT_INITIAL_CAPACITY =16 默认容量
MAXIMUM_CAPACITY =1 << 30 最大容量
DEFAULT_LOAD_FACTOR = 0.75f 默认负载因子
TREEIFY_THRESHOLD=8 链表转换红黑树的阀值
UNTREEIFY_THRESHOLD=6 红黑树转换链表的阀值
MIN_TREEIFY_CAPACITY=64 桶中 bin 最小 hash 容量，如果大于这个值会进行 resize 扩容操作，此值至多是 TREEIFY_THRESHOLD 的 4 倍HashMap 构造函数
首先看初始化容量、负载因子的有参函数源码
public HashMap(int initialCapacity, float loadFactor) {if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity:" +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor:" +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}惯例的边界判断、赋值操作，通过 tableSizeFor 办法计算初始容量
HashMap put 办法源码剖析
办法调用
public V put(K key, V value) {return putVal(hash(key), key, value, false, true);
}
传入 key 的 hash 计算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
理论调用办法
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
// 部分 node 节点 tab
Node<K,V>[] tab; Node<K,V> p; int n, i;
// 将初始化的 table 赋值给 tab 并判 null，如果为空则进行 tab 初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 依据 hash 计算 tab[i]地位，判断如果为空则调用 newNode()存储新的 node<K,V> 中
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 依据 hash 值和 equals 判断 key，如果 key 雷同就把老的 node 赋值给变量 e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//key 不同，判断是否时红黑树，如果是则调用 putTreeVal()放在树中
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) {// 没有下一个元素，则把以后元素传入 newNode()作为下一个元素
p.next = newNode(hash, key, value, null);
// 链表长度超过阈值 TREEIFY_THRESHOLD=8
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;
}
}
// 判断 value 是否替换
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;
}-
resize 实现
当 put 时，如果 bucke 占用水平曾经超过了 DEFAULT_LOAD_FACTOR 参数初始比例，就把 bucket 裁减为 2 倍，之后从新计算 index，再把节点放到新的 bucket 中，源代码阐明如下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
实现办法在【JDK1.7】和【JDK1.8】中有差别 (1.8 引入红黑树)，感兴趣能够钻研 JDK 源码对 reszie() 的实现
HashMap get 办法源码剖析
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//hash 值同 put 操作
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
// 判断 tab 节点是否为空，依据 hash 算出下标
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 在第一个 node 中查找
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 如果有下一个元素
if ((e = first.next) != null) {// 如果是树，调用 getTreeNode()在红黑树中查找
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;
}HashMap put、get 办法思路总结
put 办法大抵思路
- 依据键值 key 做 hash 计算，失去插入数组下标，如果 tab[i]为 null，间接 newNode 插入新节点
- 如果 tab[i]不为 null，判断 tab[i]首个元素和 key 是否雷同，雷同就把老元素赋值给局部变量
- 如果比拟的 key 不同，判断是否为 TreeNode(红黑树), 如果是，调用 putTreeVal()插入树中
- 如果不是 TreeNode, 对链表做遍历，链表长度超过阈值 TREEIFY_THRESHOLD= 8 转换成红黑树
get 办法大抵思路
- 判断 tab 节点是否为空，依据 hash 算出下标
- 在第一个 node 节点中查找，如果有间接 return first
- 如果没有，判断是否有下一个元素，如果有判断是否为 TreeNode, 如果是则在树中查找
- 如果不是，循环链表查找
equals()和 hashCode()的作用
通过对 key 的 hashCode()进行 hashing，并计算下标 ( n-1 & hash)，从而取得 buckets 的地位。如果比拟的 key 雷同，则利用 key.equals() 办法去链表或树中去查找对应的节点
<br/>
ConcurrentHashMap 实现原理
ConcurrentHashMap 在 Java 8 中勾销了 Segment 分段锁的数据结构，采纳数组 + 链表 + 红黑树的数据结构，而对于锁的粒度，调整为对每个数组元素加锁 (Node 节点)，简化定位节点的 hash 算法，这样带来的弊病是 hash 碰撞会增大，因而在链表节点数量大于 8 时，会将链表转化为红黑树进行存储。这样一来，查问的工夫复杂度就会由原先的 O(n) 变为 O(logN)
对于 CAS 算法
CAS 的全称叫 ”Compare And Swap”，也就是比拟并替换，应用时次要波及到三个操作数，内存值 V 、预期值 A 、新值 B ，如果在执行时发现 内存值 V 与 预期值 A 相匹配，那么他会将 内存值 V 更新为 新值 B ，相同处理器就不会执行任何操作
外围属性
// 用于 table[]的初始化和扩容操作，- 1 示意正在初始化，- N 示意有 N 个线程正在扩容，非正数时，示意初始化 table[]的大小，曾经初始化则示意扩容阈值，默认为 table[]容量的 0.75 倍
private transient volatile int sizeCtl;
// 示意默认的并发级别，也就是 table[]的默认大小
private static finalint DEFAULT_CONCURRENCY_LEVEL = 16;
// 默认的负载因子
private static final float LOAD_FACTOR = 0.75f;
// 链表转红黑树的阀值
static final int TREEIFY_THRESHOLD = 8;
// 红黑树转链表的阀值，static final int UNTREEIFY_THRESHOLD = 6;
// 哈希表的最小树形化容量
static final int MIN_TREEIFY_CAPACITY = 64;构造函数
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 容量 size、concurrencyLevel 并发级别
}put 操作
// 惯例 put 入口
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();
int hash = spread(key.hashCode());// 计算 key hash
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();// 惯例初始化 tab[]
// 依据 hash 值与运算确认下标并将节点赋值给 f，而后判 null
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 如果为空，采纳 CAS 算法将新值插入 Node 节点
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//hash 值 ==-1，阐明正在扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);// 扩容后返回最新 tab[]
else {
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;
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;//key 雷同，进行 value 替换，退出循环
}
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;
}
}
else if (f instanceof ReservationNode)// 空节点，占位符
throw new IllegalStateException("Recursive update");
}
}
if (binCount != 0) {
// 链表转换红黑树阈值判断
if (binCount >= TREEIFY_THRESHOLD)
// 与 HashMap 类中转换红黑树有区别，当 hash 表长度小于 MIN_TREEIFY_CAPACITY 属性值时尝试扩容操作，相同进行树形化
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}ConcurrentHashMap 的 put()操作大抵流程
- 初始化 map 容量 size、concurrencyLevel 并发级别
- 对键、值非 null 判断，计算 hash 值，判断 table[]是否创立，没有就初始化
- 如果 table[i]为 null，采纳 CAS 算法将新值插入 Node 节点
- 如果不为 null, 判断 hash 值是否为 -1，如果是则调用 helpTransfer()扩容
- 如果 hash 值不为 -1，就在链表尾部或者和红黑树中插入节点
- 最初对链表转红黑树阈值做判断，当 hash 表长度小于 MIN_TREEIFY_CAPACITY 属性值时尝试扩容操作，相同进行树形化
get 操作
public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());// 计算 key hash
// 判断 table[]是否为 null, 依据下标确认 table[i]节点并做非 null 束缚
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 比拟头部元素是否雷同，雷同则间接返回该键对应的值
if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 如果头结点的 hash 小于 0，阐明正在扩容，或者该地位是红黑树
else if (eh < 0)
//e.find 可比照查看 ForwardingNode 类的 find()、TreeBin 类的 find()源码
return (p = e.find(h, key)) != null ? p.val : null;
// 遍历链表
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}ConcurrentHashMap 的 get()操作大抵流程(不加锁)
- 计算 key 的 hash 值，判断 table[]是否为 null，同时依据下标判断 table[i]是否为 null
- 如果 table[i]则比拟链表头部元素是否雷同，如果是间接返回该键地位所对应的值
- 如果 hash 不雷同，判断是否是红黑树或是正在扩容操作，如果是则在树中查找
- 如果不是红黑树或是正在扩容操作，则遍历链表查找
Java8 对 ConcurrentHashMap 实现改良
- 不采纳 segment 而采纳 node，锁住 node 来实现减小锁粒度，退出红黑树机制
- 换回 Synchronized 关键字，替换 ReentrantLock 分段锁
- 设计了 MOVED 状态，容许多线程进行帮忙扩容操作
- 应用 CAS 操作来确保 node 的一些操作的原子性，这种形式代替了锁
- 采纳 sizeCtl 的不同值来代表不同含意，起到了管制的作用