# Deterministic algorithm to find number of collisions

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.

• Do you have any particular hash functions and target datasets in mind? Feb 16 '18 at 7:01

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)$.
• I could also sort with counting sort and get W.C. $O(n+m),$ right? Feb 16 '18 at 7:05
• @Itay4, yup! That might be slower or faster, depending on whether $m$ is much larger than $|D|$ or not.