学科分类
目录
数据结构

哈希文件

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

对于文件来说,它与哈希表还是不同的,磁盘的文件记录通常是成组存放的,若干个记录组成一个存储单位,在哈希文件中,这个存储单位叫作桶(Bucket)。假如一个桶能存放m个记录,当桶中已经有m个同义词记录时,再存放第m+1个同义词记录时就会发生“溢出”。处理“溢出”可采用哈希表中处理冲突的各种方法,但在哈希文件中,主要采用拉链法。

处理冲突时,需要将第m+1个记录放到另一个桶中,通常称此桶为“溢出桶”,相对的,称前m个同义词存储的桶为“基桶”。注意:溢出桶和基桶大小相同,相互之间用指针相连接。

例如现在有一组关键字集合{12,65,26,5,896,15,64,25,698,6,97,321,256,14,3,8,68,50};假如有4个桶,桶的容量为5,则根据除留余数法构建哈希函数,那么构建的哈希文件如图1所示。

图1 哈希文件结构图

在哈希文件中进行查找时,首先根据给定值求出哈希桶地址,将基桶的记录读入内存,进行顺序查找,若找到关键字等于给定值的记录,则检索成功;当在基桶中没有找到待查找记录时,就沿着指针到所指的溢出桶中进行查找。因此,在构建文件时,希望同一哈希地址的溢出桶和基桶,在磁盘上的物理位置不要相距太远,最好在同一柱面上。而删除记录时,仅需对删除记录标记即可。

哈希文件的文件记录是随机存放的,不需要对记录进行排序;而且其插入删除操作也颇为方便,存取速度快,不需要索引区,节省存储空间。当然,它也有一些缺点,不能进行顺序存储,只能按关键字随机存取,查询方式限于简单查询,在经过多次插入、删除后,可能造成文件结构不合理,需要重新组织文件。

点击此处
隐藏目录