每日一面系列之HashMap夺命连环问

1.HashMap的底层数据结构是什么？

底层数据结构是哈希表结构（链表散列：数组+单向链表），结合了数组和链表的优点，当链表长度超过8时，链表会转为红黑树。数组中的每一个元素都是链表。总结来说就是HashMap在JDK1.8之前底层是由数组+链表实现的，在JDK1.8开始底层是由数组+链表或者数组+红黑树实现的。

追问：为什么在1.8中增加红黑树？

当需要查找某个元素的时候，线性探索是最直白的方式，它会把所有数据遍历一遍直到找到你所查找的数据，对于数组和链表这种线性结构来说，当链表长度过长（数据有成百上千）的时候，会造成链表过深的问题，这种查找方式效率极低，时间复杂度是O(n)。简单来说红黑树的出现就是为了提高数据检索的速度。

追问：链表过深问题为什么不用二叉查找树代替，而选择红黑树？为什么不一直使用红黑树？

二叉树在特殊情况下会变成一条线性结构，这就跟原来的链表结构一样了，选择红黑树就是为了解决二叉树的缺陷。

红黑树在插入数据的时候需要通过左旋、右旋、变色这些操作来保持平衡，为了保持这种平衡是需要付出代价的。当链表很短的时候，没必要使用红黑树，否则会导致效率更低，当链表很长的时候，使用红黑树，保持平衡的操作所消耗的资源要远小于遍历链表锁消耗的效率，所以才会设定一个阈值，去判断什么时候使用链表，什么时候使用红黑树。

追问：讲一下你对红黑树的认识

每个节点非红即黑

根节点总是黑色的

如果节点是红色，则它的子节点必须是黑色（反之不一定）

每个叶子节点都是黑色的空节点

从根节点到叶子节点或者空节点的每条路径必须包含相同数量的黑色节点（黑色节点的深度相同）

2.讲一下HashMap的工作原理，put()和get()的过程分别是怎么样的？

存储对象时，将key和vaule传给put()方法：

判断数组是否为空，为空进行初始化;

不为空，计算 k 的 hash 值，通过(n - 1) & hash计算应当存放在数组中的下标 index;

查看 table[index] 是否存在数据，没有数据就构造一个Node节点存放在 table[index] 中；

存在数据，说明发生了hash冲突(存在二个节点key的hash值一样), 继续判断key是否相等，相等，用新的value替换原数据(onlyIfAbsent为false)；

如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中；(如果当前节点是树型节点证明当前已经是红黑树了)

如果不是树型节点，创建普通Node加入链表中；判断链表长度是否大于8并且数组长度大于64，大于的话链表转换为红黑树；

插入完成之后判断当前节点数是否大于阈值（capacity*loadFactor），如果大于开始扩容为原数组的二倍。

下面以流程图方式更加直观的看一下插入流程：

获取对象时，将key传给get()方法：

调用hash(key)方法获取key对应的hash值从而获取该键值对在数组中的下标。

对链表进行顺序遍历，使用equals()方法查找链表中相等的key对应的value值。

追问：说一下数组是怎么扩容的？

创建一个新数组，新数组初始化容量大小是旧数组的两倍，对原数组中元素重新进行一次hash从而定位在新数组中的存储位置，元素在新数组中的位置只有两种，原下标位置或原下标+旧数组的大小。

追问：为什么要对原数组中元素再重新进行一次hash？直接复制到新数组不行吗？

因为数组长度扩大以后Hash规则也会随之变化。

Hash的公式—> index = HashCode（Key） & （Length - 1）

追问：在插入元素的时候，JDK1.7与JDK1.8有什么不同？

1.7是先判断是否需要扩容，再进行插入操作。1.8是先插入，插入完成之后再判断是否需要扩容。

注：hashcode是用来定位的，定键值对在数组中的存储位置。equals()方法是用来定性的，比较两个对象是否相等。

3.你说JDK1.8之前使用头插法将Entry节点插入链表，那么头插法具体是怎么做的？设计头插法的目的是什么？

新值会作为链表的头部替换原来的值，原来的值会被顺推到链表当中。下面以图解方式说明一下：

设计者认为后来插入的值被查找的概率比较高，使用头插法可以提高查找的效率。

4.之前是头插法，为什么JDK1.8之后要改成尾插法？

JDK1.8之前扩容的时候，头插法会导致链表反转，在多线程情况下会出现环形链表，导致取值的时候出现死循环，JDK1.8开始在同样的前提下就不会导致死循环，因为在扩容转移前后链表的顺序不变，保持之前节点的引用关系。

例： A线程和B线程同时向同一个下标位置插入节点，遇到容量不够开始扩容，重新hash，放置元素，采用头插法，后遍历到的B节点放入了头部，这样形成了环，如下图所示：

5.HashMap是怎么设定初始化容量大小的？

使用new HashMap()不传值，默认大小是16，负载因子是0.75。如果传入参数K，那么初始化容量大小为大于K的2的最小整数幂。比如传入的是10，那么初始化容量大小就是16（2的4次方）。

追问：为什么HashMap的数组长度要取2的整数幂？

因为这样数组长度-1正好相当于一个“低位掩码”。“与”操作的结果就是散列值的高位全部归零，只保留低位值，用来做数组下标访问。以初始长度16为例，16-1=15。2进制表示是00000000 00000000 00001111。和某散列值做“与”操作如下，结果就是截取了最低的四位值。

6.讲一下HashMap中的哈希函数时怎么实现的？

key的hashcode是一个32位的int类型值，hash函数就是将hashcode的高16位和低16位进行异或运算。

追问：哈希函数为什么这么设计？

这是一个扰动函数，这样设计的原因主要有两点：

可以最大程度的降低hash碰撞的概率（hash值越分散越好）；

因为是高频操作，所以采用位运算，让算法更加高效；

7.HashMap是线程安全的吗？

不是，在多线程的情况下，1.7的HashMap会导致死循环、数据丢失、数据覆盖。在1.8中如果有多个线程同时put()元素还是会存在数据覆盖的问题。以1.8位例，A线程判断index位置为空后正好挂起，B线程开始向index位置写入节点数据，这时A线程恢复现场，执行赋值操作，就把A线程的数据给覆盖了。

追问：如何解决这个线程不安全的问题？

可以使用HashTable、Collections.synchronizedMap、以及ConcurrentHashMap这些线程安全的Map。

追问：分别讲一下这几种Map都是如何实现线程安全的？

HashTable是直接在操作方法上加synchronized关键字，锁住整个数组，粒度比较大；

Collections.synchronizedMap是使用Collections集合工具的内部类，通过传入Map封装出一个SynchronizedMap对象，内部定义了一个对象锁，方法内通过对象锁实现；

ConcurrentHashMap在JDK1.7中使用分段锁，降低了锁粒度，让并发度大大提高，在JDK 1.8 中直接采用了CAS（无锁算法）+ synchronized的方式来实现线程安全。

8.说一下HashMap在JDK1.8中都有哪些改变？

底层数据结构：1.7中是数组+链表。1.8中是数组+链表或数组+红黑树；

元素插入方式：1.7是头插法插入链表。1.7是尾插法插入链表；

节点类型：1.7中数组中节点类型是Entry节点，1.8中数组中节点类型是Node节点；

元素插入流程：1.7中是先判断是否需要扩容，再插入。1.8中是先插入，插入成功之后再判断是否需要扩容；

扩容方式：1.7中需要对原数组中元素重新进行hash定位在新数组中的位置。1.8中采用更简单的逻辑判断，原下标位置或原下标+旧数组的大小。

9.HashMap的内部节点是有序的吗？

是无序的，根据hash值随机插入。

追问：你知道哪些有序的Map？

LinkedHashMap和TreeMap。

追问：说一下这两种Map分别是怎么实现有序的

LinkedHashMap：LinkedHashMap内部维护了一个单链表，有头尾节点，同时LinkedHashMap节点Entry内部除了继承HashMap的Node属性，还有before 和 after用于标识前置节点和后置节点。可以实现按插入的顺序或访问顺序排序。

TreeHashMap： TreeMap是按照Key的自然顺序或者Comprator的顺序进行排序，内部是通过红黑树来实现。所以要么key所属的类实现Comparable接口，或者自定义一个实现了Comparator接口的比较器，传给TreeMap用于key的比较。

10.HashMap，LinkedHashMap，TreeMap 有什么区别？

LinkedHashMap 保存了记录的插入顺序，在用 Iterator 遍历时，先取到的记录肯定是先插入的；遍历比 HashMap 慢。TreeMap 实现 SortMap 接口，能够把它保存的记录根据键排序（默认按键值升序排序，也可以指定排序的比较器）

追问：讲一下这三种Map的使用场景

一般情况下，使用最多的是 HashMap。

HashMap：在 Map 中插入、删除和定位元素时；

TreeMap：在需要按自然顺序或自定义顺序遍历键的情况下；

LinkedHashMap：在需要输出的顺序和输入的顺序相同的情况下。