HashMap面试题目
HashMap
1.简述
HashMap是由数组和链表组合构成的数据结构，数组里每个地方豆村了Key-Value这样的实例，jdk1.7叫做Entry,jdk1.8叫做Node。初始化是所有位置都是null，put插入的时候会根据Key的hash函数去计算出一个index值，比如index是 2 ，就将这个Key-Value插入到数组下标为2 的位置。
2.为什么需要链表，链表又是什么样子的？
由于数组的长度是有限的，在有限的数组长度使用哈希，不同的key 经过hash会hash到同一个值上，这样就形成了链表。
看Node的源码 可以知道：每一个节点保存了自身的hash值、key、value，以及下一个节点的信息。
3.新的节点Node在插入时，它的插入方式是什么？
JDK1.8之前采用的是头插法，就是说新来的值会取代原有的值，原来的值就会被顺推到链表上去。写这个代码的作者认为后来的值被查询的可能性会大一点，为了提高查询效率。
JDK1.8之后，都是用的尾插法。尾插法在扩容时会保持链表元素原来的顺序，不会出现链表成环的问题。java8链表有红黑树的部分， 红黑树的引入巧妙的将原本O(n)的时间复杂度降低到了O（logn）
4. 为什么改成尾插法了？
因为头插法会改变链表上数据的顺序，可能会出现 Infinite Loop ,所以 JDK1.8之后，都是用的尾插法。
eg：一个容量为2的Entry数组，使用不同的线程插入A，B，C，假设在resize之前打一个断点，那就意味着数据都插入了，但是还没有扩容resize。结果可能是：在数组同一条Entry链上A->B->C(图1)；
因为1.7是头插法，resize后，在旧数组同一条Entry链上的元素，通过计算可能会在不同的位置上，可能的结果
如图2
一旦所有线程完成，可能出现环形链表，导致Infinite Loop 如图三
5. HashMap的扩容机制
由于数组的容量是有限的，数据多次插入的时候，到达一定的容量时，就会进行扩容，也就是resize。
6. 什么时候扩容（resize）？
两个因素：
- Capatity : HashMap的长度
- LoadFactoy : 负载因子，默认值时0.75f
eg：一个Hashmap的初始容量是100，当你存储第76个的时候 ，判断的时候就发现需要resize了。
7. HashMap怎么进行扩容？
扩容分两步：
- 扩容：创建一个新的Entry空数组，长度是原来的两倍
- ReHash：遍历原来的Entry数组，把所有的Entry重新Hash到新的数组中去。
问题：为什么要重新Hash？直接复制过去不香吗？
答：长度扩大了，Hash的规则也随之改变。Hash的公式：index=HashCode（key）& （Length-1）
8. Java8 HashMap是否可以用在多线程上？
java7在多线程操作的时候HashMap可能出现死循环，原因就是扩容转移后，前后链表顺序倒置，在转移过程中修改了原来链表中节点的引用关系。
java8在同样的前提下不会引起死循环，原因时扩容转移后，前后链表顺序不变，保持之前节点的引用关系。
java8 即使不会出现死循环，但是通过源码看到put/get方法没有加同步锁。多线程情况最容易出现的就是：无法保证上一秒put的值，下一秒get的时候还是原值，所以线程安全还是无法保证。
9. HasMap 的默认初始长度是多少？
16
之所以是16，是为了服务将key映射到index的算法，也是为了保证得到一个均匀分布的hash
10. 为什么重写equals方法的时候 需要重写hashCode？（用HashMap举例）
equals ：
- 对于值对象：==比较的是两个对象的值
- 对于引用对象：比较的是两个对象的地址
要重写hashCode？（用HashMap举例）
equals ：
- 对于值对象：==比较的是两个对象的值
- 对于引用对象：比较的是两个对象的地址
以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值