2
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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, 2013 at 8:24

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
7
  • $\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, 2013 at 23:50
  • $\begingroup$ Expected running time is $O(n)$, worst case is $O(n^2)$. $\endgroup$
    – vonbrand
    Mar 13, 2013 at 0:02
  • $\begingroup$ How did you derive the O(n)? $\endgroup$
    – omega
    Mar 13, 2013 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, 2013 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 'SO- stop being evil'
    Mar 13, 2013 at 20:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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