• Author / Uploaded
• jorge barbas barker

Citation preview

Tabla hash Ir a la navegaci�n Ir a la b�squeda Commons-emblem-question book orange.svg Este art�culo o secci�n necesita referencias que aparezcan en una publicaci�n acreditada. Este aviso fue puesto el 29 de noviembre de 2017. Una tabla hash, matriz asociativa, hashing, mapa hash, tabla de dispersi�n o tabla fragmentada es una estructura de datos que asocia llaves o claves con valores. La operaci�n principal que soporta de manera eficiente es la b�squeda: permite el acceso a los elementos (tel�fono y direcci�n, por ejemplo) almacenados a partir de una clave generada (usando el nombre o n�mero de cuenta, por ejemplo). Funciona transformando la clave con una funci�n hash en un hash, un n�mero que identifica la posici�n (casilla o cubeta) donde la tabla hash localiza el valor deseado. Las tablas hash se suelen implementar sobre vectores de una dimensi�n, aunque se pueden hacer implementaciones multi-dimensionales basadas en varias claves. Como en el caso de los arrays, las tablas hash proveen tiempo constante de b�squeda promedio O(1),1? sin importar el n�mero de elementos en la tabla. Sin embargo, en casos particularmente malos el tiempo de b�squeda puede llegar a O(n), es decir, en funci�n del n�mero de elementos. Comparada con otras estructuras de arrays asociadas, las tablas hash son m�s �tiles cuando se almacenan grandes cantidades de informaci�n. Las tablas hash almacenan la informaci�n en posiciones pseudo-aleatorias, as� que el acceso ordenado a su contenido es bastante lento. Otras estructuras como �rboles binarios auto-balanceables tienen un tiempo promedio de b�squeda mayor (tiempo de b�squeda O(log n)), pero la informaci�n est� ordenada en todo momento. �ndice 1 Ejemplo 2 Funcionamiento 2.1 Inserci�n 2.2 B�squeda 3 Pr�cticas recomendadas para las funciones hash 4 Resoluci�n de colisiones 4.1 Direccionamiento Cerrado, Encadenamiento separado o Hashing abierto 4.2 Direccionamiento abierto o Hashing cerrado 5 Ventajas e inconvenientes de las tablas hash 6 Implementaci�n en pseudoc�digo 7 Implementaci�n en Java 7.1 Restas Sucesivas 7.2 Aritm�tica Modular 7.3 Mitad del Cuadrado 7.4 Truncamiento 7.5 Plegamiento 7.6 Tratamiento de Colisiones 7.7 Prueba Lineal 8 Hash Din�mico 8.1 M�todos Totales 8.1.1 M�todo de las expansiones totales 8.1.2 M�todo de las reducciones totales 8.2 M�todos Parciales 8.2.1 M�todo de las expansiones parciales 8.2.2 M�todo de las reducciones parciales 9 Tablas hash distribuidas 10 Referencias

11 Enlaces externos 11.1 Art�culos e implementaciones Ejemplo Un ejemplo pr�ctico para ilustrar que es una tabla hash es el siguiente: Se necesita organizar los peri�dicos que llegan diariamente de tal forma que se puedan ubicar de forma r�pida, entonces se hace lo siguiente: se hace una gran caja para guardar todos los peri�dicos (una tabla), y se divide en 31 contenedores (ahora es una hash table o tabla fragmentada), y la clave para guardar los peri�dicos es el d�a de publicaci�n (�ndice). Cuando se requiere buscar un peri�dico se busca por el d�a que fue publicado y as� se sabe en que z�calo (bucket) est�. Varios peri�dicos quedar�n guardados en el mismo z�calo (es decir, colisionan al ser almacenados), lo que implica buscar en la sub-lista que se guarda en cada z�calo. De esta forma se reduce el tama�o de las b�squedas de O(n) a O(log(n)). Ejemplo de tabla hash. Funcionamiento Las operaciones b�sicas implementadas en las tablas hash son: Inserci�n La forma de implementar en funci�n esta operaci�n es pidiendo la llave y el valor, para con estos poder hacer la inserci�n del dato. Para almacenar un elemento en la tabla hash se ha de convertir su clave a un n�mero. Esto se consigue aplicando la funci�n resumen (hash) a la clave del elemento. El resultado de la funci�n resumen ha de mapearse al espacio de direcciones del vector que se emplea como soporte, lo cual se consigue con la funci�n m�dulo. Tras este paso se obtiene un �ndice v�lido para la tabla. El elemento se almacena en la posici�n de la tabla obtenido en el paso anterior. Si en la posici�n de la tabla ya hab�a otro elemento, se ha producido una colisi�n. Este problema se puede solucionar asociando una lista a cada posici�n de la tabla, aplicando otra funci�n o buscando el siguiente elemento libre. Estas posibilidades han de considerarse a la hora de recuperar los datos. B�squeda La forma de implementar en funci�n esta operaci�n es pidiendo la llave y con esta devolver el valor. Para recuperar los datos, es necesario �nicamente conocer la clave del elemento, a la cual se le aplica la funci�n resumen. El valor obtenido se mapea al espacio de direcciones de la tabla. Si el elemento existente en la posici�n indicada en el paso anterior tiene la misma clave que la empleada en la b�squeda, entonces es el deseado. Si la clave es distinta, se ha de buscar el elemento seg�n la t�cnica empleada para resolver el problema de las colisiones al almacenar el elemento. La mayor�a de las implementaciones tambi�n incluyen la funci�n de borrar a la cual se le env�a una llave que deber� eliminar. Tambi�n se pueden ofrecer funciones como iteraci�n en la tabla, crecimiento y vaciado. Algunas tablas hash permiten almacenar m�ltiples valores bajo la misma clave. Para usar una tabla hash se necesita: Una estructura de acceso directo (normalmente un array).

Una estructura de datos con una clave Una funci�n resumen (hash) cuyo dominio sea el espacio de claves y su imagen (o rango) los n�meros naturales. Pr�cticas recomendadas para las funciones hash Una buena funci�n hash es esencial para el buen rendimiento de una tabla hash. Las colisiones son generalmente resueltas por alg�n tipo de b�squeda lineal, as� que si la funci�n tiende a generar valores similares, las b�squedas resultantes se vuelven lentas. En una funci�n hash ideal, el cambio de un simple bit en la llave (incluyendo el hacer la llave m�s larga o m�s corta) deber�a cambiar la mitad de los bits del hash, y este cambio deber�a ser independiente de los cambios provocados por otros bits de la llave. Como una funci�n hash puede ser dif�cil de dise�ar, o computacionalmente cara de ejecuci�n, se han invertido muchos esfuerzos en el desarrollo de estrategias para la resoluci�n de colisiones que mitiguen el mal rendimiento del hasheo. Sin embargo, ninguna de estas estrategias es tan efectiva como el desarrollo de una buena funci�n hash de principio. Es deseable utilizar la misma funci�n hash para arrays de cualquier tama�o concebible. Para esto, el �ndice de su ubicaci�n en el array de la tabla hash se calcula generalmente en dos pasos: 1. Un valor hash gen�rico es calculado, llenando un entero natural de m�quina. 2. Este valor es reducido a un �ndice v�lido en el vector encontrando su m�dulo con respecto al tama�o del array. El tama�o del vector de las tablas hash es con frecuencia un n�mero primo. Esto se hace con el objetivo de evitar la tendencia de que los hash de enteros grandes tengan divisores comunes con el tama�o de la tabla hash, lo que provocar�a colisiones tras el c�lculo del m�dulo. Sin embargo, el uso de una tabla de tama�o primo no es un sustituto a una buena funci�n hash. Un problema bastante com�n que ocurre con las funciones hash es el aglomeramiento. El aglomeramiento ocurre cuando la estructura de la funci�n hash provoca que llaves usadas com�nmente tiendan a caer muy cerca unas de otras o incluso consecutivamente en la tabla hash. Esto puede degradar el rendimiento de manera significativa, cuando la tabla se llena usando ciertas estrategias de resoluci�n de colisiones, como el sondeo lineal. Cuando se depura el manejo de las colisiones en una tabla hash, suele ser �til usar una funci�n hash que devuelva siempre un valor constante, como 1, que cause colisi�n en cada inserci�n. Funciones Hash m�s usadas: 1. Hash de Divisi�n: Dado un diccionario D, se fija un n�mero m >= |D| (m mayor o igual al tama�o del diccionario) y que sea primo no cercano a potencia de 2 o de 10. Siendo k la clave a buscar y h(k) la funci�n hash, se tiene h(k)=k%m (Resto de la divisi�n k/m). 2. Hash de Multiplicaci�n Si por alguna raz�n, se necesita una tabla hash con tantos elementos o punteros como una potencia de 2 o de 10, ser� mejor usar una funci�n hash de multiplicaci�n, independiente del tama�o de la tabla. Se escoge un tama�o de tabla m >= |D| (m mayor o igual al tama�o del diccionario) y un cierto n�mero irracional f

(normalmente se usa 1+5^(1/2)/2 o 1-5^(1/2)/2). De este modo se define h(k)= Suelo(m*Parte fraccionaria(k*f)) Resoluci�n de colisiones Si dos llaves generan un hash apuntando al mismo �ndice, los registros correspondientes no pueden ser almacenados en la misma posici�n. En estos casos, cuando una casilla ya est� ocupada, debemos encontrar otra ubicaci�n donde almacenar el nuevo registro, y hacerlo de tal manera que podamos encontrarlo cuando se requiera. Para dar una idea de la importancia de una buena estrategia de resoluci�n de colisiones, considerese el siguiente resultado, derivado de la paradoja de las fechas de nacimiento. Aun cuando supongamos que el resultado de nuestra funci�n hash genera �ndices aleatorios distribuidos uniformemente en todo el vector, e incluso para vectores de 1 mill�n de entradas, hay un 95% de posibilidades de que al menos una colisi�n ocurra antes de alcanzar los 2.500 registros. Hay varias t�cnicas de resoluci�n de colisiones, pero las m�s populares son encadenamiento y direccionamiento abierto. Direccionamiento Cerrado, Encadenamiento separado o Hashing abierto En la t�cnica m�s simple de encadenamiento, cada casilla en el array referencia una lista de los registros insertados que colisionan en la misma casilla. La inserci�n consiste en encontrar la casilla correcta y agregar al final de la lista correspondiente. El borrado consiste en buscar y quitar de la lista. Ejemplo de encadenamiento. La t�cnica de encadenamiento tiene ventajas sobre direccionamiento abierto. Primero el borrado es simple y segundo el crecimiento de la tabla puede ser pospuesto durante mucho m�s tiempo dado que el rendimiento disminuye mucho m�s lentamente incluso cuando todas las casillas ya est�n ocupadas. De hecho, muchas tablas hash encadenadas pueden no requerir crecimiento nunca, dado que la degradaci�n de rendimiento es lineal en la medida que se va llenando la tabla. Por ejemplo, una tabla hash encadenada con dos veces el n�mero de elementos recomendados, ser� dos veces m�s lenta en promedio que la misma tabla a su capacidad recomendada. Las tablas hash encadenadas heredan las desventajas de las listas ligadas. Cuando se almacenan cantidades de informaci�n peque�as, el gasto extra de las listas ligadas puede ser significativo. Tambi�n los viajes a trav�s de las listas tienen un rendimiento de cach� muy pobre. Otras estructuras de datos pueden ser utilizadas para el encadenamiento en lugar de las listas ligadas. Al usar �rboles auto-balanceables, por ejemplo, el tiempo te�rico del peor de los casos disminuye de O(n) a O(log n). Sin embargo, dado que se supone que cada lista debe ser peque�a, esta estrategia es normalmente ineficiente a menos que la tabla hash sea dise�ada para correr a m�xima capacidad o existan �ndices de colisi�n particularmente grandes. Tambi�n se pueden utilizar vectores din�micos para disminuir el espacio extra requerido y mejorar el rendimiento del cach� cuando los registros son peque�os. Direccionamiento abierto o Hashing cerrado Las tablas hash de direccionamiento abierto pueden almacenar los registros directamente en el array. Las colisiones se resuelven mediante un sondeo del array, en el que se buscan diferentes localidades del array (secuencia de sondeo) hasta que el registro es encontrado o se llega a una casilla vac�a, indicando que no existe esa llave en la tabla. Ejemplo de direccionamiento abierto. Las secuencias de sondeo m�s utilizadas son:

1. Sondeo lineal En el que el intervalo entre cada intento es constante (frecuentemente 1). El sondeo lineal ofrece el mejor rendimiento del cach�, pero es m�s sensible al aglomeramiento. 2. Sondeo cuadr�tico En el que el intervalo entre los intentos aumenta linealmente (por lo que los �ndices son descritos por una funci�n cuadr�tica). El sondeo cuadr�tico se sit�a entre el sondeo lineal y el doble hasheo. 3. Doble hasheo En el que el intervalo entre intentos es constante para cada registro pero es calculado por otra funci�n hash. El doble hasheo tiene pobre rendimiento en el cach� pero elimina el problema de aglomeramiento. Este puede requerir m�s c�lculos que las otras formas de sondeo. Una influencia cr�tica en el rendimiento de una tabla hash de direccionamiento abierto es el porcentaje de casillas usadas en el array. Conforme el array se acerca al 100% de su capacidad, el n�mero de saltos requeridos por el sondeo puede aumentar considerablemente. Una vez que se llena la tabla, los algoritmos de sondeo pueden incluso caer en un c�rculo sin fin. Incluso utilizando buenas funciones hash, el l�mite aceptable de capacidad es normalmente 80%. Con funciones hash pobremente dise�adas el rendimiento puede degradarse incluso con poca informaci�n, al provocar aglomeramiento significativo. No se sabe a ciencia cierta qu� provoca que las funciones hash generen aglomeramiento, y es muy f�cil escribir una funci�n hash que, sin querer, provoque un nivel muy elevado de aglomeramiento. Ventajas e inconvenientes de las tablas hash Una tabla hash tiene como principal ventaja que el acceso a los datos suele ser muy r�pido si se cumplen las siguientes condiciones: Una raz�n de ocupaci�n no muy elevada (a partir del 75% de ocupaci�n se producen demasiadas colisiones y la tabla se vuelve ineficiente). Una funci�n resumen que distribuya uniformemente las claves. Si la funci�n est� mal dise�ada, se producir�n muchas colisiones. Los inconvenientes de las tablas hash son: Necesidad de ampliar el espacio de la tabla si el volumen de datos almacenados crece. Se trata de una operaci�n costosa. Dificultad para recorrer todos los elementos. Se suelen emplear listas para procesar la totalidad de los elementos. Desaprovechamiento de la memoria. Si se reserva espacio para todos los posibles elementos, se consume m�s memoria de la necesaria; se suele resolver reservando espacio �nicamente para punteros a los elementos.