C++ 哈希表封装与实现原理详解

本文详细介绍了 C++ 中哈希表（Hash Table）的封装与实现原理。内容涵盖哈希函数的设计（除法散列法）、哈希冲突的产生原因及负载因子的概念。重点讲解了两种解决哈希冲突的方法：开放定址法（含线性探测、二次探测）和链地址法（拉链法）。文章提供了完整的 C++ 模板代码实现，包括初始化、插入、查找、删除及扩容策略（基于质数列表的动态扩容），并针对非数字类型（如字符串、浮点数）的哈希处理进行了特化说明。

蓝绿部署发布于 2026/3/270 浏览

哈希表封装与实现原理

**哈希(hash)**又称散列，是一种组织数据的方式。从译名来看，有散乱排列的意思。本质就是通过哈希函数把关键字 Key 跟存储位置建立一个映射关系，查找时通过这个哈希函数计算出 Key 存储的位置，进行快速查找。

哈希函数

一个好的哈希函数应该让 N 个关键字被等概率的均匀地散列分布到哈希表的 M 个空间中，但是实际中却很难做到。因此我们要尽量往这个方向去考量设计。

除法散列法

当数据比较分散的情况下，用直接定址法是无法很好地处理问题的。除法散列法也叫做除留余数法，假设哈希表的大小为 M，那么通过 key 除以 M 的余数作为映射位置的下标，也就是哈希函数为：h(key) = key % M。

哈希冲突和负载因子

当使用除法散列法时，要避免 M 为某些值，如 2 的幂、10 的幂等。如果是 2 的幂，那么 key % 2^X 本质相当于保留 key 的后 X 位，后 x 位相同的值计算出的哈希值都是一样的，就冲突了。因此当使用除法散列法时，建议 M 取不太接近 2 的整数次幂的一个质数。

负载因子：假设哈希表中已经映射存储了 N 个值，哈希表的大小为 M，M 一定要大于 N，那么负载因子 = N/M，保证负载因子小于 1。负载因子越大，说明 M 是接近于 N 的，则空间利用率越高，相对地哈希冲突的概率越高；负载因子越小，说明 M 的空间很大，则空间利用率低，相对地哈希冲突的概率越低。

处理哈希冲突

实践中哈希表一般还是选择除法散列法作为哈希函数，当然哈希表无论选择什么哈希函数也避免不了冲突，那么插入数据时，如何解决冲突呢？主要有两种方法，开放定址法和链地址法。

开放定址法

在开放定址法中所有的元素都放到哈希表里，当一个关键字 key 用哈希函数计算出的位置冲突了，则按照某种规则找到一个没有存储数据的位置进行存储，开放定址法中负载因子一定是小于 1 的。这里的规则有三种：线性探测、二次探测、双重探测。

状态表示

哈希表有三种状态表示：存在、空、删除。

enum Status { EMPTY, EXIST, DELETE };
template<class K, class V>
struct HashData {
    pair<K, V> _kv;
    Status _status = EMPTY;
};

线性探测

在映射数据的时候可能会存在哈希冲突，此时从发生冲突的位置开始，依次线性向后探测，直到寻找到下一个没有存储数据的位置为止，如果走到哈希表尾，则回绕到哈希表头的位置。

h(key) = hash0 = key % M，hash0 位置冲突了，则线性探测公式为：hc(key, i) = hashi = (hash0 + i) % M，i = {1, 2, 3, ..., M − 1}，保证线性探测时能从队尾走到队头，且因为负载因子小于 1，则最多探测 M-1 次，一定能找到一个存储 key 的位置。

可以发现线性探测的问题会占用其他值可能映射到的空间，会导致原本不冲突的值产生哈希冲突。严重的话可能会使多个 hash0，hash1，hash2，hash3 的值都争夺 hash3 位置，这种现象叫做群集/堆积。

扩容

方案一：新建一个哈希表，遍历旧表让里面的数据重新映射到新表当中；方案二：采用复用的手段将旧表数据映射到新表中。

if ((double)_n / (double)_tables.size() > 0.7) {
    HashTable<K, V, Hash> newHT(__stl_next_prime(_tables.size() + ));
     ( i = ; i < _tables.(); i++) {
         (_tables[i]._status == EXIST) {
            newHT.(_tables[i]._kv);
        }
    }
    _tables.(newHT._tables);
}

相关免费在线工具

加密/解密文本

使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。在线工具，加密/解密文本在线工具，online

Base64 字符串编码/解码

将字符串编码和解码为其 Base64 格式表示形式即可。在线工具，Base64 字符串编码/解码在线工具，online

Base64 文件转换器

将字符串、文件或图像转换为其 Base64 表示形式。在线工具，Base64 文件转换器在线工具，online

Markdown 转 HTML

将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。在线工具，Markdown 转 HTML在线工具，online

HTML 转 Markdown

将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。在线工具，HTML 转 Markdown在线工具，online

JSON 压缩

通过删除不必要的空白来缩小和压缩JSON。在线工具，JSON 压缩在线工具，online

static const int __stl_num_primes = 28; static const unsigned long __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } enum Status { EMPTY, EXIST, DELETE }; template<class K, class V> struct HashData { pair<K, V> _kv; Status _status = EMPTY; }; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { public: HashTable(size_t size = __stl_num_primes) :_tables(size), _n(0) {} bool Insert(const pair<K, V>& kv) { // 扩容 --> 负载因子大于 0.7 if ((double)_n / (double)_tables.size() > 0.7) { HashTable<K, V, Hash> newHT(__stl_next_prime(_tables.size() + 1)); for (size_t i = 0; i < _tables.size(); i++) { if (_tables[i]._status == EXIST) { newHT.Insert(_tables[i]._kv); } } _tables.swap(newHT._tables); } size_t hash0 = kv.first % _tables.size(); size_t hashi = hash0; size_t i = 1; // 如果该点存在 --> 线性探测 while (_tables[hashi]._status == EXIST) { hashi = (hashi + i) % _tables.size(); i++; } _tables[hash0]._kv = kv; _tables[hash0]._status = EXIST; ++_n; return true; } HashData<K, V>* Find(const K& key) { size_t hash0 = key % _tables.size(); size_t hash1 = hash0; size_t i = 1; while (_tables[hash1]._status != EMPTY) { if (_tables[hash1]._kv.first == key && _tables[hash1]._status != DELETE) { return &_tables[hash1]; } hash1 = (hash1 + i) % _tables.size(); ++i; } return nullptr; } bool Erase(const K& key) { HashData<K, V>* ret = Find(key); if (ret) { ret->_status = DELETE; return true; } else { return false; } } private: vector<HashData<K, V>> _tables; size_t _n; };

static const int __stl_num_primes = 28; static const unsigned long __stl_prime_list[__stl_num_primes] = { 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593, 49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469, 12582917, 25165843, 50331653, 100663319, 201326611, 402653189, 805306457, 1610612741, 3221225473, 4294967291 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } template<class K, class V> struct HashNode { pair<K, V> _kv; HashNode<K, V>* _next; HashNode(const pair<K, V>& kv) :_next(nullptr), _kv(kv) {} }; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t hash0 = 0; for (auto& ch : key) { hash0 *= 131; hash0 += ch; } return hash0; } }; template<class K, class V, class Hash = HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; public: HashTable(size_t size = __stl_next_prime(0)) :_tables(size, nullptr), _n(0) {} bool Insert(const pair<K, V>& kv) { if (Find(kv.first)) return false; Hash hs; if (_n == _tables.size()) { vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr); for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; size_t hash0 = hs(cur->_kv.first) % newtables.size(); cur->_next = newtables[hash0]; newtables[hash0] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newtables); } size_t hash0 = hs(kv.first) % _tables.size(); Node* newnode = new Node(kv); newnode->_next = _tables[hash0]; _tables[hash0] = newnode; ++_n; return true; } Node* Find(const K& key) { Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (cur->_kv.first == key) return cur; cur = cur->_next; } return nullptr; } bool Erase(const K& key) { Hash hs; size_t hash0 = hs(key) % _tables.size(); Node* prev = nullptr; Node* cur = _tables[hash0]; while (cur) { if (cur->_kv.first == key) { if (prev == nullptr) { _tables[hash0] = cur->_next; } else { prev->_next = cur->_next; } --_n; delete cur; return true; } prev = cur; cur = cur->_next; } return false; } ~HashTable() { for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _tables[i] = nullptr; } } private: vector<Node*> _tables; size_t _n; };

C++ 哈希表封装与实现原理详解

哈希表封装与实现原理

哈希函数

除法散列法

哈希冲突和负载因子

处理哈希冲突

开放定址法

状态表示

线性探测

扩容

更多推荐文章

相关免费在线工具

查找和删除

完整代码实现

链地址法

结构实现

特殊情况：插入元素不是数字

扩容

删除

完整代码实现

C++ 哈希表封装与实现原理详解

哈希表封装与实现原理

哈希函数

除法散列法

哈希冲突和负载因子

处理哈希冲突

开放定址法

状态表示

线性探测

扩容

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

查找和删除

完整代码实现

链地址法

结构实现

特殊情况：插入元素不是数字

扩容

删除

完整代码实现