Skip to main content

hash

哈希表（Hash Table）的核心挑战在于如何处理哈希冲突（即两个不同的键经过哈希函数计算后得到了同一个索引）

拉链法 (Separate Chaining)​

目前最常用的实现方式（例如 Java 的 HashMap）。 它的核心思想是：将冲突的元素存储在同一个哈希桶对应的链表（或其他数据结构）中。 实现原理：哈希表的每个“桶”位置不直接存储数据，而是存储一个指向链表的指针。 当发生冲突时，直接将新节点挂在对应索引的链表末尾。 优化：当链表过长时，为了防止查询效率退化为 O(n)， 现代实现（如 Java 8+）会将过长的链表转换为红黑树，从而将搜索复杂度降低到 O(log n)。

优点

  • 简单易行：删除操作非常简单，直接从链表中移除节点即可。
  • 容错性高：即使装载因子（Load Factor）超过 1，哈希表依然能正常工作，只是性能会下降。

缺点

  • 额外内存：需要额外的空间存储链表指针。
  • 缓存不友好：链表节点在物理内存中通常是不连续的，无法充分利用 CPU 缓存

开放寻址法 (Open Addressing)​

开放寻址法的思想是：所有的元素都存储在数组本身中。 当发生冲突时，按照某种策略探测（Probe）数组中的其他空闲位置。 常见的探测策略包括：

  1. 线性探测 (Linear Probing)：顺序检查下一个位置（索引 +1, +2...），直到找到空位。
  2. 二次探测 (Quadratic Probing)：探测间隔以二次方增长（索引 +$1^2$, +$2^2$...）。
  3. 双重哈希 (Double Hashing)：使用第二个哈希函数来计算探测步长。

优点:

  • 内存利用率高：不需要指针，数据全部存储在数组内。
  • 缓存友好：数据在内存中是连续存放的，能提高 CPU 缓存命中率。 缺点:
  • 容易堆积 (Clustering)：线性探测容易导致元素聚集在一起，造成很长的探测序列，性能急剧下降。
  • 删除复杂：不能直接物理删除元素（否则会切断后续元素的搜索路径），通常需要标记为“已删除”（Lazy Deletion）。装载因子敏感：当表快满时，性能会断崖式下跌，必须及时扩容。