开散列方法

冲突解决技术可以分为两类：开散列方法( open hashing，也称为拉链法，separate chaining )和闭散列方法( closed hashing，也称为开地址方法，open addressing )。这两种方法的不同之处在于：开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内。

冲突解决策略——开散列方法

1、拉链法

开散列方法的一种简单形式是把散列表中的每个槽定义为一个链表的表头。散列到一个特定槽的所有记录都放到这个槽的链表中。例，一个开散列的散列表，这个表中每一个槽存储一个记录和一个指向链表其余部分的指针。这7个数存储在有11个槽的散列表中，使用的散列函数是h(K) = K mod 11。数的插入顺序是77、7、110、95、14、75和62。有2个值散列到第0个槽，1个值散列到第3个槽，3个值散列到第7个槽，1个值散列到第 9个槽。

2、桶式散列

桶式散列方法的基本思想是把一个文件的记录分为若干存储桶，每个存储桶包含一个或多个页块，一个存储桶内的各页块用指针连接起来，每个页块包含若干记录。散列函数h把关键码值K转换为存储桶号，即h(K)表示具有关键码值K的记录所在的存储桶号。

例，一个具有B个存储桶的散列文件组织。有一个存储桶目录表，存放B个指针，每个存储桶一个，每个指针就是所对应存储桶的第一个页块的地址。

有些存储桶仅仅由一个页块组成，如下图中的1号存储桶。有的存储桶由多个页块组成，每一个页块的块头上有一个指向下一个页块的指针，例如，如下图中的第B-1号存储桶由b4，b5，b6三个页块组成，每个存储桶中最后一个页块的头上为空指针。