https://blog.csdn.net/qq_43338695/article/details/102736304

hashset和hashmap都是hashtable的一种实现形式。

接下来我要介绍的unordered_set和unordered_map都是基于hashtable的实现。

unordered_set实现了不存储重复的元素。

unordered_map实现了key和value的映射

一. set和unordered_set
·对比
    set unordered_set
是否有序    有序  无序
实现  BST或RBT Hash Table
插入  log n   平均O(1)，最坏O(n)
删除  log n   平均O(1), 最坏O(n)
由此可见，用hash table实现的，其实是unordered_set而不是set。
所以我们只有使用set才是利用了hash table的特点。

之后的讲解我们都会围绕unordered_set来展开。

·支持操作
 插入（insert），删除（erase），查找（count）
 获得大小（size），遍历（begin, end）
清空操作（clear， empty）
·其他注意事项
 不论是unordered_set还是set，都是集合的实现形式。都用来存储不重复的元素。
unordered_set的实现形式是使用数组把一些不同的值储存在同一个桶中。
（想一想y = x % 1000）。桶足够小的时候，复杂度为O(1)，然而如果桶特别大，
那么复杂度就是O(n)，n是桶的大小。
有一些实现，
当桶特别大的时候，会抛弃数组采用BST或者RBT的形式来降低复杂度（原来的O(n)变成O(log n)）


二. map和unordered_map
·对比
与上面一样，接下来我介绍unordered_map为主。

其实大家发现没有，由于都是基于hashtable的实现，
所以unordered_map和unordered_set在插入和删除的复杂度不尽相同

·支持操作
 插入（insert，[]）， 删除（erase），查找（[], count）
获得大小（size）， 遍历（begin，end）
清空操作（empty， clear）
·其他注意事项
hashset中数组中的每一个位置存储的是该元素是否存在的信息——一般以1和0来区分。
而hashmap中是根据key来找桶，实现桶的数组中存放的是与key对应的value。
两者都用到了hashtable的思想。
与hashset相同，hashmap的有些实现，会在数组的长度太大的时候，
改用高度平衡的BST或者RBT来实现。此时我们的插入和删除的节点的复杂度都是O(log n)。