oi~,让我告诉你如何实现哈希表

1.哈希概念

        哈希（hash）又称散列，是一种组织数据的方式。从译名来看有散乱排列的意思，其本质是通过哈希函数将关键字key值与存储位置建立映射关系，查找时通过哈希函数计算出key值的位置，实现快速查找。

1.1直接定址法

        当关键字key值比较集中时，直接定址法是最简单也是最有效的方法。比如一组数据集中在[ 0 - 99 ]，我们开一组大小为100的数组即可，数据直接作为下标来定位存储位置。再比如一组数据集中在[ a - z]，我们开一个大小为26的数组即可，让数据减去字符‘a\'的结果来定位存储位置。
        例题：387. 字符串中的第一个唯一字符 - 力扣（LeetCode）

class Solution{public: int firstUniqChar(string s) { int arr[26]={0}; //范围for 遍历 for(auto e: s) { arr[e-\'a\']++; } for (int i = 0; i < s.size(); i++) { if (arr[s[i] - \'a\'] == 1) { return i; } } return -1; }};

 1.2哈希冲突

        直接定址法适用于数据比较集中的情况，当数据过于分散时这意味这我们将会开一个过大的数组来存储，而这会极大的浪费内存空间，不可取。

        所以当面对这种情况的时候，我们会使用哈希函数:h(key)，通过哈希函数对关键字key值在存储空间的映射，来定位key值的存储位置。而这里存在一个问题：不同的值通过哈希函数的映射后的位置可能相同，这就会导致哈希冲突（哈希碰撞）。我们可以通过设计一个好的哈希函数来减少哈希冲突，但是在实际情况下，哈希冲突是不可避免的。

1.3负载因子

        假设存储空间的大小为M，已经放入存储空间的数据个数是N，那么负载因子就是：N/M。负载因子也称载荷因子。负载因子越大，哈希冲突概率越大，空间利用率越高。负载因子越小，哈希冲突概率越小，空间利用率越低。

1.4哈希函数

1.4.1除法散列法/除留余数法

        顾名思义就是通过取余，其余值就是映射的存储位置。假设存储空间的大小为M，关键字为key，哈希函数h(key)=key%M。

        使用除法散列法时，对M有一个要求：要求M不能为2的幂、10的幂。假设M为 2^3，这相当于直接保留了2进制中的后3位，那么只要key值的后3位相同那么就一定冲突，例如：3，11，19，27......，它们二进制的后三位都是011，所以它们同时取余M都等于3。所以当M为2的幂时会导致很高的冲突概率，不可取。同理当M为10的幂时，假设为10^3，这相当于保留了10进制中的后3位，那么只要key值的后3位相同就一定冲突，例如：1001，2001，3001.....，所以也不可取。

        综上所述，建议M的取值为不接近2的幂的值（素数）

        但在实际操作中也有存在直接去2的幂，10的幂的情况。比如java中实现的哈希表就是直接取的2的幂。当然他不仅仅的取余这么简单，还有其他操作保证了较低的冲突概率。比如M为2^16，先取余得到2进制的后16位，再将key>>16，将取余的结果和右移的结果做异或运算。这样的操作将每个数都参与的运算，使其分布的更加的均匀。（了解，在后续的代码实现中我们还是以取素数为例）

1.4.2乘法散列法（了解）

        使用乘法散列法对M没用要求，其大体思路为：关键值key乘上一个常量A(0<A<1)，然后在对其结果取余，得到小数部分。再将M乘上小数部分，再向下取整，得到最终结果。哈希函数为：h(key)= floor( M*( ( key*A ) %1.0) )  ,floor表示向下取整

        A的取值范围为0~1，结论表明A的取值为：(根号5 - 1)/2 = 0.6180339887....（黄金分割点）比较好

1.5将关键字转化为整型

        在哈希函数里面我们说到了，要通过哈希函数将key值映射到存储位置。不管是那种方法，我们可以看到key值都要参与具体的运算的。但是如果key不为整型时，这么办？

        这里我们就需要将key值转化为整型，如果为负数、浮点数等等就强制类型转化为整型。如果为string类型，可以通过将每个字符的ascll码相加，来得到整型。其他的都类似，通过映射的值来转化为整型。

1.6解决哈希冲突

        哈希表中使用的哈希函数主要还是除法散列法，但对于哈希冲突，不论选择什么哈希函数都不可避免。所以我们需要知道可以解决哈希冲突的方法，主要分为两种：开放地址法、链地址法。

1.6.1开放地址法

        在开放地址法中，所有元素都存于哈希表中，当通过哈希函数映射key的存储位置发生冲突时，按照一定规则去找下一个空白位置进行存储。开放地址法的负载因子一定是小于1的。这里的规则一共有3种：线性探测、二次探测、双重探测（对于开放地址法，不论什么规则都是治标不治本，这里就主要讲讲线性探测，后面我会详细解释为什么说是治标不治本）

线性探测

        发生冲突时，从映射位置开始向后遍历，找到第一个空白位置时就存储，当找到表尾就返回到表头继续向后找。

        下面演示 {19,30,5,36,13,20,21,12} 等这一组值映射到M=11的表中

        h(19) = 8，h(30) = 8，h(5) = 5，h(36) = 3，h(13) = 2，h(20) = 9，h(21) = 10，h(12) = 1

        我们可以看到30与19发生冲突，30存储到了9这个位置。随后20与30也发生了冲突，20存储到了10这个位置。21又与20发生冲突，21返回到表头存储到了0这个位置。

        这就是开发地址法的弊端，发生了冲突就去占别人的位置。当别人来找自己的位置时发现被占用了，又只能去占用其他人的位置。由此不断的恶性循环，这种现象叫做群集/堆积，会极大的影响插入和查找效率。

        而二次探测法和双重探测法，都只是去减小群集效应，并不能真正的解决这个弊端。链地址法没有这个弊端，是相对而言更优的方法，也是我们实际上更常用的方法。

开放地址法的代码实现

哈希表的基本结构

//通过枚举哈希表的节点状态，以便于我们后面更好的管理enum State{EXIST,EMPTY,DELETE};templatestruct HashData{pair _kv;State _state = EMPTY;};templateclass HashTable{private:vector<HashData> _tables;size_t _n = 0; // 表中存储数据个数 };

        当我们删除节点时，为了不影响后续数据的查找，这里我们枚举哈希表节点的状态。如图，如果这里我们删除30这个值，后续查找时发现20这个值冲突，根据插入规则，我们会去往后面找，当找到空时查找停止，查找20就会失败。我们不用真的去删除30，只需将状态 EXIST修改为 DELETE，并不影响为 EMPTY时查找停止的条件

 扩容

        这里我们将负载因子控制到0.7左右，当负载因子超过0.7时我们就需要扩容。前面我们提到M的大小建议为素数，但扩容我们一般是扩2倍，扩2倍之后M就不再为素数了，这怎么办呢？这里c++库的解决方法是直接列出素数表

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;}

        扩容后，我们需要重新遍历原表，重新计算映射位置，重新插入元数据。因为扩容后，M的大小改变了，通过哈希函数计算出的映射位置也改变了 

如果key不能取余的问题

        这里我们可以传一个仿函数来实现将key值转化为整型的功能，对于负数、浮点数这种可以直接转化为整型的类型，我们可以直接将其写成一个仿函数并作为缺省值传给模板，这样我们初始化的时候，就可以不用反复写仿函数了。

        对于string类型，将每个字符的ascll码相加后返回，鉴于string类作为key就是很常用的情况，所以这里我们可以考虑特化。这样也避免就我们反复的传仿函数。

        对于自定义类型，我们就只能自己单独写仿函数，并显示的传仿函数

templateclass HashFunc{public:size_t operator()(const K& key){return (size_t)key;}};//偏特化（可以单独写成一个仿函数，但是string作为key是常有的情况，为避免反复的传仿函数，写成偏特化）templateclass HashFunc{public:size_t operator()(const string& key){int ch = 0;for (auto& e : key){ch += e;ch *= 131; //使用BKDR哈希的思路：每次结果乘131，避免“abcd” “dcba”这种不相同字符，转化为整型却相同的情况}return ch;}};template<class K,class V,class Hash = HashFunc> //直接给出缺省值，避免常用的key值，反复传仿函数class HashTable{public:private:vector<HashData> _tables;size_t _n = 0; // 表中存储数据个数 };

完整代码实现

//HashTable.h#include#includeusing namespace std;//使用开放地址法，实现HashTable//仅实现探测法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;}//枚举状态enum STATE{EMPTY,EXIST,DELETE};templatestruct HashDate{pair _kv;STATE _state=EMPTY;};templateclass HashFunc{public:size_t operator()(const K& key){return (size_t)key;}};//偏特化（可以单独写成一个仿函数，但是string作为key是常有的情况，为避免反复的传仿函数，写成偏特化）templateclass HashFunc{public:size_t operator()(const string& key){int ch = 0;for (auto& e : key){ch += e;ch *= 131; //使用BKDR哈希的思路：每次结果乘131，避免“abcd” “dcba”这种不相同字符，转化为整型却相同的情况}return ch;}};template<class K,class V,class Hash = HashFunc> //直接给出缺省值，避免常用的key值，反复传仿函数class HashTable{public:HashTable():_n(0), _table(11){}Hash hash;bool Insert(const pair& kv){//负载因子 控制到0.7左右if (_n * 10 / _table.size() >= 7){size_t size = __stl_next_prime(_table.size());HashTable newHash;newHash._table.resize(size);for (auto& e : _table){if(e._state==EXIST)newHash.Insert(e._kv);}_table.swap(newHash._table);}//找位置size_t pos = hash(kv.first) % _table.size();size_t i = 1;while (_table[pos]._state!= EMPTY)//探测{pos = (pos + i) % _table.size(); //处理越界情况i++;}//插入_table[pos]._kv = kv;_table[pos]._state = EXIST;_n++;return true;}HashDate* Find(const K& key){size_t pos = hash(key) % _table.size();size_t i = 1;while (_table[pos]._state != EMPTY){if (_table[pos]._kv.first == key && _table[pos]._state != DELETE){return &_table[pos];}pos = (pos + i)% _table.size(); //处理越界情况i++;}return nullptr;}//删除不是真正的删除，只需要将其状态修改为DELETE即可bool Erase(const K& key){HashDate* ret = Find(key);if (ret){ret->_state = DELETE;return true;}elsereturn false;}private://HashDate包含：pair、节点的状态vector<HashDate> _table;size_t _n;//记录元素个数};//test.cpp#include\"HashTable.h\"//处理key为string的仿函数，但作为常用的key类型，建议直接写成偏特化，避免反复传仿函数struct StringHashFunc{size_t operator()(const string& key){int ret = 0;for (auto& e : key){//采用BKDR哈希思路ret += e;ret *= 131;}return ret;}};//日期类(自定义类型要支持 = 符号，用于Find函数)struct Date{bool operator==(Date& key){return _year == key._year&& _month == key._month&& _day == key._day;}//重点！！！：这里给缺省值，是为了形成默认构造函数//template//struct HashDate//{//pair _kv;//STATE _state = EMPTY;//};//在头文件的HashDate函数在初始化时，会调用自定义类型的默认构造！如果默认构造不存在就会报错Date(const int year = 1, const int month = 1, const int day = 1){_day = day;_month = month;_year = year;}int _day;int _month;int _year;};//处理key为Date的仿函数struct DateHashFunc{size_t operator()(const Date& key){//采用BKDR哈希思路int ret = 0;ret += key._day;ret *= 131;ret += key._month;ret *= 131;ret += key._year;ret *= 131;return ret;}};int main(){//测试key为int的情况HashTable hash;for (int i = 0; i < 15; i++){hash.Insert({ i,i });}cout << hash.Find(10)<<endl;hash.Erase(10);cout << hash.Find(10)<<endl;//测试key为string的情况HashTable hash1;vector arr = { \"abc\",\"asd\",\"qwe\",\"fgh\" };for (auto& e : arr){hash1.Insert({ e,e });}cout << HashFunc()(\"abc\") <<endl;cout << HashFunc()(\"asd\") << endl;cout << HashFunc()(\"qwe\") << endl;cout << HashFunc()(\"fgh\") << endl;//cout << StringHashFunc()(\"abc\") << endl;//cout << StringHashFunc()(\"asd\") << endl;//cout << StringHashFunc()(\"qwe\") << endl;//cout << StringHashFunc()(\"fgh\") << endl;//测试key为自定义的情况HashTable hash2;Date r1(2025, 4, 1);Date r2(2025, 1, 4);hash2.Insert({ r1, r1 });hash2.Insert({ r2,r2 });}

链地址法 

        链地址法中，哈希表中的每个节点不再存储某个具体的值，而是存储“链表”。当发生冲突时，不在去寻找，而是直接将其数据“挂”在当前冲突的位置 

扩容 

        链地址法的负载因子我们控制到1左右，超过1就要扩容。而扩容的方法我们也使用上述的素数表。

        扩容后，我们也需要将原数据重新映射到新表中。因为扩容后M的大小改变，通过哈希函数映射出的位置也改变了

链地址法代码实现

//HashTable.h#include#includeusing namespace std;//实现链地址法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;}templatestruct Node{Node(const pair& kv):_kv(kv),next(nullptr){}Node(){}pair _kv;Node* next = nullptr;};//仿函数（将key值转化为正整数）templatestruct HashFunc{size_t operator()(const K& key){return size(key);}};//偏特化(处理常用key值类型：string)templatestruct HashFunc{size_t operator()(const string& key){int ret = 0;for (auto& e : key){//BKDR哈希的思路ret += e;ret *= 131;}return ret;}};template<class K,class V,class Hash = HashFunc>class HashTable{public://typedef Node Node;using Node = Node;HashTable():_table(__stl_next_prime(0)),_n(0){}~HashTable(){for (int i = 0; i next;delete cur;cur = next;}}}Hash hash;bool Insert(const pair& kv){//不允许键值冗余if (Find(kv.first)){return false;}//扩容(链地址法的负载因子控制在1左右)//更好的扩容方法（将原节点移下来，避免不断的开空间）if (_n / _table.size() >= 1){vector newtable(__stl_next_prime(_table.size() + 1));for (int i = 0; i next;//映射新表位置size_t pos = hash(cur->_kv.first) % newtable.size();//头插到哈希cur->next = newtable[pos].next;newtable[pos].next = cur;cur = next;}}_table.swap(newtable);}//有点拉//复用Insert函数，再交换,我们不断的创建Node节点，需要显示的写出析构函数，避免内存泄露if (_n / _table.size() >= 1){HashTable newHash;newHash._table.resize(__stl_next_prime(_table.size() + 1));for (int i = 0; i _kv);cur = cur->next;}}_table.swap(newHash._table);}//映射位置size_t hash0 = hash(kv.first) % _table.size();Node* cur = _table[hash0].next;Node* newNode = new Node(kv); //需要显示写出构造函数//头插_table[hash0].next = newNode;newNode->next = cur;//统计元素个数_n++;return true;}Node* Find(const K& key){size_t pos = hash(key) % _table.size();Node* cur = _table[pos].next;while (cur){if (cur->_kv.first == key)return cur;cur = cur->next;}return nullptr;}bool Erase(const K& key){//映射位置size_t pos = hash(key) % _table.size();Node* cur = _table[pos].next;Node* per = &_table[pos]; //记录cur的前节点while (cur){if (cur->_kv.first == key){per->next = cur->next;delete cur;return true;}per = cur;cur = cur->next;}return false;}private:vector _table; int _n = 0; //记录插入元素个数};//test.cpp#include\"HashTable.h\"struct Date{bool operator==(const Date& key){return _day == key._day&& _month == key._month&& _year == key._year;}Date(const int year = 2025,const int month = 4,const int day = 2):_day(day),_month(month),_year(year){}int _day;int _month;;int _year;};struct DateFunc{size_t operator()(const Date& key){int ret = 0;ret += key._day;ret *= 131;ret += key._month;ret *= 131;ret += key._year;ret *= 131;return ret;}};int main(){//测试key值为int//HashTable Hash0;//Hash0.Insert({ 1,1 });//Hash0.Insert({ 2,2 });//Hash0.Insert({ 3,3 });//Hash0.Insert({ 4,4 });//cout << Hash0.Find(3) << endl;//cout << Hash0.Erase(3) << endl;//cout << Hash0.Find(3) << endl;//cout << Hash0.Erase(10) << endl;//测试key值为string//HashTable Hash0;//Hash0.Insert({ \"abc\",\"abc\"});//Hash0.Insert({ \"huang\",\"huang\"});//Hash0.Insert({ \"yu\",\"yu\"});//Hash0.Insert({ \"chi\",\"chi\"});//cout << Hash0.Find(\"huang\") << endl;//cout << Hash0.Erase(\"huang\") << endl;//cout << Hash0.Find(\"huang\") << endl;//cout << Hash0.Erase(\"asdf\") << endl;//测试key值为自定义类型HashTable Hash0;Date r1({ 2025,4,2 });Date r2({ 2025,2,4 });Hash0.Insert({ r1,r1 });Hash0.Insert({ r2,r2});cout << Hash0.Find(r2) << endl;cout << Hash0.Erase(r2) << endl;cout << Hash0.Find(r2) << endl;/*cout << Hash0.Erase({ 2000,1,1 }) << endl;*/}

以上就是本文的全部内容，如有错误还请大佬斧正。
点个赞再走吧~