哈希王座：线性探测×二次探测×链式革命——冲突解决的终极博弈-恒创新域建站

★ FEATURED ARTICLE

目录一、哈希概念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 (hash0i) % M再对hash0取模来规律计算可替代的位置i不断。缺点就是可能会导致堆积就是出现哈希冲突的key占据了别人的哈希计算的值然后不断影响后面的值这会导致查询和插入的效率大幅度减低。#includeiostream #includevector using namespace std; //列举状态 enum Status { EMPTY, EXIT, DELTE }; //将key转换为数字方便除留计算 templateclass K struct Keynum { size_t operator()(const K key) { return size_t(key); } }; //全特化考虑所有情况 template struct Keynumstring { size_t operator()(const string str) { size_t hash 0; for (auto e : str) { hash (size_t)e; hash * 131; } return hash; } }; //存储哈希表数据的类 templateclass K,class V struct HashData { pairK, V _kv;//哈希数据 Status _status EMPTY; //初始化 HashData() { } }; //哈希桶 templateclass K,class V,class HashNum KeynumK class HashTable { typedef HashDataK, 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 pairK, 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._tablenewhash是一个局部对象所以需要交换 } 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: vectorData _table; size_t _n 0; };2.2 二次探测实现对于二次探测和线性探测大差不差只是在应对冲突的时候进行指的运算然后进行左右探测hash0 key % M计算后状态为EXIT就需要进行二次平方左右探测也就是hash 0 (hash0/-)%M这个是为了改善线性探测中的堆积问题呈现减少探测时候堆积问题。#pragma once #includeiostream #includevector using namespace std; //列举状态 enum Status { EMPTY, EXIT, DELTE }; //将key转换为数字方便除留计算 templateclass K struct Keynum { size_t operator()(const K key) { return size_t(key); } }; //全特化考虑所有情况 template struct Keynumstring { size_t operator()(const string str) { size_t hash 0; for (auto e : str) { hash (size_t)e; hash * 131; } return hash; } }; //存储哈希表数据的类 templateclass K, class V struct HashData { pairK, V _kv;//哈希数据 Status _status EMPTY; //初始化 HashData() {} }; //哈希桶 templateclass K, class V, class HashNum KeynumK class HashTable { typedef HashDataK, 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 pairK, 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._tablenewhash是一个局部对象所以需要交换 } 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: vectorData _table; size_t _n 0; };2.3 双重散列了解改善堆积/聚集对查询效率的影响不能根本解决冲突2.4 链地址法实现哈希桶能够彻底解决冲突问题解决散列法中出现冲突问题有线性探测法多重散列法链地址法一般来说链地址法会更好一点)。链地址法就是通过一串指针数组再结合链表把哈希冲突的值去连接在一起避免了哈希冲突/堆积问题还能很好的节约空间此时负载因子可以为1查询也很简单先计算哈希值然后再遍历链表来查询一般只有在此链表结点超过8个才使用红黑树来提高效率。#pragma once #includeiostream #includevector using namespace std; //哈希结点 templateclass K,class V struct HashData { pairK, V _kv; ///哈希数据 HashDataK, V* _next;//实现链表 //初始化 HashData(const pairK,V kv) :_next(nullptr) ,_kv(kv) { } }; //将key转换为数字用于计算 templateclass K struct KeyNum { size_t operator()(const K key) { return (size_t)key; } }; //全特化 template struct KeyNumstring { size_t operator()(const string key) { size_t hash 0; for (auto data : key) { hash data; hash * 131; } return hash; } }; templateclass K,class V,class Num KeyNumK class HashTable { typedef HashDataK, 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 pairK,V kv) { //存在不插入 if (Find(kv.first)) return false; Num num; //负载因子为1扩容 if(_n _table.size()) { vectorNode* 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: vectorNode* _table; //指针数组 size_t _n; //计算哈希个数 };

阅读完成 · 觉得有帮助？

咨询建站