HashMap

Map的实现类：
HashMap、LinkedHashMap、TreeMap、ConcurrentHashMap

底层结构：
hash表：数组+链表
HashMap：数组+链表/红黑树
LinkedHashMap：数组+链表+双向链表
ConcurrentHashMap：数组+链表/红黑树

new HashMap时：
（构造方法可以指定初始大小和负载因子，但是是懒惰创建数组，put时才创建）
默认初始大小为16，负载因子为0.75
hash的大小只能是2次幂的。如传10，初始值为16；传7，初始值为8。

负载因子的大小决定了哈希表的扩容和哈希冲突
以初始大小16和负载因子0.75为例，意味着数组最多只能放12个元素，即16*0.75个，一旦超过12个，hash表就需要扩容。每次put元素进去的时候，都需要检查有没有超过这个阈值，如果有，就扩容。扩容大小默认为原来的2倍（维持2次幂的规则）

负载因子的默认大小为何是0.75？
在空间占用与查询时间之间取得较好的权衡
大于这个值，空间节省了，但链表就会比较长影响性能
小于这个值，冲突减少了，但扩容就会更频繁，空间占用多

扩容肯定是耗时的，那我是否可以将负载因子调高，比如1，这样就到长度为16的时候才扩容，减少扩容的次数呢？
可以，但不推荐。负载因子调高，意味着hash冲突的概率会增大，会导致查找的速度变慢，同样会耗时。

hashMap中如何判断一个元素是否相同？
先比较hash值，再用==或者equels比较值是否相等，两者都相同，说明元素是同一个。

hashMap结构为：数组+链表/红黑树，什么情况下会用到红黑树呢？
当数组的大小大于等于64，且链表的长度大于8的时候，链表才会改为红黑树，当红黑树大小为6时，会退化为链表。
退化为链表主要是对查询和插入时性能的考量。链表查询时间复杂度O(N)，插入时间复杂度O(1)，红黑树查询和插入时间复杂度O(log2N)。

为什么要用红黑树？
链表长度过长影响查询效率，因此在链表长度超过一定阈值的时候，就转变为红黑树来优化查询效率。

为什么一上来不用红黑树？
短链表性能比红黑树要好，没有必要树化。链表的底层是node，红黑树的底层是treenode，treenode里的成员变量要比链表多很多，占用更多的内存。从性能和内存占用上来看，没有必要一上来就树化。

链表会超过8吗？
会。长度小于64，但key的原始hash值又相等，扩容并不能缩短链表。

扩容的时机？
元素超过16*0.75，或者链表的长度大于8但长度又小于64。

为什么阈值选择8？
红黑树本身应当被视为一种偶然情况，用来防止DoS攻击，防止链表超长而性能下降。常规业务中很难遇到链表长度为超过8的情况。hash值如果足够随机，应当符合泊松分布，在负载因子为0.75，出现长度超过8的链表导致树化的概率为亿分之6。

树退化的两种情况：
1、扩容时，树拆分后元素小于等于6；
2、remove节点时，根节点、左子、右子、左孙有一个为null，退化成链表，四个都存在，则不会退化。

如何计算索引？
计算对象的hashCode()，再进行调用HashMap的hash()方法进行二次哈希，最后&(capacity-1)（按位与数组容量-1）得到索引（桶下标），比普通的取模运算效率更高。前提：数组长度的2的n次幂。

如何得到二次hash值？为什么要用二次哈希来计算？
1.8源码：(h = key.hashCode()) ^ (h >>> 16)
原始hash与其高16位做异或运算得到二次hash值。
对原始hash进行一个扰动，让高位的数字也参与运算，使其分布的更加均匀，避免链表过长的情况。

为什么数组长度是2的n次幂？
有2点好处：
1、计算索引时可以用按位与代替取模，提高计算性能；
2、扩容时，重新计算索引时可以进行计算的优化。用二次hash值按位与原始容量，结果为0不用移动，结果不为0需要移动，新的索引即为原始索引+原始容量。
缺点：hash分布性不如长度为质数的时候。
综合考虑，设计者选择性能更优，因此选择2的n次幂作为数组容量。

put方法的实现？
1，对key做hash运算，得到key所在的index；
2，如果没有碰撞，直接放到数组中；
3，如果碰撞了
1）判断是链表结构还是红黑树结构，根据结构进行插入；
2）如果key值相同，替换原来的值；
4，判断hash表是否满了，满了则扩容。（先扩容，再迁移）

get方法实现？
1，对key做hash运算，得到key所在的index；
2，如果没有碰撞，直接取出
3，如果碰撞了，判断是链表结构还是红黑树结构，根据结构取出；

HashMap是线程安全的吗？
HashMap不是线程安全的。
1.7：扩容死链（头插法导致，变量e和next，next指向了上一个元素，导致链表中的元素循环引用）
1.7、1.8：数据错乱（HashMap有可能出现多线程操作下并发丢失数据的现象）

HashMap的key可以为null吗？作为key的对象有什么要求？
hashMap可以，其他的不行。
要求：重写hashCode和equals方法，并且key的内容不能修改。

String的hashCode是如何设计的？为什么每次都是乘31？
hashCode的设计的目的应该是让其具有更好的散列性。
乘31是因为：
1，31有更好的散列性，即分布更加均匀；
2，31的乘法可以转变为位运算（左移5位再做减法），使计算更加高效。

关于LinkedHashMap：
底层：数组+链表+双向链表。实际就是在HashMap的基础上，维护了一个双向链表，可以使得插入有序（非大小），在遍历的时候也是采用双向链表，所以其大小不会影响到遍历的性能。

关于TreeMap：
底层：红黑树。TreeMap的key不能为null，TreeMap有序是通过Comparator来进行比较的，如果Comparator为null，则使用自然排序。

关于ConcurrentHashMap：
ConcurrentHashMap是线程安全的Map实现类。
还有Hashtable，或用Collections包装出一个线程安全的Map，但由于这两种线程安全都是在外层套synchronize，所以我们一般有线程安全问题考量的，都使用ConcurrentHashMap。
ConcurrentHashMap底层数组+链表/红黑树，支持高并发的访问和更新，是线程安全的。

ConcurrentHashMap是如何实现线程安全的？
分段加锁，1.8之后优化了锁的细粒度，对每个元素进行CAS操作，即比较再交换

HashMap 1.8和1.7的区别