FIGURA 1
Funciones de Asociatividad [Hash Functions]
Suponga que tenemos celdas en la memoria de la computadora con índices del
0 al 10 (ver Figura 1). Deseamos almacenar y recuperar
arbitrariamente
enteros no negativos en estas celdas. Un acercamiento es usar una función
de asociatividad. Una función de asociatividad toma un dato elemento
para ser almacenado o recuperado y computa la primera opción para una
localidad del elemento. Por ejemplo, para nuestro problema, almacenar o
recuperar el número n, debemos tomar la primera opción para una
localidad, residuo de dividir n entre 11 (casi siempre se opta
por un número primo como divisor). Nuestra función de asociatividad viene
a ser
a(n) = residuo de dividir n entre 11.
La Figura 1 muestra el resultado de almacenar 15, 558,
32, 132, 102 y 5, en orden, en celdas inicialmente vacías.
Ahora suponga que deseamos almacenar 257.
Siendo a(257) = 4, 257 debe ser almacenado en la
localidad 4; sin embargo, esta posición ya está ocupada. En este caso
decimos que una colisión ha ocurrido. Más precisamente, una colisión
ocurre para una función de asociatividad A si A(x)
= A(y), pero x ¹
(y). Para manejar colisiones, una política para resolución
de colisión es requerida. Una política simple para resolución de
colisión es encontrar la más alta (con 0 asumido como continuación de 10)
celda desocupada. Si usamos esta política para resolución de colisión,
debemos almacenar 257 en la localidad 6 (ver Figura 1).
Si deseamos localizar y a almacenar un valor
n computamos m = a(n) y empezamos
viendo una localidad m. Si n no está en esta posición, debemos
proceder a la siguiente posición más alta, y así en adelante. Si alcanzamos
una celda vacía o regresamos a nuestra posición original, concluimos que
n no está presente; de otra manera, obtenemos la posición de
n.
