数据结构-查找-哈希表（散列表）查找-科班学习笔记

本篇是查找第三篇，需要第一篇基本概念的基础，请前往

查找1

---

哈希表

哈希表是一种存储结构，它是一定长度的连续内存单元，它并未适合任何情况，主要适合记录的关键字与存储地址存在某种函数关系的数据，就像我们常用的键值对存储结构

如图

1. 计算地址d = 201001025 - 201001001 = 24
2. 和24处的学号作对比，相等，返回姓名王五

该过程的时间复杂度为O（1）

哈希函数：

h（k） ：把关键字为ki的对象存放在相应的哈希地址中

哈希冲突：

关键字（key）不同而哈希函数（h（k））（地址）相同称哈希冲突，哈希冲突很难避免，哈希表设计的核心就是较好解决哈希冲突

引发哈希冲突的因素

• 装填因子

  装填因子α=存储的记录个数/哈希表的大小，装填因子越小，冲突的可能性越小，通常使装填因子控制在0.6~0.9的范围内

• 哈希函数

• 解决方案

哈希表的设计

直接定址法

直接定址法是以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法

直接定址法的哈希函数h(k)为：

h(k) = k+c（k为关键字，c为常量）

例如，

h(学号) = 学号-201001001

除留余数法

除留余数法就是把n个记录按关键字映射到0～m-1的哈希空间中

模p（素数）时出现冲突的可能性更小。

除留余数法的哈希函数h(k)为：

h(k)=k mod p (mod为求余运算，p≤m，k为关键字，m为记录数)

数字分析法

以上，一行就是一个key

哈希冲突的解决方法

开放定址法

即冲突时找一个新的空闲的哈希地址

例如：

你买了电影票，到电影院时已经开映了，你的位置被别人占用了，你需要找一个空位置。这就是开放定址法的思路

线性探查法：

线性探查法的数学递推描述公式为：

d[0]=h(k)

di=(d[i-1]+1) mod m (1≤i≤m-1)

模m是为了保证找到的位置在0～m-1（即哈希表空间大小）的有效空间中

同义词冲突：这个方法会产生堆积聚集现象：哈希函数值不相同的两个记录争夺同一个后继哈希地址

平方探查法

思路：在电影院中找被占用位置的前后空位置！

平方探查法的数学描述公式为：

d[0]=h(k)

d[i]=(d[0]±i方) mod m (1≤i≤m-1)

查找的位置依次为：d[0]、 d[0 +1]、 d[0 -1] 、 d[0 +4]、 d[0 -4]

平方探查法是一种较好的处理冲突的方法，可以避免出现堆积现象。它的缺点是不能探查到哈希表上的所有单元，但至少能探查到一半单元

拉链法

拉链法是把所有的同义词用单链表链接起来的方法，即存在哈希冲突的记录不用另寻空间，在冲突的位置有一个后继指针空间，放入即可

哈希查找

看到这， 其实哈希查找已经讲了，就是上面的线性探查与平方探查

即每个key的探查次数累加除以记录数