Clase 08 Hashing I

IBD
Clase 8

Hashing (Dispersión)


Necesitamos un mecanismo de acceso a
registros con una lectura solamente



Hasta el momento
 Secuencia:

N/2 accesos promedio
 Ordenado: Log2 N
 Árboles:



2

Problema

3 o 4 accesos

Solución
IBD - CLASE 8

UNLP - Facultad d

Hashing (Dispersión)


Dispersión o Hashing
 Técnica

para generar una dirección base única para
una clave dada. Ladispersión se usa cuando se
requiere acceso rápido a una clave.

 Técnica

que convierte la clave del registro en un
número aleatorio, el que sirve después para
determinar donde se almacena el registro.

 Técnica

de almacenamiento y recuperación que usa
una función de hash para mapear registros en
dirección de almacenamiento.

3

IBD - CLASE 8

UNLP - Facultad d

Hashing (Dispersión)
Llave#intermedio

Dirección

Conversión
del # a una
dirección

Conversión de
l ave a número

 Atributos

del hash

• No requiere almacenamiento adicional (índice)
• Facilita inserción y eliminación rápida de registros
• Encuentra registros con muy pocos accesos al
disco en promedio (generalmente menos de 2)

4

IBD - CLASE 8

UNLP - Facultad d

Hashing (Dispersión)
 Costo

• No se puede usar registros delongitud variable
• No hay orden físico de datos
• No se permite llaves duplicadas
 Para

•
•
•
•

5

determinar la dirección

La clave se convierte en un número casi aleatorio
# se convierte en una dirección de memoria
El registro se guarda en esa dirección
Si la dirección está ocupada
overflow
(tratamiento especial)
IBD - CLASE 8

UNLP - Facultad d

Hashing (Dispersión)


Parámetros que afectan laeficiencia
 Tamaño

de las cubetas (espacio de
almacenamiento)

 Densidad
 Función
 Método

6

de empaquetamiento

de hash
de tratamiento de desbordes
IBD - CLASE 8

UNLP - Facultad d

Hashing (Dispersión)
 Función

de hash

• Caja negra que a partir de una clave se
obtiene la dirección donde debe estar el
registro.
• Diferencias con índices
• Dispersión: no hay relación aparente entrellave y dirección
• Dos claves distintas pueden transformarse en
iguales direcciones (colisiones)->son claves
sinónimos

7

IBD - CLASE 8

UNLP - Facultad d

Hashing (Dispersión)
 Colisión:

• Situación en la que un registro es asignado a una
dirección ya ocupada (no tiene suficiente espacio
para ser almacenado)
• A las claves que por dispersión se convierten en
la misma dirección  sinónimos
•Ejemplo.
• Soluciones
• Algoritmos de dispersión sin colisiones (perfectos)
(imposible de conseguir)
• Almacenar los registros de alguna otra forma,
esparcir

8

IBD - CLASE 8

UNLP - Facultad d

Hashing (Dispersión)
 Soluciones

para las colisiones

• Esparcir registros: buscar métodos que distribuyan los
registros de la forma más aleatoria posible entre las
direcciones disponibles.
• Utilizar 2letras no es bueno.

• Usar memoria adicional: distribuir pocos registros en
muchas direcciones (ej: 75 registros en 1000
direcciones):
• Disminuye el overflow (colisiones)
• Desperdicia espacio

9

IBD - CLASE 8

UNLP - Facultad d

Hashing (Dispersión)
 Soluciones

para las colisiones

• Colocar más de un registro por dirección:
• direcciones con N claves
• mejoras notables
• Ej: archivo conregistro físicos de 512 bytes
y el registro a almacenar es de 80 bytes 
se puede almacenar hasta 6 registros por
cada dirección de archivo.
• Cada dirección tolera hasta 5 sinónimos
• Las direcciones que pueden almacenar
varios registros en esta forma 
compartimentos
10

IBD - CLASE 8

UNLP - Facultad d

Hashing (Dispersión)
 Algoritmos

simples de dispersión

• Condiciones
• Repartir registros enforma uniforme en el espacio de
direcciones disponible
• Aleatoria (las claves son independientes, no influyen
una sobre la otra)

• Tres pasos (ver ejemplo)
• Representar la llave en forma numérica (en caso que
no lo sea)
• Aplicar la función
• Relacionar el número resultante con el espacio
disponible

11

IBD - CLASE 8

UNLP - Facultad d

Hashing (Dispersión)
función Dispersión (llave,...