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