HashMap.Key的故事:Key为什么出现Hash碰撞及冲突呢?

HashMap中出现哈希撞是由于哈希算法和数组长度之间的关系引出的。

哈希碰撞指的是当不同的键经过哈希函数计算之后得到相同的哈希值，从而导致它们在数字组中存储位置相同的情况。

以下是几个导致HashMap出现哈希撞的原因：

1、哈希算法的限制：

• 哈希计算法是将任意长的输入投影为固定长的哈希值。
• 由于输入的长度是无限的，而哈希值的长度是有限的，所以不同的输入可能会射到相同的哈希值上。

2、分组长度的限制：

• HashMap使用数组来存储键值对，通过哈希值决定元素在数组中的位置。
• 数组的长度是固定的，当哈希值超过数组长度时，就会产生撞击。
• 分组长度的选择对减少撞击的发生非常重要，过小的分组长度会增加撞击的可能性。

3、哈希奇数的设计：

• 哈希函数的设计也会影响撞击的发生。
• 一个比较差的哈希奇数可能会导致更多的撞击。
• 在设计哈希尼数时，需要考虑均衡分配和比较低的撞击率。

为了解决哈希撞的问题，HashMap使用了链接表和红黑树的数据结构来处理撞撞的情况。当发生撞撞时，新的关键值对会被添加到撞位置的链接或红黑树上。这样，在发生哈希撞击时，仍然可以高效地访问和操作按键值对。

Java 8引入了更高级别的解决方案，当链表长度超过阄值（默认为8）时，会链表转为红黑树，一步提高查找、插入和去除操作的效率。

需要注意的是，优化哈希算法和数组的长度可以减少撞击的发生，同时提高HashMap的性能和效率。

延伸阅读：

HashMap.Key的故事：什么是Hash碰撞？

HashMap 的基础结构，必须掌握！

深度！HashMap的底层数据结构