高频面试题-JDK源码篇(HashMap)

前言

我觉得HashMap是一个高频面试题，甚至被问烂了，如果你还不懂HashMap原理，你很幸运，看了这边文章之后你将不存在这个问题！这里整理了一下HahsMap可能会被问到的知识点，从源码的角度去做了一些分析，当然你可以试着自己先回答一下：

1. HashMap底层用到了那些数据结构？
2. 为什么要用到链表结构？
3. 为什么要用到红黑树？
4. HashMap如何扩容的？
5. HashMap是如何Put一个元素的？
6. HashMap是如何Get一个元素的？
7. 什么是Hash冲突
8. 还有哪些解决Hash冲突的方式？

1. HashMap底层用到了那些数据结构？

HashMap用到了数组，链表，红黑树 。 数组中的每一个元素都是一个Key-Value键值对结构的Node对象,数组初始长度为16。 HashMap源码如下：

public class HashMap extends AbstractMap
    implements Map, Cloneable, Serializable {

	 /** 16 初始容量
     * The default initial capacity - MUST be a power of two.
     */
    static final int DEFAULT_INITIAL_CAPACITY = 1  0 &&
        //计算key存储位置，取出该位置的元素
            (first = tab[(n - 1) & hash]) != null) {
            //检查是不是第一个元素，比较key，如果是直接返回
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                //直接返回第一个元素
                return first;
                //如果next不为空，开始遍历链表
            if ((e = first.next) != null) {
           		 //如果是红黑树，就遍历红黑树
                if (first instanceof TreeNode)
                    return ((TreeNode)first).getTreeNode(hash, key);
                do {
                	//一直next遍历下一个元素，然后比较key，知道遍历完
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

9.你知道HashMap在多线程下死循环问题吗

这个问题在JDK1.8中已经得到解决，在JDK1.7及以前是有这个问题，造成原因是因为之前HashMap链表插入元素使用的是头插法，当HashMap扩容后，进行元素重新Hash位置重排的时候会出现链表上的元素循环指向的问题。

比如：有链表上元素按照：A -> B -> C 顺序排列，三者Hash值相同 ， 现在HashMap扩容，然后进行元素重新Hash，A,B,C三者由于Hash值相同，在新的数组中依然会计算出相同的存储位置。

我们可以这样理解，链表上的元素在进行重新Hash的时候是先取第一个元素A进行Hash，然后存储到数组上的某个位置 ， 然后再取B进行Hash,同样存储到该位置，由于使用头插法，所以形成了下图第二部的效果：B -> A , 这时你已经意识到问题了，在之前的链表上是： A -> B， 而重新Hash之后变成了B -> A ，其实这里就出现了元素相互引用的问题，即：死循环。 JDK1.8通过链表元素尾插法解决了这个问题，尾插法可以维持原有链表的顺序：

10.在多线程环境中能使用HashMap吗？

不能，HashMap暴露给外界的方法并不是同步的，在多线程环境中是可能会出现线程安全问题，在多线程环境中可以使用HashTable ，或者ConcurrentHashMap。 HashTable直接使用 synchronized 同步锁来保证线程安全，比较古老现在基本不用了。ConcurrentHashMap是JUC并发库中的容器 ，它是专门为多线程环境设计，并发控制使用 Synchronized 和 CAS 来操作，性能良好，在JDK1.8中ConcurrentHashMap也使用到了数组链表红黑树的结构来存储数据。

11.HashMap和HashTable的区别

HashTable是HashMap的线程安全版本，也是比较老旧的一个map,HashTable方法是加了同步锁，线程安全，性能会受到影响。而HashMap没有加同步锁，线程不安全，但是性能更高。

Hashtable既不支持Null key也不支持Null value ， 而HashMap值可以为null，key支持一个key为nul。

文章到这就结束了，喜欢的话就给个好评吧！！！