Conjuntos y diccionarios

Ambos se construyen sobre la tabla hash: un conjunto es una tabla cuyas claves son los elementos (el valor no importa), así que no admite repetidos y la pertenencia es una búsqueda; un diccionario es la tabla guardando, además, un valor por clave.

Velocidad
Dos conjuntos y un diccionario, todos construidos sobre una tabla hash. Escribe los elementos y opera.
Resultado—
Se usa con «Añadir», «¿Pertenece?» y «Quitar» de cada conjunto.

Conjunto A

|A| = 3
0
·
1
·
2
uva
3
·
4
·
5
manzana
6
pera
7
·
8
·
9
·
10
·
A = {uvamanzanapera}

Conjunto B

|B| = 4
0
melon
1
·
2
uva
3
·
4
·
5
·
6
pera
7
kiwi
8
·
9
·
10
·
B = {melonuvaperakiwi}

Operaciones

A ∪ B = {kiwi, manzana, melon, pera, uva}
A ∩ B = {pera, uva}
A − B = {manzana}
A △ B = {kiwi, manzana, melon}

A ⊆ B: no · A ⊇ B: no · A ∩ B = ∅: no · A = B: no

Métricas de A y B

|A|
3
factor de carga A
0.273
colisiones A
0
|B|
4
factor de carga B
0.364
colisiones B
0

Leyenda

  • Casilla libre
  • Elemento guardado
  • Casilla en curso
  • Lápida ⋈

Por qué un conjunto es una tabla hash

La tabla guarda cada elemento como clave, así que no puede haber repetidos: insertar dos veces «pera» no aumenta el cardinal. La pertenencia (¿está «pera»?) es una búsqueda, la operación que la tabla hace bien. Las operaciones entre conjuntos se apoyan en eso: A ∪ B inserta los de B en A; A ∩ B y A − B recorren A y preguntan si el elemento está en B.