【C++】哈希表的使用

unordered_map/unordered_set

这是C++11才新增的两个容器

原本觉得avl树和红黑树效率已经够了。

后来探索和觉得哈希还是有必要加进来的。

JAVA里面是这样取名的：

unordered_set

unordered_map/set与map/set的功能基本一致，但细节上有所不同，它们底层用的分别是红黑树和哈希表。

• unordered_set默认要求Key⽀持转换为整形，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key转成整形的仿函数传给第⼆个模板参数
• unordered_set默认要求Key⽀持⽐较相等，如果不⽀持或者想按⾃⼰的需求⾛可以⾃⾏实现⽀持将Key⽐较相等的仿函数传给第三个模板参数
• unordered_set底层存储数据的内存是从空间配置器申请的，如果需要可以⾃⼰实现内存池，传给 第四个参数
• ⼀般情况下，我们都不需要传后三个模板参数
• unordered_set底层是⽤哈希桶实现，**增删查平均效率是$O(1)$ ，**迭代器遍历不再有序，为了跟set 区分，所以取名unordered_set
• 前⾯部分我们已经学习了set容器的使⽤，set和unordered_set的功能⾼度相似，只是底层结构不同，有⼀些性能和使⽤的差异，这⾥我们只讲他们的差异部分

它是单向迭代器

在这里也可以看出：

它没有rbegin和rend

unordered_set和set的第⼆个差异是迭代器的差异，set的iterator是双向迭代器，unordered_set 是单向迭代器，其次set底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以set迭代 器遍历是有序+去重。⽽unordered_set底层是哈希表，迭代器遍历是⽆序+去重。

去重还是一样的，如果这个值已经有了就不再插入。

unordered_set和set的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_set的增删 查改更快⼀些，因为红⿊树增删查改效率是$O(logN)$ ，⽽哈希表增删查平均效率是 $O(1)$，其实$O(1)$没有比$O(logN)$快很多。

对比：

1kw个随机值的插入、查找、删除的二者（set/unordered_set)对比

全方位碾压

看看如果重复值很多：

优势更明显了

因为unordered的查找优势很明显，而大量重复值需要查找，如果有了就不再插入，所以重复值很多时，插入优势很明显。

而当没有重复值时，是有序值，则优势不那么明显：

数据有序的情况下，set甚至有翻身之意。查找依旧快。

这是100w个有序值，再来看看1000w个有序值：

set的插入甚至更快了

所以在有序情况用set、map，剩下情况就用unordered系列。

一个是3个模版参数一个是4个

unordered_map

• unordered_map和map的第⼀个差异是对key的要求不同，map要求Key⽀持⼩于⽐较，⽽ unordered_map要求Key⽀持转成整形且⽀持等于⽐较，要理解unordered_map的这个两点要求 得后续我们结合哈希表底层实现才能真正理解，也就是说这本质是哈希表的要求。

• unordered_map和map的第⼆个差异是迭代器的差异，map的iterator是双向迭代器， unordered_map是单向迭代器，其次map底层是红⿊树，红⿊树是⼆叉搜索树，⾛中序遍历是有序的，所以map迭代器遍历是Key有序+去重。⽽unordered_map底层是哈希表，迭代器遍历是 Key⽆序+去重。

• unordered_map和map的第三个差异是性能的差异，整体⽽⾔⼤多数场景下，unordered_map的增删查改更快⼀些，因为红⿊树增删查改效率是$O(logN)$ ，⽽哈希表增删查平均效率是$O(logN)$。

unordered_multimap/unordered_multiset

• unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似，⽀持Key冗余。

ered_multiset

• unordered_multimap/unordered_multiset跟multimap/multiset功能完全类似，⽀持Key冗余。

• unordered_multimap/unordered_multiset跟multimap/multiset的差异也是三个⽅⾯的差异， key的要求的差异，iterator及遍历顺序的差异，性能的差异。