1
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ I could also sort with counting sort and get W.C. $O(n+m),$ right? $\endgroup$ – Itay4 Feb 16 '18 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 '18 at 16:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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