链式哈希表与开放寻址哈希表 [英] Chained Hash Tables vs. Open-Addressed Hash Tables

问题描述

有人能解释一下这两个实现（优势/劣势）之间的主要区别是什么？

Can somebody explain the main differences between (advantages / disadvantages) the two implementations?

有关库，建议采取什么执行？

For a library, what implementation is recommended?

推荐答案

维基百科上关于哈希表文章，给出了一个明显更好解释的，人们已经使用比我能够把我的头顶部的不同哈希表方案概述。事实上你可能会更好过阅读的文章比问的问题在这里。 ：）

Wikipedia's article on hash tables gives a distinctly better explanation and overview of different hash table schemes that people have used than I'm able to off the top of my head. In fact you're probably better off reading that article than asking the question here. :)

这表示...

一个链式哈希表的索引到一个指针数组链表的头。每一个链表单元具有其所分配的重点和插入该键的值。当你想从它的键查找特定的元素，关键的哈希值是用来工作，这链表跟随，然后该特定列表运行到发现你以后的元素。如果哈希表中的多个键具有相同的哈希，那么你就必须链表与多个元素。

A chained hash table indexes into an array of pointers to the heads of linked lists. Each linked list cell has the key for which it was allocated and the value which was inserted for that key. When you want to look up a particular element from its key, the key's hash is used to work out which linked list to follow, and then that particular list is traversed to find the element that you're after. If more than one key in the hash table has the same hash, then you'll have linked lists with more than one element.

链式散列的缺点是其遵循的指针，以搜索链表。的好处是，链式哈希表只能得到作为负载因数（在哈希表中的元素到铲斗阵列的长度的比）的增加线性地慢，即使它高于1

The downside of chained hashing is having to follow pointers in order to search linked lists. The upside is that chained hash tables only get linearly slower as the load factor (the ratio of elements in the hash table to the length of the bucket array) increases, even if it rises above 1.

这是开放寻址哈希表的索引到一个指针数组对（键，值）。您可以使用密钥的散列值摸出首先看该插槽数组中为止。如果哈希表中的多个键具有相同的哈希，然后你用一些计划，在另一个插槽决定看在代替。例如，线性探测是你看后一个选择，并在那之后的下一个插槽，依此类推，直至下一个时隙或者找到一个你正在寻找的密钥相匹配插槽，或者你打空槽（在这种情况下，钥匙必须不存在）。

An open-addressing hash table indexes into an array of pointers to pairs of (key, value). You use the key's hash value to work out which slot in the array to look at first. If more than one key in the hash table has the same hash, then you use some scheme to decide on another slot to look in instead. For example, linear probing is where you look at the next slot after the one chosen, and then the next slot after that, and so on until you either find a slot that matches the key you're looking for, or you hit an empty slot (in which case the key must not be there).

开放寻址是当客座率低，因为你没有按照列表中的节点之间的指针不是链式散列通常较快。它变得非常，非常缓慢的加载因子接近1​​，因为你最终通常有经过许多桶数组中的插槽来搜索你发现要么是你要找的关键还是一个空槽前。此外，你永远无法在哈希表中更多的元素之外还有斗阵中的条目。

Open-addressing is usually faster than chained hashing when the load factor is low because you don't have to follow pointers between list nodes. It gets very, very slow if the load factor approaches 1, because you end up usually having to search through many of the slots in the bucket array before you find either the key that you were looking for or an empty slot. Also, you can never have more elements in the hash table than there are entries in the bucket array.

要处理的事实，至少所有的哈希表变慢（在某些情况下，实际上完全打破）时，他们的负荷率接近1，实用的哈希表的实施使斗阵较大（通过分配一个新的水桶阵，和复制元素从旧到新的一个，那么释放旧的），当客座率得到超过一定值（通常约0.7）。

To deal with the fact that all hash tables at least get slower (and in some cases actually break completely) when their load factor approaches 1, practical hash table implementations make the bucket array larger (by allocating a new bucket array, and copying elements from the old one into the new one, then freeing the old one) when the load factor gets above a certain value (typically about 0.7).

有很多对所有上述的变型。再次，请参见维基百科的文章，还真是相当不错的。

There are lots of variations on all of the above. Again, please see the wikipedia article, it really is quite good.

有关，是为了被其他人使用图书馆，我的强烈的建议进行试验。因为他们一般是相当性能的关键，通常是最好关闭用别人的实现，它已经被精心调校的哈希表。有很多开源的BSD的，LGPL和GPL许可的哈希表的实现。

For a library that is meant to be used by other people, I would strongly recommend experimenting. Since they're generally quite performance-crucial, you're usually best off using somebody else's implementation of a hash table which has already been carefully tuned. There are lots of open-source BSD, LGPL and GPL licensed hash table implementations.

如果您正在使用GTK的工作，例如，那么你会发现，有一个很好的哈希表中GLib的。

If you're working with GTK, for example, then you'll find that there's a good hash table in GLib.

这篇关于链式哈希表与开放寻址哈希表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！