哈希表

定义：根据设定的哈希函数 H(key) 和提供的处理冲突的方法，将一组关键字映象到一个地址连续的地址空间上，并以关键字在地址空间中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为哈希表。 散列存储的基本思路： 以数据中每一个元素的keywordK为自变量。通过散列函数H（k）计算出函数值，以该函数值作为一块连续存储空间的的单元地址，将该元素存储到函数值相应的单元中。 时间复杂度： 哈希表存储的是键值对，其查找的时间复杂度与元素数量多少无关。哈希表在查找元素时是通过计算哈希码值来定位元素的位置从而直接訪问元素的，因此，哈希表查找的时间复杂度为O（1）

常用的哈希函数

1.直接哈希函数： 取关键字本身或关键字的某个线性函数值作为哈希地址， H(key) = a * key + b （a，b为常数） 适用于关键字取值集合不是很大 2.数字分析法： 设ｎ个ｄ位数的关键字，由ｒ个不同的符号组成，此ｒ个符号在关键字各位出现的频率不一定相同，可能在某些位上均匀分布，即每个符号出现的次数都接近于ｎ／ｒ次，而在另一些位上分布不均匀。则选择其中分布均匀的s位作为哈希地址，即H（key）=“key中数字均匀分布的s位” n=80,d=8,r=10,s=2 1，2，3，8位分布不均匀，不能取。可取第4、6两位组成的2位十进制数作为每个数据的哈希地址，则图中列出的关键字的哈希 地址分别为： 45，72，84，03，28，39，51，65，13 适用情况：事先明确知道关键字每一位数值的分布情况，且关 键字的位数比哈希表的地址位数多 3.平方取中法： •取关键字平方后的中间几位作为哈希地址，即哈希函数为： H（key）=“key2的中间几位”， 其中，所取的位数由哈希表的大小确定 4.折叠法： 若关键字位数较多，可根据表长B的位数将关键字分割成位数相同的若干段（最后一段位数可以不同），然后将各段叠加和(舍去进位)作为存储地址 适用情况： 关键码位数很多 5.除留余数法： 取关键字被某个不大于哈希表长度m的数p除后的余数作为哈希地址，即 H（key）=key MOD p(p≤m) 6.随机数法： 选择一个随机函数，取关键字的随机函数值作为哈希地址， 即：H（key）=random（key）

冲突处理

冲突是指由关键字得到的Hash地址上已有其他记录。 好的哈希函数可以减少冲突，但很难避免冲突

常见的冲突处理方法有： • 开放地址法 • 再哈希法 • 链地址法 • 公共溢出区法

开放地址法

1.线性探测再散列 采用线性探测再散列处理冲突，请求出解决冲突的查找成功的ASL和查找失败的ASL 那查找失败的平均查找长度怎么算呢，我们应该从哈希值的角度来考虑，我们这的哈希函数为key MOD11，无论key是多少，哈希值只能是0到10这11个数，所以关键字是0时，需要查找9次失败，（此处一种认为空指针需要加进失败次数里，一种认为不要加，两种都对，具体情况题目会说明），依次算出剩余关键字查找失败次数 2.二次探测再散列： 这里的di取法如下： 3.随机数探测再散列：

ASL(成功）=（1+1+1+1+1+5+1+2+2）/9=5/3 ASL(失败）=（3+5+4+6+1+5+2+1+3+2+4）/11=36/11

再哈希法

链地址法（拉链法）

这里的相同地址关键字插入可以前插也可以后插，我们这里是后插， ASL（成功）=（16+22+3）/9=13/9 ASL（失败）=（1+2+1+0+1+3+1）/7=9/7 注意：查找成功时。分母为哈希表元素个数，查找不成功时，分母为哈希表长度。

公共溢出区法

装填因子

装填因子 = （哈希表中的记录数） / （哈希表的长度）

装填因子是哈希表装满程度的标记因子。值越大。填入表中的数据元素越多，产生冲突的可能性越大

查找性能分析

哈希表的平均查找长度是装填因子 α 的函数，而不是 n 的函数。 这说明，用哈希表构造查找表时，可以选择一个适当的装填因子α ，使得平均查找长度限定在某个范围内。