HashMap

java8

HashMap是键值对的容器核心常用功能是put，get方法。首先分析put方法。

put方法有一些核心逻辑，按照顺序。

1. 初始化容量，HashMap是调用put方法的时候才初始化容量。默认初始长度为16；

2. 根据key重新计算hash目的是为了更散列一些

   • 当key为null时返回的hash值为0，也就意味着空键值一定放在数组第一位；

   static final int hash(Object key) {
       int h;
       return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
   }
   

   • key本身的hashcode与他的高十六位做异或运算；

   0000 0100 1011 0011  1101 1111 1110 0001
   >>> 16 
   0000 0000 0000 0000  0000 0100 1011 0011
   ^    相同为0不同为1
   0000 0100 1011 0011   1101 1011 0101 0010
   
   由于绝大多数情况下length一般都小于2^16即小于65536。所以return h & (length-1);结果始终是h的低16位与（length-1）进行&运算，高位没有参与运算散列不好（参与的位数越多越随机），所以将h的高十六为与低十六为异或运算让hash的后16位更随机一些。
   

3. 得出hash后通过 hash & (length - 1) 求出 0~15的int值，此处不用hash%16取余是因为&运算效率高。为什么数组容量需要时2的幂次，就是因为length-1时，保证末尾二进制数全是1，然后做&运算时最大int值也不会超出数组长度。

4. 求出int值后就可以判断int指针位置是否为空了如果为空创建新节点放入对应位置。如果不为空；
   （1）先判断Node的hash是否一致，并且Node的key是否一致，如果都一致就替换v值；
   （2）如果以上不满足那么就需要增加新节点了，首先要判断当前int指针的Node节点是不是红黑树结构，如果是就通过红黑树的算法去添加新节点。
   （3）如果int指针的node节点不是红黑树，那么就是需要继续以链表的形式增加。1.8增加节点是通过尾插添加的（为什么通过尾插而不是向1.7使用头插）。因为1.8增加红黑树存储结构，当链表长度>=8-1时就需要树化，所以需要通过遍历重头到尾算出数量，顺便就在末尾追加newNode节点了。通过尾插也解决了1.7时数组扩容时迁移node时导致死循环，列外也避免了使用头插法导致的链表顺序变化。

扩容

​ resize()方法负责初始化数组容量，和扩充数组容量。也就是扩容和初始化容量都是put方法的第一件要判断的事情。

1. 扩容是2的倍数
2. 扩容后迁移node节点，链表迁移算法？红黑树迁移算法？
3. 树化算法？
4. java7头插法容易循环引用？

红黑树

​ 为什么是红黑树而不是平衡二叉树，是因为红黑树的插入效率与查找效率介于链表与平衡二叉树之间。

​ 红黑树的算法待学习.......。

HashMap1.7与1.8区别

1. 1.7链表节点增加到头节点，再向下移动引用，1.8增加到尾节点

   为什么加在为节点，因为在插入的时候会从链表头节点向后遍历数数，数到7就会树化，左右也是遍历，那么就顺便插入尾节点。

2. 1.8当链表长度为8会改为红黑树，当remove到6个节点时会转为链表

3. hash算法简化，因为1.8用红黑树之后就没有必要太散列了，但是高位也会参与计算

4. resize的逻辑修改（1.7会出现死循环，1.8不会）

5. 1.7扩容条件有两个（map容量超过了75%并且hash散列的数组位置不为空），1.8第二个条件去掉了。