C++常用std集合—map/set
- unordered_map在C++11的时候被引入标准库了，而hash_map没有，所以建议还是使用unordered_map比较好。查询平均时间是O(1)，无序，类似于Java中HashMap。
- map的内部结构是R-B-tree来实现的，所以保证了一个稳定的动态操作时间，查询、插入、删除都是O（logN），最坏和平均都是。而unordered_map如前所述，是哈希表。顺便提一下，哈希表的查询时间虽然是O（1），但是并不是unordered_map查询时间一定比map短，因为实际情况中还要考虑到数据量，而且unordered_map的hash函数的构造速度也没那么快，所以不能一概而论，应该具体情况具体分析。最坏会是O(n)，额外空间复杂度则要高出许多。map中的元素是按照二叉搜索树存储，进行中序遍历会得到有序遍历，默认遍历顺序为以key从小到大。
- 无序集合（Unordered Set）容器是一个存储唯一（Unique，即无重复）元素的关联容器（Associative container），容器中的元素无特别的次序关系。该容器允许基于值地快速元素检索。类似于HashSet。
- set/multiset/map/multimap的内部实现和常用函数
- 红黑树原理
BloomFilter布隆过滤器
核心实现是一个很长的二进制向量 （位数组）再加上一系列随机函数 (哈希)，空间效率和查询效率高，不会漏判，但是有一定的误判率（哈希表是精确匹配）。