5. 桶散列¶
5.1. 桶散列¶
闭散列把所有记录直接存储在散列表中。 每条具有键值 \(k_R\) 的记录 \(R\) 都有一个 起始位置 ，即由散列函数计算出的槽位 \(\textbf{h}(k_R)\) 。 如果要插入 \(R\) ，而另一条记录已经占据了 \(R\) 的起始位置，那么 \(R\) 将被存储在表中的其他某个槽位。 由冲突解决策略来决定是哪一个槽位。 当然，查找时必须遵循与插入时相同的策略，这样，任何不在其起始位置找到的记录都可以通过重复冲突解决过程来找到。
闭散列的一种实现是把散列表的槽位分组为 桶 。 散列表的 \(M\) 个槽位被划分成 \(B\) 个桶，每个桶由 \(M/B\) 个槽位组成。 散列函数把每条记录分配到某个桶内的第一个槽位。 如果该槽位已被占用，则依次查找该桶内的槽位，直到找到一个空槽位。 如果某个桶完全满了，那么该记录就被存储在表末尾一个容量无限的 溢出桶 中。 所有桶共享同一个溢出桶。 好的实现会使用能把记录均匀分配到各个桶的散列函数，从而让尽可能少的记录进入溢出桶。
查找一条记录时，第一步是对键进行散列，以确定该记录应位于哪个桶。 然后查找该桶中的记录。 如果没有找到所需的键值，而该桶仍有空闲槽位，那么查找就结束了。 如果该桶已满，那么所需记录可能存储在溢出桶中。 在这种情况下，必须查找溢出桶，直到找到该记录或检查完溢出桶中的所有记录。 如果溢出桶中有很多记录，这将是一个昂贵的过程。
现在你可以自己试一试。
5.2. 另一种方法¶
桶散列的一种简单变体是：像没有使用分桶一样，把键值散列到散列表中的某个槽位。 如果起始位置已满，我们就查找该桶中其余的槽位，以找到一个空槽位。 如果该桶中的所有槽位都已满，那么该记录就被分配到溢出桶。 这种方法的优点是减少了初始冲突，因为任何槽位都可以作为起始位置，而不仅仅是桶中的第一个槽位。
桶方法非常适合实现存储在磁盘上的散列表，因为桶的大小可以设置为磁盘块的大小。 每当发生查找或插入时，整个桶都会被读入内存。 由于整个桶随后都在内存中，处理一次插入或查找操作只需一次磁盘访问，除非该桶已满。 如果该桶已满，那么还必须从磁盘取回溢出桶。 当然，应使溢出保持很小，以尽量减少不必要的磁盘访问。
