开放散列和封闭散列的含义 [英] Meaning of Open hashing and Closed hashing

问题描述

打开哈希（单独链接）：

在打开的哈希中，键存储在链接列表中，该列表附加到哈希表的单元格中。

封闭散列（Open Addressing）：

<

在封闭散列中，所有键都存储在散列表本身中，而不使用链表。为什么他们被称为开放，封闭和分离。有人可以解释它吗？

解决方案

使用封闭与开放反映我们是否被锁定使用某个位置或数据结构（这是一个非常模糊的描述，但希望其他的帮助）。

例如，开放寻址告诉我们一个对象将被存储在哈希表中的索引（又名。地址）并不完全由其哈希码确定。相反，索引可能会有所不同，具体取决于散列表中已有的内容。

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

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

总之，封闭总是指某种严格保证，就像我们保证对象总是直接存储在散列表中一样（关闭散列）。然后，封闭的对面就是开放，所以如果你没有这样的保证，那么这个策略就被认为是开放的。

Open Hashing (Separate Chaining):

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

Closed Hashing (Open Addressing):

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

I am unable to understand why they are called open, closed and Separate. Can some one explain it?

解决方案

The use of "closed" vs. "open" reflects whether or not we are locked in to using a certain position or data structure (this is an extremely vague description, but hopefully the rest helps).

For instance, the "open" in "open addressing" tells us the index (aka. address) at which an object will be stored in the hash table is not completely determined by its hash code. Instead, the index may vary depending on what's already in the hash table.

The "closed" in "closed hashing" refers to the fact that we never leave the hash table; every object is stored directly at an index in the hash table's internal array. Note that this is only possible by using some sort of open addressing strategy. This explains why "closed hashing" and "open addressing" are synonyms.

Contrast this with open hashing - in this strategy, none of the objects are actually stored in the hash table's array; instead once an object is hashed, it is stored in a list which is separate from the hash table's internal array. "open" refers to the freedom we get by leaving the hash table, and using a separate list. By the way, "separate list" hints at why open hashing is also known as "separate chaining".

In short, "closed" always refers to some sort of strict guarantee, like when we guarantee that objects are always stored directly within the hash table (closed hashing). Then, the opposite of "closed" is "open", so if you don't have such guarantees, the strategy is considered "open".

这篇关于开放散列和封闭散列的含义的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！