HashMap

设计考虑点：

降低碰撞概率；

提高空间利用率；

提高查询概率

• 初始容量 ：16

• 负载因子 默认 0.75
  扩容：add的时候判断数组个数和阈值比较，如果满足负载因子，JDK1.7还要判断此时元素对应的桶是否是空的，如果是空的则无需进行扩容；不空则创建2倍于原来的数组并对元素重新rehash.

• Rehash: 是否所有元素都重新计算索引值？
  JDK1.7中rehash的时候，旧链表迁移新链表的时候，如果在新表的数组索引位置相同，则链表元素会倒置;
  JDK1.8不会倒置，经过rehash之后，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。

  
  image.png
  

  因此1.8在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap(原来的长度)”

• key.hash()计算方法：
  h ^ (h<<16)
  h:32位整数，上述计算保留所有位数的信息，降低冲突概率

• index计算方法：
  hash & (length - 1) 位运算效率高

• 冲突：
  链表 头插法，新插入的元素在链表头部

• 查询时间复杂度：先hash确定桶的位置，再equals确定最终元素位置
  无冲突，相当于数组中查找，hash值--- 索引 O(1)
  有冲突，且桶里元素不超过8，即在链表中查 O(1) + O(n)
  有冲突，且桶里元素不超过8，即在红黑树中查 O(1) + O(logn)

参考：https://blog.csdn.net/qq_27093465/article/details/52270519