手把手教你锤面试官01——HashMap面试全攻略
本文是手把手教你锤面试官系列第一篇文章，该系列主要为大家分析和讲解在面试过程中，遇到面试官经常提出的面试问题如何进行攻防。另外本系列的文章也会提供许多小技巧给大家去间接试探出面试官的技术能力和专业水平，从而达到碾压面试官的目的。本系列文章只适用于JAVA工程师。
很多面试官喜欢问HashMap的一个原因就是因为HashMap我们经常在开发中用到，而且它线程不安全。这里有几个隐藏的问题：
0.HashMap的结构是怎么样的？
1.HashMap为什么线程不安全？
2.HashMap线程不安全在程序中的体现是什么？
3.既然HashMap线程不安全，为什么我们还经常用它？
4.怎么样可以让HashMap线程安全？
因为HashMap的数据结构是散列结构，散列结构就是我们说的key-value结构，它由一个数组和多个链表组成。每个数组节点对应一个链表。key值是一个数组存放，value的值放在多个链表中存放。下图就是一个典型的散列结构的图，左边是一个数组，右边是每个数组节点对应的链表。
HashMap中put操作的主函数，如果没有hash碰撞则会直接插入元素。如果线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，所以这线程A、B都会进入下面代码的第6行代码中。
假设一种情况，线程A进入后还未进行数据插入时挂起，而线程B正常执行，从而正常插入数据，然后线程A获取CPU时间片，此时线程A不用再进行hash判断了，问题出现：线程A会把线程B插入的数据给覆盖，发生线程不安全。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node[] tab; Node p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null) // 如果没有hash碰撞则会直接插入元素
tab[i] = newNode(hash, key, value, null);
else {
Node e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
} 废话，因为好用嘛。请看下图，下图是JAVA官方API中截取出来的类图。从下面这张图我们可以看出来Map是一个接口，我们常用的实现类有HashMap、HashTable、LinkedHashMap、TreeMap。
HashTable类是线程安全的，它使用synchronize来做线程安全，全局只有一把锁，在线程竞争比较激烈的情况下hashtable的效率是比较低下的。因为当一个线程访问hashtable的同步方法时，其他线程再次尝试访问的时候，会进入阻塞或者轮询状态，进而导致线程挂起。当你在多线程场景下使用Map，虽然不能使用HashMap但也尽量别使用HashTable。其实我个人觉得这个类可以废掉了。
LinkedHashMap就更不用说了，本身也是线程不安全的，而且每次插入的时候都要自己排序一次，每次排序都要进行一次遍历查询。你都用map了，你还会在意插入的顺序嘛？大多数情况你也不会在意插入的节点顺序。除非你一定要记录Map中节点插入的先后顺序，否则使用LinkedHashMap只会消耗性能。
TreeMap合LinkedHashMap一样，线程不安全而且要排序。
在多线程场景下放弃使用HashMap，可以使用CurrentHashMap替代HashMap。CurrentHashMap是綫程安全的，因为它和HashTable一样加了锁。而且我们上边也提到了，由于HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易线程阻塞、挂起。而CurrentHashMap采用CAS + synchronized + Node + 红黑树的多段分級锁的机制，可以对链表进行非常细粒度的加锁，不容易造成线程阻塞。