哈希表你真的学透了嘛
原创
哈希
哈希表 你真的懂吗
哈希表 你真的懂吗
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到 log2_N ，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同，本文中只对unordered_map和unordered_set进行介绍。
unordered_map和unordered_set
性质
- unordered_map是存储<key,value>键值对的关联式容器，键值key通常用于唯一表示元素，其映射值是一个对象，其内容和键值key关联，允许通过键值key查寻其对于的value。
- 在内部，没有对键值对<key,value>按照特定的顺序排序，为了能够在常数范围内找到key所对应的vlaue，该容器将相同哈希值键值对放到同一个桶中。
- unordered_map容器通过key对单个元素的访问速度比map快，但遍历效率较低。
- 实现了[]重载，允许通过key直接访问value
- 迭代器是单向（前向）迭代器。
unordered_set底层是哈希，而set底层是红黑树，unordered_set使用方法和set没有太大差异，这里不展开介绍。
性能比较
这里的性能比较就不用map和unordered_map做比较了，用set和unordered_set做比较。
set的底层是红黑树，而unordered_set底层是哈希表，在这里对这两者底层设计性能对比。
int main()
{
const size_t N = 1000000;
unordered_set<int> us;
set<int> s;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
//数据大多数不相同时，set更有优势
//v.push_back(rand());//插入随机数，但只有3w多个，大部分重复了;insert:us<s
v.push_back(rand() + i);//少量的重复值的随机数 ;insert :差不多
//v.push_back(i);//有序数;insert:s<us
}
size_t begin1 = clock();
for (auto e : v)
{
us.insert(e);
}
size_t end1 = clock();
size_t begin2 = clock();
for (auto e : v)
{
s.insert(e);
}
size_t end2 = clock();
size_t begin3 = clock();
for (auto e : v)
{
us.find(e);
}
size_t end3 = clock();
size_t begin4 = clock();
for (auto e : v)
{
s.find(e);
}
size_t end4 = clock();
cout << us.size() << endl;
cout << s.size() << endl;
size_t begin5 = clock();
for (auto e : v)
{
us.erase(e);
}
size_t end5 = clock();
size_t begin6 = clock();
for (auto e : v)
{
s.erase(e);
}
size_t end6 = clock();
cout << "unordered_set insert:" << " " << end1 - begin1 << endl;
cout << "set insert:" << " " << end2 - begin2 << endl;
cout << "unordered_set find:" << " " << end3 - begin3 << endl;
cout << "set find:" << " " << end4 - begin4 << endl;
cout << "unordered_set erase:" << " " << end5 - begin5 << endl;
cout << "set erase:" << " " << end6 - begin6 << endl;
return 0;
}对set和unordered_set的insert性能进行比较（在release下跑）
- 在100w个数据下有大量重复值（随机数最多可以产生32768个），可以看到unordered_set的insert相比于set还是占有很大优势的
image-20230417110228383
- 在100w个数据下相比前一个实验较少重复值的随机数下（这次的随机数量有60多w），unordered_set的insert相比于set都差不多
image-20230417110534023
- 在100w个有序数集合中（没有重复值），unordered_set的insert相比于set还是稍微逊色了些。底层红黑树对于有序数的插入就是一个简单的左旋或右旋，既是红黑树的最强形态拉！
image-20230417110903282
对set和unordered_set的find性能进行比较（在debug下跑）
在release下跑编译器会优化掉，set和unordered_set find所用的时间都是0,无法得出结论。所以得在debug下跑
image-20230417111544557
- 在100w个数据下有大量重复值（随机数最多可以产生32768个），可以看到unordered_set的find的速度比set快
image-20230417111852526
- 在100w个数据下相比前一个实验较少重复值的随机数下（这次的随机数量有60多w），unordered_set的find速度比set快
image-20230417112028303
- 在100w个有序数集合中（没有重复值），unordered_set的find相比于set还是要快。综上，在find这层，红黑树即使是最强形态还是比不过unordered_set
image-20230417112201421
对set和unordered_set的erase性能进行比较（在release下跑）
- 在100w个数据下有大量重复值（随机数最多可以产生32768个），可以看到unordered_set的erase相比于set还是占有优势的
image-20230417112722854
- 在100w个数据下相比前一个实验较少重复值的随机数下（这次的随机数量有60多w），unordered_set的erase相比于set要快不少
image-20230417112842261
- 在100w个有序数集合中（没有重复值），unordered_set的erase相比于set稍稍逊色。
image-20230417112956791
看完性能对比，言而总之底层是哈希表的查询效率会比红黑树快，那么下面开始介绍哈希表。
哈希表
概念
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即O(log_2 N)，搜索的效率取决于搜索过程中元素的比较次数。
那么有没有一种结构，可以让其在查询元素的时候可以不经过比较或者少量比较在结构中得到要搜索的元素呢？
有！哈希表。通过哈希函数使元素存储位置直接与关键码进行一一映射联系，那么在查询的元素的时候就很快。
当往哈希表结构插入元素时：
根据插入元素的关键码，通过哈希函数计算出该元素应该存储的位置并进行存放。
当在哈希表中搜索元素时：
对元素的关键码同样进行哈希函数的计算，求得的参数当作元素的存储位置，然后按照这个位置进行关键码的比较，若关键码相同则搜索成功。
哈希函数有以下几点规则：
- 哈希函数的定义域须包括存储的全部关键码，如果散列表中有m个地址时，其值域须在0~m-1之间
- 哈希函数计算出来的地址能均匀分布在整个空间
- 哈希函数应该比较简单
常见的哈希函数：
- 直接定址法（下面介绍）
- 取关键码的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要提前知道关键码的分布情况
场景：适用于查找范围比较小且连续的情况
- 除留余数法（下面介绍）
- 平方取中法--(了解) 假设关键字为1234，对它平方就是1522756，抽取中间的3位227作为哈希地址；再比如关键字为4321，对它平方就是18671041，抽取中间的3位671(或710)作为哈希地址。平方取中法比较适合：不知道关键码的分布，而位数又不是很大的情况
- 折叠法--(了解) 折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加求和，并按散列表表长，取后几位作为散列地址。 折叠法适合事先不需要知道关键码的分布，适合关键码位数比较多的情况
- 随机数法--(了解) 选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为随机数函数。通常应用于关键码长度不等时采用此法
- 数学分析法等
以上提到的各种哈希函数设计的越精妙，产生哈希冲突的可能性就越小，但是无法避免哈希冲突。那哈希冲突是什么呢？
<font size=4 color="red">当关键码映射到的位置上有元素时，即不同的元素映射到相同的位置时，这里称哈希冲突或哈希碰撞。</font>
解决哈希冲突有两种常见方法：闭散列和开散列。即是其哈希表结构两种主要方式，一是闭散列又称开放定址法，当发生哈希冲突时，若表中还有位置，就往表中的空位置去填；<font color="red" size=4>二是开散列又称链地址法，首先通过哈希函数对插入元素的关键码进行计算并放置对应的位置上，当发生哈希冲突时，把具有相同地址的关键码归于同一子集即以单链表的方式链接起来，表头在哈希表中，这样的相同关键码的元素集合称为哈希桶。</font>，下面着重介绍这两种方式。
闭散列
直接定址法
根据已知对象转化为整形，已知整形的范围，开辟一定大小的连续空间（比如vector）按照连续空间的下标与数据一一映射。一般用于整形，且数据范围相对集中。
如下图，把数据存入vector中，按照数据和vector的下标（这里把下标看作hashi）进行一一映射。第二种情况，插入1和99999时，只插入了2个数据，但是要开辟将近10w个int的空间，造成了极大的空间浪费。若数据不是整形，那么数据通过hashfun函数进行转化后，若整形大小不可控制，那么数据的范围更加不可控。
image-20230416203808839
综上得出结论：直接定址法只适用于数据是整形且数据范围相对集中的情况。
除留余数法
把传进来的关键码key%表的size即hashi=key%_table.size()，得到的hashi就是映射的位置。
如17%10=7，那么映射的位置是7，当27来的时候27%10=7，但7位置上有数据了，这时候就往后找，到下标为8的位置存下，依次来8，28来的时候后半段的位置都有数据了，就跳到最前面去找。
image-20230416204936581
动图所示，当hashi映射到的位置上有元素时，即不同的值映射到相同的位置时，这里称哈希冲突或哈希碰撞。然后按照hashi一个个往后寻找空位置存放，这样探测空间的方法叫<font size=4 color="red">线性探测法</font>。
除留余数法2
实现
仿函数
由于散列表需要将对象转化为整形进行对空间上的位置一一映射，那么当传过来的对象是整形时，可以强转成统一整形（size_t)。但传过来的对象不是整形时，就需要对对象配套算法，该算法可以把对象转化成整形。这里需要一个仿函数把传过来的对象的key转化为整形——我称为HashFunc函数。
假设传过来的是对象的key是string，可以把字符串的每个字符的ASCII码值相加成整形。但对于类似"abc","bac","cba"，这样的字符串就很容易发生冲突。参照大佬的方法，我用了BKDR哈希。BKDR哈希函数
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;//能转化为整形的对象强制转化为无符号整形
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t ch = 0;
for (auto e : s)
{
ch *= 131;//BKDR哈希
ch += e;
}
return ch;
}
};哈希节点
这里的节点有三种形态：存在EXIST，空EMPTY，删除DELETE
由于我这里的哈希表底层是用的vector，若删除元素则损耗很大，所以用伪删除法：在被删除元素的位置上标记为DELETE。
节点里存一个键值对对象和一个状态
enum State//状态
{
EMPTY,
EXIST,
DELETE,
};
template<class K,class V>
struct HashNode
{
pair<K, V> _kv;
State _state = EMPTY;
};Find函数
这里是返回元素节点的地址。
上层传过来键值key，然后根据key去表里面找已经存在的元素，如果元素状态不为空就一直找,当元素的键值==key并且元素的状态是EXIST时，才算是找到，返回元素节点的地址。
哈希Find函数
node* Find(const K& key)
{
HashF hf;
size_t hashi =hf( key) % _table.size();
size_t starti = hashi;
while (_table[hashi]._state != EMPTY)
{
if (_table[hashi]._state==EXIST &&_table[hashi]._kv.first == key)
{
return &_table[hashi];
}else
{
hashi++;
hashi %= _table.size();
if (starti == hashi)//防止极端情况：当哈希表中不是删除位就是存在位时，没有空位，这里就出不去，死循环了--所以这里表走了一圈就得出去了
break;
}
}
return nullptr;
}Insert函数
既然底层用的是vector，那么扩容是不可避免的。那什么时候扩容最好呢？一定空间上，插入的元素越多，元素发生哈希冲突的概率就越大。这里引出一个载荷因子的概念载荷因子a=表内元素个数/散列表的长度。当a越大，表明表内原有元素个数越多，插入新元素发生哈希冲突的概率越大。反之，当a越小，表明表内原有元素个数越少，插入新元素发生哈希冲突的概率越小。
根据大佬们的统计计算，载荷因子应严格限制在0.7-0.8，超过0.8查表的CPU缓冲不命中率按指数函数上升。如JAVA库中载荷因子就为0.75，超过此值就resize散列表。
这里我规定载荷因子a=0.7,超过0.7就扩容；
扩容也有不同的实现方式，我这里是新建个表，扩容时，新表先扩容为旧表的二倍，然后遍历旧表，当遇到的元素状态为EXIST时，可以复用哈希表的Insert函数，最后把新表和旧表的指向交换。
bool Insert(const pair<K, V>& kv)
{
auto cur = Find(kv.first);
if (cur)
{
//不为空--找到了
return false;
}
HashF hf;
if (_n * 10 / _table.size() > 7)//负载因子大于0.7时，需要扩容
{
HashTable<K, V> newHT;
newHT._table.resize(2 * _table.size());//扩容二倍
for (auto& e : _table)
{
if(e._state==EXIST)
newHT.Insert(e._kv);
}
_table.swap(newHT._table);
}
size_t hashi =hf( kv.first) % _table.size();
while (_table[hashi]._state == EXIST)
{
hashi++;
hashi %= _table.size();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
_n++;
return true;
}整体代码
这里我用的底层是vector，所以拷贝构造，析构函数等都不需要去手搓实现了，但是内置类型_n记得初始化。
enum State//状态
{
EMPTY,
EXIST,
DELETE,
};
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t ch = 0;
for (auto e : s)
{
ch *= 131;
ch += e;
}
return ch;
}
};
template<class K,class V>
struct HashNode
{
pair<K, V> _kv;
State _state = EMPTY;
};
template<class K, class V,class HashF=HashFunc<K>>
class HashTable
{
typedef HashNode<K,V> node;
public:
HashTable()
:_n(0)
{
_table.resize(10);
}
bool Insert(const pair<K, V>& kv)
{
auto cur = Find(kv.first);
if (cur)
{
//不为空--找到了
return false;
}
HashF hf;
if (_n * 10 / _table.size() > 7)//负载因子大于0.7时，需要扩容
{
HashTable<K, V> newHT;
newHT._table.resize(2 * _table.size());//扩容二倍
for (auto& e : _table)
{
if(e._state==EXIST)
newHT.Insert(e._kv);
}
_table.swap(newHT._table);
}
size_t hashi =hf( kv.first) % _table.size();
while (_table[hashi]._state == EXIST)
{
hashi++;
hashi %= _table.size();
}
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
_n++;
return true;
}
node* Find(const K& key)
{
HashF hf;
size_t hashi =hf( key) % _table.size();
while (_table[hashi]._state != EMPTY)
{
if (_table[hashi]._state==EXIST &&_table[hashi]._kv.first == key)
{
return &_table[hashi];
}else
{
hashi++;
hashi %= _table.size();
}
}
return nullptr;
}
bool Erase(const K& key)//删除元素用伪删除法---把元素的状态置为DELETE
{
node* cur = Find(key);
if (cur)
{
cur->_state = DELETE;
_n--;
return true;
}
else
{
return false;
}
}
private:
vector<node> _table;
size_t _n = 0;
};二次探测
上面用的是线性探测，本质是从起点start+i这样依次往后探测，这样容易导致表中某一部分数据相对集中，冲突的话容易导致所有的冲突在一起。：不同的关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低了。在这方面稍稍比线性好一点的是二次探测。从起点start+i^2这样探测，如图展示
哈希二次探测
根据大佬的研究表明：当表的长度为质数且表装载因子a不超过0.5时，新的表项一定能够插入，而且任何一个位置都不会被探查两次。因此只要表中有一半的空位置，就不会存在表满的问题。在搜索时可以不考虑表装满的情况，但在插入时必须确保表的载荷因子a不超过0.5，如果超出必须考虑增容。
即使是这样，也避免不了闭散列的缺陷：空间利用率比较低！因此也引出了另一种哈希表结构---开散列。
开散列
如同前面提到的定义：
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
闭散列法中哈希表的位置存的是对象，而开散列表中的位置存的是指针，可以把开散列表看作成指针数组。未被插入的位置初初始化成空。
仿函数
这里的仿函数和闭散列那里的一样，都需要针对对象通过仿函数来转化成整形去映射。
template<class K>
struct HashFunc
{
size_t operator()(const K& key)
{
return (size_t)key;//能转化为整形的对象强制转化为无符号整形
}
};
template<>
struct HashFunc<string>
{
size_t operator()(const string& s)
{
size_t ch = 0;
for (auto e : s)
{
ch *= 131;//BKDR哈希
ch += e;
}
return ch;
}
};节点
这里的节点不像闭散列那样，有个状态用来标记，这里删除可以直接删了，多了个next指针用来连接发生哈希冲突的元素。
template<class K,class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K,V>& kv)
:_kv(kv)
,_next(nullptr)
{}
};Find函数
这里的Find函数就需要到表上的位置的桶里面去遍历
node* Find(const K& key)
{
size_t hashi = HashF()(key) % _tables.size();
node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)//找到了--返回节点的地址
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;//没找到返回空
}Insert函数
当插入元素时，通过哈希函数计算关键码对应的地址位置，然后进行头插。当发生哈希冲突时，继续往该位置头插元素，并用单链表把发生哈希冲突的元素链接起来。
如动图所示
哈希桶插入动图
代码如下
在实现闭散列表时为了降低载荷因子减少哈希冲突的几率，所以设置载荷因子为0.7。而在开散列表，可以允许发生哈希冲突，当冲突时就以哈希桶的方式（单链表）链接起来，这里的载荷因子设置成1。
当载荷因子为1时，再插入元素就要扩容了，这里的扩容用的和闭散列表中的方法一样。创建了一个节点，然后拿着旧表节点的值去创建新表的节点，这样效率颇低。
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))//找到了不为空
return false;
//没找到则插入
if (_n == _tables.size())//载荷因子为1---满了扩容
{
//扩容旧方法
BucketHash<K, V> newHT;
newHT._tables.resize(2 * _tables.size());//扩容二倍
for (auto cur : _tables)
{
while (cur)//桶不为空
{
newHT.Insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(newHT._tables);
}
size_t hashi = HashF()(kv.first) % _tables.size();
node* newnode = new node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
}这里依次插入 17,27,8,28,22 ,23,24,25,35,45,11,11,28,5这些值，通过调试观察
扩容前 元素为45的地址是0x0134f108,元素为35的地址是0x0134f140,元素为25的地址是0x0134f648。
image-20230418164851031
扩容前 元素为45的地址是0x0134f450,元素为35的地址是0x0134f220,元素为25的地址是0x0134f098。这里扩容前后节点的地址改变了，说明新表里的是新创建的节点。
image-20230418165008189
扩容新方法：可以把旧表的节点挪到新表新映射的位置上去，这样就省去了创建了新节点又析构旧节点这样的消耗。
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))//找到了不为空
return false;
//没找到则插入
if (_n == _tables.size())//载荷因子为1---满了扩容
{
//旧方法
/*BucketHash<K, V> newHT;*/
//newHT._tables.resize(2 * _tables.size());//扩容二倍
//for (auto cur : _tables)
//{
// while (cur)//桶不为空
// {
// newHT.Insert(cur->_kv);
// cur = cur->_next;
// }
//}
//_tables.swap(newHT._tables);
vector<node*> newtables;
newtables.resize(2 * _tables.size());
for (size_t i = 0; i < _tables.size(); i++)
{
node* cur = _tables[i];
while (cur)
{
node* next =cur->_next ;
size_t hashi = HashF()(cur->_kv.first) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = HashF()(kv.first) % _tables.size();
node* newnode = new node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
}这里依次插入 17,27,8,28,22 ,23,24,25,35,45,11,11,28,5这些值，通过调试观察
扩容前 元素为45的地址是0x0181f6e8,元素为35的地址是0x0181f800,元素为25的地址是0x0181f410。
image-20230418163659454
扩容后， 元素为45的地址是0x0181f6e8,元素为35的地址是0x0181f800,元素为25的地址是0x0181f410。说明节点（地址）并没有被改变，而是从旧表转移到了新表。
image-20230418164052115
Erase函数
这里的Erase函数也是需要到表上的位置的桶里去找，找到就删除。
bool Erase(const K& key)
{
size_t hashi = HashF()(key) % _tables.size();
node* cur = _tables[hashi];
node* prev = nullptr;
while (cur)
{
if (cur->_kv.first == key)
{
if (cur == _tables[hashi])//如果找到的是哈希桶的第一个元素
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}析构函数
这里开散列表和闭散列相同的是底层都是vector存储元素，而闭散列存储的是对象，析构时调用vector的析构函数即可。而开散列存储的是指针，默认析构函数会把表内的指针析构掉，但不会去到哈希桶里把节点析构掉，所以在开散列这里的析构函数需要写。
~BucketHash()
{
for (size_t i = 0; i < _tables.size(); i++)
{
node* prev = nullptr;
node* cur = _tables[i];
while (cur)
{
node* prev = cur;
cur = cur->_next;
delete prev;
}
_tables[i] = nullptr;
}
}再谈扩容
上面Insert函数当载荷因子达到一时，就需要扩容，上面实现的是阔为原来空间的二倍。而大佬设计为除留余数法 阔容则是：最好模一个素数(每次扩容时选一个最近的素数)，如何每次快速取一个类似两倍关系的素数：在ST sgi版本中有素数表(用于增容) ul: unsigned long
size_t GetNextPrime(size_t prime)
{
const int PRIMECOUNT = 28;
static const size_t primeList[PRIMECOUNT] =
{
53ul, 97ul, 193ul, 389ul, 769ul,
1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
1572869ul, 3145739ul, 6291469ul, 12582917ul,
25165843ul,
50331653ul, 100663319ul, 201326611ul, 402653189ul,
805306457ul,
1610612741ul, 3221225473ul, 4294967291ul
};
size_t i = 0;
for (; i < PRIMECOUNT; ++i)
{
if (primeList[i] > prime)
return primeList[i];
}更改后的Insert函数
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))//找到了不为空
return false;
//没找到则插入
if (_n == _tables.size())//载荷因子为1---满了扩容
{
//旧方法
BucketHash<K, V> newHT;
newHT._tables.resize(__stl_next_prime(_n));//扩容二倍
for (auto cur : _tables)
{
while (cur)//桶不为空
{
newHT.Insert(cur->_kv);
cur = cur->_next;
}
}
_tables.swap(newHT._tables);
/* vector<node*> newtables;
newtables.resize(2 * _tables.size());
for (size_t i = 0; i < _tables.size(); i++)
{
node* cur = _tables[i];
while (cur)
{
node* next =cur->_next ;
size_t hashi = HashF()(cur->_kv.first) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}*/
//_tables.swap(newtables);
}
size_t hashi = HashF()(kv.first) % _tables.size();
node* newnode = new node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
}
//扩容函数素数表---用内联函数展开
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
};
for (int i = 0; i < __stl_num_primes; ++i)
{
if (__stl_prime_list[i] > n)
{
return __stl_prime_list[i];
}
}
return __stl_prime_list[__stl_num_primes - 1];
}整体代码
template<class K,class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K,V>& kv)
:_kv(kv)
,_next(nullptr)
{}
};
template<class K,class V,class HashF=HashFunc<K>>
class BucketHash
{
typedef HashNode<K, V> node;
public:
BucketHash()
:_n(0)
{
_tables.resize(__stl_next_prime(0));
}
~BucketHash()
{
for (size_t i = 0; i < _tables.size(); i++)
{
node* prev = nullptr;
node* cur = _tables[i];
while (cur)
{
node* prev = cur;
cur = cur->_next;
delete prev;
}
_tables[i] = nullptr;
}
}
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
};
for (int i = 0; i < __stl_num_primes; ++i)
{
if (__stl_prime_list[i] > n)
{
return __stl_prime_list[i];
}
}
return __stl_prime_list[__stl_num_primes - 1];
}
bool Insert(const pair<K, V>& kv)
{
if (Find(kv.first))//找到了不为空
return false;
//没找到则插入
if (_n == _tables.size())//载荷因子为1---满了扩容
{
//旧方法
/*BucketHash<K, V> newHT;
newHT._tables.resize(__stl_next_prime(_n));//扩容二倍
for (auto cur : _tables)
{
while (cur)//桶不为空
{
newHT.Insert(cur->_kv);
cur = cur->_next;
}
}*/
// _tables.swap(newHT._tables);
vector<node*> newtables;
newtables.resize(__stl_next_prime(_n));
for (size_t i = 0; i < _tables.size(); i++)
{
node* cur = _tables[i];
while (cur)
{
node* next =cur->_next ;
size_t hashi = HashF()(cur->_kv.first) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = HashF()(kv.first) % _tables.size();
node* newnode = new node(kv);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return true;
}
node* Find(const K& key)
{
size_t hashi = HashF()(key) % _tables.size();
node* cur = _tables[hashi];
while (cur)
{
if (cur->_kv.first == key)//找到了--返回节点的地址
{
return cur;
}
else
{
cur = cur->_next;
}
}
return nullptr;//没找到返回空
}
bool Erase(const K& key)
{
size_t hashi = HashF()(key) % _tables.size();
node* cur = _tables[hashi];
node* prev = nullptr;
while (cur)
{
if (cur->_kv.first == key)
{
if (cur == _tables[hashi])//如果找到的是哈希桶的第一个元素
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
size_t _n = 0;
vector<node*> _tables;
};用哈希表封装Unordered_map和Unordered_set
取key
由于Unordered_map的值是键值对pair<const K,V>,取出的关键码是pair里面的K的对象。而Unordered_set的值就是K，取出的关键码就是K的对象，这两者不同，所以要再上层Unordered_map和Unordered_set通过模板参数传进去各自的关键码key
Unordered_map的取key函数
struct KeyofMap
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};Unordered_set的取key函数
struct KeyofSet
{
const K& operator()(const K& key)
{
return key;
}
};迭代器
迭代器需要用一个类来实现
框架
template<class K, class T,class HashF, class KeyofT>
class BucketHash;//前置声明---迭代器需要用到哈希表的成员
template<class K,class T,class HashF,class KeyofT>
struct __HTIterator
{
//public:
typedef __HTIterator<K, T, HashF, KeyofT> Self;//迭代器
typedef HashNode<T> node;//节点
typedef BucketHash<K, T, HashF, KeyofT> HT;//哈希表
HT* _ht;
node* _node;
__HTIterator(node* pnode,HT* ht)
//需要传节点的指针和哈希表的指针过来构造
:_node(pnode)
,_ht(ht)
{}
};operator++
先遍历当前桶，当当前桶的此节点的下一个节点不为空时，就取下一个节点。当当前桶为空时，先计算当前桶位于哈希表的哪个位置，然后往后到遍历不为空的桶。
Self& operator++()
{
//当前桶没遍历完
if (_node->_next)
{
_node = _node->_next;
}
else//当前桶遍历完了，遍历后面的桶
{
KeyofT kot;
size_t hashi = HashF()(kot(_node->_Data))%_ht->_tables.size();//算出当前桶的位置
hashi++;
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
else
{
hashi++;
}
}
if(hashi==_ht->_tables.size())
_node = nullptr;
}
return *this;
}迭代器整体代码
template<class K, class T,class HashF, class KeyofT>
class BucketHash;//前置声明---迭代器需要用到哈希表的成员
template<class K,class T,class HashF,class KeyofT>
struct __HTIterator
{
//public:
typedef __HTIterator<K, T, HashF, KeyofT> Self;
typedef HashNode<T> node;
typedef BucketHash<K, T, HashF, KeyofT> HT;
HT* _ht;
node* _node;
__HTIterator(node* pnode,HT* ht)
:_node(pnode)
,_ht(ht)
{}
T& operator*()const
{
return _node->_Data;
}
T* operator->()const
{
return &_node->_Data;
}
Self& operator++()
{
//当前桶没遍历完
if (_node->_next)
{
_node = _node->_next;
}
else//当前桶遍历完了，遍历后面的桶
{
KeyofT kot;
size_t hashi = HashF()(kot(_node->_Data))%_ht->_tables.size();//算出当前桶的位置
hashi++;
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
else
{
hashi++;
}
}
if(hashi==_ht->_tables.size())
_node = nullptr;
}
return *this;
}
bool operator!=(const Self& s)const
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}
};begin
取哈希表内从头到尾遍历到的第一个不为空的位置，若遍历完了，就返回空（构造end）
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
node* cur = _tables[i];
if (cur)
{
return iterator(cur, this);
}
}
return iterator(nullptr, this);
}end
用空节点来构造
iterator end()
{
return iterator(nullptr, this);
}为了封装，哈希表部分也进行了变动
主要变动的部分
转化key
image-20230419211548277
取关键字过程（附转化成整形过程）
image-20230419213348437
哈希表整体代码
template<class T>
struct HashNode
{
T _Data;
HashNode<T>* _next;
HashNode(const T& Data)
:_Data(Data)
,_next(nullptr)
{}
};
template<class K, class T,class HashF, class KeyofT>
class BucketHash;
template<class K,class T,class HashF,class KeyofT>
struct __HTIterator
{
//public:
typedef __HTIterator<K, T, HashF, KeyofT> Self;
typedef HashNode<T> node;
typedef BucketHash<K, T, HashF, KeyofT> HT;
HT* _ht;
node* _node;
__HTIterator(node* pnode,HT* ht)
:_node(pnode)
,_ht(ht)
{}
T& operator*()const
{
return _node->_Data;
}
T* operator->()const
{
return &_node->_Data;
}
Self& operator++()
{
//当前桶没遍历完
if (_node->_next)
{
_node = _node->_next;
}
else//当前桶遍历完了，遍历后面的桶
{
KeyofT kot;
size_t hashi = HashF()(kot(_node->_Data))%_ht->_tables.size();//算出当前桶的位置
hashi++;
while (hashi < _ht->_tables.size())
{
if (_ht->_tables[hashi])
{
_node = _ht->_tables[hashi];
break;
}
else
{
hashi++;
}
}
if(hashi==_ht->_tables.size())
_node = nullptr;
}
return *this;
}
bool operator!=(const Self& s)const
{
return _node != s._node;
}
bool operator==(const Self& s)const
{
return _node == s._node;
}
};
template<class K, class T, class HashF, class KeyofT>
class BucketHash
{
typedef HashNode<T> node;
template<class K, class T, class HashF, class KeyofT>
friend struct __HTIterator;
public:
typedef __HTIterator<K, T,HashF,KeyofT> iterator;
iterator begin()
{
for (size_t i = 0; i < _tables.size(); i++)
{
node* cur = _tables[i];
if (cur)
{
return iterator(cur, this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
BucketHash()
:_n(0)
{
_tables.resize(__stl_next_prime(0));
}
~BucketHash()
{
for (size_t i = 0; i < _tables.size(); i++)
{
node* prev = nullptr;
node* cur = _tables[i];
while (cur)
{
node* prev = cur;
cur = cur->_next;
delete prev;
}
_tables[i] = nullptr;
}
}
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
};
for (int i = 0; i < __stl_num_primes; ++i)
{
if (__stl_prime_list[i] > n)
{
return __stl_prime_list[i];
}
}
return __stl_prime_list[__stl_num_primes - 1];
}
pair<iterator,bool> Insert(const T& Data)
{
KeyofT kot;
iterator cur = Find(kot(Data));
if (cur != end())
{
return make_pair(cur, false);
}
//没找到则插入
if (_n == _tables.size())//载荷因子为1---满了扩容
{
//旧方法
//BucketHash<K, T,> newHT;
//newHT._tables.resize(__stl_next_prime(_n));//扩容二倍
//for (auto cur : _tables)
//{
// while (cur)//桶不为空
// {
// newHT.Insert(cur->_Data);
// cur = cur->_next;
// }
//}
//_tables.swap(newHT._tables);
vector<node*> newtables;
newtables.resize(__stl_next_prime(_n));
for (size_t i = 0; i < _tables.size(); i++)
{
node* cur = _tables[i];
while (cur)
{
node* next =cur->_next ;
size_t hashi = HashF()(kot(cur->_Data)) % newtables.size();
cur->_next = newtables[hashi];
newtables[hashi] = cur;
cur = next;
}
_tables[i] = nullptr;
}
_tables.swap(newtables);
}
size_t hashi = HashF()(kot(Data)) % _tables.size();
node* newnode = new node(Data);
newnode->_next = _tables[hashi];
_tables[hashi] = newnode;
++_n;
return make_pair(iterator(_tables[hashi],this),true);
}
iterator Find(const K& key)
{
KeyofT kot;
size_t hashi = HashF()(key) % _tables.size();
node* cur = _tables[hashi];
while (cur)
{
if ( kot(cur->_Data) == key)//找到了--返回节点的地址
{
return iterator(cur,this);
}
else
{
cur = cur->_next;
}
}
return iterator( nullptr,this);//没找到返回空
}
bool Erase(const K& key)
{
KeyofT kot;
size_t hashi = HashF()(key) % _tables.size();
node* cur = _tables[hashi];
node* prev = nullptr;
while (cur)
{
if ( kot(cur->_Data)== key)
{
if (cur == _tables[hashi])//如果找到的是哈希桶的第一个元素
{
_tables[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
--_n;
delete cur;
return true;
}
else
{
prev = cur;
cur = cur->_next;
}
}
return false;
}
private:
size_t _n = 0;
vector<node*> _tables;
};封装后的哈希表const迭代器不能复用普通迭代器
封装后，可以看到迭代器只实现了普通迭代器，并没有用普通迭代器复用实现const迭代器，参考stl库源码
image-20230419215339076
image-20230419221057838
Unordered_map 整体代码
template<class K,class V,class HashF= HashFunc<K>>
class Unordered_Map
{
struct KeyofMap
{
const K& operator()(const pair<const K, V>& kv)
{
return kv.first;
}
};
typedef typename BUCKET::BucketHash<K, pair<const K, V>, HashF, KeyofMap>::iterator iterator;
public:
iterator begin()
{
return _mp.begin();
}
iterator end()
{
return _mp.end();
}
pair<iterator,bool> Insert(const pair<K, V>& kv)
{
return _mp.Insert(kv);
}
iterator Find(const K& key)
{
return _mp.Find(key);
}
bool Erase(const K& key)
{
return _mp.Erase(key);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _mp.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
BUCKET::BucketHash<K,pair<const K,V> , HashF ,KeyofMap> _mp;
};Unordered_map整体代码
template<class K,class HashF=HashFunc<K>>
class Unordered_Set
{
struct KeyofSet
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename BUCKET::BucketHash<K,K, HashF, KeyofSet>::iterator iterator;
iterator begin()
{
return _st.begin();
}
iterator end()
{
return _st.end();
}
pair<iterator,bool> Insert(const K& key)
{
return _st.Insert(key);
}
iterator Find(const K& key)
{
return _st.Find(key);
}
bool Erase(const K& key)
{
return _st.Erase(key);
}
private:
BUCKET::BucketHash<K, K, HashF, KeyofSet> _st;
};原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
容器服务
腾讯云容器服务（Tencent Kubernetes Engine, TKE）基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务，覆盖 Serverless、边缘计算、分布式云等多种业务部署场景，业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者，主导开源项目Crane，全面助力客户实现资源优化、成本控制。
腾讯云开发者
