Let $h:U \to[m]=\{0,1,\dots,m\}$ be hash function, which can calculate $h(u), \forall u\in U$ in $O(1).$

Let $D \subseteq U$ be a subset of size $n.$

I'm looking for a deterministic algorithm, efficient as possible, to find the number of collisions of $h$ on $D$

I thought to start operating $h$ on all elements in $D,$ place the results in an array and work with that, but not sure how to continue.

Any help is appreciated.

  • $\begingroup$ Do you have any particular hash functions and target datasets in mind? $\endgroup$
    – Sagnik
    Feb 16, 2018 at 7:01

1 Answer 1


You could hash all of the elements of $D$, sort them, and then count duplicates. Sorting brings all duplicates next to each other, so a linear scan lets you count the number of duplicates. The running time will be $O(|D| \log |D|)$.

If you don't insist on a deterministic algorithm, you could place elements of $D$ into a hashtable, using $h$ as your hash, and then count the size of each hash bucket. If the hash function is any good, then there is a sense in which the expected running time is $O(|D|)$ (e.g., if the elements of $D$ are random and the hash function is sufficiently good) -- but the worst case is $O(|D|^2)$.

  • $\begingroup$ I could also sort with counting sort and get W.C. $O(n+m),$ right? $\endgroup$
    – Itay4
    Feb 16, 2018 at 7:05
  • $\begingroup$ @Itay4, yup! That might be slower or faster, depending on whether $m$ is much larger than $|D|$ or not. $\endgroup$
    – D.W.
    Feb 16, 2018 at 16:15

Your Answer

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

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