数据结构-基于C++语言（微课版） 课件 1-1 散列表

散列表的基本概念；散列函数的设计方法；处理冲突的方法。本节目录：本节内容：散列表散列表

散列表

什么是查找?

确定待查找值k在存储结构中的位置。有哪些查找技术？

顺序查找、折半查找、二叉排序树查找等技术都是通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数。关键码可以直接确定存储位置？

在记录的存储地址和它的关键码之间建立一个确定的对应关系散列表

散列的基本思想：在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。3关键码集合kiriH(ki)…………H散列表

散列表：采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表，可以用一维数组来描述。关键码集合kiriH(ki)…………H散列表散列表

散列函数：将关键码映射为散列表中适当存储位置的函数。关键码集合kiriH(ki)…………H散列表散列函数散列表

散列地址：由散列函数所得的存储地址。关键码集合kiriH(ki)…………H散列表散列函数散列地址下标散列表

由于在散列表中记录的存储位置是根据关键码和散列函数计算所得，因此散列表并不支持范围查找，例如，散列表不支持查找关键码最大、最小、大于等于某值、小于等于某值等范围查找。散列表最适合的问题是，散列表中哪个记录的关键码等于待查找的关键码值。散列技术在计算机领域具有广泛的应用，例如信息加密、数据校验、负载均衡等。对于两个不同的关键码ki≠kj，有H(ki)=H(kj)，即两个不同的记录需要存储到同一个散列地址中，这种现象称为冲突。ki和kj相对于H称做同义词。冲突太多会降低查找效率，因此要设计一个均匀、存储利用率高的散列函数，即散列函数计算出来的地址应能均匀分布在整个地址空间中。但是冲突难以避免。散列查找中最关键的两个问题为散列函数的设计和冲突的处理。散列函数

散列函数设计原则：散列函数的定义域必须包括需要存储的全部数据元素的关键字，而如果散列表允许有m个地址时，其值域必须在0到m-1之间；散列函数计算出来的地址应能均匀分布在整个地址空间中，若key是从关键字集合中随机抽取的一个关键字，散列函数应能以同等概率取0到m-1中的每一个值；散列函数应是简单的，能在较短的时间内计算出结果。散列函数

散列函数——直接定址法

0123456789103050708090散列函数

散列函数——数字分析法分析关键码，例如前几位数字大体相同的一组学号，如果选用前几位数字构造散列地址，则出现冲突的概率较大。如选择差别较大的几位数字构造散列地址，则冲突的概率会明显降低。找出数字的规律，利用这些数据来构造冲突较少的散列地址。例：关键码为8位十进制数，散列地址为2位十进制数81346

5

3

281372

2

4281387

4

2281301

3

6781322

8

1781338

9

67①②③④⑤⑥⑦⑧散列函数

散列函数——除留余数法

1470147014散列地址56494235282114关键码例：若取p=21，产生了大量冲突散列表

在构造散列表的过程中，在存储关键码对应的记录时，如果H(key)已经被占用，则必须另外再寻找一个空闲的位置来存储记录。采用不同的处理冲突的方法，就会得到不同的散列表。常用的处理冲突的方法有开地址方法和链地址方法。散列表

处理冲突的方法——开放定址法由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。使用开放定址法构造的散列表称为闭散列表。如何寻找下一个空的散列地址?线性探测法二次探测法随机探测法散列表

线性探测法当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地址。假设对于关键码key，H(key)=d，闭散列表的长度为m，则线性探测法寻找下一个空闲位置的公式为：Hi=(H(key)+di)

%

m

(di=1,2,⋯,m−1)例：关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用线性探测法处理冲突，则散列表为：47729111692292222883333堆积：在处理冲突的过程中出现的非同义词之间对同一个散列地址争夺的现象。012345678910线性探测法散列表

二次探测法当发生冲突时，寻找下一个散列地址的公式为：

Hi=(H(key)＋di)%m，di=12，-12，22，-22，…，q2，-q2

且q≤m/2例：关键码集合为{47,7,29,11,16,92,22,8,3}，散列表表长为11，散列函数为H(key)=keymod11，用线性探测法处理冲突，则散列表为：4772911169229222288333012345678910散列表

双散列法使用双散列方法处理冲突时，需要两个散列函数。第一个散列函数Hash()按数据元素的关键字key计算出数据元素存放地址。一旦发生冲突，利用第二个散列函数ReHash()计算出数据元素下一地址，它的取值与key的值有关，应小于地址空间的大小。散列表

散列表

处理冲突的方法——链地址法解决冲突的另一种方法称为开散列法，也称为链地址法、拉链法。基本思想为：将所有的同义词的记录存储为一个单链表，称为同义词子表，散列表存储的是同义词子表的头指针。使用链地址方法处理冲突构造的散列表称为开散列表。开散列表不会出现堆积现象。散列表

例：关键码集合{47,7,29,11,16,92,22,8,3}，散列函数为H(key)=keymod11，用拉链法处理冲突，构造的开散列表为：012345678910

11∧∧∧∧∧∧

22

47∧

3

92∧

16∧

7∧

29

8∧散列表

处理冲突的方法——链地址法解决冲突的另一种方法称为开散列法，也称为链地址法、拉链法。基本思想为：将所有的同义词的记录存储为一个单链表，称为同义词子表，散列表存储的是同义词子表的头指针。使用链地址方法处理冲突构造的散列表称为开散列表。开散列表不会出现堆积现象。散列表

散列表的装载因子是散列表中的记录数n和散列表表长m的比值，可表示为：