哈希表始终是O(n)进行查找的时间吗? [英] Hash table is always O(n) time for lookup?

问题描述

如果存储桶数量恒定，我不了解哈希表如何进行恒定时间查找.假设我们有100个存储桶和1,000,000个元素.显然，这是O(n)查找，这就是复杂性的要点，以了解n的很大值时事物的行为.因此，哈希表永远不会进行常量查找，而始终是O(n)查找.

I don't understand how hash tables are constant time lookup, if there's a constant number of buckets. Say we have 100 buckets, and 1,000,000 elements. This is clearly O(n) lookup, and that's the point of complexity, to understand how things behave for very large values of n. Thus, a hashtable is never constant lookup, it's always O(n) lookup.

为什么人们会说平均是O(1)查找，而在最坏的情况下只有O(n)查找?

Why do people say it's O(1) lookup on average, and only O(n) for worst case?

推荐答案

使用哈希的目的是能够像数组一样直接索引表.在理想情况下，每个存储桶中只有一项，我们可以轻松实现O(1).

The purpose of using a hash is to be able to index into the table directly, just like an array. In the ideal case there's only one item per bucket, and we achieve O(1) easily.

实际的哈希表将具有比其具有的元素更多的存储桶，因此每个存储桶中只有一个元素的几率很高.如果插入表中的元素数量过多，则将调整表的大小以增加存储桶的数量.

A practical hash table will have more buckets than it has elements, so that the odds of having only one element per bucket are high. If the number of elements inserted into the table gets too great, the table will be resized to increase the number of buckets.

总是有可能每个元素都具有相同的哈希值，或者所有活动哈希值都将分配给相同的存储桶；在这种情况下，查找时间确实为O(n).但是，将设计一个好的哈希表实现来最大程度地减少这种情况的发生.

There is always a possibility that every element will have the same hash, or that all active hashes will be assigned to the same bucket; in that case the lookup time is indeed O(n). But a good hash table implementation will be designed to minimize the chance of that occurring.

这篇关于哈希表始终是O(n)进行查找的时间吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！