unordered_map和和unordered_set的模拟实现的模拟实现
unordered_map和和unordered_set的模拟实现的模拟实现
（一）哈希表的特性及概念（一）哈希表的特性及概念
定义：定义：
哈希表（Hash table，也叫散列表），是根据关键字值（key,value）直接进行访问的数据结构。也就是说，它通过把关键字映
射到表中一个位置来访问的纪录，以加快查找的速度。这个映射函数叫做散列函数，存放纪录的数组叫散列表。
基本原理：基本原理：
使用一个下标范围比较大的数组来存储元素。可以设计一个函数（哈希函数，也叫做散列函数），使得每个元素的关键字都与
一个函数值（即数组下标，hash值）相对应，于是用这个数组单元来存储这个元素；也可以简单的理解为，按照关键字为每
一个元素“分类”，然后将这个元素存储在相应“类”所对应的地方，称为桶。
常见哈希函数常见哈希函数
1.直接定制法
取关键字或关键字的某个线性函数值为哈希地址。
H(key) = key 或 H(key) = a*key+b
2.除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函 数：
H(key) = key% p(p<=m)
将关键码转换成哈希地址
3.平方取中法
取关键字平方后的中间几位为哈希地址。
4.折叠法
折叠法是将关键字从左到右分割成位数相等的几部分(最后一部分位数可以短些)，然后将这几部分叠加 求和，并按散列表表
长，取后几位作为散列地址。
5.随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H(key) = random(key),其中random为 随机数函数。 通常应用
于关键字长度不等时采用此法 。
6.数学分析法
找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。
冲突解决冲突解决
1.闭散列
也叫开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那 么可以把key存放到冲突位
置中的“下一个” 空位置中去。
（1）当要插入一个元素时，连续地检查散列表的个各项，直到找到一个空位置来放置这个元素为止。
（2）当查找一个元素时，要检查所有的表项，直到找到所需的元素，或元素不在表中。
（3）当我们从位置中删除关键字时，不能将此位置元素置空。否则会导致在无法判断此位置是否有元素。应该用个特殊值表
示该元素已经删除。
2.开散列
又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码 归于同一子集合，每一个子集合
称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结 点存储在哈希表中。
（二）（二）unordered_map与与unordered_set的实现的实现
unordered_set
(1) 哈希函数，需要实现一个class重载operator()，将自定义class变量映射到一个size_t类型的数。一般常用std::hash模板来
实现。
(2) 判断两个自定义class类型的变量是否相等的函数，一般在自定义class里重载operator==。
unordered_map
(1) 哈希函数，需要实现一个class重载operator()，将自定义class变量映射到一个size_t类型的数。一般常用std::hash模板来
实现。
(2) 判断两个自定义class类型的变量是否相等的函数，一般在自定义class里重载operator==。
template
class UnorderedMap
{
struct UMapKeyOfValue
{
评论10
最新资源