2022-04-25

<aside> 💡 Tablas de hash como generalización del concepto de arreglo

• Podemos indexar a partir de claves que no son sólo necesariamente enteros positivos
• Acceso en $O(1)$ </aside>

Motivación

Queremos una forma de representar un diccionario que nos permita

• Indexar con otros tipos de datos
• $n = \#$claves efectivamente usadas
• Tiempo de acceso $O(1)$

Pre-hashing

Función de correspondencia entre cualquier tipo de datos y un entero. Nos va a ayudar a indexar otros tipos de datos.

Tabla de hash

Representaremos un diccionario con una tupla $<T, h>$ donde:

• $T$ es una arreglo de tamaño $n$
• $h$ es una función de hash $h: K \to \{0,...,n - 1\}$ donde
  • $K$ es el conjunto de claves posibles
  • $\{0,...,n - 1\}$ son las posiciones de la tabla (pseudoclaves)
  • La posición del elemento en el arreglo se calcula a través de la función $h$.