Tablas hash

Tablas HASH

www.inacap.cl

Introducción
• Muchas aplicaciones requieren un conjunto dinámico que soporte las operaciones de un diccionario: Insert, Search, Delete. Por ejemplo el compilador cuando guarda los identificadores de un programa. Es posible hacer uso de una lista enlazada con un tiempo O(n) ; sin embargo, este tiempo se puede reducir notablemente a orden O(1) en la mayoría de loscasos usando una tabla hash. La idea surge de los arreglos que nos permiten acceso a sus elementos en orden O(1). Una opción sería usar un arreglo tan grande como el rango de posibles claves. La desventaja es el espacio de memoria requerido en tal estrategia. Otra opción es usar un arreglo menor, al cual podemos mapear las claves en uso. Esta función de mapeo es la función hash. La tabla asíorganizada es la tabla hash. Como es posible que dos claves conduzcan al mismo mapeo (lo cual se conoce como una colisión), es necesario buscar formas para resolver esta situación.

•

• •

•

•

• Una forma, conocida como hashing abierto (hay otros términos dependiendo del texto), crear una lista asociada a cada entrada del arreglo.

www.inacap.cl

Visión gráfica (hashing abierto)Desde un “gran” Universo sólo un número reducido de claves serán consideradas.

www.inacap.cl

Visión gráfica (hashing cerrado)
Desde un “gran” Universo sólo un número reducido de claves serán consideradas.

www.inacap.cl

Hashing Abierto
•Suposición de hashing uniforme: es cuando cualquier elemento es igualmente probable de caer en cualquiera de las m entradas de la tabla hash,independientemente de cualquier otro elemento. •Aún con hashing uniforme, el peor caso de hashing abierto nos conduce a una lista con todas las claves en una única lista. El peor caso para búsqueda es así Θ(n). •En hashing abierto la búsqueda no exitosa de una clave toma tiempo Θ(1+α), donde α es el factor de carga =número de claves en la tabla/número de entradas en la tabla hash. ¿Por qué esto? El costode calcular la función hash Θ(1), más la prueba en cada una de los nodos de la lista asociada a la entrada. En promedio hay n/m nodos en cada lista y hay que probarlos todos ==> Θ(α). Luego se tiene que el tiempo total es Θ(1+α). •Análogamente la búsqueda exitosa de una clave toma un tiempo Θ(1+α/2) ! •La inserción de una clave toma Θ(1) •La eliminación de una clave toma un tiempo Θ(1+α). Aquísuponemos que la clave debe ser buscada dentro de la lista, para luego ser eliminada. •En resumen, si la tabla mantiene un número limitado de claves, n/m está acotado por una constante, todas las operaciones toman un tiempo Θ(1).

www.inacap.cl

Funciones Hash
• • • • • Una buena función hash debería satisfacer la suposición de hash uniforme. Como el recorrido de la función de hash es un númeronatural, hay que saber interpretar o transformar a número natural el tipo de clave. Si se trata de claves enteras, el problema está más o menos resuelto. Si se trata de secuencia de caracteres, strings, se puede interpretar cada carácter como un número en base 128 (los números ASCII van del 0 al 127) y el string completo como un número en base 128. Así por ejemplo la clave “pt” puede sertransformada a (112*128+116)=14452. OBS: ASCII(p)=112 y ASCII(t)=116. En adelante supondremos que las claves son números naturales (o ya han sido transformadas a números naturales) www.inacap.cl

•

Funciones Hash: Método de División
• Método de división: • Este método consiste en tomar el resto de la división por m, el número de entradas de la tabla. Así h(k) = k mod m En C sería h(k) = k % m; •Usar m = una potencia de 2, no es buena idea, ya que el valor de hash queda dependiendo de sólo los bits menos significativos de k. • Una forma de hacer hash(k) dependiente de todos los bits menos significativos es usar número primos no muy cercanos a una potencia de dos.

www.inacap.cl

Funciones Hash: Método de Multiplicación
• Este método opera en dos pasos. Primero, multiplicamos la clave...