¿Cómo se puede garantizar que la intersección de dos conjuntos está vacía con respecto a su valor hash?

Question

Digamos que tenemos conjuntos

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

y nuestra función hash es

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

por lo tanto H(A) = {3,5,7} H(B) = {3,7}

Por lo tanto, si no hay intersección entre los elementos de H(A) y H(B), ¿podemos decir que está garantizado que la intersección de A y B está vacía? Si es así, ¿cómo podemos demostrarlo?

Answer 1

En efecto, $H(A) \cap H(B)=\emptyset$ garantiza que $A$ y $B$ son disjuntos, es decir, que $A \cap B=\emptyset$ .

Prueba : Si $a \in A \cap B$ entonces $h(a) \in H(A) \cap H(B)$ Así que $H(A) \cap H(B) \neq \emptyset$ .