散列文件

基本概念

文件优缺点

基本概念

散列文件是利用散列存储方式组织的文件，亦称为直接存取文件。它类似于散列表，即根据文件中关键字的特点，设计一个散列函数和处理冲突的方法，将记录散列到存储设备上。

与散列表不同的是，对于文件来说，磁盘上的文件记录通常是成组存放的，若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶(Bucket)。假如一个桶能存放m个记录，则当桶中已有m个同义词的记录时，存放第m+1个同义词会发生"溢出"。处理溢 出虽可采用散列表中处理冲突的各种方法，但对散列文件而言，主要采用拉链法。

在散列文件中进行查找时，首先根据给定值求出散列桶地址，将基桶的记录读入内存，进行顺序查找，若找到关键字等于给定值的记录，则检索成功；否则，读入溢出桶的记录继续进行查找。

在散列文件中删去一个记录，仅需对被删除记录标记即可。

文件优缺点

散列文件的优点是：文件随机存放，记录不需进行排序；插入、删除方便；存取速度快；不需要索引区，节省存储空间。其缺点是：不能进行顺序存取，只能按关键字随机存取，且询问方式限于简单询问，并且在经过多次插入、删除后，也可能造成文件结构不合理，需要重新组织文件。