1
Problema
• Telemóviles, una gran companía de telefonía, requiere mejorar la
capacidad de identificación del usuario que llama:
–
–
–
–
dado un número de usuario, devolver el nombre del que llama
los números de teléfonos están en el rango de 0 a R = 1010-1
n es el número de los números de teléfonos usados
se desea realizar esto de la manera más eficiente
• Conocemos dos formas para diseñar este diccionario:
-un árbol de búsqueda balanceado (AVL, red-black) con el número de
teléfono como llave tiene un tiempo de consulta O(log n) y un espacio O(n).
Buen uso del espacio y tiempo de búsqueda, pero se puede reducir el tiempo
de búsqueda a constante?
-un array indexado por los números de teléfonos tiene un tiempo de
consulta óptimo de O(1), pero requiere una gran cantidad de espacio: O(n +
R)
Pedro
2
Otra Solución
• Una Tabla Hash es una solución alternativa con un tiempo de consulta esperado de
O(1) y espacio O(n + N), donde N es el tamaño de la tabla.
• Como un array, pero con una función que proyecta el rango amplio de llaves en uno
más pequeño
-e.g., tomar la llave original, mod el tamaño de la tabla, y usarlo como indice
• Insertar telefono (401-863-7639, Pedro) en la tabla de tamaño 5
-4018637639 mod 5 = 4, pro tanto (401-863-7639, Pedro) se almacena en el cajetin 4
de la tabla
Pedro
• Después de varias inserciones pueden existir colisiones!
3
Resolución de Colisiones
• Usar encadenamiento
-Configurar listas de elementos con el mismo índice
• Complejidad O(n/N)
4
De Llaves a Indices
• La proyección de llaves a índices de una tabla hash se llama funcion hash
• Una función hash usualmente es la composición de dos proyección, una hash code
map y otra compression map.
– Un requerimiento esencial de una función hash es proyectar llaves iguales al
mismo índice
– Una función hash “buena” minimiza la probabilidad de colisiones
• Java tiene un mértodo hashCode() para la clase Object, que normalmente retorna la
dirección de 32-bit de memoria del objeto.
• Este código hash trabaja mal para objetos Integer y String
5
Proyección de códigos Hash
• Integer cast: para tipos numéricos de 32 bits or less,
• suma de Componentes: para tipos numéricos
• acumulación Polynomica: en cadenas, combinar los valores (ASCII or
Unicode) a0a1 ... an-1 como coeficientes de un polinomio:
a0 + a1x + ...+ xn-1an-1
-Se usa la regla de Horner para evaluar para un valor fijo de x:
a0 + x (a1 +x (a2+ ... x (an-2+ x an-1) ... ))
-Si x = 33, 37, 39, o 41produce como mucho 6 colisiones para un vocabulario
de 50,000 palabras
6
Proyección de Compression
comunes
• Division: h(k) = |k| mod N
– N = 2k es mala
– el tamaño de la tabla N se escoge como número primo
• Multiplicar, Sumar, y Dividir (MSD): h(k) = |ak + b| mod N
7
Tratamiento de Colisiones
• Encadenamiento
• Direccionamiento abierto
-Doble Hashing
-Prueba lineal
8
Descargar

Hashing