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

Question

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?

Answer 1

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