前言
友善揭示，本文篇幅波及知识点较多，耗费脑力比拟大。如果你怕当前找不到此文，倡议先珍藏
如果你不必温习，可间接跳到——面试开始
以下代码都出自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并发容器
发表回复