HashMap知识点

1. Hashmap 的原理，内部数据结构？
底层使用哈希表（数组+链表），当链表过长会将链表转成红黑树以实现 o (ogn）时间复杂度内查找

2. 讲一下 Hashmap 中 put 方法过程？
对 Key求 Hash 值，然后再计算下标
如果没碰撞，直接放入桶中，
如果碰撞了，以链表的方式链接到后面，
如果链表长度超过阀值（TREEIFY THRESHOLD==8），就把链表转成红黑树
如果节点已经存在就替换旧值
如果桶满了（容量*加载因子），就需要 resize。

3. Hashmap 中 hash 函数怎么是是实现的？
高 16 bit 不变，低 16 bit 和高 16 bit 做了一个异或
(n-1) &hash->得到下标

4. Hashmap 怎样解决沖突，讲一下扩容过程，假如个值在原数组中，现在移动了新数组，位置肯定改变了，那是什么定位到在这个值新数组中的位置，
   将新节点加到链表后，容量扩充为原来的两倍，然后对每个节点重新计算哈希值
   这个值只可能在两个地方，一个是原下标的位置，另一种是在下标为<原下标+原容量>的位置

5. 抛开 Hashmap, hash 冲突有那些解决法？
开放定址，链地址法

6. 针对 Hashmap 中某个 Enty 链太长，查找的时间复杂度可能达到 O (n），怎么优化？
   将链表转为红黑树，JDK1.8 已经实现了

7. 为什么说Hash不安全
jdk7中多线程环境下容易造成死循环。 在hash map的扩容函数transfer时，对元素进行转移时使用头插法，链表的顺序会翻转，容易造成死循环

在jdk8中对HashMap进行了优化，在发生hash碰撞，不再采用头插法方式，而是直接插入链表尾部，因此不会出现环形链表的情况，但是在多线程的情况下仍然不安全，
jdk8中HashMap的put操作源码中，线程A和线程B同时进行put操作，刚好这两条不同的数据hash值一样，并且该位置数据为null，会发生覆盖现象

总结:
在jdk1.7中，在多线程环境下，扩容时会造成环形链或数据丢失。
在jdk1.8中，在多线程环境下，会发生数据覆盖的情况。