溢出处理

 若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做桶（Bucket）。

 假若一个桶能存放m个记录，这就是说，m个同义词的记录可以存放在同一地址的桶中，而当第m＋1个同义词出现时才发生“溢出”。对散列文件主要采用链地址法处理溢出。

 当发生“溢出”时，需要将第m＋1个同义词存放到另一个桶中，通常称此桶为“溢出桶”；相对地，称前m个同义词存放的桶为“基桶”。溢出桶和基桶大小相同，相互之间用指针相链接。当在基桶中没有待查记录时，就顺指针所指到溢出桶中进行查找。因此，希望同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。

图形表示

 例如，某一文件有18个记录，其关键字分别为278，109，063，930，589，184，505，269，008，083，164，215，330，810，620，110，384，355。桶的容量为m＝3，桶数b＝7。用除留余数法作哈希函数H(key)＝key MOD 7。由此得到的直接存取文件如图所示。

    查找过程：首先根据给定值求得哈希地址（即基桶号），将基桶的记录读入内存进行顺序查找，若找到关键字等于给定值的记录，则检索成功；否则，若基桶内没有填满记录或其指针域为空，则文件内不含有待查记录；否则根据指针域的值的指示将溢出桶的记录读入内存继续进行顺序查找，直至检索成功或不成功。

因此，总的查找时间为：

  其中：a为存取桶数的期望值（相当于哈希表中的平均查找长度），对链地址处理溢出来说，a = 1 + α/2；te为存取一个桶所需的时间；ti为在内存中顺序查找一个记录所需的时间。

直接存取文件的特点

  优点：文件随机存放，记录不需进行排序；插入、删除方便，存取速度快，不需要索引区，节省存储空间。

  缺点：不能进行顺序存取，只能按关键字随机存取，且询问方式限于简单询问，并且在经过多次的 插入、删除之后，也可能 造成文件结构不合理，即溢出桶满而基桶内多数为被删除的记录。此时亦需重组文件。