闭散列之线性探查

来自计算思维百科
跳转至: 导航搜索
闭散列之线性探查1.png

我们知道散列法是存储大量数据的有效方法,但是任何散列函数都会出现碰撞的现象,闭散列就是讲所有键都存在散列表中的一种解决碰撞的方法。

基本概念

在闭散列中,所有键都存储在散列表本身(意味着表长不能小于键的数量)。当发生碰撞时,就把后来的键安排在当前位置的下一个,若下一个被占,则继续下一个,有空就进,若一直走到表尾都无,则回到开头再找空位。

应用范围

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

使用方法及步骤

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

2.根据散列函数计算得到地址,并填入散列表

3.若发生碰撞,则后来者往后面的空位走,有空就存入;若走到表尾都没有,就回到起始处找空位存入。

应用案例

应用1-线性探查和平解决抢座位

案例:在介绍开散列解决冲突的时候我们采用的是往后面坐的方法,这里我们再次回到那个案例,回到下面的座位图:(假设同学来的次序按学号大小排列)

              散列法分布学生座位表

闭散列之线性探查2.png

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

解决步骤:

利用线性探查方法解决作为问题:同学40和同学51,同学41先来了坐到了第一排的7号桌,然后51号同学来了,发现座位被占了,于是51就看看8号,发现8好也被占了,那就再看9号。9号没人,可以坐下。同样对于52号同学来说,也是一样8号没位了,那就坐9号也不行。10号可以,坐下。这就是线性探查的方法思想。

应用2-坐公交

案例:坐过公交的人都知道,公交车上的座位分为普通座位、孕妇专用、残疾人专座。一开始人不太多时,我们可以随意找个普通的空座位坐下;后来人越来越多,普通座位空的慢慢变少,这时候有人上车,从入口进来他想坐他习惯的那个靠窗的位置,但发现被坐了,然后售货员就会让车上的人往后坐。那他就继续往后走,有位置就坐下,一直走到车尾都没空位,那就可以走到前面看看有没有人下车了可能有空位。

解决步骤:在这个案例中,公车座位就可以看成是一个散列表,普通座有很多个,找位置的过程就相当于散列函数,每个乘客相当于键,而本来想坐的位置就可以看出键的目标地址,发现位置被占后寻找空位的过程就是一个线性探查的过程。

可以体现的计算思维

闭散列的线性探查处理碰撞的方式没有耗费更多的存储空间,但是线性探查需要消耗时间,是利用时间换取了空间,表现了计算思维中的折中特点。