跳到主要内容

哈希冲突与扩容

哈希冲突是如何产生的？​

  • 定义: 多个不同的输入对应相同的输出;
  • 原因: 哈希函数把大输入空间压到小输出空间, 之后还要对数组长度取模;
  • 必然性: 输入空间大于桶数量时, 冲突无法完全避免;

链式地址如何解决冲突？​

  • 做法: 数组的每个桶挂一个链表, 冲突的键值对挂在同一个桶的链表里;
  • 查找: 先定位桶, 再在链表中按 key 匹配;
  • 缺点: 需要额外的指针空间; 冲突严重时查询退化为链表遍历;
  • 实现见 链式地址实现哈希表;

开放寻址的线性探测如何插入、查找和删除？​

  • 思路: 所有元素都存回数组内, 冲突时按规则寻找下一个空桶;
  • 插入: 定位到已被占用的桶时, 按步长向后线性遍历, 直到找到空位;
  • 查找: 定位后向后线性遍历, 找到元素即命中, 遇到空位则说明元素不存在;
  • 删除: 不能直接置空, 必须用一个标识位表示"已删除", 否则会截断后续查找路径;

多次哈希与线性探测有什么区别？​

  • 多次哈希: 准备多个哈希函数, 出现冲突时改用下一个哈希函数;
  • 区别: 线性探测只改变位置, 多次哈希改变散列方式;

为什么哈希表需要扩容？​

  • 目的: 减少哈希冲突;
  • 原因: 元素数量接近桶数量时冲突概率上升, 链表变长, O(1) 退化;
  • 代价: 扩容需要把已有元素重新散列, 计算开销极大;

哈希扩容

负载因子如何触发扩容？​

  • 负载因子: 哈希表元素数量 / 桶数量;
  • 触发: 负载因子达到设定阈值时执行扩容;
  • 简单策略: 负载因子到达 0.75 时, 容量乘 2;
  • 实践: 尽量预留足够大的容量, 减少扩容次数;