perlmeditation
pg
<p>I read a post today saying that hash search performance is O(1), which is wrong. </p>
<p>I am posting this short meditation to correct the expectation. (I don't know how many times this false analysis have appeared in the past)</p>
<p>O(1) means that the worst case performance is not a function of the number of elements in the hash (n). Or the performance is a constant regardless how many elements you store in the hash.</p>
<p>That's not true.</p>
<p>The worst case hash search performance is O(n). This happens when all the hash elements happen to resolve the same hash key. In this case, a hash is no difference than a list.</p>
<p>If the number of valid hash keys is m, and you have n elements in a hash, the average search performance is o(n/2m), as the average queue length under a valid hash key in this case is n/m. I assume the search algorithm for the queue is simply go from the beginning to the end, so in average you have to go thru half length of the queue.</p>