稠密哈希表

密集探测哈希表（Dense Probing Hash Table）是一种哈希表实现技术，它通过在哈希表中连续探测（probing）来寻找空槽（empty slot），以便插入新的键值对。这种技术通常用于解决哈希冲突，即当两个不同的键映射到哈希表的同一个位置时。以下是密集探测哈希表的一些关键特点：基本概念

1. 哈希函数：将键转换为哈希表索引的函数。

2. 探测序列：当发生冲突时，算法按照一定的顺序（如线性探测、二次探测或双重散列）在哈希表中寻找下一个可用的槽。

3. 填充因子：哈希表中已占用槽的比例。填充因子过高会导致性能下降，因此需要适当的重新哈希（rehashing）策略。

密集探测的特点

• 连续内存分配：与链表法等其他冲突解决方法相比，密集探测通常要求哈希表在内存中是连续分配的。

• 缓存友好：由于数据在内存中是连续存储的，因此密集探测哈希表通常对CPU缓存更加友好，可以提高访问速度。

• 动态扩容：当哈希表的填充因子超过某个阈值时，需要进行扩容操作，通常是创建一个更大的哈希表，并将所有现有元素重新插入到新的哈希表中。

探测方法

• 线性探测：如果位置 h(key) 已被占用，则尝试 h(key) + 1，依此类推，直到找到空槽。

• 二次探测：使用二次函数来寻找下一个槽，例如 h(key) + i^2，其中 i 是探测的步数。

• 双重散列：使用第二个哈希函数来确定探测步长，例如 h(key) + i * h'(key)。

优点

• 较低的额外空间需求：不需要额外的指针（如链表法中的节点指针）。

• 较好的缓存性能：连续的内存布局有助于提高缓存的命中率。

缺点

• 聚集问题：线性探测可能导致聚集现象，即连续的槽被占用，这会增加探测的平均长度。

• 二次探测和双重散列更复杂：虽然它们可以减少聚集问题，但实现起来更为复杂。

应用场景密集探测哈希表适用于需要快速查找、插入和删除操作的场景，尤其是在内存使用和缓存性能方面有较高要求的场合。在 LLVM 项目中，DenseSet 和 SmallDenseSet 就是利用了密集探测哈希表的特性来实现高效的集合操作。