目录

1.散列表的基本概念

2.散列表的查找

3.散列函数的构造方法

1.直接定址法

2.除留余数法

4.散列表解决冲突的方法

1.开放定址法

2.链地址法

1.散列表的基本概念

基本思想：记录的存储位置与关键字之间存在的对应关系

对应关系——hash函数

Loc(i) = H(keyi)

Hash：哈希——翻译为：散列、杂凑（感觉还是哈希听起来更好听）

是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位。

例题1：

若将学生信息按如下方武存入计算机，如 将2001011810211的所有信息存入V[11]单元： 将2001011810207的所有信息存入V[07]单元： …… 将2001011810231的所有信息存入V[31]单元。

通过取出最后两位定义一个关键存储。

例题2：

数据元素序列(21,23,39,9,25,11)，若规定每个元素k的存储地址H(k)=k,请画出存储结构图。

  

按照每一个元素的值，存储到相应下标的位置上，从而完成对散列表的构建。

散列表的若干术语：

散列方法（杂凑法）：

1. 选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；

2. 查找时，由同一个函数对给定值k计算地址，将k与地址单元中元素关键码进行比，确定查找是否成功。

散列函数（杂凑函数）：散列方法中使用的转换函数

散列表（杂凑表）：按上述思想构造的表（也就是例题2所建构出来的图表）

散列函数：H(key)=k

冲突：不同的关键码映射到同一个散列地址，key1≠key2,但是H(key1)=H(key2)

例题：有6个元素的关键码分别为：（25,21,39,9,23,11)。

1. 选取关键码与元素位置间的函数为H(k)= k mod 7，

2. 地址编号从0-6。

3. 这时候会发现有好多计算出来的关键词一致，造成了冲突

2.散列表的查找

 

 根据散列函数H(key) = k

查找key=9,则访问H(9)=9号地址，若内容为9则成功；

若查不到，则返回一个特殊值，如空指针或空记录。

优点：查找效率高

缺点：空间效率低！

 

 注意：第一次计算的时候，即使不符合，也不能说明Hash表里面没有该值。

例题：

已知一组关键字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79)

散列函数为：H(key)=key mod13，散列表长为m=16，

设每个记录的查找概率相等

线性探测再散列：

用线性探测再散列处理冲突，即Hi=(H(key)+di) MOD m

 

 H(19)=6 H(84)=6冲突，H(84)=(6+1)MOD13=7

H(14)=1 冲突，H(84)=(6+2)MOD13=8

H(23)=10 H(27)=1冲突，H(27)=(1+1)MOD13=2

H(1)=1 冲突，H(1)=(1+1)MOD13=2 冲突，H(27)=(1+2)MOD13=3

H(68)=3 冲突，H(27)=(1+3)MOD13=4

H(20)=7 ……

ASL=(1 * 6 + 2 + 3 * 3 + 4 + 9)/12=2.5

用链地址法处理冲突：

 

 散列表的查找效率分析

使用平均查找长度ASL来衡量查找算法，ASL取决于

1. 散列函数

2. 处理冲突的方法

3. 散列表的装填因子α

α=表中填入的记录数/哈希表长度

ASL与装填因子α有关！既不是严格的O(1)，也不是O(n)

 

 结论：

1. 散列表技术具有很好的平均性能，优于一些传统的技术

2. 链地址法优于开地址法

3. 除留余数法作散列函数优于其它类型函数

3.散列函数的构造方法

 

散列存储

选取某个函数，依该函数按关键字计算元素的存储位置

Loc(i)=H(keyi)

冲突，不同的关键码映射到同一个散列地址

key1≠key2，但是H(key1)=H(key2)

在散列查找方法中，冲突是不可能避免的，只能尽可能减少。

使用散列表要解决两个重要的问题

1）构造好的散列函数

1. 所选函数尽可能简单，以便提高转换速度

2. 所选函数对关键码计算出的地址，应该在散列地址集中致均匀分布，以减少空间浪费

2）制定一个好的解决冲突的方案

查找时，如果从散列函数计算出的地址中查不到关键码，则应该依据解决冲突的规则，有规律地查询其它相关单元。

构造散列函数考虑的因素：

1. 执行速度（即计算散列函数所需要的时间）

2. 关键字的长度

3. 散列表的大小

4. 关键字的分布情况

5. 查找频率

所以根据元素集合的特性构造，我们就必须考虑到散列查找实际上就是以空间换时间，但我们仍然希望散列的地址空间尽量小而且无论是用什么方法进行存储，目的都是尽可能均匀地存放元素，以避免冲突。

通常，我们会采取以下六种常见方法：

1. 直接定址法

2. 数字分析法

3. 平方取中法

4. 折叠法

5. 除留余数法

6. 随机数法

接下来，主要来介绍上述的6种方法

1.直接定址法

Hash(key)=a·key+b（a、b为常数）

优点：以关键码key的某个线性函数值为散列地址，不会产生冲突。

例：{100, 300, 500, 700, 800, 900} 散列函数Hash(key) = key/100 (a=1/100, b = 0)

 

2.除留余数法

Hash(key) = key mod p（p是一个整数）

关键在于选取合适的p

技巧在于设表长为m，取p≤m且为质数

例：{15, 23, 27, 38, 53, 61, 70}，

散列函数Hash(key)=key mod 7

 

4.散列表解决冲突的方法

1. 开放定址法（开地址法）

2. 链地址法（拉链法）

3. 再散列表法（双散链函数法）

4. 建立一个公共的溢出区

1.开放定址法

基本思想：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。

例如：除留余数法 Hi = (Hash(key) + di) mod m di为增量序列

常用方法：

1. 线性探测法 di为1,2，……m-1线性序列

2. 二次探测法 di为1^2, -1^2，…… q^2二次序列

3. 伪随机探测法 di为伪随机数序列

线性探测法：

Hi = (Hash(key) + di) mod m (1≤ i ≤ m)

其中的m为散列表长度，di为增量序列1,2，……m-1，且di = i

一旦冲突，就找到下一个地址，直到找到空地址存入。

例：关键码集为{47, 7, 29, 11, 16, 92, 22, 8, 3}，散列表的表长为m=11；散列函数为Hash(key) = key mod 11；拟用线性探测是否有冲突。建散列表加下：

  

如图，因为当29mod11得到7，与我们的原有的7相冲突，此时，通过线性探测法，我们应该判断7的下一个位置，是否为空，若为空则线性往下进行存储。

  

依次往复地进行计算、存储，有如下图形式：

  

当我们要对其中数据进行查找的时候，实际上也是要重复上述的操作的，也就是取模，如果发现数据不符，则继续往后面线性查找。

二次探测法：

例：关键码集为{47, 7, 29, 11, 16, 92, 22, 8, 3}，散列表的表长为m=11；散列函数为Hash(key) = key mod 11；拟用二次探测法是否有冲突。

Hi = (Hash(key) + di) mod m (1≤ i ≤ m)

其中的m为散列表长度，di为增量序列1,2，……m-1，且di = i

其中：m为散列表长度，m要求是某个4k+3的质数；

di为增量序列1^2 ， -1^2， 2^2， -2^2，……， q^2

  

例如存储3的时候发现原来的位置已经被占用了，即Hash(3)=3，散列地址冲突，由 H1=(Hash(3)+12)mod11=4，仍然冲突，则继续H2=(Hash(3)-12)mod 11 = 2，找到空的散列地址，存入。

伪随机探测法：

H1 = (Hash(key)+di) mod m (1≤ i ≤ m)

其中：m为散列表长度，di为伪随机数

2.链地址法

基本思想：相同散列地址的记录链成一单链表

m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。

例如：一组关键字为{19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79}，散列函数为Hash(key)=key mod 13

 

链地址法建立散列表步骤

Step1:取数据元素的关键字key,计算其散列函数值（地址）。若该地址对应的链表为空，则将该元素插入此链表；否则执行Step2解决冲突。

Step2:根据选择的冲突处理方法，计算关键字key的下一个存储地址。若该地址对应的链表为不为空，则利用链表的前插法或后插法将该元素插入此链表。

链地址法的优点：

1. 非同义词不会产生冲突，无“集聚”现象

2. 链表上结点空间动态申请，更适合子表不确定的情况