hashtable——散列表

时间:2024-01-02 11:10:26
2018-11-01

散列表---哈希表
基于快速存取,时间换空间
一种基于线性数组的线性表,不过元素之间并非紧密排列 散列函数--通过函数,有key关键码计算地址(相当于数组下标),函数尽可能使元素均匀分布 负载因子a:实际元素只有 n 个时,我们为其申请了 m 个元素空间(m>n),即桶的个数;
负载因子 = n/m
a > 1 碰撞频率大
a < 1 碰撞频率小
同义词(synonym):如果两个元组通过hash函数计算得到的地址相同《冲突》,那么这两个元素就叫做synonym 桶(bucket):散列函数计算所得到的存储单位,每个单位称为一个桶,如果一个散列表有m个桶,那么散列函数的值域
为[0,m-1] 冲突主要取决于:
1.散列函数,(均匀度)
2.处理冲突的方法
3.负载因子大小(过大:浪费空间,过小,时间问题),负载因子也散列函数是联动的 hash function:
1.取余法
H( Key ) = Key % M
其中 :M <= 基本区长度的最大质数(在各种进制下都必须要满足)
即要保证一个桶不能是另一个桶的倍数
基本区长 M
8 7
16 13
2048 2039
为什么取最大质数?
1) 若取偶数,如 10,100,…., 2, 4, …, 冲突率是比较大的;
2)若取含有质因子的M,如 M=21 (3*7) 含质因子3和7,对下面的例子:
key: 28 35 63 77 105
则 7 14 0 14 0 关键码中含质因子7的哈希值均为7的倍数。
2.平方取中法
H( Key ) = Key^2 的中间部分,其长度取决于表的大小。
设表长 = 2^9 = (512)10 地址 000~777(八进制)
(2061)8 4310541
(2062)8 4314704
(2161)8 4734741
(2162)8 4741304
(1100)8 1210000
3. 乘法杂凑函数
H( Key ) = |_ M * (( r * Key ) % 1 ) _| (向下取整)
例:设表长 = 29 = (512)10 地址 000~777(八进制),则
H( 1 ) = 29 * ( 0.618 )10  =  29 * ( 0.4743…)8  = 474 4.直接寻址法:取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a?key + b,其中a和b为常数(这种散列函数叫做自身函数) 5. 数字分析法:分析一组数据,比如一组员工的出生年月日,这时我们发现出生年月日的前几位数字大体相 同,这
样的话,出现冲突的几率就会很大,但是我们发现年月日的后几位表示月份和具体日期的数字差别很大,如果用
后面的数字来构成散列地址,则冲突的几率会 明显降低。因此数字分析法就是找出数字的规律,尽可能利用这些
数据来构造冲突几率较低的散列地址。
注意:数值分析法仅适用于事先知道表中所有关键玛的每一位的分布情况,完全依赖于关键码的集合 设有 n 个d位数。每一位可能有 r 种不同的符号,这r为符号在某些位上分布均匀些,分布不均匀的不经常出现,
可以根据散列表,只选取其中的若干位作为散列地址,
计算各位数字中符号分布的均匀度 T 的公式 T = sum(a(ik) - n/r )^2
a(ik)表示第i位符号在k中出现的次数 6.折叠法:将关键字分割成位数相同的几部分,最后一部分位数可以不同,然后取这几部分的叠加和(去除进位)作为散列地址。
注意:
1.适用条件:
当关键码的位数很多,而且关键码上的数字的分布大致均匀时
2.叠加时舍去多余的位数
叠加方法:
1.移位法: 普通的加法
2.分界法 7. 随机数法:选择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。 散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到,另一些关键码在散列函数得到的地址上产生了冲突,需要按 处理冲突的方法进行查找。在介绍的三种处理冲突的方法中,产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以,对散列表查找效率的量度,依然用平 均查找长度来衡量。
查找过程中,关键码的比较次数,取决于产生冲突的多少,产生的冲突少,查找效率就高,产生的冲突多,查找效率就低。因此,影响产生冲突多少的因素,也就是影响查找效率的因素。影响产生冲突多少有以下三个因素:
  1. 散列函数是否均匀;
  2. 处理冲突的方法;
  3. 散列表的装填因子。
  散列表的装填因子定义为:α= 填入表中的元素个数 / 散列表的长度
  α是散列表装满程度的标志因子。由于表长是定值,α与“填入表中的元素个数”成正比,所以,α越大,填入表中的元素较多,产生冲突的可能性就越大;α越小,填入表中的元素较少,产生冲突的可能性就越小。
  实际上,散列表的平均查找长度是装填因子α的函数,只是不同处理冲突的方法有不同的函数。 著名的hash算法:MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法,而它们都是以 MD4 为基础设计的
hash在信息安全:文件校验、数字签名、授权协议 关于查找不成功
address 0 1 2 3 4 5 6 7 8 9
key 7 14 8 11 30 18 9
查找不成功,说明要查找的数字肯定不在上述的散列表中。
因为这里哈希函数的模为7,所以要查找的数只可能位于0~6的位置上。
(1)若要查找的数key对应的地址为0,有(key * 3) % 7 = 0。
因为key不属于{7, 8, 30, 11, 18, 9, 14},可设key = 28。
第一次查找,address = 0时key = 7,不是要找的28,
第二次查找,往后挪移一位,address = 1时key = 14,不是要找的28;
第三次查找,往后再挪移一位,address = 2时key为空。可知查找不成功,否则28应该放在adress = 2的位置上。
结论:查找3次可知查找不成功。
--------------------- 解决冲突的方式: 闭散列方法(开地址法):
1.线性探查法 linear probing
Hi = (H0+i)%m
缺点:1.闭散列的情形下不能物理删除表中已有的元素
2.仅适用于散列表不经常变化
3.线性探查法容易产生堆积cluster(不同的探查序列的关键码占据了可利用的bullet,使得为了寻找某一关键码需要经历不同的探查序列的元素,导致搜索时间增加
2.二次探查法 quadratic probing
Hi = (H0 +/- i^2 )%m
优点:当表的长度为质数且负载因子 不超过 0.5 时,新的表项一定能够插入,而且任何一个位置不会被探查两次
3.双散列方法
两个散列函数,hash()计算第一次的地址 , rehash()是在发生冲突时用于计算下一个空桶所在的 位移量。
于是,它解决了线性探查的堆积问题,
Hi = (H0 +i*rehash(key))%m; 开散列方法(链地址法)
将根据散列表函数计算的地址将其分为m个子集合,同一词位于相同的子集合中,每一个子集合称为一个桶
采用的是链表实现
优点:速度快 性能分析:
开散列方法 优于 闭散列
hash:
取余法最好,折叠法最差 散列表有很好的平衡性能,优于如平衡树的传统技术,但是在最坏的情况下性能不好,执行插入/搜索
在最坏情况下是 O(n);