好的模板网站,哈尔滨营销网站建设公司哪家好,蜀都网站建设舜王,内蒙古建设工程社保中心网站哈希表介绍、实现与封装 一、哈希概念二、哈希表实现直接定址法其他映射方法介绍1. 哈希冲突2. 负载因子3. 将关键字转为整数4. 设计哈希函数除法散列法 / 除留余数法乘法散列法全域散列法其他方法 将关键字转为整数处理哈希冲突开放定址法线性探测二次探测双重散列 开放定址法… 哈希表介绍、实现与封装 一、哈希概念二、哈希表实现直接定址法其他映射方法介绍1. 哈希冲突2. 负载因子3. 将关键字转为整数4. 设计哈希函数除法散列法 / 除留余数法乘法散列法全域散列法其他方法 将关键字转为整数处理哈希冲突开放定址法线性探测二次探测双重散列 开放定址法的哈希表结构解决冲突的思路扩容 开放定址法代码实现链地址法解决冲突的思路扩容极端场景 链地址法代码实现 三、链地址法哈希表封装HashTable_basekey 复用key / value 复用源码展示 以下代码环境为 VS2022 C。
一、哈希概念
哈希(hash) 又称散列是一种组织数据的方式。从译名来看有散乱排列的意思。本质就是通过哈希函数把关键字 key 跟存储位置建立一个映射关系查找时通过这个哈希函数计算出 key 存储的位置进行快速查找。
二、哈希表实现
直接定址法
当关键字的范围比较集中时直接定址法是非常简单高效的方法比如一组关键字都在 [ 0 , 99 ] 之间那么我们开一个 100 个数的数组每个关键字的值直接就是存储位置的下标。再比如一组关键字的值都在 [ a , z ] 的小写字母我们开一个 26 个数的数组每个关键字的ACSII码 - 小写字母a的ACSII码 就是存储位置的下标。
也就是说直接定址法本质是用关键字计算出一个绝对位置或者相对位置。
void test1()
{int nums[100] { 0 }; // 直接定址法int arr[10] { 2, 93, 38, 56, 51, 22, 88, 38, 56, 31 };for (int i 0; i 10; i){nums[arr[i]]; // 统计}for (int i 0; i 100; i){if (nums[i] 1) // 排序打印{cout i ;}}cout endl;
}void test2()
{string str abcdefggaaecea;int count[26] { 0 };for (char ch : str){count[ch - a]; // ch - a 相对位置}for (int i 0; i 26; i){if (count[i] 0) // 统计字母出现次数{cout (char)(i a) : count[i] endl;}}cout endl;
}直接定址法的缺点也非常明显当关键字的范围比较分散时很浪费内存甚至内存不够用。
其他映射方法介绍
假设我们只有数据范围是 [ 0 , 9999 ] 的 N 个值我们要映射到一个 M 个空间的数组中(一般情况下 M N)那么就要借助哈希函数(hash function) hf将关键字 key 映射到数组的 hf(key) 位置要注意的是 hf(key) 计算出的值必须在 [ 0 , M ) 之间。 1. 哈希冲突
上述存在一个问题两个不同的 key 可能会映射到同一个位置去这种问题我们叫做哈希冲突或者哈希碰撞。理想情况是找出一个好的哈希函数避免冲突但在实际场景中冲突是不可避免的所以我们需要尽可能设计出优秀的哈希函数减少冲突次数的同时也要去设计出解决冲突的方案。
2. 负载因子
假设哈希表中已经映射存储了 N 个值哈希表的大小为 M那么 负载因子 N / M负载因子有些地方也翻译为 载荷因子 或 装载因子 等他的英文为 load factor。负载因子越大哈希冲突的概率越高空间利用率越高负载因子越小哈希冲突的概率越低空间利用率越低。
3. 将关键字转为整数
我们将关键字映射到数组中的位置一般是使用整数做映射计算如果不是整数需要转换成整数这个细节我们后面代码实现中再进行细节展示。
4. 设计哈希函数
一个好的哈希函数应该让 N 个关键字被等概率均匀的散列分布到哈希表的 M 个空间中但实际中却很难做到我们需要尽量往这个方向去设计。
除法散列法 / 除留余数法 除法散列法也叫做除留余数法顾名思义假设哈希表的大小为 M那么通过 key 除以 M 的余数作为映射位置的下标也就是哈希函数为hf(key) key % M。 当使用除法散列法时要尽量避免 M 为某些值如 2 的幂10 的幂等。如果是 2 ^ x那么 key % 2 ^ x 本质相当于保留 key 的后 x 位后 x 位相同的值计算出的哈希值都是一样的就冲突了。如{ 63 , 31 } 看起来没有关联的值如果 M 是 16也就是 2 ^ 4那么计算出的哈希值都是 15因为 63 的二进制后 8 位是 0011111131 的二进制后 8 位是 00011111。如果是 10 ^ x就更明显了保留的都是 10 进值的后 x 位如{ 112, 12312 }如果 M 是 100也就是 10 ^ 2那么计算出的哈希值都是 12。 当使用除法散列法时建议 M 取不太接近 2 的整数次幂的一个质数(素数)。
需要说明的是有一种做法很巧妙Java 的 HashMap 采用除法散列法时就是 2 的整数次幂做哈希表的大小 M这种做法不用取模可以直接位运算相比于取模位运算更高效一些。但这不是单纯的去位运算比如 M 是 2 ^ 16 次方本质是取后 16 位那么用 key’ key 16然后把 key 和 key’ 异或的结果作为哈希值。也就是说我们映射出的值还是在 [ 0 , M ) 范围内但尽量让 key 所有的位都参与计算这样映射出的哈希值更均匀一些即可。
乘法散列法 乘法散列法对哈希表大小 M 没有要求它的大思路第一步用关键字 K 乘上常数 A (0 A 1)并抽取出 k * A 的小数部分。第二步后再用 M 乘以 k * A 的小数部分再向下取整。 hf(key) floor(M × ( (A × key) % 1.0 ) )其中 floor 表示对表达式进行下取整A∈(0 , 1)这里最重要的是 A 的值应该如何设定Knuth 认为 A 0.6180339887…(黄金分割点) 比较好。 乘法散列法对哈希表大小 M 是没有要求的假设 M 为 1024key 为 1234A 0.6180339887A * key 762.6539420558取小数部分为 0.6539420558M × ( ( A × key ) % 1.0 ) 0.6539420558 * 1024 669.6366651392那么 hf(1234) 669。
全域散列法 如果存在一个恶意的对手他针对我们提供的散列函数特意构造出一个发生严重冲突的数据集。比如让所有关键字全部落入同一个位置中这种情况是可能存在的只要散列函数是公开且确定的就可以实现此攻击。解决方法自然是见招拆招给散列函数增加随机性攻击者就无法找出确定可以导致最坏情况的数据。这种方法叫做全域散列。 hf(key) ( ( a × key b ) % P ) % MP 需要选一个足够大的质数a 可以随机选 [ 1 , P - 1 ] 之间的任意整数b 可以随机选 [ 0 , P - 1 ] 之间的任意整数这些函数构成了一个 P * ( P - 1 ) 组全域散列函数组。假设 P 17M 6a 3 b 4, 则 hf(8) ( ( 3 × 8 4 ) % 17 ) % 6 5 需要注意每次初始化哈希表时随机选取全域散列函数组中的一个散列函数使用后续增删查改都固定使用这个散列函数否则每次哈希都是随机选一个散列函数插入是一个散列函数查找又是另一个散列函数会导致找不到插入的 key。
其他方法
哈希函数采用的方法还有平方取中法、折叠法、随机数法、数学分析法等这些方法相对更适用于一些局限的特定场景这里不过多介绍。
将关键字转为整数
当 key 是 string 等类型时key 不能取模那么我们需要给 HashTable 增加一个仿函数这个仿函数支持把 key 转换成一个可以取模的整形如果 key 可以转换为整形并且不容易冲突那么这个仿函数就用默认参数即可如果这个 key 不能转换为整形我们就需要自己实现一个仿函数传给这个参数实现这个仿函数的要求是尽量让 key 的每个值都参与到计算中让不同的 key 转换出的整形值不同。string 做哈希表的 key 非常常见所以我们可以考虑把 string 特化一下。 typedef unsigned int Hash_mapping;templateclass Keystruct defaultHashFunc{Hash_mapping operator()(const Key key) const{return key; // 隐式类型转换}};template // 特化struct defaultHashFuncstd::string {Hash_mapping operator()(const std::string key) const{Hash_mapping the_map 0;for (char ch : key) // 将每个字符都参与映射{the_map ch; the_map * 131;}return the_map;}};处理哈希冲突
实践中哈希表一般是选择除法散列法作为哈希函数下面使用的哈希函数都是除法散列法。当然哈希表无论选择哪种哈希函数也避免不了冲突。插入数据时解决冲突主要有两种方法开放定址法和链地址法。
开放定址法
在开放定址法中所有的元素都放到哈希表里当一个关键字 key 用哈希函数计算出的位置冲突了则按照某种规则找到一个没有存储数据的位置进行存储开放定址法中负载因子一定是小于的。这里介绍三种规则线性探测、二次探测、双重探测。
线性探测 从发生冲突的位置开始依次线性向后探测直到寻找到下一个没有存储数据的位置为止如果走到哈希表尾则回绕到哈希表头的位置。 hf(key) hash0 key % M, hash0 位置冲突了则线性探测公式为hc(key , i) hashi (hash0 i) % M i {1, 2, 3, …, M − 1}因为负载因子小于1则最多探测 M - 1 次一定能找到一个存储 key 的位置。 线性探测比较简单且容易实现线性探测的问题假设hash0 位置连续冲突hash0hash1hash2 位置已经存储数据了后续映射到 hash0hash1hash2hash3 的值都会争夺 hash3 位置这种现象叫做群集 / 堆积。下面的二次探测可以一定程度改善这个问题。
下面演示 { 19 , 30 , 5 , 36 , 13 , 20 , 21 , 12 } 这一组值映射到 M 11 的表中。 二次探测 从发生冲突的位置开始依次左右按二次方跳跃式探测直到寻找到下一个没有存储数据的位置为止如果往右走到哈希表尾则回绕到哈希表头的位置如果往左走到哈希表头则回绕到哈希表尾的位置。 hf(key) hash0 key % M , hash0 位置冲突了则二次探测公式为 hc(key , i) hashi (hash0 ± i ^ 2 ) % M i {1, 2, 3, …, M / 2 }。 二次探测当 hashi (hash0 − i ^ 2 ) % M 时当 hashi 0 时需要hashi M。 下面演示 { 19 , 30 , 52 , 63 , 11 , 22 } 这一组值映射到 M 11 的表中。 双重散列 第一个哈希函数计算出的值发生冲突使用第二个哈希函数计算出一个跟 key 相关的偏移量值不断往后探测直到寻找到下一个没有存储数据的位置为止。 hf1(key) hash0 key % M , hash0 位置冲突了则双重探测公式为 hc(key , i) hashi (hash0 i ∗ hf2(key)) % M i { 1, 2, 3, …, M }。 要求 hf2(key) M 且 hf2(key) 和 M 互为质数有两种简单的取值方法1.当 M 为 2 整数幂时hf2(key) 从 [ 0 M - 1 ] 任选一个奇数2.当 M 为质数时hf2(key) key % (M − 1) 1。 保证 hf2(key) 与 M 互质是因为根据固定的偏移量所寻址的所有位置将形成一个群若最大公约数 p gcd(M, hf1(key) ) 1那么所能寻址的位置的个数为 M / P M使得对于一个关键字来说无法充分利用整个散列表。举例来说若初始探查位置为 1偏移量为 3整个散列表大小为 12那么所能寻址的位置为 { 1, 4, 7, 10 }寻址个数为 12 / gcd(12, 3) 4 下面演示 { 19 , 30 , 52 } 这一组值映射到 M 11 的表中设 hf2(key) key % 10 1
开放定址法的哈希表结构
解决冲突的思路
要注意的是这里需要给每个存储值的位置加一个状态标识否则删除一些值以后会影响后面冲突的值查找。如下图我们删除 30会导致查找 20 失败当我们给每个位置加一个状态标识 { EXIST , EMPTY , DELETE } 删除 30 就可以不用删除值而是把状态改为 DELETE 那么查找 20 时是遇到 EMPTY 没有找到才能退出不然可以找到 20。
扩容
我们实现的哈希表负载因子控制在 0.7 以后进行扩容这里按照 2 倍扩容但是同时我们要保持哈希表大小是一个质数第一个是质数2 倍后就不是质数了。如何解决一种方案就是上述除法散列法中我们讲的 Java HashMap 的使用 2 的整数幂但是计算时不能直接取模的改进方法。另外一种方案是 SGI版本的STL中哈希表使用的方法给了一个近似 2 倍的质数表每次去质数表获取扩容后的大小。
这里我们使用的是 SGI 版本的 STL 中哈希表使用的方法 static const int prime_num 28;int getNextPrime(int num) // 近似 2 倍的质数表{static const Hash_mapping prime_list[prime_num] {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,};int left 0;int right prime_num - 1;while (left right) //二分查找{int mid left ((right - left) 1);if (prime_list[mid] num){left mid 1;}else{right mid;}}return prime_list[left];}开放定址法代码实现
开放定址法在实践中不如下面讲的链地址法因为开放定址法解决冲突不管使用哪种方法占用的都是哈希表中的空间始终存在互相影响的问题。所以开放定址法我们简单选择线性探测实现即可。
#pragma once#include iostream
#include string
#include vector// 以下采用开放定址法即线性探测解决冲突
namespace my
{typedef unsigned int Hash_mapping;templateclass Keystruct defaultHashFunc{Hash_mapping operator()(const Key key) const{return key;}};templatestruct defaultHashFuncstd::string{Hash_mapping operator()(const std::string key) const{Hash_mapping the_map 0;for (char ch : key){the_map ch;the_map * 131;}return the_map;}};templateclass Keystruct defaultEqualTo{bool operator()(const Key key1, const Key key2) const{return key1 key2;}};templateclass Key, class Value, class HashFunc defaultHashFuncKey, class EqualTo defaultEqualToKeyclass HashTable{typedef std::pairKey, Value Type;enum State{EMPTY 0,EXIST,DELETE};struct HashData{Type _data;State _state EMPTY;};typedef HashData Data;typedef Data* pData;static const constexpr HashFunc _hashFunc HashFunc();static const constexpr EqualTo _equal_to EqualTo();std::vectorData _table;size_t _size 0; // 表中存储数据个数private:static const int prime_num 28;int getNextPrime(int num) // 近似 2 倍的质数表{static const Hash_mapping prime_list[prime_num] {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,};int left 0;int right prime_num - 1;while (left right) //二分查找{int mid left ((right - left) 1);if (prime_list[mid] num){left mid 1;}else{right mid;}}return prime_list[left];}void checkCapacity(){if (1.0 * _size / _table.size() 0.7){return;}HashTable newHashTable;newHashTable._table.resize(getNextPrime(_table.size()));for (auto e : _table){if (e._state EXIST){newHashTable.insert(e._data);}}std::swap(newHashTable, *this);}public:HashTable():_table(53){;}templateclass InputIteratorHashTable(InputIterator begin, InputIterator end):_table(53){while (begin ! end){insert(*begin);begin;}}HashTable(std::initializer_listType list):_table(53){for (auto e : list){insert(e);}}bool insert(const Type data){checkCapacity();Hash_mapping index _hashFunc(data.first) % _table.size();while (_table[index]._state EXIST){if (_equal_to(_table[index]._data.first, data.first)){return false;}index (index 1) % _table.size();}_table[index]._data data;_table[index]._state EXIST;_size;return true;}pData find(const Key key) const{Hash_mapping index _hashFunc(key) % _table.size();while (_table[index]._state ! EMPTY){if (_table[index]._state EXIST _equal_to(_table[index]._data.first, key)){return _table[index];}index (index 1) % _table.size();}return nullptr;}bool erase(const Key key){if (_size 0){return false;}pData aim find(key);if (aim ! nullptr){aim-_state DELETE;--_size;return true;}else{return false;}}size_t size() const{return _size;}};
}
链地址法
解决冲突的思路
开放定址法所有元素都是放在哈希表里的而链地址法中所有数据不再直接存储在哈希表中而是存储一个指针。没有数据映射这个位置时这个指针为空有多个数据映射到这个位置时我们把这些冲突的数据链接成一个链表挂在哈希表这个位置下面链地址法也叫做拉链法或者哈希桶。
下面演示 { 19 , 30 , 5 , 36 , 13 , 20 , 21 , 12 , 24 , 96 } 这一组值映射到 M 11 的表中。
扩容
开放定址法负载因子必须小于 1链地址法的负载因子没有限制可以大于 1。STL 中 unordered_xxx 的最大负载因子基本控制在 1大于 1 就扩容我们实现也使用这个方式。
极端场景
在极端场景下某个桶特别长可以考虑使用全域散列法这样就不容易被针对。但是假设不是被针对用了全域散列法在偶然情况下某个桶依然很长查找效率低。可以参考 Java8 的 HashMap当桶的长度超过一定阀值 (8) 时它会把链表转换成红黑树。一般情况下不断扩容单个桶很长的场景还是比较少的我们实现就不搞这么复杂这个解决极端场景的思路了解一下即可。
链地址法代码实现
#pragma once #include iostream
#include string
#include vectornamespace my
{typedef unsigned int Hash_mapping;templateclass Typestruct HashNode // 链地址法{HashNode* _next nullptr;Type _data;HashNode(const Type data):_data(data){;}};templateclass Keystruct defaultHashFunc{Hash_mapping operator()(const Key key) const{return key;}};templatestruct defaultHashFuncstd::string{Hash_mapping operator()(const std::string key) const{Hash_mapping the_map 0;for (char ch : key){the_map ch;the_map * 131;}return the_map;}};templateclass Keystruct defaultEqualTo{bool operator()(const Key key1, const Key key2) const{return key1 key2;}};templateclass Key, class Value, class HashFunc defaultHashFuncKey, class EqualTo defaultEqualToKeyclass HashTable{typedef std::pairKey, Value Type;typedef HashNodeType Node;typedef Node* pNode;static const constexpr HashFunc _hashFunc HashFunc();static const constexpr EqualTo _equal_to EqualTo();std::vectorpNode _table;size_t _size 0;private:static const int prime_num 28;int getNextPrime(int num){static const Hash_mapping prime_list[prime_num] {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,};int left 0;int right prime_num - 1;while (left right){int mid left ((right - left) 1);if (prime_list[mid] num){left mid 1;}else{right mid;}}return prime_list[left];}void checkCapacity(){if (_size _table.size()){return;}std::vectorpNode newTable;newTable.resize(getNextPrime(_table.size()));for (pNode head : _table) // 可以不用删除节点修改它的指针成员链接即可{if (head nullptr){continue;}pNode cur head;while (cur ! nullptr) // 链表遍历修改链接{Hash_mapping index _hashFunc(cur-_data.first) % newTable.size();pNode temp cur;cur cur-_next;if (newTable[index] nullptr) // 为空{newTable[index] temp;temp-_next nullptr;}else // 否则头插{temp-_next newTable[index];newTable[index] temp;}}head nullptr;}std::swap(_table, newTable); // 交换即可}public:HashTable():_table(53){}templateclass InputIteratorHashTable(InputIterator begin, InputIterator end):_table(53){while (begin ! end){insert(*begin);begin;}}HashTable(std::initializer_listType list):_table(53){for (auto e : list){insert(e);}}~HashTable(){for (pNode head : _table) // 遍历哈希表{if (head nullptr){continue;}pNode cur head; // 检查是否有资源while (cur ! nullptr){pNode temp cur;cur cur-_next;delete temp; // 释放}head nullptr; // 指针置空}_size 0;}public:bool insert(const Type data){checkCapacity();Hash_mapping index _hashFunc(data.first) % _table.size();pNode cur _table[index];while (cur ! nullptr) // 检查重复值有则插入失败{if (_equal_to(cur-_data.first, data.first)){return false;}cur cur-_next;}pNode newNode new Node(data);newNode-_next _table[index];_table[index] newNode;_size; return true;}pNode find(const Key key) const{if (_size 0){return nullptr;}Hash_mapping index _hashFunc(key) % _table.size();pNode cur _table[index];while (cur ! nullptr){if (_equal_to(cur-_data.first, key)) // 找到直接返回地址{return cur;}cur cur-_next;}return nullptr; // 否则为空}bool erase(const Key key){Hash_mapping index _hashFunc(key) % _table.size();pNode cur _table[index];pNode prev cur;if (prev nullptr) // 哈希表指针为空 {return false;}else if (_equal_to(prev-_data.first, key)) // 哈希表链接的元素{_table[index] prev-_next; // 置空或链接下一个delete prev;--_size;return true;}while (cur ! nullptr) // 寻找{if (_equal_to(cur-_data.first, key)){prev-_next cur-_next; delete cur;--_size;return true;}prev cur;cur cur-_next;}return false;}size_t size() const{return _size;}};
}三、链地址法哈希表封装
注意上述中我们设计的只是 key / value 的链地址法哈希表还有 key 这种类型这里将两者整合。
HashTable_base
我们先将之前介绍的基础函数都封装到一个模版类也就是 HashTable_base 里方便后续 key / value 与 key 类型复用 templateclass Type, class Key, class GetKey, class HashFunc, class EqualToclass HashTable_base{typedef HashNodeType Node;typedef Node* pNode;static const constexpr GetKey _getKey GetKey();static const constexpr EqualTo _equal_to EqualTo();static const constexpr HashFunc _hashFunc HashFunc();std::vectorpNode _table;size_t _size 0;private:static const int prime_num 28;int getNextPrime(int num){static const Hash_mapping prime_list[prime_num] {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,};int left 0;int right prime_num - 1;while (left right){int mid left ((right - left) 1);if (prime_list[mid] num){left mid 1;}else{right mid;}}return prime_list[left];}void checkCapacity(){if (_size _table.size()){return;}std::vectorpNode newTable;newTable.resize(getNextPrime(_table.size()));for (pNode head : _table) // 可以不用删除节点修改它的指针成员链接即可{if (head nullptr){continue;}pNode cur head;while (cur ! nullptr) // 链表遍历修改链接{Hash_mapping index _hashFunc(_getKey(cur-_data)) % newTable.size();pNode temp cur;cur cur-_next;if (newTable[index] nullptr) // 为空{newTable[index] temp;temp-_next nullptr;}else // 否则头插{temp-_next newTable[index];newTable[index] temp;}}head nullptr;}std::swap(_table, newTable); // 交换即可}public:HashTable_base():_table(53){;}templateclass InputIteratorHashTable_base(InputIterator begin, InputIterator end):_table(53){while (begin ! end){insert(*begin);begin;}}HashTable_base(std::initializer_listType list):_table(53){for (auto e : list){insert(e);}}~HashTable_base(){for (pNode head : _table) // 遍历哈希表{if (head nullptr){continue;}pNode cur head; // 检查是否有资源while (cur ! nullptr){pNode temp cur;cur cur-_next;delete temp; // 释放}head nullptr; // 指针置空}_size 0;}public:bool insert(const Type data){checkCapacity();Hash_mapping index _hashFunc(_getKey(data)) % _table.size();pNode cur _table[index];while (cur ! nullptr) // 检查重复值有则插入失败{if (_equal_to(_getKey(cur-_data), _getKey(data))){return false;}cur cur-_next;}pNode newNode new Node(data);newNode-_next _table[index];_table[index] newNode;_size;return true;}pNode find(const Key key) const{if (_size 0){return nullptr;}Hash_mapping index _hashFunc(key) % _table.size();pNode cur _table[index];while (cur ! nullptr){if (_equal_to(_getKey(cur-_data), key)) // 找到直接返回地址{return cur;}cur cur-_next;}return nullptr; // 否则为空}bool erase(const Key key){Hash_mapping index _hashFunc(key) % _table.size();pNode cur _table[index];pNode prev cur;if (prev nullptr) // 哈希表指针为空 {return false;}else if (_equal_to(_getKey(prev-_data), key)) // 哈希表链接的元素{_table[index] prev-_next; // 置空或链接下一个delete prev;--_size;return true;}while (cur ! nullptr) // 寻找{if (_equal_to(_getKey(cur-_data), key)){prev-_next cur-_next;delete cur;--_size;return true;}prev cur;cur cur-_next;}return false;}size_t size() const{return _size;}};key 复用
这里处理节点与 Key 获取将 HashTable_base 组合为成员加上接口即可 templateclass Key, class HashFunc defaultHashFuncKey, class EqualTo defaultEqualToKeyclass HashOne{typedef const Key Type;typedef HashNodeType Node;typedef Node* pNode;typedef Node const* const_pNode;struct GetSetKey{const Key operator()(const Type data) const{return data;}};HashTable_baseType, Key, GetSetKey, HashFunc, EqualTo _hashTable;public:HashOne() default;templateclass InputIteratorHashOne(InputIterator begin, InputIterator end):_hashTable(begin, end){;}HashOne(std::initializer_listType list):_hashTable(list){;}public:bool insert(const Type data){return _hashTable.insert(data);}bool erase(const Key key){return _hashTable.erase(key);}const_pNode find(const Key key) const // const_pNode 防止使用者修改内容{return _hashTable.find(key);}size_t size() const{return _hashTable.size();}};key / value 复用
同上这里处理节点与 Key 获取将 HashTable_base 组合为成员加上接口即可 templateclass Key, class Value, class HashFunc defaultHashFuncKey, class EqualTo defaultEqualToKeyclass HashTwo{typedef std::pairconst Key, Value Type;typedef HashNodeType Node;typedef Node* pNode;typedef Node const* const_pNode;struct GetMapKey{const Key operator()(const Type data) const{return data.first;}};HashTable_baseType, Key, GetMapKey, HashFunc, EqualTo _hashTable;public:HashTwo() default;templateclass InputIteratorHashTwo(InputIterator begin, InputIterator end):_hashTable(begin, end){;}HashTwo(std::initializer_listType list):_hashTable(list){;}public:bool insert(const Type data){return _hashTable.insert(data);}bool erase(const Key key){return _hashTable.erase(key);}const_pNode find(const Key key) const{return _hashTable.find(key);}size_t size() const{return _hashTable.size();}};源码展示
#pragma once #include iostream
#include string
#include vectornamespace my
{templateclass Typestruct HashNode{HashNode* _next nullptr;Type _data;HashNode(const Type data):_data(data){;}};typedef unsigned int Hash_mapping;templateclass Keystruct defaultHashFunc{Hash_mapping operator()(const Key key) const{return key; }};template // 特化struct defaultHashFuncstd::string {Hash_mapping operator()(const std::string key) const{Hash_mapping the_map 0;for (char ch : key) // 将每个字符都参与映射{the_map ch; the_map * 131;}return the_map;}};templateclass Keystruct defaultEqualTo{bool operator()(const Key key1, const Key key2) const{return key1 key2;}};templateclass Type, class Key, class GetKey, class HashFunc, class EqualToclass HashTable_base{typedef HashNodeType Node;typedef Node* pNode;static const constexpr GetKey _getKey GetKey();static const constexpr EqualTo _equal_to EqualTo();static const constexpr HashFunc _hashFunc HashFunc();std::vectorpNode _table;size_t _size 0;private:static const int prime_num 28;int getNextPrime(int num){static const Hash_mapping prime_list[prime_num] {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,};int left 0;int right prime_num - 1;while (left right){int mid left ((right - left) 1);if (prime_list[mid] num){left mid 1;}else{right mid;}}return prime_list[left];}void checkCapacity(){if (_size _table.size()){return;}std::vectorpNode newTable;newTable.resize(getNextPrime(_table.size()));for (pNode head : _table) // 可以不用删除节点修改它的指针成员链接即可{if (head nullptr){continue;}pNode cur head;while (cur ! nullptr) // 链表遍历修改链接{Hash_mapping index _hashFunc(_getKey(cur-_data)) % newTable.size();pNode temp cur;cur cur-_next;if (newTable[index] nullptr) // 为空{newTable[index] temp;temp-_next nullptr;}else // 否则头插{temp-_next newTable[index];newTable[index] temp;}}head nullptr;}std::swap(_table, newTable); // 交换即可}public:HashTable_base():_table(53){;}templateclass InputIteratorHashTable_base(InputIterator begin, InputIterator end):_table(53){while (begin ! end){insert(*begin);begin;}}HashTable_base(std::initializer_listType list):_table(53){for (auto e : list){insert(e);}}~HashTable_base(){for (pNode head : _table) // 遍历哈希表{if (head nullptr){continue;}pNode cur head; // 检查是否有资源while (cur ! nullptr){pNode temp cur;cur cur-_next;delete temp; // 释放}head nullptr; // 指针置空}_size 0;}public:bool insert(const Type data){checkCapacity();Hash_mapping index _hashFunc(_getKey(data)) % _table.size();pNode cur _table[index];while (cur ! nullptr) // 检查重复值有则插入失败{if (_equal_to(_getKey(cur-_data), _getKey(data))){return false;}cur cur-_next;}pNode newNode new Node(data);newNode-_next _table[index];_table[index] newNode;_size;return true;}pNode find(const Key key) const{if (_size 0){return nullptr;}Hash_mapping index _hashFunc(key) % _table.size();pNode cur _table[index];while (cur ! nullptr){if (_equal_to(_getKey(cur-_data), key)) // 找到直接返回地址{return cur;}cur cur-_next;}return nullptr; // 否则为空}bool erase(const Key key){Hash_mapping index _hashFunc(key) % _table.size();pNode cur _table[index];pNode prev cur;if (prev nullptr) // 哈希表指针为空 {return false;}else if (_equal_to(_getKey(prev-_data), key)) // 哈希表链接的元素{_table[index] prev-_next; // 置空或链接下一个delete prev;--_size;return true;}while (cur ! nullptr) // 寻找{if (_equal_to(_getKey(cur-_data), key)){prev-_next cur-_next;delete cur;--_size;return true;}prev cur;cur cur-_next;}return false;}size_t size() const{return _size;}};templateclass Key, class HashFunc defaultHashFuncKey, class EqualTo defaultEqualToKeyclass HashOne{typedef const Key Type;typedef HashNodeType Node;typedef Node* pNode;typedef Node const* const_pNode;struct GetSetKey{const Key operator()(const Type data) const{return data;}};HashTable_baseType, Key, GetSetKey, HashFunc, EqualTo _hashTable;public:HashOne() default;templateclass InputIteratorHashOne(InputIterator begin, InputIterator end):_hashTable(begin, end){;}HashOne(std::initializer_listType list):_hashTable(list){;}public:bool insert(const Type data){return _hashTable.insert(data);}bool erase(const Key key){return _hashTable.erase(key);}const_pNode find(const Key key) const // const_pNode 防止使用者修改内容{return _hashTable.find(key);}size_t size() const{return _hashTable.size();}};templateclass Key, class Value, class HashFunc defaultHashFuncKey, class EqualTo defaultEqualToKeyclass HashTwo{typedef std::pairconst Key, Value Type;typedef HashNodeType Node;typedef Node* pNode;typedef Node const* const_pNode;struct GetMapKey{const Key operator()(const Type data) const{return data.first;}};HashTable_baseType, Key, GetMapKey, HashFunc, EqualTo _hashTable;public:HashTwo() default;templateclass InputIteratorHashTwo(InputIterator begin, InputIterator end):_hashTable(begin, end){;}HashTwo(std::initializer_listType list):_hashTable(list){;}public:bool insert(const Type data){return _hashTable.insert(data);}bool erase(const Key key){return _hashTable.erase(key);}const_pNode find(const Key key) const{return _hashTable.find(key);}size_t size() const{return _hashTable.size();}};
}
