1 1.7 和 1.8 的底层数据结构

1.7 数组+链表
1.8 数组+链表|红黑树

2 树化

在数组大小大于64，并且链表长度≥8时树化
如果链表长度≥8，但是数组大小不足64，会优先选择扩容。

2.1 为什么会选择8作为链表树化阈值？

	1.hash值足够随机，则hash表内按照泊松分布，在负载因子0.75时，长度超过8的链表出现概率是0.000000006，选择8就是为了让树化的概率足够小

3 退化

1 在扩容时如果拆分树时，树元素个数≤6，则会退化成链表
2 remove树节点时，若root，root.left,root.right,root.left.left有一个为null，也会退化成为链表。

3.1 注意点：

1.树元素≤6退化，只会在扩容后，树拆分之后才是。
2.在remove操作之前判断根节点，左孩子，右孩子和左孙子是否为空。

3.2 源码：

1.在扩容时如果是红黑树会执行红黑树的split方法，在这个方法之中会判断树的元素个数，如果≤6,会调用untreeify方法，取消树化，否则调用treeify方法进行树化。
2.在remove时，如果时红黑树则会调用removeTreeNode( ) 方法
判断条件时这个
if (root == null || root.right == null || (rl = root.left) == null || rl.left == null) {
            //太小了，转换为链表
            tab[index] = first.untreeify(map);
            return;
        }
	
可以看出remove时如果满足条件会退化，但是并没有≤6退化的条件。

4 索引如何计算？为什么要二次hash？数组容量为什么是2的n次幂？

1.计算对象的hashCode（），在调用HashMap的hash()方法二次hash，最后&（capacity-1）得到索引。
2.二次hash是为了综合高位数据，让hash分布更加均匀
（hash&(hash>>>16)）
3.计算索引是，如果是2的幂可以使用位与运算代替取模，速度更快；扩容时hash&oldCap==0的元素留在原来位置，否则新位置=旧位置+oldCap
4 但是 1 2 3都是基于2的n次幂做的优化，例如Hashtable的容量就不是2的N次幂，并不能说那种设计更好，这应该是设计这综合各种因素选择了使用2的n次幂作为容量。

4.1 容量不使用2的N次幂

如果追求hash分布性使用质数会更好，还不需要二次hash
如果追求效率使用2的N次幂会更好。
所以不存在那种更好，只是HashMap更侧重性能。
比如Hashtable 容量是上一次的容量*2+1（0,11,23....）

5 put流程

1.HashMap是懒惰创建数组的，首次使用才创建数组。
2.计算索引（桶下标）
3.如果桶下标还没使用，创建Node占位返回
4.如果被占用
	1.TreeNode则使用红黑树的逻辑
    2.Node，走链表添加或者更新逻辑，如果链表长度超过阈值，走树化逻辑
 5.返回前检查容量是否超过阈值，一旦超过就扩容
 	1. 先插入元素，在扩容。
 6 1.7-1.8 不同
 	1.链表插入节点时，1.7头插法 1.8尾插法
    2. 1.7是≥阈值且没有空位时才扩容，1.8是大于阈值就扩容。
    	1.7 是元素放的位置是空的就不会扩容，有元素就扩容，不管其他位置是否为空，只管放的位置是否为空。
    3.1.8在扩容计算Node索引时，会优化

6 扩容因子为什么是0.75f

空间利用率比较高，而且避免了相当多的Hash冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率。

7 多线程下的HashMap

数据错乱。
扩容死锁（1.7）

8 key是否能为null，作为key的对象有什么要求

1.HashMap的key可以为null，但Map的其他则不然
2.使用对象必须重写hashcode和equals方法且应该不可变。