系统学习HashMap

HashMap的底层结构

HashMap的底层数据结构是哈希表
哈希表也称散列表。可以理解为一个数组，基于哈希算法得到元素的哈希值，基于哈希值对数组长度取余得到元素在数组的下标，实现O(1)时间复杂度的增删查效率
这种方式在哈希算法不能保证绝对散列时，会存在哈希冲突

哈希冲突：作为key的两个不同对象在put时，经过哈希算法得到的哈希值对数组长度取余后结果相同，即在哈希表的位置相同。
因为最后用哈希值对数组长度取余，所以两个不同对象发生哈希冲突的概率还是比较大的，尽管两个对象的哈希值一般情况下不相同

解决哈希冲突有两种方式：

• 开放定址法。就是继续寻找下一块未被占用的存储地址
• 链地址法。数组+链表的结构来解决哈希冲突

链地址法是如何解决哈希冲突的？
HashMap使用链地址法解决哈希冲突，将冲突的元素追加到链表尾部。基于Key查询value时，尽管产生了哈希冲突，也会遍历链表，找到真正的key（哈希值相等且equals为true或对象相等）对应的value

所以HashMap的底层结构可以总结为：采用链地址法解决哈希冲突的哈希表

实现细节

• HashMap的无参实例化并没有初始化数组，而是在put的时候进行，初始化默认数组长度为16，默认阈值因子为0.75
• HashMap数组长度一定是二次幂
• HashMap使用的哈希算法：取key的hashCode，对高十六位和低十六位做异或运算作为新的低十六位，加大低十六位的随机性
  • (h = key.hashCode()) ^ (h >>> 16)
• HashMap计算key对应数组下标的算法：哈希值对(数组长度-1)做与运算
  • 因为数组长度是二次幂，所以”对(数组长度-1)做与运算 === 对数组长度取模”
• put时，如果发生哈希冲突，且key的equals方法也为true或对象严格等，则认为是同一个对象，会updateValue，并返回oldValue。否则认为是两个不同key对象，用链地址法将新Entry加到链表尾部
• get时，先通过计算哈希值并对数组长度取余得到下标，取出entry链表并遍历，当哈希值相同且对象严格等或equals为true，则取出entry.value，否则返回null
• 当map里元素数目超过阈值（默认16*0.75）时进行扩容
  • 当元素数目超过64，会使用红黑树替代链表（Java8新增）
  • 扩容后，rehash的策略是：对所有在哈希表里存储的Entry对象（包括在链表上的每个Entry对象）重新计算下标：(Entry.key.hash & 新数组长度-1），因此之前在链表里的元素可能会移动到扩容后的新空间，链表长度缩短，提高空间利用率和查询效率

参考资料：

https://blog.csdn.net/qq_38182963/article/details/78942764
https://blog.csdn.net/cnm10050/article/details/105082209