1. HashMap数据结构是什么

Java1.8插入元素为什么采用尾插法?
因为使用头插会改变链表的上的顺序，但是如果使用尾插，在扩容时会保持链表元素原本的顺序，就不会出现链表成环的问题了。具体原因如下:

1. 头插法的插入顺序和链表原顺序相反；

2. table是线程间共享的，每次操作都会修改table元素的next；
   

   Java7在多线程操作HashMap时可能引起死循环，原因是扩容转移后前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
   Java8在同样的前提下并不会引起死循环，原因是扩容转移后前后链表顺序不变，保持之前节点的引用关系

HashMap的数据结构为什么使用[数组+链表]?
组成HashMap的基本结构是数组和链表,数组里面每个地方都存了Key-Value这样的实例。那为什么需要链表呢?因为数组长度是有限制的

HashMap中的链表大小超过8个时会自动转化为红黑树，当删除小于六时重新变为链表，为啥呢？
根据泊松分布，在负载因子默认为0.75的时候，单个hash槽内元素个数为8的概率小于百万分之一，所以将7作为一个分水岭，等于7的时候不转换，大于等于8的时候才进行转换，小于等于6的时候就化为链表

是8仅仅是因为是统计学的结果

细问: 红黑树转回链表的阈值为什么是6，而不是8?
因为如果这个阈值也设置成8，假如发生碰撞，节点增减刚好在8附近，会发生链表和红黑树的不断转换，导致资源浪费

2. HashMap如何解决Hash冲突?

为什么会发生Hash冲突

当put的时候需要计算hash和下标，这个时候计算出来的值可能存在一样的，那么存到数组中的相同位置，就会发生hash冲突

如何解决Hash冲突？

1. 链地址法(HashMap使用)
   HashMap的解决方式是使用【链地址法】，即使用链表的方式解决。key一样的时候才会覆盖，否则就把元素放到链表的下一个位置

2. 【开放】定址法
   开放定址法就是从冲突的位置再接着往下找，给冲突元素找个空位。有以下两个方法:
   线行探查法: 从冲突的位置开始，依次判断下一个位置是否空闲，直至找到空闲位置
   平方探查法: 从冲突的位置x开始，第一次增加1^{2个位置，第二次增加2}2…，直至找到空闲的位置

3. 再哈希法
   换种哈希函数，重新计算冲突元素的地址

4. 建立公共溢出区
   再建一个数组，把冲突的元素放进去

3. HashMap的默认初始化长度是多少?

16

为什么是16？

1. 作者认为16这个初始容量是能符合常用而已

2. 同时16是2的次幂,方便位运算，位与运算比算数计算的效率高了很多

3. 之所以选择16，是为了服务将Key映射到index的算法。index = HashCode(Key)&(Length- 1)

4. 怎么尽可能得到一个均匀分布的hash?

只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

5. 为啥我们重写equals方法的时候需要重写hashCode方法呢?

在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，但是我们需要比较值，所以需要重写，
重写完equals方法后,在对hashCode进行重写，保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

6. 怎么处理HashMap在线程安全的场景?

1. ConcurrentHashMap

2. 使用Collections.synchronizedMap(Map)创建线程安全的map集合

3. Hashtable
   

   1. Hashtable和HashMap的不同点

2. 为什么Hashtable不允许键或值为null，而HashMap的键值则都可以为null?
   因为Hashtable使用的是安全失败机制（fail-safe），这种机制会使你此次读到的数据不一定是最新的数据(因为遍历的是拷贝的数据)。
   如果你使用null值，就会使得其无法判断对应的key是不存在还是为空，因为你无法再调用一次contain(key）来对key是否存在进行判断，ConcurrentHashMap同理。

在介绍怎么处理HashMap在线程安全的场景?时,有介绍到fail-safe和fail-fast 2个概念，它们具体是什么

安全失败（fail—safe）—— 并发度很低,是直接使用synchronized

采用安全失败机制的集合容器，使用迭代器进行遍历时不是直接在集合内容上访问的，而是将原有集合内容进行【拷贝】，在拷贝的集合上进行遍历。

原理
迭代器在遍历时访问的是【拷贝的集合】，所以在遍历过程中对原集合所作的修改并不能被迭代器检测到，所以不会触发 ConcurrentModificationException 异常。

应用场景
java.util.concurrent包下的容器都是安全失败，可以在多线程下并发使用，并发修改。不会报ConcurrentModificationException异常

优缺点

1. 由于对集合进行了拷贝，避免了 ConcurrentModificationException 异常，但拷贝时产生大量的无效对象，开销大。

2. 无法保证读取到的数据是原集合中最新的数据，即迭代器进行遍历的是拷贝的集合，在遍历期间原集合发生的修改，迭代器是检测不到的。

fail-fast是啥？

快速失败（fail—fast）是java集合中的一种机制， 在用迭代器遍历一个集合对象时，如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），则会抛出ConcurrentModification Exception

fail-fast原理
迭代器在遍历时直接访问集合中的内容，并且在遍历过程中使用一个 modCount 变量。集合在被遍历期间如果内容发生变化，就会改变modCount的值。每当迭代器使用hashNext()/next()遍历下一个元素之前，都会检测modCount变量是否为expectedmodCount值，是的话就返回遍历；否则抛出异常，终止遍历

注意:这里异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。 因此，不能依赖于这个异常是否抛出而进行并发操作的编程

哪些集合是fail-fast的?
java.util包下的集合类都是快速失败,不能在多线程下发生并发修改（迭代过程中被修改）

7. 有序Map

HashMap是无序的，根据 hash 值随机插入。如果想使用有序的Map，可以使用LinkedHashMap 或者 TreeMap

LinkedHashMap 怎么实现有序的？
LinkedHashMap维护了一个双向链表，有头尾节点，同时 LinkedHashMap 节点 Entry 内部除了继承 HashMap 的 Node 属性，还有 before 和 after 用于标识前置节点和后置节点。

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

8. HashSet

HashSet 底层就是基于 HashMap 实现的。HashSet 的源码⾮常⾮常少，因为除了 clone() 、 writeObject() 、 readObject() 是 HashSet⾃⼰不得不实现之外，其他⽅法都是直接调⽤ HashMap 中的⽅法。