共计 8187 个字符,预计需要花费 21 分钟才能阅读完成。
前言
友善揭示,本文篇幅波及知识点较多,耗费脑力比拟大。如果你怕当前找不到此文,倡议先珍藏
如果你不必温习,可间接跳到——面试开始
以下代码都出自 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 并发容器