哈希结构

unordered系列的关联式容器之所以查找效率比较高，是因为其底层使用了哈希结构。

哈希映射，key值跟存储位置建立映射关系。

哈希表或散列表（一种存储结构），通过哈希函数或散列函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。

常见哈希函数

哈希函数设计原则：哈希函数的定义域必须包括需要存储的全部关键码，而如果散列表允许有m个地址时，其值域必须在0到m-1之间；哈希函数计算出来的地址能均匀分布在整个空间中；哈希函数应该比较简单。

1. 直接定址法–(常用)
   取关键字的某个线性函数为散列地址：Hash（Key）=A∗Key+BHash（Key）= A*Key + BHash（Key）=A∗Key+B

   优点：简单、均匀、无哈希冲突；
   缺点：需要事先知道关键字的分布情况，一堆整型值哈希映射到表，如果这些值太分散了（如2，3，12，9999），消耗空间太大；
   使用场景：适合查找整型、值小且连续的情况

2. 除留余数法–(常用)
   设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key % p (p<=m)，将关键码转换成哈希地址。有哈希冲突。一般p就取哈希表的size()。

   注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突。

哈希冲突

概念

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。简而言之是指不同的值映射到相同位置。把具有不同关键码而具有相同哈希地址的数据元素称为“同义词”。

如下一组数据3、5、7、12、999、13，当采用除留余数法时，取p=10，Hash(key) = Key % p，(p<=m)，当遇到3和13时，3%10=3，13%10=3，那这个哈希映射对于的位置到底存3还是存13呢？

解决方法一：闭散列

也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把key存放到冲突位置中的“下一个” 空位置中去。闭散列是不会让存储空间为满的状态，依靠负载因子来判断是否满了。

哈希表中的存储节点结构定义为

enum State
{EMPTY,//该位置为空，可以存放新keyEXIST,//该位置已经记录了keyDELETE,//该位置数据被删除，可以存放新key
};template
struct HashData
{std::pair _kv;State _state;//要用来标记该位置的状态，用于停止搜索的逻辑判断，当状态为
};

根据key找映射位置

key为整型等

当Key为整型值时，找对应的映射位置方法：Hash（Key）= Key % _table.size()。此处用size不能用capapcity，因为后续用下标来访问对应位置的数据时，operator[]会强制检查访问的位置是否超出有效数据范围size，在实际应用中，一般会让size==capacity，避免空间浪费。

key为字符型–BKDR思路

当Key为其他类型时，需要进行二次映射，此时借助仿函数强制转换来完成。BKDR思路

template<>//特化
struct HashFunc
{size_t operator()(const std::string& key){size_t hash = 0;for (auto ch : key){hash *= 131;//BKDR思路 每次的结果31、131、13131...hash += ch;}return hash;}
};

采用闭散列处理哈希冲突时，不能随便物理删除哈希表中已有的元素，若直接删除元素会影响其他元素的搜索，因此线性探测采用标记的伪删除法来删除一个元素，即状态置为DELETE。

负载因子–控制扩容

散列表的载荷因子定义为: a = 填入表中的元素个数 / 散列表的长度size。a是散列表装满程度的标志因子。

由于表长是定值，a与“填入表中的元素个数”成正比，所以，a越大，表明填入表中的元素越多，产生冲突的可能性就越大，空间利用率越高；反之，a越小，标明填入表中的元素越少，产生冲突的可能性就越小，空间利用率越低。典型的以空间换时间的做法。

实际上，散列表的平均查找长度是载荷因子a的函数，只是不同处理冲突的方法有不同的函数。
对于开放定址法，荷载因子是特别重要因素，应严格限制在0.7-0.8以下。超过0.8，查表时的CPU缓存不命中(cachemissing)按照指数曲线上升。

超过标定的载荷因子，先扩容散列表，再重新建立映射关系。

闭散列会占用别的键值对的位置，空间利用率比较低，不太合理。那如何寻找下一个空位置呢？

查找空位置的方法一：线性探测

从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

线性探测优点：实现非常简单；缺点：一旦发生哈希冲突，所有的冲突连在一起，容易产生数据“堆积”，即：不同关键码占据了可利用的空位置，使得寻找某关键码的位置需要许多次比较，导致搜索效率降低。

while (_tables[hashi]._state == EXIST)
{//线性探测++hashi;hashi %= _tables.size();//避免越界
}

查找空位置的方法二：二次探测

找下一个空位置的方法为：HiH_iHi​ = (H0H_0H0​ + i2i^2i2 ) % m, 或者：HiH_iHi​ = (H0H_0H0​ - i2i^2i2 ) % m。其中：i =1,2,3…， H0H_0H0​是通过散列函数Hash(x)对元素的关键码 key 进行计算得到的位置，m是表的大小（_tables.size()）。

size_t hashi = hf(kv.first) % _tables.size();//Hash()函数

解决方法二：开散列（更优）

又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个无头单链表链接起来，各链表的头结点存储在哈希表中。

当使用无序容器存储键值对时，会先申请一整块连续的存储空间，但此空间并不用来直接存储键值对，而是存储各个链表的头指针，各键值对真正的存储位置是各个链表的节点。STL 标准库通常选用 vector 容器存储各个链表的头指针。

Insert()

当有新键值对存储到无序容器中时，整个存储过程分为

1. 若负载因子是否超过1.0，要扩容；
2. 将该键值对中键Key带入设计好的哈希函数，会得到一个哈希值（一个整数，用 H 表示）；
3. 将 H 和无序容器拥有桶的数量 n 做整除运算（即 H % n），该结果即表示应将此键值对存储到的桶的编号；
4. new一个新节点存储此键值对，同时将该节点头插到相应编号的桶上。

//普通版本的插入
bool Insert(const std::pair& kv)
{if (Find(kv.first))return false;if (_tables.size() == _n)//默认情况下，无序容器的最大负载因子为 1.0{//扩容HashTable newHT;newHT._tables.resize(_tables.size() * 2);for (auto cur : _tables){while (cur){newHT.Insert(cur->_kv);//每个节点都是重新new再插入的，当数据量大的时候不合适cur = cur->_next;}}_tables.swap(newHT._tables);}Hash hf;//根据映射关系找下标size_t hashi = hf(kv.first) % _tables.size();Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}

普通版本插入的实现，思路是new一个HashTable，让这个表里面的_tables重新扩容，再插入每个节点，能让数据重新排布，减少哈希冲突。不好的地方在于，1、每个节点都是重新new再插入的，当数据量大的时候不合适；2、HashTable有自己的析构函数，当出了函数要调用析构，释放所有节点。==>总的来说，是节点无法重复利用造成的性能消耗。

新的思路是，直接new一个_tables，循环利用旧表节点。对每个旧表节点进行重新映射（这一步不可省略），再头插到新表对应位置，将旧表中存储的指针置空，找不到其他指针，相当于让旧表的析构函数起不了实质性的作用即可。最后交换新旧表即完成扩容。

bool Insert(const std::pair& kv)
{if (Find(kv.first))return false;if (_tables.size() == _n)//默认情况下，无序容器的最大负载因子为 1.0{//扩容std::vector newtables;newtables.resize(_tables.size() * 2, nullptr);for (size_t = 0; i < _tables.size(); ++i){Node* cur = _tables[i];while (cur){Node* next = cur->_next;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 hf;//根据映射关系找下标size_t hashi = hf(kv.first) % _tables.size();Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}

负载因子

哈希表存储结构有一个重要的属性，称为负载因子（load factor）。该属性同样适用于无序容器，用于衡量容器存储键值对的空/满程序，即负载因子越大，意味着容器越满，即各链表中挂载着越多的键值对，这无疑会降低容器查找目标键值对的效率；反之，负载因子越小，容器肯定越空，但并不一定各个链表中挂载的键值对就越少。

负载因子的计算方法为： 负载因子 = 容器存储的总键值对 / 桶数。

if (_tables.size() == _n)//默认情况下，无序容器的最大负载因子为 1.0

**默认情况下，无序容器的最大负载因子为 1.0。**如果操作无序容器过程中，使得最大复杂因子超过了默认值，则容器会自动增加桶数， 并重新进行哈希，以此来减小负载因子的值。需要注意的是，此过程会导致容器迭代器失效，但指向单个键值对的引用或者指针仍然有效。

析构函数

用开散列的哈希结构要自己写析构函数。

~HashTable()
{for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}
}

哈希表的size()最好为素数的处理方法

研究人员认为，当模一个素数时，哈希冲突概率更小。

size_t hashi = hf(kv.first) % _tables.size();

// 除留余数法，最好模一个素数，即要求哈希表的size是素数
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];
}

在一些场景下，如数据较大、考虑空间和效率等，桶的底层结构可以由单链表改成红黑树。

开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

注意map和set、unordermap和unorderset对key的要求不一样，序列容器的要求key能比较大小；无序容器要求key能转换成整数。