由网友(薄情女王)分享简介：我不明白这其中的解释说，如果n为元素的哈希表中的数字，m是桶的总数则哈希表在不断的平均访问时间仅当n是成正比的THETA（N）。为什么一定成正比？ I don't understand this explanation which says if n is the number of elements in the...

我不明白这其中的解释说，如果n为元素的哈希表中的数字，m是桶的总数则哈希表在不断的平均访问时间仅当n是成正比的THETA（N）。为什么一定成正比？

I don't understand this explanation which says if n is the number of elements in the hash table and m is the total number of buckets then hashtables have constant access time in average only if n is proportional to theta(n). Why does it have to be proportional ?

推荐答案

以及实际m应该为与n成比例。否则，你可以，例如，刚刚1桶，这将是就像一个无序集。

well actually m should be proportional to n. Otherwise you could, for example, have just 1 bucket and it would be just like an unsorted set.

要更precise，如果m与n成比例，也就是M = * n，则在每个桶中的项目数将为n /米= 1 / C是一个常数。去任何桶是一个O（1）操作（只计算哈希值code），然后通过水桶搜索是恒定的顺序（你可能只是做通过在桶中的项目这将是一个恒定的线性搜索）。

To be more precise, if m is proportional to n, i.e. m = c * n, then the number of items in each bucket will be n/m = 1/c which is a constant. Going to any bucket is an O(1) operation (just compute the hash code) and then the search through the bucket is constant order (you could just do a linear search through the items in the bucket which would be a constant).

这样的算法的顺序是O（1），如果m = C * N。

Thus the order of the algorithm is O(1), if m = c * n.

要采取一个相反的例子，假设我们有大小tableSize一个固定大小的表格。然后在每个桶项的预期​​数量为n / tableSize其中是n的线性函数。通过斗任何一种搜索充其量为O（log（n））的一个树（我假设你不坚持斗内的另一个哈希表，或者我们再有超过该哈希表相同的参数），所以它不会是O（1）在这种情况下

To take a converse example, suppose we had a fixed size table of size tableSize. Then the expected number of items in each bucket is n/tableSize which is a linear function of n. Any kind of search through the bucket is at best O(log(n)) for a tree (I'm assuming you don't stick another hash table inside the bucket or we then have the same argument over that hash table), so it would not be O(1) in this case.