|
||||
|
|
|||
三、冲突解决策略/开散列方法 1、拉链法
2、桶式散列 桶式散列方法的基本思想是把一个文件的记录分为若干存储桶,每个存储桶包含一个或多个页块,一个存储桶内的各页块用指针连接起来,每个页块包含若干记录。散列函数h把关键码值K转换为存储桶号,即h(K)表示具有关键码值K的记录所在的存储桶号。 图9-6表示了一个具有B个存储桶的散列文件组织。有一个存储桶目录表,存放B个指针,每个存储桶一个,每个指针就是所对应存储桶的第一个页块的地址。 有些存储桶仅仅由一个页块组成,如下图中的1号存储桶。有的存储桶由多个页块组成,每一个页块的块头上有一个指向下一个页块的指针,例如,如下图中的第B-1号存储桶由b4,b5,b6三个页块组成,每个存储桶中最后一个页块的头上为空指针。 |