Hash Tabla

Tablas HASH
Agustín J. González ELO320: Estructura de Datos y Algoritmos 1er. Sem. 2002

1

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, estetiempo se puede reducir notablemente a orden O(1) en la mayoría de los casos 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 enuso. 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. Otra forma, conocidacomo hashing cerrado (el término depende del libro), 2 almacena las claves en las mismas entradas del arreglo o tabla hash.

•

• • •

• • •

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

Universo de Claves

Claves usadas

Función de mapeo o Función de hash

Lista Enlazada

3

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

Universo de Claves

Claves usadas

La “lista” se almacena en la misma tabla Función de mapeo Función de hash
4

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 decualquier 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 costo de calcular la funciónhash Θ(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 0 ==> Θ(α). 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 debeser buscada dentro de la lista, para luego ser eliminada. En resumen, si la tabla mantiene un limitado número de claves, n/m está acotado por una constante, todas las operaciones toman un tiempo Θ(1).

•

•

• • • •

5

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úmero natural, hay que saberinterpretar o transformar a número natural 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 ser transformada 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)

6

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...