How can one gurantees the intersection of two set is empty with respect to its hash value?

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?

• 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. – Memming Sep 9 '13 at 14:02
• @hardmath thank you. I edited the question. – 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$.
• 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)$. – Rebecca J. Stones Sep 9 '13 at 14:21