1. 开放寻址法实现要点
1.1 基本思想
在开放寻址法中，哈希表只使用一个连续的数组来存放键值对，当发生冲突时通过探测序列寻找下一个空槽，避免了额外的指针开销。随着装填因子增加，缓存友好性下降，因此合理的负载因子对性能至关重要。
为了提升缓存局部性，哈希函数应尽可能产生均匀分布，避免冲突聚集，并且在实现中尽量简化探测路径。下面给出一个简化的思想示例。
1.2 探测策略
线性探测在实现上简单，遍历顺序是线性的，但当负载因子较高时会产生主聚簇的问题。二次探测和双重哈希可以缓解此问题，降低冲突聚集，但实现要保持简洁和高效。
template<typename K, typename V>
struct OpenAddressSlot {K key;V value;bool occupied;
};template<typename K, typename V>
class OpenAddressHash {
public:OpenAddressHash(size_t capacity=16) : cap(capacity), size_(0) {data = new OpenAddressSlot< K, V>[cap];for (size_t i=0; i< cap; ++i) data[i].occupied = false;}// 简易的哈希size_t h(const K& key) const { return std::hash< K >{}(key) & (cap-1); }bool put(const K& key, const V& val) {if (size_ * 2 >= cap) rehash(cap*2);size_t idx = h(key);for (size_t i=0; i<cap; ++i) {size_t pos = (idx + i) & (cap-1);if (!data[pos].occupied || data[pos].key == key) {data[pos].key = key;data[pos].value = val;data[pos].occupied = true;++size_;return true;}}return false;}// ...
private:OpenAddressSlot< K, V>* data;size_t cap;size_t size_;void rehash(size_t newCap) { /* 省略实现，关键是重新分配并拷贝 */ }
};
1.3 删除处理与再哈希
在开放寻址法中，直接删除会导致探测路径破坏，因此需要引入墓碑（tombstone）标记或采用重新组织策略。有效的实现通常会在删除时标记为墓碑，并在后续插入/查找时清理或触发再哈希。
墓碑策略的核心在于保持查找路径的正确性，避免误判为未分配槽。合理的再哈希触发条件可以在达到一定比例时进行整表再哈希，确保性能稳定。
2. 链地址法实现要点
2.1 基本思想
链地址法通过使用一个数组的每个槽存放一个指向链表头的指针，同一槽位的冲突通过链表串联解决，避免了搬迁整个表。此法的内存分配通常更灵活，扩容时不需要对所有元素重新哈希，只是简单地重新分配桶并将现有链表链接到新桶上。
在实现中，常见的数据结构是 vector<vector<pair<K,V>>> 或 vector<std::list<std::pair<K,V>>>。需要注意避免过度分配导致内存碎片，另外，哈希冲突的统计信息对调优有帮助。
template<typename K, typename V, typename Hash=std::hash< K >>
class ChainingHash {
public:explicit ChainingHash(size_t buckets = 16) : buckets_(buckets), size_(0) {table_.resize(buckets_);}size_t h(const K& key) const { return Hash{}(key) % buckets_; }void put(const K& key, const V& val) {size_t idx = h(key);for (auto &p : table_[idx]) {if (p.first == key) { p.second = val; return; }}table_[idx].emplace_back(key, val);++size_;// 省略扩容策略}bool get(const K& key, V& out) const {size_t idx = h(key);for (const auto &p : table_[idx]) {if (p.first == key) { out = p.second; return true; }}return false;}
private:std::vector>> table_;size_t buckets_;size_t size_;
};
3. 性能对比与优化
3.1 性能指标与测试要点
要点：吞吐量、查找/插入延迟、缓存命中率和内存占用密切相关，实验中应尽量控制外部变量，使用固定种子哈希函数以获得可重复性。
通过对比开放寻址法和链地址法在不同负载因子下的表现，可以观察到 在低负载下两者接近，而在高负载时开放寻址法对缓存的依赖更强，而链地址法的内存碎片更明显。
#include <chrono>
#include <iostream>
#include <vector>template<typename HashTable>
double benchmarkHash(HashTable& ht, int ops) {using namespace std::chrono;auto t0 = high_resolution_clock::now();for (int i = 0; i < ops; ++i) {ht.put(i, i*2);volatile int sink = ht.get(i);(void)sink;}auto t1 = high_resolution_clock::now();duration<double> d = t1 - t0;return d.count() / ops;
}
3.2 缓存友好性与扩容成本
开放寻址法的数据局部性较好，当探测序列连续时，缓存行命中率可能更高，但若需要扩容，重新分配成本较高。链地址法则在扩容时局部性较弱，但对并发友好度更高，尤其是分段锁策略可降低锁粒度。
4. 设计考虑与最佳实践
4.1 哈希函数设计
选择强哈希函数和良好的桶数量是性能的关键之一。避免简单模运算带来的分布偏斜，优先使用32/64位混合哈希，并确保容量为2的幂在开放寻址法中可简化探测。
为了提升可预测性，应在实现中提供可配置的哈希策略，并对不同数据分布进行基准测试，以选择最适合的方案。
4.2 并发与锁策略
在多线程场景中，分段锁和无锁化的读写路径可以显著提升并发吞吐，但实现复杂度会增加。对开放寻址法，并发写入需要更细的原子性保障或链式结构替代，对链地址法则更容易实现粒度锁。
在实际系统中，可以结合以下做法提升并发性：对读写分离路径采用无锁读取、短路多路访问，以及对写入阶段采用分段重哈希/分段扩容，以降低锁竞争并提升吞吐。
