尧图网站建设 免费方案咨询
ARTICLE DETAIL

资讯详情

深耕网站建设、视觉设计与SEO优化的一线实战洞察。

首页/资讯中心/资讯详情

哈希王座：线性探测×二次探测×链式革命——冲突解决的终极博弈

发布时间：2026/10/28 9:38:35 尧图网站建设
哈希王座：线性探测×二次探测×链式革命——冲突解决的终极博弈

目录

一、哈希概念

1.1 概念

1.2 哈希冲突

1.3 直接定值法和开放定址法

1.4 负载因子

1.5 哈希函数

二、哈希表的实现

2.1 线性探测实现

2.2 二次探测实现

2.3 双重散列了解（改善堆积/聚集对查询效率的影响，不能根本解决冲突）

2.4 链地址法实现（哈希桶能够彻底解决冲突问题）

一、哈希概念

1.1 概念

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

1.2 哈希冲突

哈希冲突就是，在使用开放定址法时候是不会保证每个数据都等概率取值域的每一个值，只能是尽最大可能去接近等概率，而那些通过哈希函数计算的key存储位置被占的这种情况就是哈希冲突。

1.3 直接定值法和开放定址法

直接定址法：直接通过计数，计算每个映射关系对应的个数，常见的是通过key直接插入到数组，查询的时候也是通过key去下标访问数组（这就不会有哈希冲突问题，因为每个key都有直接对应的映射关系）。局限性：只适合范围集中的整形，如果范围太大容易浪费空间。

 开放定址法：即当哈希散列函数计算的key存储位置被占的时候，我们就会按照一个规则来存储哈希值，这是解决哈希冲突的一种方法。

散列函数一个共同性质，即函数值按同等概率取值域的每一个值，这里只能是尽可能最求等概率。（后面哈希表的实现会讲）。

1.4 负载因子

负载因子是哈希表中存储数据N/哈希表大小M的除数（小于1），负载因子是判断空间利用的情况。当然负载因子越小，哈希冲突发生的概率也就越小，相对应的查询插入效率会很高，但是空间利用率很低；当负载因子越大，哈希冲突发生的概率就越大，相对于的查询插入效率会很低，空间利用率就会很高。所以我们在选择负载因子选则0.7较好，既能减小哈希冲突的概率，还能利用好空间。

1.5 哈希函数

针对于解决哈希冲突的哈希函数（哈希冲突的无法避免的，只能是通过哈希散列函数和好的冲突处理，如二次/多重探测）

1.除留余数法

除留余数法，顾名思义就是通过取key和哈希表大小M的余数，h(key) = key % M;这能尽可能保证数据避免哈希冲突。但是对哈希表大小就有要求了，需要我们去取素数的哈希大小M，这能保证余数尽量不一样，否则可能冲突概率会很大。

2. 乘法散列法

3全域散列法

二、哈希表的实现

2.1 线性探测实现

当我们遇到h(key) = hash0 = key % M(哈希表总大小)计算后的值出现哈希冲突时,我们通过对hash0 = (hash0+i) % M再对hash0取模来规律计算可替代的位置（i不断++）。缺点就是可能会导致堆积（就是出现哈希冲突的key占据了别人的哈希计算的值，然后不断影响后面的值），这会导致查询和插入的效率大幅度减低。

#include<iostream> #include<vector> using namespace std; //列举状态 enum Status { EMPTY, EXIT, DELTE }; //将key转换为数字方便除留计算 template<class K> struct Keynum { size_t operator()(const K& key) { return size_t(key); } }; //全特化考虑所有情况 template<> struct Keynum<string> { size_t operator()(const string& str) { size_t hash = 0; for (auto& e : str) { hash += (size_t)e; hash *= 131; } return hash; } }; //存储哈希表数据的类 template<class K,class V> struct HashData { pair<K, V> _kv;//哈希数据 Status _status = EMPTY; //初始化 HashData() { } }; //哈希桶 template<class K,class V,class HashNum = Keynum<K>> class HashTable { typedef HashData<K, V> Data; public: //初始化 HashTable() :_table(__stl_next_prime(1)) { } inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. 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 }; 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; } //插入(线性探测的除留余数法) bool insert(const pair<K, V>& kv) { if(_n / _table.size() >= 0.7)//设置负载因子为0.7 { HashTable newhash; newhash._table.resize(__stl_next_prime(_table.size() + 1));//扩容（素数） for (auto& data : _table) { if(data._status == EXIT)//优化 newhash.insert(data._kv);//复用自己代码（这里因为扩容了，不可能达到负载因子） } _table.swap(newhash._table);//交换_table即可，这里的复用是用的newhash._table，newhash是一个局部对象所以需要交换 } HashNum Num; size_t hash0 = Num(kv.first) % _table.size();//记录初始计算值 size_t hashi = hash0;//用于解决哈希冲突值，方便回到hash0 size_t i = 1; //判断是否哈希冲突(线性探测) while (_table[hashi]._status == EXIT) { hashi = (hashi + i) % _table.size(); ++i; } //_table[hashi]._status == DELTE/EMPTY _table[hashi]._kv = kv; _table[hashi]._status = EXIT; ++_n; return true; } //寻找 Data* Find(const K& key) { HashNum Num; size_t hash0 = Num(key) % _table.size(); size_t hashi = hash0; size_t i = 1; //探测 while (_table[hashi]._status != EMPTY)//这里有可能是哈希冲突并且已经删除了，所以这不能直接用存在判断 { //判断值是否相同 if (_table[hashi]._status == EXIT && _table[hashi]._kv.first == key) return &_table[hashi]; //继续探测 hashi = (hashi + i) % _table.size(); ++i; } return nullptr;//没找到 } //删除 bool Erase(const K& key) { HashNum Num; size_t hash0 = Num(key) % _table.size(); size_t hashi = hash0; size_t i = 0; //探测 while (_table[hashi]._status != EMPTY) { //先寻找到 if (_table[hashi]._status == EXIT && _table[hashi]._kv.first == key) { //再删除 _table[hashi]._status = DELTE; --_n; return true; } hashi = (hashi + i) % _table.size(); ++i; } return false; //Data* find = Find(key); //if (find) //{ // find->_status = DELTE; // --_nl; // return true; //} //else //{ // return false; //} } private: vector<Data> _table; size_t _n = 0; };

2.2 二次探测实现

对于二次探测和线性探测大差不差，只是在应对冲突的时候进行指的运算然后进行左右探测，hash0 = key % M计算后状态为EXIT就需要进行二次平方左右探测，也就是hash 0 = (hash0+/-)%M，这个是为了改善线性探测中的堆积问题，呈现减少探测时候堆积问题。

#pragma once #include<iostream> #include<vector> using namespace std; //列举状态 enum Status { EMPTY, EXIT, DELTE }; //将key转换为数字方便除留计算 template<class K> struct Keynum { size_t operator()(const K& key) { return size_t(key); } }; //全特化考虑所有情况 template<> struct Keynum<string> { size_t operator()(const string& str) { size_t hash = 0; for (auto& e : str) { hash += (size_t)e; hash *= 131; } return hash; } }; //存储哈希表数据的类 template<class K, class V> struct HashData { pair<K, V> _kv;//哈希数据 Status _status = EMPTY; //初始化 HashData() {} }; //哈希桶 template<class K, class V, class HashNum = Keynum<K>> class HashTable { typedef HashData<K, V> Data; public: //初始化 HashTable() :_table(__stl_next_prime(1)) { } inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. 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 }; 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; } //插入(线性探测的除留余数法) bool insert(const pair<K, V>& kv) { if (_n / (double)_table.size() >= 0.7)//设置负载因子为0.7 { HashTable newhash; newhash._table.resize(__stl_next_prime(_table.size() + 1));//扩容（素数） for (auto& data : _table) { if (data._status == EXIT)//优化 newhash.insert(data._kv);//复用自己代码（这里因为扩容了，不可能达到负载因子） } _table.swap(newhash._table);//交换_table即可，这里的复用是用的newhash._table，newhash是一个局部对象所以需要交换 } HashNum Num; size_t hash0 = Num(kv.first) % _table.size();//记录初始计算值 size_t hashi = hash0;//用于解决哈希冲突值，方便回到hash0 size_t i = 1; size_t flag = 0; //判断是否哈希冲突(线性探测) while (_table[hashi]._status == EXIT) { if (flag == 0) { hashi = (hash0 - i * i) % _table.size(); flag = 1; if (hashi < 0) hashi += _table.size(); continue; } else { hashi = (hash0 + i * i) % _table.size(); flag = 0; } ++i; } //_table[hashi]._status == DELTE/EMPTY _table[hashi]._kv = kv; _table[hashi]._status = EXIT; ++_n; return true; } //寻找 Data* Find(const K& key) { HashNum Num; size_t hash0 = Num(key) % _table.size(); size_t hashi = hash0; size_t i = 1; size_t flag = 0; //探测 while (_table[hashi]._status != EMPTY)//这里有可能是哈希冲突并且已经删除了，所以这不能直接用存在判断 { //判断值是否相同 if (hashi < 0) hashi += _table.size(); if (_table[hashi]._status == EXIT && _table[hashi]._kv.first == key) return &_table[hashi]; //继续探测 if(flag == 0) { hashi = (hash0 - i * i) % _table.size(); flag = 1; if (hashi < 0) hashi += _table.size(); continue; } else { hashi = (hash0 + i * i) % _table.size(); flag = 0; } if (hashi == hash0) break; ++i; } return nullptr;//没找到 } //删除 bool Erase(const K& key) { HashNum Num; size_t hash0 = Num(key) % _table.size(); size_t hashi = hash0; size_t i = 1; size_t flag = 0; //探测 while (_table[hashi]._status != EMPTY) { //先寻找到 if (_table[hashi]._status == EXIT && _table[hashi]._kv.first == key) { //再删除 _table[hashi]._status = DELTE; --_n; return true; } //左右切换 if(flag == 0) { hashi = (hash0 - i * i) % _table.size(); flag = 1; if (hashi < 0) hashi += _table.size(); continue; } else { hashi = (hash0 + i * i) % _table.size(); flag = 0; } //防止死循环 if (hashi == hash0) break; ++i; } return false; } private: vector<Data> _table; size_t _n = 0; };

2.3 双重散列了解（改善堆积/聚集对查询效率的影响，不能根本解决冲突）

2.4 链地址法实现（哈希桶能够彻底解决冲突问题）

 解决散列法中出现冲突问题有线性探测法，多重散列法，链地址法（一般来说链地址法会更好一点)。链地址法就是通过一串指针数组再结合链表，把哈希冲突的值去连接在一起，避免了哈希冲突/堆积问题，还能很好的节约空间，此时负载因子可以为1；查询也很简单先计算哈希值，然后再遍历链表来查询（一般只有在此链表结点超过8个，才使用红黑树来提高效率）。

#pragma once #include<iostream> #include<vector> using namespace std; //哈希结点 template<class K,class V> struct HashData { pair<K, V> _kv; ///哈希数据 HashData<K, V>* _next;//实现链表 //初始化 HashData(const pair<K,V> kv) :_next(nullptr) ,_kv(kv) { } }; //将key转换为数字用于计算 template<class K> struct KeyNum { size_t operator()(const K& key) { return (size_t)key; } }; //全特化 template<> struct KeyNum<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto& data : key) { hash += data; hash *= 131; } return hash; } }; template<class K,class V,class Num = KeyNum<K>> class HashTable { typedef HashData<K, V> Node; public: inline unsigned long __stl_next_prime(unsigned long 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 }; 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; } //初始化 HashTable() :_table(11,nullptr) ,_n(0) { } //析构 ~HashTable() { for (auto& data : _table) { Node* cur = data; while (cur) { Node* next = cur->_next; delete cur; cur = next; } cur = nullptr; } } //插入 bool insert(const pair<K,V>& kv) { //存在不插入 if (Find(kv.first)) return false; Num num; //负载因子为1，扩容 if(_n == _table.size()) { vector<Node*> table(__stl_next_prime(_table.size()+1)); for (auto& data : _table) { Node* cur = data; while (cur) { Node* next = cur->_next;//衔接下一个结点 size_t hashi = num(cur->_kv.first) % table.size(); //cur->_next --- table[hashi] cur->_next = table[hashi]; //table[hashi] --- cur 头结点变为cur table[hashi] = cur; cur = next; } //再清除置空 data = nullptr; } _table.swap(table); } size_t hashi = num(kv.first) % _table.size();//除留余数法 Node* newnode = new Node(kv); //头插 //newnode->next ---- _table[hashi] newnode->_next = _table[hashi]; //_table[hashi] ---- newnode,头结点取代newnode _table[hashi] = newnode; ++_n; return true; } //查找 Node* Find(const K& key) { //防止出现未定义行为%0会出现未定义 if (_table.empty()) return nullptr; Num num; size_t hashi = num(key) % _table.size(); Node* cur = _table[hashi]; while(cur) { if (cur->_kv.first == key) return cur; cur = cur->_next; } return nullptr; } //删除 bool Erase(const K& key) { //防御未定义 if (_table.empty()) return false; Num num; size_t hashi = num(key) % _table.size(); Node* cur = _table[hashi]; Node* prev = nullptr; while (cur) { if(cur->_kv.first == key) { //判断是否为头结点 if (prev == nullptr) _table[hashi] = cur->_next; else prev->_next = cur->_next; --_n; delete cur; cur = nullptr; return true; } prev = cur; cur = cur->_next; } return false; } private: vector<Node*> _table; //指针数组 size_t _n; //计算哈希个数 };
网站建设 视觉设计 SEO优化
返回列表