哈希冲突

HashMap是一种键值对的存储数据结构，通过哈希函数把key映射到数组下标(bucket),哈希冲突就是不同的key经过哈希函数后得到相同的数组下标，因为数组有限，而key无限，所以冲突是不可避免的

HashMap常见的解决哈希冲突的方法

拉链法(Separate chaining/链地址法)

每个数组下标不直接存储单个元素，而是存储一个链表或链式结构，当key冲突时，放到这个链表中。

查找时，根据key的哈希值找到数组的下标，遍历链表，比较key是否相等

  • 优点

    • 简单易实现
    • 当冲突少时，效率很高

  • 缺点

    • 链表过长时查找效率下降(后续Java8+用红黑树替换链表提升性能)

地址开放法(Open Addressing)

所有元素都存储在数组中，没有链表。当冲突发生时，寻找数组中下一个空槽位存放元素。常用探查方式：线性探查(下一个空槽依次查找)、二次探查(查找间隔平方递增，减少群聚现象)、双哈希(用第二个哈希函数计算步长)

  • 优点

    • 节约内存，不需要链表指针

  • 缺点

    • 数组负载因子过高时，插入/查找效率下降

再哈希法

当哈希冲突严重时，通过扩容数组+重新计算哈希值，把元素分散到更大的数组里，Java中的HashMap在达到负载因子0.75时会自动扩容(容量翻倍),并将链表/红黑树元素重新哈希到新数组

Java中HashMap的冲突处理(核心机制)

链表+红黑树

  • Java8之前：链表存储冲突元素
  • Java8之后：当链表长度>8且数组长度>=64->链表转换成红黑树，查找复杂度O(logn)

负载因子与扩容

  • 默认负载因子0.75，超过就扩容并重新分布元素

哈希函数优化

  • HashMap内部对key的hashCode做扰动处理，提高冲突分散性