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
最新资源