HashMap关键知识点总结

数据结构：

数组 + 列表 / 红黑树

时间复杂度：

理想情况是没有哈希碰撞，在没有哈希碰撞的情况下，时间复杂度为1

哈希算法优化：

(h = key.hashCode()) ^ h >>> 16

因为大多数情况下，hashmap的数组的容量不会超过2的16次方，所以导致高16位不会被用到，所以哈希算法优化的方式是：将高16位与低16位进行异或运算，这样大大增加了低16位的散列特性，从而减少了哈希冲突的可能。

寻址优化：  

(n-1) & hash

其中n为2的若干次方（数组每次扩容都默认扩大为原来的2倍），因为这样的原因，所以可以直接通过 & 位运算来取模；同时在每次扩容之后，可以保证一半的数据不需要进行迁移。

哈希碰撞：

所谓的哈希碰撞就是说两个key计算出的哈希值相同了，这时后放进来的会挂在前一个放进来的后面，形成列表（时间复杂度为n），通过next指针去关联下一个；当列表长度达到阈值后，列表转化为红黑树（时间复杂度为log2n）。