每周学点大数据 | No.61磁盘算法实践（下）

NO.61

磁盘算法实践（下）

Mr. 王：嗯，这是一个应用非常广泛的数据结构，跟你讲讲它的原理吧。Hash 表又叫散列表，是一种非常常见的用于实现数据字典的数据结构。它的原理非常简单，却能实现非常高效的插入、删除和查找。其时间复杂度为O(1)。

小可：这么快，常数时间的查找在以前提到过的数据结构中还是非常少见的啊！

Mr. 王：先来谈谈散列表的原理。其之所以能够以这么快的速度进行查找，就是因为在散列表中，数据记录值和其所保存的位置（地址）之间有着非常强的直接关联。一般来说，最常见的散列表的空间大小为一个素数m，这个素数的大小根据要存储的数据多少来定。这里先以存储的关键字是数字为例。比如要存储学生的编号和姓名，一条记录就是

这样的结构，例如<19,Peter>。假如散列表大小为11。每当要执行一个添加或者查找操作时，我们就进行如下运算：

address = key mod m

对于这个例子，address = 19 mod 11 = 8。

所以我们将 <19,Peter> 这条记录存储在散列表中的8 号位置。

小可：哦！我明白了。同理，当我需要查找编号为19 的记录时，需要做的同样是用这个编号去对m=11 求余数，求出的结果8 就是它的地址了。

Mr. 王：非常好，如果散列表是用数组实现的，每当我们拿到一个数据时，就可以直接求出它的数组下标，根据对应的下标查找数据就可以了。不难看出，查找一个数据和数据规模n没有关系，只需要通过对数据的值进行计算即可，所以时间复杂度是O(1)。

小可：可是，19 mod 11 = 8，30 mod 11 也是8，如果这个散列表中同时存在编号为19 和30 两条记录怎么办呢？

Mr. 王：很好，你注意到了这个问题。当数据逐渐增多时，很多时候两个数据要放在同一个地址中，散列表的内部会发生冲突。这时候我们就需要对这些冲突的数据进行处理，常见的方法有内散列和外散列。内散列的策略是，当发生冲突时，新添加的数据放置到下一个位置上，这时只需要增加一个判断，判断该地址上是不是已经有数据了即可。

内散列的缺点是很明显的，一旦发生了冲突，就会去冲撞其他的地址，引起的冲突会越来越严重。

外散列又叫拉链法，其策略是，当发生冲突时，它会在对应地址的外部创建一个链表，当查找数据时，去查找这个链表即可。

相比之下，外散列方法会更加常用一些。

Mr. 王：当散列表中的数据不那么多，冲突不严重时，可以近似达到O(1) ；而当其中存储的数据较多时，性能会发生一定程度的下降，但散列表仍然不失为一种非常好的查找结构。关于散列表的寻址方法，这里只是举了一个最简单、最经典的散列函数例子，散列函数除了取模这种方法外，还有很多方法，如果你感兴趣，可以去查阅关于散列表的资料。相应的，Unpin 操作是将编号为pid 的页解除Pin 状态。如果这个页是一个脏页，则要对其进行标注。所谓的脏页，就是磁盘和内存缓冲区中的内容不一致的数据。其执行的前置条件是，这个页本身一定是保存在缓冲区中，并且是已经被Pin 过的，否则会向用户报错。

下面是UnpinPage 的源代码。

Mr. 王：其中，PinPage 和UnpinPage 这两个函数对页的Pin 和Unpin 操作，只需要修改

Pin 和Unpin 帧数的计数就可以了。

文章作者：王宏志

文章编辑：秦革