散列的复杂性 [英] Complexity of Hashing
问题描述
我们如何找出哈希表上的搜索操作的平均和最坏情况时间复杂度，并已按以下方式实施：
让我们说' N'是需要散列的密钥数量。我们取一个大小为M的散列表（M = alpha * N，alpha〜0.1）。通过以链式链表的方式存储密钥来解决冲突，将每个新条目存储在由'hashTable [i]'指向的每个链表的头部。
恕我直言，最好的，平均和最坏的情况下的复杂性可能是O（1），O（N / M）和O（N）。纠正我，如果我错了。详细解释将不胜感激。
答案取决于哈希函数的特性，以及alpha的特定值。最坏的情况发生在散列实现不良分布的情况下（对于任何字母），正如你在原始文章中所述，是O（N）。最好的情况发生在散列分布良好并且alpha相对较大（> 1.0）的情况下，正如你所说的，这就是O（1）。所以我们就最好的情况和最坏的情况达成一致。然而，我认为平均情况需要更多的分析，因为阿尔法对性能有非线性影响。考虑两个极端的例子。情况1，alpha = 100,1000,10000。随着α变为无穷大，你将没有可避免的冲突（即由于必须截断散列以映射到M个桶中而不是散列的非一致行为），所以不会有可避免的冲突所以平均情况收敛到最好的情况，或O（1）。情况2，α= 0.01,0.001,0.0001。当alpha的比例为零时，你的hash bucket越来越少，直到整个table只是一个哈希桶，所有值都在该桶的单个列表中，所以平均情况收敛于线性搜索最坏情况，或者O（ N）。
平均情况在O（1）和O（N）之间，取决于alpha。我们可以把它表示为O（N ^ x），其中x是一个将alpha = 0映射到x = 1，alpha =无穷大映射到x = 0的函数。所以为了辩论的缘故（参见 http://en.wikipedia.org/wiki/Heaviside_function ），也许像O（N ^（e ^（ -alpha）））。
How do we find out the average and the worst case time complexity of a Search operation on Hash Table which has been Implemented in the following way:
Let's say 'N' is the number of keys that are required to be hashed. We take a hash table of size M (M=alpha*N, alpha ~ 0.1). Collisions are resolved by storing the keys in a chained linked list fashion, storing each new entry at the head of each linked list pointed to by 'hashTable[i]'.
IMHO, the best , avg and worst case complexities could be O(1), O(N/M) and O(N). Correct me if I am wrong. A detailed explanation would be appreciated.
The answer depends on the characteristics of the hashing function, and the particular value of alpha. The worst case occurs if the hash achieves poor distribution (for any alpha), and as you stated in your original post, is O(N). The best case occurs when you have a well-distributed hash and alpha is relatively large (>1.0), and as you said, that is O(1). So we agree on the best case and worst case.
However I think the average case needs more analysis, because alpha has a non-linear effect on performance. Consider two extreme examples. Case 1, alpha = 100, 1000, 10000. As alpha scales to infinity, you will have no avoidable collisions (i.e. those caused by having to truncate hashes to map into M buckets, as opposed to non-uniform behavior of the hash), and so the average case converges to the best case, or O(1). Case 2, alpha = 0.01, 0.001, 0.0001. As alpha scales to zero, you have fewer and fewer hash buckets until the entire table is just one hash bucket with all values in a single list in that bucket, and so the average case converges to the linear-search worst case, or O(N).
The average case is between O(1) and O(N), depending on alpha. We could express this as O(N^x), where x is a function that maps alpha = 0 to x = 1, and alpha = infinity to x = 0. So for the sake of debate, (see http://en.wikipedia.org/wiki/Heaviside_function), maybe something like O(N^(e^(-alpha))).
这篇关于散列的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
