Hashing

Se usa para hacer diccionarios

• Si está bien implementado, todas las operaciones son O(1)

Primitivas

• Escribir
• Pertenece
• Obtener

Funciones de hash

h(x) → Número (acotado entre [0, 2 a la 32] aprox)

x son bytes (cualquier cosa que puedo representar con bytes), puede ser:

• Número
• String
• ABB

Calcular el hashing es O(1) también

La tabla de hash es un vector, por ej “hola” → h(hola) → 700

Ejemplo de función de hash h: num → num

h(n) = (3n + 4) % 5 → [0, 5]

h(1) → 2

h(5) → 4