Let's say we have sets

  • A = {1,2,3} and
  • B = {1,3,10}

and our hash function is

  • h(x) = 2x + 1(mod9)

therefore H(A) = {3,5,7} H(B) = {3,7}

Therefore if there is no intersection between the elements of H(A) and H(B) then can we say that the it is guaranteed that intersection of A and B is empty? If so, how can we show it?

  • $\begingroup$ Consider the preimage of $h$. BTW, $h$ in this example is not really a hash function, since it is a bijective function. Hashes are usually not invertible. $\endgroup$ – Memming Sep 9 '13 at 14:02
  • $\begingroup$ @hardmath thank you. I edited the question. $\endgroup$ – yns Sep 9 '13 at 14:05

Indeed $H(A) \cap H(B)=\emptyset$ guarantees that $A$ and $B$ are disjoint, i.e., that $A \cap B=\emptyset$.

Proof: If $a \in A \cap B$, then $h(a) \in H(A) \cap H(B)$, so $H(A) \cap H(B) \neq \emptyset$.

  • $\begingroup$ thanks for the answer @Rebecca. Does it true for all hash functions? What happens if the hash function is h(x) = (x-2)(x-1)? In that case both 1 and 2 maps to 0. Does it make any difference? $\endgroup$ – yns Sep 9 '13 at 14:20
  • $\begingroup$ The property "$H(A) \cap H(B) = \emptyset$ implies $A \cap B = \emptyset$" is true regardless of the choice of hash function (the proof remains the same). The trick is to choose a hash function that is (a) fast to compute and (b) will often result in situations where $H(A) \cap H(B)$. $\endgroup$ – Rebecca J. Stones Sep 9 '13 at 14:21

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.