通常的哈希表实现相比树 [英] usual hashtable implementation compared to tree

问题描述

通常（如在C ++中），散列函数返回任何size_t值 - 因此许多不同的散列值是可能的（2 ^ 32）。

Usually (as in C++), the hash function returns any size_t value -- thus many different hash values are possible (2^32).

我总是认为，当人们谈论他们被实现为表，这在实践中不是真的真的，因为表将是太大（2 ^ 32条目）。当然，我的假设是错误的，表必须和散列值的全部范围一样大。

That is why I always thought that when people talked about them being implemented as tables, that is not really true in practice because the table would be much too big (2^32 entries). Of course my assumption was wrong that the table must be as big as the full range of hash values.

似乎实际的实现比我想象的更困难。我总是想到，什么是天真的实现，是这样的：

It seems that the actual implementation is more difficult than I thought. What I always had in mind, what would be the naive implementation, is something like:

typedef list< pair<Key,Value> > Bucket;
typedef map< size_t, Bucket > Hashtable;

现在我的问题：这个朴素的实现如何与实践中的实践不同运行时和内存）？

Now my question: How does this naive implementation differs from actual implementations in the praxis in terms of complexity (runtime and memory)?

推荐答案

注意，还有其他方法来实现哈希表Matthieu M指出。本回答的其余部分假设您想使用由某种列表构成的桶进行哈希。

Note that there are other ways to implement hash tables as Matthieu M points out. The remainder of this answer assumes that you want to use hashing with buckets made of some kind of list.

假设您在谈论时间复杂性。

Assuming you are talking about time complexity.

哈希表希望具有O（1）最佳情况访问。您在该问题中的实施提案使用 地图< size_t，Bucket> 访问桶，这将导致O（log n）时间复杂性。您需要一些O（1）访问时间复杂性，例如 矢量< Bucket> 以符合散列表的预期时间复杂度。

Hash tables are expected to have O(1) best-case access. Your proposal for implementation in the question uses a map<size_t,Bucket> for access to the buckets which would result in O(log n) time complexity. You need something with O(1) access time complexity, such as a vector<Bucket> to comply with the expected time complexity of a hash table.

散列表可以在优秀和差的时间复杂性之间变化，取决于它们是如何稀疏地填充。

Hash tables can vary between having excellent and poor time complexity, depending on how sparsely populated they are.

在最好的情况下，每个桶最多一个条目，并且通过密钥访问是O（1）。这是哈希表的通常引用的复杂性。

In the best case, each bucket has at most one entry, and access by key is O(1). This is the commonly quoted complexity for hash tables.

在最坏的情况下，每个键具有相同的哈希值，并且通过键访问有效地搜索列表， O（n）行为。

In the worst case, each key has the same hash value, and access by key is effectively searching a list which results in O(n) behaviour.

现实世界的使用通常介于这些极端之间，希望更接近O（1）。

Real-world use is usually somewhere between these extremes, hopefully closer towards O(1).

您对其他问题接受的答案有一些简化的代码，您可以通过这两个极端来满足自己这是这种情况。

The accepted answer to your other question has some simplified code you can use to work through these two extremes to satisfy yourself that this is the case.

这篇关于通常的哈希表实现相比树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！