unordered_set:
接口函数:
对应的应用:
unrodered_map:
对应的函数接口:
对应的应用:
比较set和unordered_set的效率:
可以看到各个方面hashset是优于set的。
哈希表的模拟实现:
哈希表的实现分为两种:
1.闭散列(线性探测)
对应的插入方法:
1.通过哈希函数获取待插入元素在哈希表中的位置:
2.如果要插入的位置已经有元素了,就使用线性探测找到下一个空位置直接插入。
线性探测的实现:
主要的实现就是insert部分:
对应的容量不够了还要进行扩容,这里直接将扩为两倍,然后再将旧表的数据插入新表。
2.开散列(哈希桶)
其实就是一个指针数组,每一个位置可以像链表一样向下延伸
对应的插入方法:
1.通过哈希函数获取待插入元素在哈希表中的位置:
2.不管元素重复不重复,都将其头插在对应的位置的链表中即可
对应认为每个位置负载因子不超过1就是好的,如果超过需要扩容:
对应实现如下:
还有寻找和删除的实现,都比较相似。