If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in the hash table and use a hash function which assumes simple uniform hashing assumption. Then before every insert you just check all elements in the chain. This makes less collisions and makes the average length of a chain $\alpha = \frac{n}{m} = \frac{n}{1000}$.

I am trying to get the expected running time of this, but from what I understand, you are doing an insert operation up to $n$ times. The average running time of a search for a linked list is $\Theta(1+\alpha)$. Doesn't this make the expected running time $O(n+n\alpha) = O(n+\frac{n^2}{1000}) = O(n^2)$? This seems too much for an expected running time. Am I making a mistake here?

  • $\begingroup$ Please don't crosspost! You should give every community time to provide a suitable answer, if only to focus your question more before reposting. $\endgroup$ – Raphael Mar 13 '13 at 8:24

If you think of $1000$ as a constant, then yes, the running time is terrible. The idea of hash tables is that if the hash table is moderately bigger than the amount of data stored in it, then operations are very fast. Suppose for example that the hash table has size $m = 2n$. Then each operation takes constant time in expectation.

In implementations of hash tables, the hash table expands as more entries are inserted, to ensure that the ratio $\alpha$ is reasonable. Amortized analysis shows that this does not cause a performance hit in terms of the total running time, though individual operations might be slower (this is only a problem if you're writing a real-time application).

  • $\begingroup$ Is there a way to get the expected running time better than O(nlogn) without making m >= n (even if the worst case running time is worse than O(nlogn))? $\endgroup$ – omega Mar 12 '13 at 23:50
  • $\begingroup$ Expected running time is $O(n)$, worst case is $O(n^2)$. $\endgroup$ – vonbrand Mar 13 '13 at 0:02
  • $\begingroup$ How did you derive the O(n)? $\endgroup$ – omega Mar 13 '13 at 0:20
  • $\begingroup$ If $m < n$ then the hash table is full. Depending on the exact implementation used, either the hash table refuses insertions, or each cell will contain a list of size roughly $n/m$. Therefore each operation takes expected time at least $n/m$, which is pretty bad if $m$ is constant. Hash tables are not normally used this way. $\endgroup$ – Yuval Filmus Mar 13 '13 at 1:40
  • $\begingroup$ Expansion could also be a problem when the entries are chosen by a malicious, who could craft insertions and deletions to make the hash table seesaw around a size threshold, leading to a denial of service ($\Theta(n^2)$ performance for $n$ operations, overloading the machine's processing capacity). Some implementations today take precautions so that attackers cannot force all entries to land in the same bucket, are you aware of similar work around size thresholds? $\endgroup$ – Gilles Mar 13 '13 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.