hash - 开放散列和封闭散列的含义

Question

开放散列(单独链接):

In open hashing, keys are stored in linked lists attached to cells of a hash table.

封闭散列(开放寻址):

In closed hashing, all keys are stored in the hash table itself without the use of linked lists.

我无法理解为什么它们被称为开放式、封闭式和分离式。谁能解释一下吗？

Answer 1

“封闭”与“开放”的使用反射(reflect)了我们是否被锁定使用某个位置或数据结构(这是一个极其模糊的描述，但希望其余部分有所帮助)。

例如，“开放寻址”中的“开放”告诉我们，对象在哈希表中存储的索引(又称地址)并不完全由其哈希码确定。相反，索引可能会根据哈希表中已有的内容而变化。

“封闭式哈希”中的“封闭”是指我们永远不会离开哈希表；每个对象都直接存储在哈希表内部数组的索引处。请注意，这只能通过使用某种开放寻址策略来实现。这解释了为什么“封闭散列”和“开放寻址”是同义词。

将此与开放散列进行对比 - 在该策略中，没有任何对象实际上存储在散列表的数组中；相反，一旦对象被散列，它就会存储在与散列表的内部数组分开的列表中。 “开放”是指我们通过离开哈希表并使用单独的列表而获得的自由。顺便说一句，“单独列表”暗示了为什么开放散列也称为“单独链接”。

简而言之，“封闭”始终指某种严格保证，例如我们保证对象始终直接存储在哈希表中(封闭哈希)。那么，“封闭”的反面是“开放”，所以如果你没有这样的保证，策略就被认为是“开放”。