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)；