C++——哈希
目录
unordered系列关联式容器
unordered_mapunordered_map在线文档说明
unordered_map的接口说明
unordered系列优势
哈希
解决哈希冲突
1.闭散列——开放定址法
思考：哈希表什么情况下进行扩容？如何扩容？
插入元素代码
查找元素
删除元素
用哈希统计某元素出现次数
编辑
闭散列——线性探测完整代码
线性探测缺陷
开散列
拉链法（哈希桶）
插入
查找元素
删除
完整代码
unordered系列关联式容器
在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$log_2
N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好
的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同。
unordered_map
unordered_map在线文档说明
1. unordered_map是存储
其对应的value， unordered_map/ unordered_set都是无序的。
2. 在unordered_map中，键值通常用于惟一地标识元素，而映射值是一个对象，其内容与此
键关联。键和映射值的类型可能不同。
3. 在内部,unordered_map没有对
找到key所对应的value，unordered_map将相同哈希值的键值对放在相同的桶中。
4. unordered_map容器通过key访问单个元素要比map快，但它通常在遍历元素子集的范围迭
代方面效率较低。
5. unordered_maps实现了直接访问操作符(operator[])，它允许使用key作为参数直接访问
value。
6. 它的迭代器至少是前向迭代器
unordered_map的接口说明
1. unordered_map的构造
| 函数声明 | 功能介绍 |
| unordered_map | 构造不同格式的unordered_map对象 |
2. unordered_map的容量
| 函数声明 | 功能介绍 |
| bool empty() const | 检测unordered_map是否为空 |
| size_t size() const | 获取unordered_map的有效元素个数 |
3. unordered_map的迭代器
| 函数声明 | 功能介绍 |
| begin | 返回unordered_map第一个元素的迭代器 |
| end | 返回unordered_map最后一个元素下一个位置的迭代器 |
| cbegin | 返回unordered_map第一个元素的const迭代器 |
| cend | 返回unordered_map最后一个元素下一个位置的const迭代器 |
力扣
class Solution {
public:int repeatedNTimes(vector& nums) {unordered_map countMap;for(auto e:nums)countMap[e]++;for(auto& kv:countMap){if(kv.second==nums.size()/2)return kv.first;}return 0;}
}; 最后如果不写这个return 0就会报错，这是编译错误，可能会在vs下正常跑，但是在这里会报错，所以要在最后面加return
对比map和set的区别：
1.map和set遍历是有序的，unordered系列是无序的
2.map和set是双向迭代器，unordered系列是单向的
unordered系列在面对大量数据时，增删查改的效率更优，尤其是查
力扣：找交集
class Solution {
public:vector intersection(vector& nums1, vector& nums2) {unordered_set s1;for(auto e:nums1){s1.insert(e);}unordered_set s2;for(auto e:nums2){s2.insert(e);}vector A;for(auto e:s1){if(s2.find(e)!=s2.end())A.push_back(e);}return A;}
}; 这里插入的时候就会去重
unordered系列优势
10000个数据进行插入时，set快，查找的时候unordered_set快，删除的时候set快
十万个数据时，size是插入的值，因为可能有重复的，所以不是十万。数据较大时，unordered系列的优势便显现出来了。
当六百多万数据时，unordered_set的插入就比较慢
比较程序
void test_op()
{int n = 1000000;vector v;v.reserve(n);srand(time(0));for (int i = 0; i < n; ++i){//v.push_back(i);v.push_back(rand() + i); // ظ//v.push_back(rand()); // ظ}size_t begin1 = clock();set s;for (auto e : v){s.insert(e);}size_t end1 = clock();size_t begin2 = clock();unordered_set us;for (auto e : v){us.insert(e);}size_t end2 = clock();cout << "size:" << s.size() << endl;cout << "set insert:" << end1 - begin1 << endl;cout << "unordered_set insert:" << end2 - begin2 << endl;size_t begin3 = clock();for (auto e : v){s.find(e);}size_t end3 = clock();size_t begin4 = clock();for (auto e : v){us.find(e);}size_t end4 = clock();cout << "set find:" << end3 - begin3 << endl;cout << "unordered_set find:" << end4 - begin4 << endl;size_t begin5 = clock();for (auto e : v){s.erase(e);}size_t end5 = clock();cout << "set erase" << endl;size_t begin6 = clock();for (auto e : v){us.erase(e);}size_t end6 = clock();cout << "unordered_set erase" << endl;cout << "set erase:" << end5 - begin5 << endl;cout << "unordered_set erase:" << end6 - begin6 << endl;unordered_map countMap;countMap.insert(make_pair("ƻ", 1));
}
哈希
哈希也叫做散列，本质是让值跟存储位置建立映射的关联关系。
顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素
时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即
O($log_2 N$)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。
如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立
一一映射的关系，那么在查找时通过该函数可以很快找到该元素
当向该结构中：
插入元素
根据待插入元素的关键码，以此函数计算出该元素的存储位置并按此位置进行存放
搜索元素
对元素的关键码进行同样的计算，把求得的函数值当做元素的存储位置，在结构中按此位置
取元素比较，若关键码相等，则搜索成功
该方式即为哈希(散列)方法，哈希方法中使用的转换函数称为哈希(散列)函数，构造出来的结构称
为哈希表(Hash Table)(或者称散列表)
例如：数据集合{1，7，6，4，5，9}；
哈希函数设置为：hash(key) = key % capacity; capacity为存储元素底层空间总的大小
用该方法进行搜索不必进行多次关键码的比较，因此搜索的速度比较快
但有个问题，如果有个300，400，这俩个映射道德位置都是0，就会出现不同的值映射相同的问题，这叫哈希冲突/哈希碰撞。
解决哈希冲突
1.闭散列——开放定址法
a.线性探测
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止
插入
通过哈希函数获取待插入元素在哈希表中的位置
如果该位置中没有元素则直接插入新元素，如果该位置中有元素发生哈希冲突，
使用线性探测找到下一个空位置，插入新元素
思考：哈希表什么情况下进行扩容？如何扩容？
负载因子越小：冲突的概率越小，反之，越大。负载因子到一个基准值就扩容，基准值越大，冲突越多，效率越低，空间利用率越高。
当扩容后，进行插入，插入则会变为这样
插入1 4 5 6 7 44 9，原表中是这样
我们设置的基准值为7，>=7的时候就插入，当插入9的时候就会扩容，扩容并不是直接把旧表拷贝下来，而是要找相对应的位置再插入元素。下图为新表部分数据，通过7和11还有5就可以看出不是直接拷贝的旧表。
插入元素代码
enum State//标志位的三种状态，空，存在，删除
{EMPTY,EXIST,DELETE
};
template
struct HashData//标志位
{pair _kv;State _state=EMPTY;
};
template
class HashTable
{
public:bool insert(const pair & kv){if (_table.size()==0||_size *10/ _table.size() >= 7)//负载因子大于7就扩容{//扩容不能直接开空间，拷贝数据，因为表大小变了，映射关系也变了，如10之前映射5，扩容后就不一定映射5size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;//vector> newTables;//建一张新表//newTables.resize(newSize);//让capacity和size保持一致旧表的数据映射到新表//for ()//{//}//_table.swap(newTables);//旧表和新表交换，这种方法有点繁琐//我们可创建一个哈希表,对哈希表里面的table进行resizeHashTable newHT;//创建一个跟自己类型相同的对象newHT._table.resize(newSize);for (auto e: _table){if (e._state == EXIST){newHT.insert(e._kv);//再调insert}_table.swap(newHT._table);//数据交换后，不需要对新表进行释放空间，因为_table是vector，它有自己的析构函数}}size_t hashi = kv.first % _table.size();//这里要对size取模，不能对容量capacity取模，访问的下标必须是在size范围以内//线性探测while (_table[hashi]._state==EXIST)//如果这个位置有值了{hashi++;//往后走找空位置hashi %= _table.size();//走到结尾之后要回到最初位置，这里不会存在死循环，因为前面有扩容}_table[hashi]._kv = kv;//找到空位置了，把值放进去_table[hashi]._state = EXIST;//修改状态；++_size;return true;}
private:vector > _table;size_t _size=0;//哈希表的有效数据，因为中间可能有空白间隔
}; 插入的时候负数也可以插入
查找元素
HashData* Find(const K& kv){if (_table.size() == 0)//表为空直接返回{return nullptr;}size_t hashi = kv % _table.size();while (_table[hashi]._state != EMPTY)//不为空就进行查找{size_t start = kv % _table.size();if (_table[hashi]._state!=DELETE&&_table[hahsi] == kv)//如果该位置既不是空也不是删除，且满足查找条件则返回该位置数值{return _table[hashi];}hashi++;hashi %= _table.size();if (hashi == start){break;//找了一圈了没找到，跳出循环}}return nullptr;} 删除元素
void Erase(const K& key){HashData* ret = Find(key);if (ret){ret->_state = DELETE;--_size;return true;}elsereturn false;} 用哈希统计某元素出现次数
void TestHT2()
{string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };HashTable countHT;for (auto& str : arr){auto ptr = countHT.Find(str);if (ptr){ptr->_kv.second++;}else{countHT.Insert(make_pair(str, 1));}}
} 
此时传的是string，在取模的时候会出现问题，C++在unordered_map中对这种问题有解决方法
这里的hash
我们增加一个哈希的仿函数
插入函数中，不要直接取模，先调用仿函数，再取模
find函数也一样
这是就是把key交给仿函数转换一下，但是string不支持转
方法一 写一个针对string的转换，把string转换为整形
这是把每个字符的ASCII码值加起来，然后返回去取模，但是在传参的时候要显示的去传
在unordered_map中用string去做Key，不需要仿函数
如果在使用哈希时，也不想每次都专门写一个仿函数，我们可以做特化
方法二 特化
如果是string， HashFunc会优先走特化版本
HashFunc改进
HashFunc里面的成员函数是把所有字母的ASCII码值加起来的，但是遇到下面这种
abcd,bcda,dbca情况HashFunc此时功能就不太完整。
我们采用BKDR的方式，对每次的值*131，这是大佬设计的一个算法，
这些值看起来都挺接近，但是都不一样，这样可以解决上面的问题
闭散列——线性探测完整代码
enum State//标志位的三种状态，空，存在，删除
{EMPTY,EXIST,DELETE
};
template
struct HashData//标志位
{pair _kv;State _state=EMPTY;
};//struct HashFuncString
//{
// size_t operator()(const string& key)
// {
// size_t val = 0;
// for (auto ch : key)
// {
// val += ch;
// }
// return val;
// }
//};
template
struct HashFunc
{size_t operator()(const K& key)//把key转成无符号整形{return (size_t)key;}
};
template<>
struct HashFunc
{size_t operator()(const string& key){size_t val = 0;for (auto ch : key){val *= 131;val += ch;}return val;}
};
template>
class HashTable
{
public:bool insert(const pair & kv){if (Find(kv.first)){return false;//该元素存在，就不插入了}if (_table.size()==0||_size *10/ _table.size() >= 7)//负载因子大于7就扩容{//扩容不能直接开空间，拷贝数据，因为表大小变了，映射关系也变了，如10之前映射5，扩容后就不一定映射5size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;//vector> newTables;//建一张新表//newTables.resize(newSize);//让capacity和size保持一致旧表的数据映射到新表//for ()//{//}//_table.swap(newTables);//旧表和新表交换，这种方法有点繁琐//我们可创建一个哈希表,对哈希表里面的table进行resizeHashTable newHT;//创建一个跟自己类型相同的对象newHT._table.resize(newSize);for (auto e: _table){if (e._state == EXIST){newHT.insert(e._kv);//再调insert}_table.swap(newHT._table);//数据交换后，不需要对新表进行释放空间，因为_table是vector，它有自己的析构函数}}Hash hash;size_t hashi =hash（ kv.first） % _table.size();//这里要对size取模，不能对容量capacity取模，访问的下标必须是在size范围以内//线性探测while (_table[hashi]._state==EXIST)//如果这个位置有值了{hashi++;//往后走找空位置hashi %= _table.size();//走到结尾之后要回到最初位置，这里不会存在死循环，因为前面有扩容}_table[hashi]._kv = kv;//找到空位置了，把值放进去_table[hashi]._state = EXIST;//修改状态；++_size;return true;}void Erase(const K& key){HashData* ret = Find(key);if (ret){ret->_state = DELETE;--_size;return true;}elsereturn false;}HashData* Find(const K& kv){if (_table.size() == 0)//表为空直接返回{return nullptr;}size_t hashi = kv % _table.size();Hash hash;size_t start = hash(key) % _table.size();while (_table[hashi]._state != EMPTY)//不为空就进行查找{size_t start = kv % _table.size();if (_table[hashi]._state!=DELETE&&_table[hahsi] == kv)//如果该位置既不是空也不是删除，且满足查找条件则返回该位置数值{return _table[hashi];}hashi++;hashi %= _table.size();if (hashi == start){break;//找了一圈了没找到，跳出循环}}return nullptr;}
private:vector > _table;size_t _size=0;//哈希表的有效数据，因为中间可能有空白间隔
};
void Test1()
{int a[] = {1,11,4,15,26,7,44,9};HashTable ht;for (auto e : a){ht.insert(make_pair(e, e));}
} 线性探测缺陷
若有这样一组值，线性探测在某个位置冲突很多的情况下，会互相占用，导致一大片出现冲突，如这里下标为2的位置被占用，2只能去占另外的位置，为了解决这种问题，有种解决方式叫二次探测
b.二次探测
一次探测是每次+i，二次探测是每次加i²，是相对于其实位置每次加i²，i开始是1，若每次计算完，那个地方有元素，则i变为2，
如这里插入12 12%10=2，2+2²
代码
Hash hash;szie_t start = hash（ kv.first） % _table.size();szie_t i = 0;size_t hashi=start+i;while (_table[hashi]._state==EXIST)//如果这个位置有值了{++ihashi=start+i*i;//往后走找空位置hashi %= _table.size();//走到结尾之后要回到最初位置，这里不会存在死循环，因为前面有扩容}_table[hashi]._kv = kv;//找到空位置了，把值放进去_table[hashi]._state = EXIST;//修改状态；++_size;二次探测仍然是占用式：这个地方被占了，我就去占其它地方。有种更好的办法叫拉链法
开散列
拉链法（哈希桶）
这个表是指针数组
当好多元素要填入同一个位置时，这个时候会把这些数据通过单链表连接起来，注意挂起来（挂起来的这一串数据可以看作是一个桶）的数据不一定有序，这里这是巧合 。
使用单链表的时间复杂度是O(N)，最极端情况要插入的数据都在同一个位置，在一个位置全部挂起来，这里由于控制了复杂因子，出现这种极坏的情况是极低的。即使出现了，也是小范围性的出现。
数据挂起来时采用头插，尾插都行，我们这里采用头插
插入
这里插入不能像前面那样复用Insert，因为会创建新节点，而且释放旧表又要写析构函数，比较麻烦，我们可以直接将旧表的桶搬下来，给新表使用，这里新表不手动释放原因，新表是一个局部变量，除了作用域后会空间会被释放
bool Insert(const pair& kv){//去重，如果有重复元素就不插入if (Find(kv.first))return false;//扩容，负载因子到1就扩容if (_size == _tables.size()){//这里不能复用Inert，因为会创建新节点，而且要写析构函数释放旧表size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector newTables;newTables.resize(newSize, nullptr);//旧表中的节点移动映射到新表for (size_t i=0;i<_tables.size();++i){Node* cur = _tables[i];while (cur){size_t hashi = cur->kv.first % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;//旧表中的桶置为空}_tables.swap(newTables);}size_t hashi = kv.first % _tables.size();//计算要插入元素的位置//头插 新节点->next指向头，之后更新头节点为新节点Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_size;return true;} 查找元素
Node* Find(const K& key){if (_tables.size() == 0){return nullptr;}size_t hashi = key % _table.size();//找到桶所在位置Node* cur = _tables[hashi];while (cur){if (key.first == cur->kv.first){return cur;}cur = cur->_next;}return nullptr;}进行插入测试，插入22的时候会进行扩容
原表：1：1和11是一个桶 6：26 9：99
4：14和4 7：7
5：55，15 8：78
增容映射后新表：把11直接挂到了11这个位置，1挂到1这个位置
删除
类似于链表的删除，不能直接用Find找到就删除，因为这里是单链表删除后还要把前后连接起来。
情况1 cur是第一个节点，prev是nullptr，这种情况需单独处理
情况2 下图最左边这种情况，只需让prev的next指向cur的next
bool Erase(const K& key){if (_tables.size() == 0)//如果该哈希表为空，就直接返回{return nullptr;}size_t hashi = key % _tables.size();Node* prev = nullptr;//要找的节点的前一个节点Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){//cur符合情况1if (prev == nullptr){_tables[hashi] = cur->_next;}//中间情况,情况2else{prev->_next = cur->_next;}delete cur;--_size;return true;}prev = cur;cur = cur->_next;}return false;}仿函数，跟前面一样需要增加一个仿函数，处理string类。
尽量让哈西表的大小是一个素数（这个优化不是必须的），这种情况下冲突会降低，STL源码中有素数表。
inline size_t __stl_next_prime(size_t n)//获取下一个素数{static const size_t __stl_num_primes = 28;static const size_t __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 (size_t i = 0; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return -1;}先测试1w个数据
void TestHT3(){int n = 10000;vector v;v.reserve(n);srand(time(0));for (int i = 0; i < n; ++i){v.push_back(rand()); // 重复多}size_t begin1 = clock();HashTable ht;for (auto e : v){ht.Insert(make_pair(e, e));}size_t end1 = clock();cout << "数据个数:" << ht.Size() << endl;cout << "表的长度:" << ht.TablesSize() << endl;cout << "桶的个数:" << ht.BucketNum() << endl;cout << "平均每个桶的长度:" << (double)ht.Size() / (double)ht.BucketNum() << endl;cout << "最长的桶的长度:" << ht.MaxBucketLenth() << endl;cout << "负载因子:" << (double)ht.Size() / (double)ht.TablesSize() << endl;
} 
大多数桶的长度是一俩个，最长的桶长度是2个
100w个数据
1000w
1500w
1600w
完整代码
#define _CRT_SECURE_NO_WARNINGS
template
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};template<>
struct HashFunc
{// BKDRsize_t operator()(const string& key){size_t val = 0;for (auto ch : key){val *= 131;val += ch;}return val;}
};namespace HashBucket
{templatestruct HashNode{pair _kv;HashNode* _next;HashNode(const pair& key):_kv(lv),_next(nullptr){}};template>class HashTable{~HashTable()//数组会被自动释放，可桶需要手动释放{for (size_t i = 0; i < _table.size(); ++i){Node* cur = _tables.size();while (cur){Node* next = cur->next;free(cur);cur = next;}_tables[i] = nullptr;}}typedef HashNode Node;public:inline size_t __stl_next_prime(size_t n)//获取下一个素数{static const size_t __stl_num_primes = 28;static const size_t __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 (size_t i = 0; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return -1;}bool Insert(const pair& kv){//去重，如果有重复元素就不插入if (Find(kv.first))return false;Hash hash;//扩容，负载因子到1就扩容if (_size == _tables.size()){//这里不能复用Inert，因为会创建新节点，而且要写析构函数释放旧表size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;vector newTables;newTables.resize(newSize, nullptr);//旧表中的节点移动映射到新表for (size_t i=0;i<_tables.size();++i){Node* cur = _tables[i];while (cur){size_t hashi = hash(cur->kv.first) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;}_tables[i] = nullptr;//旧表中的桶置为空}_tables.swap(newTables);}Hash hash;size_t hashi = hash(kv.first) % _tables.size();//计算要插入元素的位置//头插 新节点->next指向头，之后更新头节点为新节点Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_size;return true;}Node* Find(const K& key){if (_tables.size() == 0){return nullptr;}Hash hash;size_t hashi = hash(key) % _table.size();//找到桶所在位置Node* cur = _tables[hashi];while (cur){if (key.first == cur->kv.first){return cur;}cur = cur->_next;}return nullptr;}bool Erase(const K& key){if (_tables.size() == 0)//如果该哈希表为空，就直接返回{return nullptr;}Hash hash;size_t hashi = hash(key) % _tables.size();Node* prev = nullptr;//要找的节点的前一个节点Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){//cur符合情况1if (prev == nullptr){_tables[hashi] = cur->_next;}//中间情况,情况2else{prev->_next = cur->_next;}delete cur;--_size;return true;}prev = cur;cur = cur->_next;}return false;}//有效数据个数size_t Size(){return _size;}size_t BucketNum()//返回桶的数量{size_t num = 0;for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i]){++num;}}}//表的长度size_t TableSize(){return _tables.size();}size_t MaxBucketLenth(){size_t Maxlen = 0;for (size_t i = 0; i < _tables.size(); ++i){size_t len = 0;Node* cur = _tables[i];while (cur){++len;cur = cur->_next;}if(len>0)printf("[%d]号桶长度:%d\n", i, len);Maxlen = len > Maxlen ? len : Maxlen;}}private:vector _tables;size_t _size=0;//存储有效数据个数};
}
void TestHT3(){int n = 10000;vector v;v.reserve(n);srand(time(0));for (int i = 0; i < n; ++i){v.push_back(rand()); // 重复多}size_t begin1 = clock();HashTable ht;for (auto e : v){ht.Insert(make_pair(e, e));}size_t end1 = clock();cout << "数据个数:" << ht.Size() << endl;cout << "表的长度:" << ht.TablesSize() << endl;cout << "桶的个数:" << ht.BucketNum() << endl;cout << "平均每个桶的长度:" << (double)ht.Size() / (double)ht.BucketNum() << endl;cout << "最长的桶的长度:" << ht.MaxBucketLenth() << endl;cout << "负载因子:" << (double)ht.Size() / (double)ht.TablesSize() << endl;}