开放散列和闭合散列的含义

“关闭”和“开放”的使用反映了我们是否被锁定在使用特定的位置或数据结构(这是一个非常模糊的描述，但希望其余部分有所帮助)。

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

“闭合散列”中的“闭合”指的是这样一个事实: 我们从不离开散列表; 每个对象都直接存储在散列表内部数组的索引中。请注意，只有使用某种开放式寻址策略才能做到这一点。这就解释了为什么“封闭散列”和“开放寻址”是同义词。

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

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".

名称 open addressing指的是元素的位置(“地址”)不是由其散列值决定的。(此方法也称为闭合散列)。

在 分开链接中，每个存储桶都是独立的，并且有一些具有相同索引的条目的 ADT (列表、二进制搜索树等)。 在一个好的哈希表中，每个 bucket 有零个或一个条目，因为我们需要 O (1)顺序的操作来插入、搜索等。

这是使用 C + + 的 分开链接的 例子，带有一个使用 mod 操作符 (显然是一个错误的哈希函数)的简单散列函数

您有一个数组，它就是“散列表”。

在 Open 散列中，数组中的每个单元格都指向一个包含冲突的列表。散列为链表中的所有项生成了相同的索引。

在闭合哈希中，对于所有内容只使用一个数组。将冲突存储在同一个数组中。诀窍是使用一些聪明的方法从一个碰撞跳到另一个碰撞，直到你找到你想要的。并且以可重复/确定的方式来做这件事。