哈希表的模拟实现

unordered_set:

接口函数：

对应的应用：

unrodered_map:

对应的函数接口：

对应的应用：

比较set和unordered_set的效率：

可以看到各个方面hashset是优于set的。

哈希表的模拟实现：

哈希表的实现分为两种：

1.闭散列（线性探测）

对应的插入方法：

1.通过哈希函数获取待插入元素在哈希表中的位置：

2.如果要插入的位置已经有元素了，就使用线性探测找到下一个空位置直接插入。

线性探测的实现：

主要的实现就是insert部分：

对应的容量不够了还要进行扩容，这里直接将扩为两倍，然后再将旧表的数据插入新表。

2.开散列（哈希桶）

其实就是一个指针数组，每一个位置可以像链表一样向下延伸

对应的插入方法：

1.通过哈希函数获取待插入元素在哈希表中的位置：

2.不管元素重复不重复，都将其头插在对应的位置的链表中即可

对应认为每个位置负载因子不超过1就是好的，如果超过需要扩容：

对应实现如下：

还有寻找和删除的实现，都比较相似。