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来展开。

·支持操作

1.  插入（insert），删除（erase），查找（count）
2.  获得大小（size），遍历（begin, end）
3. 清空操作（clear， empty）

·其他注意事项

1.  不论是unordered_set还是set，都是集合的实现形式。都用来存储不重复的元素。
2. unordered_set的实现形式是使用数组把一些不同的值储存在同一个桶中。（想一想y = x % 1000）。桶足够小的时候，复杂度为O(1)，然而如果桶特别大，那么复杂度就是O(n)，n是桶的大小。
3. 有一些实现，当桶特别大的时候，会抛弃数组采用BST或者RBT的形式来降低复杂度（原来的O(n)变成O(log n)）

 

二. map和unordered_map

·对比

与上面一样，接下来我介绍unordered_map为主。

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

·支持操作

1.  插入（insert，[]）， 删除（erase），查找（[], count）
2. 获得大小（size）， 遍历（begin，end）
3. 清空操作（empty， clear）

·其他注意事项

1. hashset中数组中的每一个位置存储的是该元素是否存在的信息——一般以1和0来区分。而hashmap中是根据key来找桶，实现桶的数组中存放的是与key对应的value。两者都用到了hashtable的思想。
2. 与hashset相同，hashmap的有些实现，会在数组的长度太大的时候，改用高度平衡的BST或者RBT来实现。此时我们的插入和删除的节点的复杂度都是O(log n)