散列法

来自计算思维百科
跳转至: 导航搜索
散列法1.png

如果我们要把一些没有规律的数据存放起来,怎么才能快速地找到呢?算列法就是一种高效查找到所需数据的方法,这种方法通过一定的方法(函数)将数据分布在散列表中,当你需要查找的时候,只要用这个函数算数据存放的位置就可以了。

基本概念

键:通常情况下,一条记录有很多字段构成,如学生的信息记录就包含学生姓名、性别、年级、专业和学号等字段。而键就是可用于标识一条记录信息的字段,可以为1个或多个。比如每个学生的学号都是唯一的,就可以做为键。

散列表:用于存储键的一维数组。

散列地址:由一个特定的函数利用键值计算得到的该键在散列表中的位址。、

在有了上面的概念后,我们可以通俗地定义散列法,即可以通过一个特定的方法(这个方法就是散列法)利用与键值相关的计算得到一个与散列表相关的地址,这样我们就把件分布到了散列表中,可是,当我们计算得到两个或多个不同的键对应到散列表的同一位置时,我们就说发生了碰撞。

应用范围

散列法被广泛用于各个计算机领域,如使用密码散列法的病毒定位,挖掘数据库中的关联规则以及数据库数据存取等。

使用方法及步骤

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

2.设计一个散列函数尽可能使得计算结果在散列表中的位址均匀分布,且函数易于计算;

应用案例

应用1-占座位

案例:步入大学,想必大家对于占座位很有感触吧!现在,我们事先给出这样一个规定:班里有10个同学都想抢夺的座位是教室的第一排,可是这排有11个座位,为了公平起见,约定根据学号的后两位来确定座位,即用学号后两位数对11求余数,余数对应着第一排的列数。这10个同学的学号中有3个同学的为40~42,剩余的7个同学的学号后两位为46~52,那么这10位同学能如愿以偿的占到这一排自己对应的座位吗?

解决步骤:

在上述案例中,学生的学号后两位就相当于键,第一排座位就相当于一个散列表,而分配座位的约定就相当于散列函数。下面我们就来分布座位:

40 mod 11=7       41 mod 11=8

42 mod 11=9       46 mod 11=2

47 mod 11=3       48mod 11=4

49 mod 11=5       50 mod 11=6

51 mod 11=7       52 mod 11=8

可以发现,即使座位是够做的,但仍不避免地存在着有同学想要的座位是同一个,这就是散列法中的碰撞。

散列法分布学生座位表

散列法2.png

显然,学号为40和51,41和52的同学对应的座位是同一个,那对于他们来说,常规的方法就是先占先得咯。当然,我们会在后续介绍如何解决碰撞的方法。

应用2-机场登机口

案例:当我们去机场时,通常的流程时先取票,过了安检后我们就可以到自己相应的登机口候机。一般情况下,如果我们将一趟航班看做一个整体,在同一时段,一个登机口只允许一趟航班的乘客通行,其他的航班乘客不能够进入此登机通道。

在这个例子中,机场就是通过了一定的航空调配(就可以看做一个散列函数)将各个航班分布到各个登机口,每一趟航班都是唯一的。各个登机口就组成了一个散列表,而航班就相当于键。

应用3-查找书籍

案例:当我们去图书馆借书时,如果我们事先不做任何检索那么我们只有一本一本去找,无疑那是非常费时的。所以聪明的做法是什么呢?我们会现在电脑上,做一个搜索,找到像要的书所在的排和列。

在这个例子中,如果事先已经存在一张散列表,该表里记录了每一类书与排的对应和架的对应,那么当我们输入一本书的信息时,系统可以依据输入的书信息比如编号,然后利用编号做一个与之整理书籍时相同的方法就可以得到结果也就是书本所在的书架号,这样一个过程里, 书的信息就相当于一个键,书架就相当于一个散列表,整理摆放书籍的方法就相当于一个散列函数。可以看出这样大大节省了时间。

可以体现的计算思维

从上面的实例中可以发现,散列法实际上是一种对空间进行管理的一种方法,生活中很多事物都可以看成一个散列表,同时,我们开拓了空间来减少了耗费的时间,这也是一个关于时空权衡的思想,体现了计算思维中的抽象和折中特点。