C++ unordered_map实现方案，与hash冲突解决办法_c++ map哈希冲突处理

unordered_map有点类似c++11之前的非标准库hash_map, c++11后， 加入了unordered_map， 可就用来代替之前的hash_map。
由于 unordered_map 内部采用 hashtable 的数据结构存储，所以，每个特定的 key 会通过一些特定的哈希运算映射到一个特定的位置，我们知道，hashtable 是可能存在冲突的，在同一个位置的元素会按顺序链在后面（也称之为开链法）。所以把这个位置称为一个 bucket 是十分形象的，每个哈希桶中可能没有元素，也可能有多个元素。
今天来看看unordered_map的底层实现。先上个图：

从图中不难看出， 首先需要开辟一段连续内存用来存储每个桶的头地址，各键值对真正的存储位置是各个链表的节点。当插入元素节点越来越多的时候， 就会超过存储桶位置序列的个数。 这时就需要扩容。扩容规则跟vector有点类似。 另外值得一提的是，哈希表存储结构还有一个重要的属性，称为负载因子（load factor）。该属性同样适用于无序容器，用于衡量容器存储键值对的空/满程序，即负载因子越大，意味着容器越满，即各链表中挂载着越多的键值对，这无疑会降低容器查找目标键值对的效率；反之，负载因子越小，容器肯定越空，但并不一定各个链表中挂载的键值对就越少。
举个例子，如果设计的哈希函数不合理，使得各个键值对的键带入该函数得到的哈希值始终相同（所有键值对始终存储在同一链表上）。这种情况下，即便增加桶数是的负载因子减小，该容器的查找效率依旧很差。
无序容器中，负载因子的计算方法为：
负载因子 = 容器存储的总键值对 / 桶数
默认情况下，无序容器的最大负载因子为 1.0。如果操作无序容器过程中，使得最大复杂因子超过了默认值，则容器会自动增加桶数，并重新进行哈希，以此来减小负载因子的值。需要注意的是，此过程会导致容器迭代器失效，但指向单个键值对的引用或者指针仍然有效。

再来说说当hash冲突的时候的解决方案， C++使用开链法， 如下图所示：
就是说将 产生哈希冲撞 的数据全部链到当前位置的下面，看上去就像是 在下面链上了一个一个的桶子，因此这样的方法我们有称作是 哈希桶， 当同位置上的元素节点小于8个的时候， 这些数据会是一个链表式的方式互相连起来。 当同位置上的元素节点大于8个的时候， 会自动转化为成一个map(红黑树)。所以理论上unorder_map最坏的情况下查找复杂度为：hashtime(hash函数计算时间)＋＋o(1)(桶定位时间) + o(lgn)(查询map时间), 当然在设计hashfuction的时候， 其实就规避了这种情况。 不会出现很多桶空着， 但小部分桶挂一个很大的MAP。 所以的unorder_map 最坏的情况下查找复杂度为：hashtime + o(1) + o(lgn/m), 总的来说很不错。 除了消耗多一点的内存。 也属于用空间换时间的实现。

说到这里， 不妨再深入一点， 探讨一下hash函数的一般实现方法。
哈希表是一个K_V的结构，又被称为是散列表
它是根据关键字(key)来直接访问这个内存存储数据位置的数据结构。
在构建哈希表的方法，我们这里主要介绍两种方法
1、直接地址法
就是直接取key(或者是某种线性函数)作为这个下表来存储数据 ，key在这里称作是 散列地址。
可以理解成这个样子 Hash（Key）= Key 或Hash（Key）= A*Key + B，A、B为常数

2、除留余数法
就是 将 key 被某个不大于散列表长m的数p除后的所得的余数为散列地址。
Hash（Key）= Key%P。
但是这两种方法都有很大 的缺陷
比如说 ：：：第一种方法来说吧！！！！！
如果数据量大的话，那么要建立的哈希表的长度就非常的了，但是也许中间的很多的位置都没有 存取数据，这样 就会造成很多的浪费。所以这种方法我们经常不是很常用
如果说是，使用第二种方法的话也是存在问题的。
如果，，，，要是不同的key值通过除留余数法得到的哈希地址是相同的，，，，在这里就会造成我们经常所说的哈希冲突（也就做是哈希碰撞 ）这种东西 。。。。
虽然这种除留余数法有这种缺陷，，，但是 我们还是常常使用这种方法。。。。。。所以我们想了许多的方法来解决这种 哈希冲突。
哈希冲突(哈希碰撞)
1、开放地址法
（1）线性探测法
线性探测的特点就是 如果得到的哈希地址冲突(该位置上已存储数据)的话 ，我们就是将这个数据 插到下一个位置，要是下个位置也已存储数据 ，就继续到下一个，直到找到正确的可以插入的数据。
(2)二次探索法
所谓的二次探索法说的是 ，当遇到冲突后 ，下次所找到的位置 为当前的位置加上 n的二次方
当然了C++的使用的是开链法， 上面已经介绍了。
END