内容摘要
本文内容包括红黑树和哈希表的性能比较逻辑分析及实现、哈希表的概念、哈希表映射关系建立的最常用的两种方法直接地址法和除留余数法介绍、介绍了哈希冲突的原因以及解决解决哈希冲突的方法、负载因子的概念、哈希表的扩容、开散列实现哈希表的思路及代码实现、闭散列实现哈希表的思路及代码实现。
红黑树和哈希表的性能比较
比较逻辑，通过set（底层是红黑树）和unordered_set（底层是哈希表）通过随机数和序列数的插入、删除、查找观察set和unoredered的速度
比较逻辑的实现
随机数的测试结果
随机数大量＋不重复
- Debug下
- Release下
随机数大量+重复
- debug
- Realease
序列数的测试结果
- Debug下
- Realease下
对于大量重复数据来说哈希表的性能非常强大，对于大量不重复随机数哈希表的性能综合考虑也是优于红黑树的，但是对于序列数哈希表就显得不如红黑树，红黑树的优化比较猛
哈希表的概念
哈希表也叫做散列表，哈希表就是通过key值和存储key值的位置建立映射关系进行实现的
映射关系的建立方式
-
直接地址法（直接映射法）
将数自身进行与存储数的位置进行映射，也就是说9这个数字就要存储到位置为9的位置，8存储到位置为8的位置，依次类推，通过直接地址法我们可以看到，当出现重复数字时，会出现好几个数据进行映射一个位置的情况出现，这种情况称为哈希冲突，哈希冲突也称为哈希碰撞。
当出现数据差值比较大的情况，例如 3 33 333 75 21 9 7 6 16这组数据时，要是通过直接地址法进行映射，则需要与数据进行映射的位置非常多，这种映射方式就非常不适用了。
适用数据的类型：数据集中，差值较小
-
除留余数法
解决上述直接地址法进行映射的局限，可以适用于分散的数据
解决哈希冲突/碰撞的方法
开散列
开散列也叫做开放定址法，当出现哈希冲突时，如果哈希表没有满，将元素向下一个位置进行映射，如果下一个位置也存在数据，继续向下一个位置进行寻找空位置，直至找到一个位置
开散列进行解决哈希碰撞的方式叫做线性探测
线性探测进行解决哈希冲突（哈希碰撞）会造成数据的“踩踏”，所谓的数据踩踏就是一个数据的位置被占用，这个数据向后进行占用其他的数据的位置，依次进行。
二次探测：为了缓解线性探测产生的数据踩踏问题，一定程度优化了线性探测。
hashi=key+i*i
hashi=key%len+i*i
闭散列
闭散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
开散列实现哈希表
插入：
将要插入的数据进行相同的哈希函数计算，然后映射到相对应的空间
查找：
进行查找数据不必从数组的首个位置进行查找，直接从理论映射位置进行开始遍历，当遍历到节点状态为空的位置进行结束即可。
删除：
思考：将节点进行删除，应如何将节点进行处理？？将节点的位置赋予一个特殊的值吗？？还是将这个节点直接进行置空？？？
答案是都不可以，首先将删除的节点进行赋予一个特殊的值，这个值是多少呢？？无论这个值是多少，都有可能后续要进行存出这个特殊的值，有可能改变这个值的位置；将节点直接置空进行处理，我们进行遍历查找的条件是遇到空节点就停止遍历，导致被删除节点之后的值，都没有办法被找到了。
解决办法：将节点中存储的数据加一个存储状态即可，进行删除后，直接进行更改节点的状态即可。
负载因子：vector中存储的实际元素和vector容量的比值，用来表示表满的状态。通过引入负载因子的概念，是为了缓解哈希表的踩踏问题，增加查找的效率，从本质上解决了哈希表满的问题。
代码实现
在进行插入的时候有两种逻辑进行实现
第一种是最容易想到的，在进行扩容后，将旧表中的数据进行遍历计算出需要映射新表的数据位置，判断此位置节点的状态是否为空，为空插入即可，不为空继续向后进行遍历。
第二种的思路非常妙，通过重新定义一个新表，调用我们实现的插入操作。
闭散列实现哈希表
闭散列实现哈希表十分重要，闭散列实现的哈希表的的效率综合要比开散列实现的哈希表的性能要好的多，这得意于得意于闭散列解决哈希冲突的方式。
代码实现
闭散列实现的哈希表通过vector中存储一个指向节点的指针进行实现，这类似于哈希桶样式的结构，必须要求我们写析构函数进行资源的释放，因为vector会自动调用析构函数释放vector中存储的那个指向节点的指针，但是这是一个哈希桶的结构，vector中存储的指针的_next是指向另一个节点的指针，直接进行vector的默认析构函数，会造成内存泄漏，所以说需要将析构函数进行手动写出来进行资源的释放。
插入操作时进行优化优化在什么地方？？
普通插入函数的逻辑是，当要进行扩容时，将旧表中的数据进行映射到新表的过程，采取再进行定义一个哈希表，重复调用插入操作进行，但是重新调用插入操作是通过new新的节点进行的，相当于将旧表中的数据进行拷贝到新表中一份，到时候调用析构函数进行资源释放的时候需要进行两次遍历新表一次，遍历旧表一次。
优化逻辑：既然旧表中的数据不再进行使用，能不能将旧表中的数据进行移动到新表呢，到时候旧表调用析构函数时不在需要vector中存放的节点指针的_next，进行提高效率。
