知识复习汇总

数据结构

哈希相关

• 简单介绍一下哈希表？
  • 哈希表是一种根据键（Key）直接计算出存储位置的数据结构。能够通过哈希函数 (Hash Function) 把键映射到一个数组的索引上，从而实现快速的增删查改操作。
• 什么是解决哈希冲突？
  • 哈希表用哈希函数把键映射到桶（数组槽位）。不同键可能落到同一桶，这就是冲突。冲突不可避免，核心是：怎么在冲突出现时，仍保持增删查改接近 O (1) 的开销。
• 如何解决哈希冲突？
  • 1、拉链法：每个桶保存一个“容器”（通常是链表、动态小数组或小型平衡树）。冲突的元素都挂到该桶的容器里。
  • 2、线性探测法：在哈希表中，如果某个键经过哈希函数映射得到的槽位（bucket）已被占用，就按照一个固定的探测序列去找下一个空槽。
  • 3、二次探测法：发生冲突时，它不像线性探测法一样一步步顺序探测，而是按照二次方步长往外扩展。
  • 4、双重散列：当发生冲突时，不是固定加 1（线性探测），也不是平方步长（二次探测），而是用“第二个哈希函数”决定探测步长。
• 如果用散列链表解决哈希冲突，那么查找时间复杂度会变成 $O(n)$ ，如何下降时间复杂度？
  • 1、控制负载因子：让期望复杂度回到 $O(1)$，负载因子 α = 元素数/桶数，当 α 逼近设定阈值的时候就扩容➕重新哈希
  • 2、优化哈希函数：降低冲突几率
  • 3、桶内结构升级：把链表换成平衡树