前言
友善揭示，本文篇幅波及知识点较多，耗费脑力比拟大。如果你怕当前找不到此文，倡议先珍藏
如果你不必温习，可间接跳到——面试开始
以下代码都出自 JDK8
面试前，咱们温习一下
HashMap 的 put 办法
public V put(K key, V value) {
// 这里曾经对 key 进行一次哈希了
return putVal(hash(key), key, value, false, true);
}
// 扰动函数，次要性能：升高哈希抵触(具体内容不开展)
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<K,V>[] tab;// 桶数组
Node<K,V> p; // 节点
int n, i;
// 如果 table 为空，也就是没初始化，或者曾经被初始化了，然而数组长度为 0，即不是 2 的幂次方
if ((tab = table) == null || (n = tab.length) == 0)
// 给 tab 扩容，调配空间，初始值为 n =16
n = (tab = resize()).length;
// 如果桶 i 地位上没有节点
if ((p = tab[i = (n - 1) & hash]) == null)
// 那么就间接，创立节点，而后把节点放在桶的 i 地位上
tab[i] = newNode(hash, key, value, null);
// 如果桶 i 地位上有节点，p 是指向节点的援用
else {
Node<K,V> e;
K k;
// 如果 hash 相等，且 key 的内存地址或 key 的值相等。那就
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
// 如果 p 是红黑树上的节点，那就把节点加到红黑树上
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 遍历链表
for (int binCount = 0; ; ++binCount) {
// 如果后一个节点为 null
if ((e = p.next) == null) {
// 就把新节点放在 p 的后一个节点
p.next = newNode(hash, key, value, null);
// 如果 bincount>=8-1，就是 bincount== 8 时，链表转变红彩色
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// 如果该节点的 hash，key 和筹备加的节点相等。在前面会进行替换操作
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 替换值
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 如果 onlyIfAbsent 为 true，就不扭转 value 的值
if (!onlyIfAbsent || oldValue == null)
// 扭转 value 值
e.value = value;
// 留给 LinkedHashMap 的空办法
afterNodeAccess(e);
// 返回 oldValue
return oldValue;
}
}
++modCount;
// map 中的元素数量大于 threshold 时，就扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}总结一下，put 办法的大抵流程如下：
- 对 key 进行哈希，取得哈希值
- 将哈希值和数组长度取余，其值就是 key 的索引值
- 如果数组的索引地位为 null，则直接插入即可
-
如果数组的索引地位有值，需分三种状况：
- 状况 1：如果结点的 Key 和行将插入的 key 相等，那就间接替换 value 值即可
- 状况 2：如果节点属于红黑树的节点，就依照红黑树的更新或插入方式进行操作即可
- 状况 3：如果节点属于链表的节点，就遍历链表，能找到对应的节点，就替换值即可；如果不能找到对应的节点，就在链表的尾巴插入新的节点。
这只是一个大略的形容，具体的实现细节，间接看源代码就好。
HashMap 的 get 办法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
// 扰动函数，和 put 办法中应用的是同一个 hash 办法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab;
Node<K,V> first, e;
int n;
K k;
// 如果数组不为空，且数组的长度大于 0，且头结点不为空；否则间接返回 null
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
// 如果头结点的哈希值和 key 的哈希值相等，且 key 的地址或 key 的内容相等；就间接返回头结点
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 头结点不相等，如果有下一个节点，就遍历；如果没下一个节点，就返回 null
if ((e = first.next) != null) {
// 如果节点是红黑树，那么就依照红黑树的形式来获取节点，并返回
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
// 如果是链表，就遍历哈希值，key 的地址或 Key 的内容，有符合条件的就立刻返回，如果没，那么持续遍历下一个节点。如果遍历全副节点后，都没，那就返回 null
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
总结一下，HashMap 的 get 办法大抵流程如下：
- 依据 key 获取哈希值
- 依据哈希值和数组长度取余，取得索引值
- 依据索引值，获取对应的节点，而后比拟节点的 key 和 hash
- 如果相等，就返回对应的节点；不相等，就持续遍历；如果遍历到最初都没，就返回 null
这只是一个大略的形容，具体的实现细节，间接看源代码就好。
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
if (key == null || value == null) throw new NullPointerException();
// 计算出 hash 值
int hash = spread(key.hashCode());
int binCount = 0;
// 遍历 table
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// table 为 null，进行初始化工作
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 如果 i 地位没有节点，则直接插入，不须要加锁
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
//CAS
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;
// 对该节点进行加锁解决（hash 值雷同的链表的头节点），对性能有点儿影响
// 特地留神一下这个 f，这个 f 是头结点，锁的粒度是节点
synchronized (f) {if (tabAt(tab, i) == f) {
//fh > 0 示意为链表，将该节点插入到链表尾部
if (fh >= 0) {
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
//hash 和 key 都一样，替换 value
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
//putIfAbsent()
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) {
// 如果链表长度曾经达到临界值 8 就须要把链表转换为树结构
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
//size + 1
addCount(1L, binCount);
return null;
}总结一下，ConcurrentHashMap 的 put 办法的大抵流程如下：
- 首先，就是判空，key 和 value 都不容许为 null。(见补充常识 1)
- 而后计算哈希值。(见补充常识 4)絮叨一下：
-
接着遍历 table, 进行节点的插入操作，具体过程如下：
- 如果 table 为空，则示意 ConcurrentHashMap 还没有初始化，则进行初始化操作：initTable()
- 依据 hash 值获取节点的地位 i，若该地位为空，则直接插入，这个过程是不须要加锁的。计算 f 地位：i=(n – 1) & hash。(见补充常识 2)
- 如果检测到 fh = f.hash == -1，则 f 是 ForwardingNode 节点，示意有其余线程正在进行扩容操作，则帮忙线程一起进行扩容操作。(见补充常识 3)
- 如果 f.hash >= 0 示意是链表构造，则遍历链表，如果存在以后 key 节点则替换 value，否则插入到链表尾部。如果 f 是 TreeBin 类型节点，则依照红黑树的办法更新或者减少节点
- 若链表长度 > TREEIFY_THRESHOLD(默认是 8)，则将链表转换为红黑树结构
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());
// 如果数组不为空，且长度大于 0，且节点不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 搜寻到的节点 key 与传入的 key 雷同且不为 null, 间接返回这个节点
if ((eh = e.hash) == h) {if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// 树
else if (eh < 0)
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 办法的大抵流程如下：
- 先计算哈希值 h
- 通过 (n – 1) & h) 获取索引值
- 如果匹配是头节点，就间接返回对应的 value
- 如果是树，就依据红黑树的读操作返回 value
- 如果是链表，进行匹配，遍历，获取对应的 value
## 补充常识
- 1、HashMap 是容许 key 和 value 都为 null 的。
- 2、这个过程用了 CAS，能够了解为有锁也行，自旋锁。也能够了解为无锁，因为 CAS 属于硬件指令，不像 Synchronized 这样的操作系统级别的锁。因而，是否有锁，仁者见仁智者见智。你本人了解就好。
- 3、ForwardingNode：一个非凡的 Node 节点，hash 值为 -1，其中存储 nextTable 的援用。只有 table 产生扩容的时候，ForwardingNode 才会发挥作用，作为一个占位符放在 table 中示意以后节点为 null 或则曾经被挪动。
- 4、这个和 HashMap 的 hash 函数比拟，都有移位操作，只有稍微不同，但目标都是为了升高哈希抵触。
好了，置信你看完 HashMap 和 ConcurrentHashMap 的 get 和 put 办法后，曾经超级无敌累了。因为我也写的好累，害。当初你能够先点个赞，以慰藉我的劳苦；最好先珍藏一下，不便你当前温习再看。如果你累了，点个在看，不便你去喝口水，吃个饭回来再看。如果你感觉写得还不错，间接点分享，转给你的敌人。
广告打完了！！！我持续了！！！面试正式开始！！！
面试开始
面试官：你说一下 HashMap 的 put 办法的过程吧？
- 巴拉巴拉一堆，本人参考下面写的大抵流程即可，我就不反复了。
面试官：HashMap 中的链表什么条件下才会变树？
- 必须满足 2 个条件，一个是链表的长度 >=8 且 HashMap 的容量 capacity 必须 >=64，才会让链表变树。如果链表的长度 >=8, 但 HashMap 的容量 capacity<64, 那么会进行扩容操作。进行扩容操作后，链表的长度也会相应变短。(相干源码如下：)
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
... 省略一堆代码面试官：HashMap 中链表变树为什么是 8 个节点？
- 你就间接通知面试官，这是一个统计学问题。官网通过测试，大于 8 个节点时，发生冲突的概率是小于千万分之一的。(为了做到成竹在胸，我从源码中截取一段正文下来)
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million // 小于千万分之一面试官：HashMap 的 JDK7 和 JDK8 有什么区别？
- JDK7 产生哈希抵触时，链表会越来越长，工夫复杂度会变为 O(N); 相同，JDK 8 产生哈希抵触，链表在肯定条件下，会变为红黑树，工夫复杂度会变为 O(LogN);
- JDK7 在高并发环境下，因线程不平安，操作 put 办法时，会因为扩容 resize 办法和头插法，使得链表成环，从而在 get 办法时，引发 cpu100% 平安问题。JDK 8 尽管线程不平安，但把头插法改为尾插法，曾经不会在 resize 时，使得链表成环。
- 总结一下，比拟重要的区别，就是引入红黑树，面试官可能会问你，为什么是引入红黑树，而不是其余树，比方搜寻二叉树。其实次要考查你对数据结构的理解，面试前，最好把均衡树，红黑树，搜寻二叉树这些树的读写的工夫复杂度，以及优缺点都理解一下。
面试官：SynchronizedMap 和 ConcurrentHashMap 有什么区别？
- SynchronizedMap
一次锁住整张表来保障线程平安，所以每次只能有一个线程来访为 map。
- ConcurrentHashMap
应用 CAS+Synchronized 来保障在线程平安。绝对 SynchronizedMap 来说。ConcurrentHashMap 锁的是节点，SynchronizedMap 锁的是整张表。能够类比到 MySQL 的行锁和表锁。ConcurrentHashMap 锁的粒度更小。
另外 ConcurrentHashMap 应用了一种不同的迭代形式。在这种迭代形式中，当 iterator 被创立后汇合再产生扭转就不再是抛出 ConcurrentModificationException 异样，取而代之的是在扭转时 new 新的数据从而不影响原有的数据，iterator 实现后再将头指针替换为新的数据，这样 iterator 线程能够应用原来老的数据，而写线程也能够并发的实现扭转。
面试官:ConcurrentHashMap 为何读不必加锁？
- 对于这个点，其实须要比照 JDK7 和 JDK 8 的 ConcurrentHashMap。
-
在 JDK7 以及以前
- 在 HashEntry 中的 key、hash、next 均为 final 型，只能表头插入节点或删除结点。
- 在 HashEntry 中的 value 为 volatile 型。
- 不容许用 null 作为键和值，当读线程读到某个 HashEntry 的 value 域的值为 null 时，便晓得产生了抵触——产生了重排序景象（put 办法设置新 value 对象的字节码指令重排序），须要加锁后从新读入这个 value 值。
- volatile 变量 count 协调读写线程之间的内存可见性，写操作后批改 count，读操作先读 count，依据 happen-before 传递性准则写操作的批改读操作可能看到。
-
在 JDK8
- Node 的 val 和 next 均为 volatile 型。
- tabAt()办法 和 casTabAt()办法 对应的 Unsafe 操作实现了 volatile 语义，这样子就能够禁止指令重排序，不必放心读取到 Null 值。
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; }面试官：面试完结，祝贺进入下一轮面试
总结
其实，对于 Java 汇合——HashMap 和 ConcurrentHashMap 还有很多面试题，这里不一一开展
- ConcurrentHashMap 的迭代器是强一致性，还是弱一致性？HashMap 呢？
- HashMap 什么时候开始扩容？如何扩容？
- ConcurrentHashMap 7 和 8 的区别？
絮叨
非常感谢你能看到这里，如果感觉文章写得不错 求关注 求点赞 求分享 (对我十分十分有用)。
如果你感觉文章有待进步，我非常期待你对我的倡议，求留言。
如果你心愿看到什么内容，我非常期待你的留言。
各位的捧场和反对，是我创作的最大能源！
参考资料
- 芋道源码
- 小明哥——J.U.C 之 Java 并发容器