手把手教你锤面试官 01——HashMap 面试全攻略

本文是手把手教你锤面试官系列第一篇文章，该系列主要为大家分析和讲解在面试过程中，遇到面试官经常提出的面试问题如何进行攻防。另外本系列的文章也会提供许多小技巧给大家去间接试探出面试官的技术能力和专业水平，从而达到碾压面试官的目的。本系列文章只适用于JAVA工程师。



很多面试官喜欢问HashMap的一个原因就是因为HashMap我们经常在开发中用到，而且它线程不安全。这里有几个隐藏的问题：

0.HashMap的结构是怎么样的？

1.HashMap为什么线程不安全？

2.HashMap线程不安全在程序中的体现是什么？

3.既然HashMap线程不安全，为什么我们还经常用它？

4.怎么样可以让HashMap线程安全？



0.0回答

因为HashMap的数据结构是散列结构，散列结构就是我们说的key-value结构，它由一个数组和多个链表组成。每个数组节点对应一个链表。key值是一个数组存放，value的值放在多个链表中存放。下图就是一个典型的散列结构的图，左边是一个数组，右边是每个数组节点对应的链表。





1.1回答

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<K,V>[] tab; Node<K,V> 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<K,V> 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<K,V>)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;
}

2.2回答

多线程操作HashMap的场景下，会发生HashMap的值被覆盖，从而导致数据丢失。既同一个数组对应的链表被反复替换。另外，如果面试官问，会不会出现死循环或者数组下标越界。你就可以尽情的嘲讽，这个问题在JDK1.8已经不会出现了，难道贵公司还用JDK1.8以下版本？（这样做的好处是避免遇到面试官问你红黑二叉树还有HashMap的扩容机制，尽量避开）



3.3回答

废话，因为好用嘛。请看下图，下图是JAVA官方API中截取出来的类图。从下面这张图我们可以看出来Map是一个接口，我们常用的实现类有HashMap、HashTable、LinkedHashMap、TreeMap。



HashTable类是线程安全的，它使用synchronize来做线程安全，全局只有一把锁，在线程竞争比较激烈的情况下hashtable的效率是比较低下的。因为当一个线程访问hashtable的同步方法时，其他线程再次尝试访问的时候，会进入阻塞或者轮询状态，进而导致线程挂起。当你在多线程场景下使用Map，虽然不能使用HashMap但也尽量别使用HashTable。其实我个人觉得这个类可以废掉了。



LinkedHashMap就更不用说了，本身也是线程不安全的，而且每次插入的时候都要自己排序一次，每次排序都要进行一次遍历查询。你都用map了，你还会在意插入的顺序嘛？大多数情况你也不会在意插入的节点顺序。除非你一定要记录Map中节点插入的先后顺序，否则使用LinkedHashMap只会消耗性能。



TreeMap合LinkedHashMap一样，线程不安全而且要排序。





4.4回答

在多线程场景下放弃使用HashMap，可以使用CurrentHashMap替代HashMap。CurrentHashMap是綫程安全的，因为它和HashTable一样加了锁。而且我们上边也提到了，由于HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易线程阻塞、挂起。而CurrentHashMap采用CAS + synchronized + Node + 红黑树的多段分級锁的机制，可以对链表进行非常细粒度的加锁，不容易造成线程阻塞。



额外技巧

知己知彼，百战不殆。在面试过程中如果不知道面试官专业水平深浅的时候，可以在进行回答的时候故意漏出一个比较大的破绽。如果面试官没有提出异议，则说明水平不高，回答的时候尽量往底层走就可以唬住对方，让主动权在你手上。比方说回答HashMap的问题时，可以卖一个破绽——HashMap的默认长度是8（其实是16）。如果面试官没有提出异议，则说明该面试官对于HashMap这块最多也就是知道它线程不安全，可用CurrentHashMap替代。本文上面粗浅的内容最够你吊打对方。如果对方指正你默认长度是16，你可以先说，没错就是16，刚才一时紧张口误了。然后尽量避开对方提问HashMap扩容机制、链表红黑二叉树转换等问题。