C++：揭秘哈希：提升查找效率的终极技巧

发布时间：2024-11-27 22:55

C#的LINQ（Language Integrated Query）用于查询数据，提升效率 #生活技巧# #工作学习技巧# #编程语言学习路径#

在这里插入图片描述

文章目录哈希概念一、直接定址法二、哈希冲突1. 哈希冲突概念引入2. 除留余数法（值的分布范围分散）3. 存在哈希冲突（闭散列-开放定址法）三、删除与查找数据1. 删除与查找数据存在的问题2. 状态标记四、什么时候扩容？1. 哈希表效率问题2. 负载因子五、哈希表框架搭建六、开放定址法代码实现——插入1. 线性探测实现2. 插入扩容逻辑3. key不能取模的问题默认缺省整形的处理string的特化仿函数的使用七、开放定址法代码实现——查找八、开放定址法代码实现——删除代码总结与运行结果

哈希概念

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

一、直接定址法

当关键字的范围比较集中时，直接定址法就是非常简单高效的方法：

比如一组关键字都在 [0,99] 之间，那么我们开一个 100 个数的数组，每个关键字的值直接就是存储位置的下标。再比如一组关键字值都在 [a,z] 的小写字母，那么我们开一个 26 个数的数组，每个关键字的 ASCII 码减去 ‘a’ 的 ASCII 码就是存储位置的下标。

也就是说，直接定址法本质就是用关键字计算出一个绝对位置或者相对位置。

小试：
387. 字符串中的第⼀个唯⼀字符 - 力扣（LeetCode）

在这里插入图片描述

class Solution { public: int firstUniqChar(string s) { int arr[26] = {0}; 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; } };

12345678910111213141516171819

二、哈希冲突

1. 哈希冲突概念引入

直接定址法的缺点也非常明显：

当关键字的范围比较分散时，会造成内存浪费，甚至内存不足的情况。
假设我们只有数据范围是 [0, 9999] 的 N 个值，但需要将它们映射到一个大小为 M 的数组中（一般情况下 M >= N），
就需要借助哈希函数（hash function，简称 hf）。关键字 key 被放到数组的 h(key) 位置。

注意：h(key) 计算出的值必须在 [0, M) 之间。

存在的问题：

哈希冲突
两个不同的 key 可能会映射到同一个位置，这种情况叫做哈希冲突或哈希碰撞。优化方向
理想情况下，我们希望找到一个好的哈希函数以避免冲突，但实际上冲突是不可避免的。
因此需要尽可能设计优秀的哈希函数来减少冲突次数，同时设计出有效的冲突解决方案。

2. 除留余数法（值的分布范围分散）

除留余数法就可以去解决上述值比较分散的问题：

hashi = key % n

如下图：

在这里插入图片描述

3. 存在哈希冲突（闭散列-开放定址法）

上述方法是会出现哈希冲突的，比如要插入40，而·40 % 9 = 4，但是 4 这个位置已经有数据 4 了，因此就会发生哈希冲突。

解决哈希冲突：

闭散列-开放定址法，即：当前位置被占用了，按规则找下一个位置(占用别人的位置）
这里我们先用 1. 线性探测

还是上述的例子，比如要在当前环境下插入40：

在这里插入图片描述

存在冲突：
在这里插入图片描述

按照顺序继续向后找，直到遇到可以插入的位置：

在这里插入图片描述

同理，我们要插入8，再插入17

在这里插入图片描述

三、删除与查找数据

1. 删除与查找数据存在的问题

查找数据：从data % n的位置开始查找，不为空就继续向后找，为空就停止。

在这里插入图片描述

2. 状态标记

如何解决上述的问题呢？

使用状态标记：
enum STATE // 状态标记
{
EXIST // 存在
DELETE // 删除
EMPTY // 空
}

每当我们删除了一个数据以后，就像该位置的数据改为 DELETE，而 DELETE 状态的数据不算在有效数据以内，查找的时候遇到该状态不停止，遇到空才停止。

而当我们新插入数据是，DELETE和EMPTY位置都可以插入数据。

这样就解决了删除和查找的问题。

四、什么时候扩容？

1. 哈希表效率问题

通过上述的观察，我们可以发现，在数据比较少的时候，不论是插入删除还是查找，我们很容易就遇到空，但是一旦数据比较到，遇到哈希冲突了之后就需要一直向后找空位置，在数据将近满了之后，查找的时间复杂度基本上就是O（n），而不在是常数级别了。

因此，每当数据达到一定数量的时候，就需要扩容！
那么如何扩容呢？

2. 负载因子

如何解决上述问题呢？

提供负载因子

假设哈希表中已经映射存储了 N 个值，哈希表的大小为 M，那么负载因子N / M（有些地方也翻译为载荷因子/装载因子等，其英文为 load factor）定义如下：

负载因子的影响 负载因子越大 哈希冲突的概率越高空间利用率越高 负载因子越小 哈希冲突的概率越低空间利用率越低

这⾥我们哈希表负载因子控制在0.7，当负载因子到0.7以后我们就需要扩容了。

五、哈希表框架搭建

接下来我们开始搭建哈希表~

#pragma once #include<vector> enum STATE {EXIST, // 存在EMPTY, // 空DELETE // 删除 }; template<class K, class V> struct HashData {pair<K, V> _kv;STATE _state = EMPTY; // 初始状态为空 }; template<class K, class V> class HashTable { public:HashTable(){_table.resize(10);} private:vector<HashData<K, V>> _table;size_t _n = 0; // 存储有效数据的个数 };

12345678910111213141516171819202122232425262728293031

六、开放定址法代码实现——插入

1. 线性探测实现

这有一个要注意的点，线性探测时我们计算hashi时Key除的是capacity还是size?

答：除以size，因为我们后面要通过[ ]进行访问，而[ ]会进行assert()是否越界越size，如果除capacity，就会造成越界。

bool Insert(const pair<K, V>& kv) {// 扩容// ... //// 线形探测size_t hashi = kv.first % _table.size();while (_table[hashi]._state == EMPTY){++hashi;hashi %= _table.size();}_table[hashi]._state = EXIST;_table[hashi]._kv = kv;++_n;return true; }

12345678910111213141516171819

2. 插入扩容逻辑

扩容这里有几个需要输入的点：

遍历旧表的时候，数据映射关系被改变了，因此要重新插入数据。
我们这里的逻辑是直接复用插入本身这个函数（也就是复用线性探测的逻辑），这里是不会出现死循环的，因为进入 if 判断条件就会扩容，也就是扩容了才会复用，而复用时因为已经扩容了所以不会循环下去。

新表的 _table 创建好了之后，直接利用swap进行交换就可以了，旧表伴随Insert栈帧的结束会自动释放。

// 扩容 if ((double)_n / _table.size() >= 0.7) {size_t newsize = _table.size() * 2;// 重新建立一个新表HashTable<K, V> newtable;newtable._table.resize(newsize);// 遍历旧表，将数据放到新表中去for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newtable.Insert(_table[i]._kv);}}_table.swap(newtable._table); }

1234567891011121314151617181920

3. key不能取模的问题

当 key 是 string / Date 等类型时，key 不能直接取模，因此我们需要给 HashTable 增加一个仿函数。这个仿函数支持将 key 转换成一个可以取模的整数。如果 key 可以转换为整数并且不容易发生冲突，那么这个仿函数可以使用默认参数；如果这个 key 不能直接转换为整数，我们就需要自己实现一个仿函数并传给这个参数。

实现这个仿函数的要求是，尽量让 key 的每个值都参与到计算中，从而使得不同的 key 转换出的整数值尽可能不同。

string 作为哈希表的 key 非常常见，因此我们可以考虑对 string 类型进行特化处理。

// 多加一种仿函数进行控制 template<class K, class V, class HashFunc = DefaultHashFunc<K>> class HashTable 123

缺省参数给DefaultHashFunc< K>，它的作用是——我们默认是整形，他会返回对应的无符号整型值。

这样的好处是，如果我们传过来的是负数，也可以正常取模进行操作~

默认缺省整形的处理

template<class K> struct DefaultHashFunc {size_t operator() (const K& key){return (size_t)key;} }; 123456789 string的特化

因为string是一种常用的类，因此这里我们把它写成特化，对于string类怎么取出对应的数进行取模运算，还要减少冲突，有许多的大佬对这里的算法进行实现：

在哈希表中，字符串转整形是一个核心问题。为了高效地将字符串映射到整数，常用的哈希算法有几种，每种方法都具有不同的性能特点，特别是在哈希冲突的处理上。以下是几种常见的哈希算法及其基本思路：

常见的哈希算法和思路：
在这里插入图片描述

性能对比表格：

哈希算法冲突概率计算复杂度适用场景优势缺点BKDR Hash中等O(n)小型字符串简单、高效，适合短字符串和小哈希表对大字符串可能存在较多冲突SDBM Hash较低O(n)字符串查找较少冲突，常用于文件查找较为简单，可能在某些场景下效率较低DJB2 Hash较低O(n)字符串查找高效、低冲突，广泛应用对长字符串的处理可能不如 MurmurHashFNV-1a Hash非常低O(n)高效字符串查找良好的分布性和抗碰撞能力比其他方法略慢，适用于不需要极端效率的场景MurmurHash极低O(n)大型数据处理非常高效、抗碰撞能力强实现较复杂，计算开销较大

这里我们用BKDR的方法实现string的特化

template<> struct DefaultHashFunc<string> {size_t operator() (const string& str){// BKDRsize_t hash = 0;for (auto ch : str){hash *= 131;hash += ch;}return hash;} };

12345678910111213141516 仿函数的使用

这里使用仿函数的时候包一层就可以了~

// 仿函数控制 HashFunc hf; size_t hashi = hf(kv.first) % _table.size(); 1234

七、开放定址法代码实现——查找

查找这里同样使用的是线性探测，如果不为空就一直向后查找，如果找到了并且状态为存在就返回。哈希表的数据不能轻易修改，因此我们返回的时候要返回HashData<const K, V>*，因为Key是不能i修改的，因此这里返回的时候最好也强转以下，增强代码可读性与健壮性。

HashData<const K, V>* Find(const K& key) {// 线性探测HashFunc hf;size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY ){if (_table[hashi]._state == EXIST&& _table[hashi]._kv.first == key){return (HashData<const K, V>*) & _table[hashi];}++hashi;hashi %= _table.size();}return nullptr; }

1234567891011121314151617181920

八、开放定址法代码实现——删除

删除复用Find就好，如果找到了就将其状态设置为DELETE。

bool Erase(const K& key) {HashData<const K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}return false; } 12345678910111213

代码总结与运行结果

// HashTable.h #pragma once #include<vector> enum STATE {EXIST, // 存在EMPTY, // 空DELETE // 删除 }; template<class K, class V> struct HashData {pair<K, V> _kv;STATE _state = EMPTY; // 初始状态为空 }; template<class K> struct DefaultHashFunc {size_t operator() (const K& key){return (size_t)key;} }; template<> struct DefaultHashFunc<string> {size_t operator() (const string& str){// BKDRsize_t hash = 0;for (auto ch : str){hash *= 131;hash += ch;}return hash;} }; template<class K, class V, class HashFunc = DefaultHashFunc<K>> class HashTable { public:HashTable(){_table.resize(10);}bool Insert(const pair<K, V>& kv){// 扩容if ((double)_n / _table.size() >= 0.7){size_t newsize = _table.size() * 2;// 重新建立一个新表HashTable<K, V> newtable;newtable._table.resize(newsize);// 遍历旧表，将数据放到新表中去for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newtable.Insert(_table[i]._kv);}}_table.swap(newtable._table);}// 线形探测// 仿函数控制HashFunc hf;size_t hashi = hf(kv.first) % _table.size();while (_table[hashi]._state == EXIST){++hashi;hashi %= _table.size();}_table[hashi]._state = EXIST;_table[hashi]._kv = kv;++_n;return true;}HashData<const K, V>* Find(const K& key){// 线性探测HashFunc hf;size_t hashi = hf(key) % _table.size();while (_table[hashi]._state != EMPTY ){if (_table[hashi]._state == EXIST&& _table[hashi]._kv.first == key){return (HashData<const K, V>*) & _table[hashi];}++hashi;hashi %= _table.size();}return nullptr;}bool Erase(const K& key){HashData<const K, V>* ret = Find(key);if (ret){ret->_state = DELETE;--_n;return true;}return false;} private:vector<HashData<K, V>> _table;size_t _n = 0; // 存储有效数据的个数 };

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134

//test.cpp #include<iostream> using namespace std; #include"HashTable.h" int main() {HashTable<int, int> ht;int a[] = { 1,111,4,7,15,25,44,9 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Erase(15);auto ret = ht.Find(4);//ret->_kv.first = 41;ret->_kv.second = 400;//HashTable<string, string, StringHashFunc> dict;HashTable<string, string> dict;dict.Insert(make_pair("sort", "排序"));dict.Insert(make_pair("left", "xxx"));auto dret = dict.Find("left");//dret->_kv.first = "xx";dret->_kv.second = "左边";string s1("xxx");string s2("xxx");DefaultHashFunc<string> hf;cout << hf(s1) << endl;cout << hf(s2) << endl;cout << hf("bacd") << endl;cout << hf("abcd") << endl;cout << hf("abbe") << endl;cout << hf("https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=STATE&fenlei=256&rsv_pq=0xdd48647300054f47&rsv_t=1cd5rO%2BE6TJzo6qf9QKcibznhQ9J3lFwGEzmkc0Goazr3HuQSIIc2zD78Pt0&rqlang=en&rsv_enter=1&rsv_dl=tb&rsv_sug3=2&rsv_n=2&rsv_sug1=1&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&prefixsug=STAT%2526gt%253B&rsp=5&inputT=656&rsv_sug4=796") << endl;return 0; }

1234567891011121314151617181920212223242526272829303132333435363738394041424344

运行结果如下：
在这里插入图片描述