开散列(分离链)

来自计算思维百科
跳转至: 导航搜索
开散列(分离链)1.png

我们知道散列法是存储大量数据的有效方法,但是任何散列函数都会出现碰撞的现象,开散列是通过将键存至散列表的附着链表上,以解决碰撞的一种散列方法。

基本概念

在开散列中,如果两个键值得到的散列函数值是相同的,我们就相同的记录数据存储在一个链表中。每个链表中包含着所有散列到此单元格的记录。

应用范围

开散列是解决散列冲突的方法,故涉及到散列方面的应用都可能用到开散列,经常用于存在大量相似数据的应用中。

使用方法及步骤

1.在给定问题中,寻找可以作为键的字段。即要可以唯一标识记录的字段。

2.利用散列函数计算键地址,将其挂到地址对应的单元格的链表中。

3.查找键:利用散列函数找到在哪个单元格,再逐一扫描附着着单元格的链表。

应用案例

应用1-和平解决抢座位

案例:在介绍散列法的时候我们说到了占座位的案例,这里我们再次回到那个案例,回到下面的座位图:

              散列法分布学生座位表

开散列(分离链)2.png

在此案列中,我们利用学号求余的方式发现有四个同学发生了抢座位的冲突,如何解决呢?

解决步骤:

很明显,一个座位不能坐两个人。那我们可以这样协调:40同学和51同学你们都想坐在这一列,但第一排只能一个人,那可以你们谁先来就先做第一排,那后来的就在第7列的后一排补上;同样地,那41同学和52同学后来的就在第8列的后一排补上。如果有更多的如学号63的同学来了,他就继续补到第8列的后后一排。这个过程就是开散列解决碰撞的方法。

应用2-开散列存单词并查找

案例:考虑下面这些单词:

A,FOOL,AND,HIS,MONEY,ARE,SOON,PARTED

我们把单词的每个字母在字母表中的位置加起来作为参与运算的键值对13取模,存入开散列中。然后在这个字典中查找KID。

解决步骤:

A:    1 mod 13=1

FOOL:  (6+15+15+12)mod 13=9

AND:  (1+14+4)mod 13=6

依次类推,得到散列地址如下:

A

FOOL

AND

HIS

MONEY

ARE

SOON

PARTED

散列地址

1

9

6

10

7

11

11

12

可以发现,ARE和SOON存在碰撞,利用开散列的方法我们就得到了这么一个字典:

开散列(分离链)3.png

在上面这个字典中,当我们要查KID时,先计算其对应地址,即(11+9+4)mod 13=11。然后我们就在字典的第11个位置开始,扫描改地址下的链表,发现没有KID,即查找失败。

可以体现的计算思维

从开散列的处理方式来看,虽然碰撞问题解决了,也节省了查找时间,但空间的开销大了,这就是时空权衡,体现了计算思维中的折中特点。