Tabla de picadillo

Asocia valores de datos con valores clave: una tabla de búsqueda

No confundir con Hash list o Hash tree .

"Rehash" vuelve a dirigir aquí. Para el episodio de South Park , vea Rehash (South Park) . Para el comando IRC, consulte la Lista de comandos de Internet Relay Chat § REHASH .

Tabla de picadillo
Tipo	Desordenada matriz asociativa
Inventado	1953
Complejidad del tiempo en notación O grande
Algoritmo Promedio Peor de los casos Espacio O ( n ) [1] O ( n ) Buscar O (1) O ( n ) Insertar O (1) O ( n ) Borrar O (1) O ( n )

Una pequeña guía telefónica como tabla hash

En informática , una tabla hash ( mapa hash ) es una estructura de datos que implementa un tipo de datos abstracto de matriz asociativa , una estructura que puede asignar claves a valores . Una tabla hash usa una función hash para calcular un índice , también llamado código hash , en una matriz de cubos o ranuras , a partir de los cuales se puede encontrar el valor deseado. Durante la búsqueda, se aplica un hash a la clave y el hash resultante indica dónde se almacena el valor correspondiente.

Idealmente, la función hash asignará cada clave a un depósito único, pero la mayoría de los diseños de tablas hash emplean una función hash imperfecta, lo que podría causar colisiones hash donde la función hash genera el mismo índice para más de una clave. Por lo general, estas colisiones se adaptan de alguna manera.

En una tabla hash bien dimensionada, el costo promedio (número de instrucciones ) para cada búsqueda es independiente del número de elementos almacenados en la tabla. Muchos diseños de tablas hash también permiten inserciones y eliminaciones arbitrarias de pares clave-valor , a un costo promedio constante ( amortizado ^[2] ) por operación. ^{[3] [4]}

En muchas situaciones, las tablas hash resultan ser, en promedio, más eficientes que los árboles de búsqueda o cualquier otra tabla de estructura de búsqueda. Por esta razón, se utilizan ampliamente en muchos tipos de software de computadora , particularmente para matrices asociativas , indexación de bases de datos , cachés y conjuntos .

Hash

Artículo principal: función hash

La idea del hash es distribuir las entradas (pares clave / valor) en una matriz de depósitos . Dada una clave, el algoritmo calcula un índice que sugiere dónde se puede encontrar la entrada:

índice = f (clave, tamaño_matriz)

A menudo, esto se hace en dos pasos:

hash = hashfunc (clave)índice = hash% tamaño_array

En este método, el hash es independiente del tamaño de la matriz y luego se reduce a un índice (un número entre 0y array_size − 1) usando el operador de módulo ( %).

En el caso de que el tamaño de la matriz sea una potencia de dos , la operación restante se reduce a enmascaramiento , lo que mejora la velocidad, pero puede aumentar los problemas con una función hash deficiente. ^[5]

Elegir una función hash

Un requisito básico es que la función debe proporcionar una distribución uniforme de valores hash. Una distribución no uniforme aumenta el número de colisiones y el costo de resolverlas. La uniformidad a veces es difícil de asegurar por diseño, pero puede evaluarse empíricamente usando pruebas estadísticas, por ejemplo, una prueba de chi-cuadrado de Pearson para distribuciones uniformes discretas. ^{[6] [7]}

La distribución debe ser uniforme solo para los tamaños de mesa que ocurren en la aplicación. En particular, si se usa un cambio de tamaño dinámico con duplicación exacta y reducción a la mitad del tamaño de la tabla, entonces la función hash debe ser uniforme solo cuando el tamaño es una potencia de dos . Aquí, el índice se puede calcular como un rango de bits de la función hash. Por otro lado, algunos algoritmos de hash prefieren que el tamaño sea un número primo . ^[8] La operación del módulo puede proporcionar una mezcla adicional; esto es especialmente útil con una función hash deficiente.

Para esquemas de direccionamiento abiertos , la función hash también debe evitar la agrupación , la asignación de dos o más claves a ranuras consecutivas. Tal agrupación puede hacer que el costo de búsqueda se dispare, incluso si el factor de carga es bajo y las colisiones son poco frecuentes. Se afirma que el popular hash multiplicativo ^[3] tiene un comportamiento de agrupamiento particularmente pobre. ^[8]

Se cree que las funciones hash criptográficas proporcionan buenas funciones hash para cualquier tamaño de tabla, ya sea mediante reducción de módulo o mediante enmascaramiento de bits ^{[ cita requerida ]} . También pueden ser apropiados si existe el riesgo de que usuarios malintencionados intenten sabotear un servicio de red enviando solicitudes diseñadas para generar una gran cantidad de colisiones en las tablas hash del servidor. Sin embargo, el riesgo de sabotaje también se puede evitar con métodos más baratos (como aplicar una sal secreta a los datos o utilizar una función hash universal ). Un inconveniente de las funciones hash criptográficas es que a menudo son más lentas de calcular, lo que significa que en los casos en que la uniformidad decualquier tamaño no es necesario, podría ser preferible una función hash no criptográfica. ^{[ cita requerida ]}

Función hash perfecta

Si todas las claves son conocidos de antemano, una función hash perfecta se puede utilizar para crear una tabla hash perfecta que no tiene colisiones. Si se utiliza un hash perfecto mínimo, también se pueden utilizar todas las ubicaciones de la tabla hash.

El hash perfecto permite búsquedas de tiempo constantes en todos los casos. Esto contrasta con la mayoría de los métodos de encadenamiento y direccionamiento abierto, donde el tiempo de búsqueda es bajo en promedio, pero puede ser muy grande, O ( n ), por ejemplo, cuando todas las claves tienen unos pocos valores.

Estadísticas clave

Una estadística crítica para una tabla hash es el factor de carga , definido como

${\displaystyle {\text{load factor}}={\frac {n}{k}}}$,

dónde

• n es el número de entradas ocupadas en la tabla hash.
• k es el número de cubos.

A medida que el factor de carga aumenta, la tabla hash se vuelve más lenta e incluso puede dejar de funcionar (según el método utilizado). La propiedad de tiempo constante esperada de una tabla hash supone que el factor de carga se mantiene por debajo de algún límite. Para un número fijo de depósitos, el tiempo de búsqueda aumenta con el número de entradas y, por lo tanto, no se alcanza el tiempo constante deseado. En algunas implementaciones, la solución es aumentar automáticamente (generalmente, duplicar) el tamaño de la tabla cuando se alcanza el límite del factor de carga, lo que obliga a volver a realizar el hash en todas las entradas. Como ejemplo del mundo real, el factor de carga predeterminado para un HashMap en Java 10 es 0,75, lo que "ofrece una buena compensación entre los costos de tiempo y espacio". ^[9]

En segundo lugar al factor de carga, se puede examinar la variación del número de entradas por cubo. Por ejemplo, dos tablas tienen 1000 entradas y 1000 depósitos; uno tiene exactamente una entrada en cada depósito, el otro tiene todas las entradas en el mismo depósito. Claramente, el hash no funciona en el segundo.

Un factor de carga bajo no es especialmente beneficioso. A medida que el factor de carga se acerca a 0, la proporción de áreas no utilizadas en la tabla hash aumenta, pero no necesariamente hay una reducción en el costo de búsqueda. Esto resulta en una pérdida de memoria.

Resolución de colisión

Las colisiones de hash son prácticamente inevitables cuando se aplica hash a un subconjunto aleatorio de un gran conjunto de claves posibles. Por ejemplo, si 2,450 claves se han codificado en un millón de depósitos, incluso con una distribución aleatoria perfectamente uniforme, de acuerdo con el problema de cumpleaños, hay aproximadamente un 95% de posibilidades de que al menos dos de las claves se hayan codificado en la misma ranura.

Por lo tanto, casi todas las implementaciones de tablas hash tienen alguna estrategia de resolución de colisiones para manejar tales eventos. Algunas estrategias comunes se describen a continuación. Todos estos métodos requieren que las claves (o punteros a ellas) se almacenen en la tabla, junto con los valores asociados.

Encadenamiento separado

Colisión de hash resuelta mediante encadenamiento independiente

En el método conocido como encadenamiento separado , cada depósito es independiente y tiene algún tipo de lista de entradas con el mismo índice. El tiempo para las operaciones de la tabla hash es el tiempo para encontrar el depósito (que es constante) más el tiempo para la operación de lista.

En la mayoría de las implementaciones, los depósitos tendrán pocas entradas, si la función hash funciona correctamente. Por tanto, se prefieren estructuras que sean eficientes en tiempo y espacio para estos casos. Las estructuras que son eficientes para un número bastante grande de entradas por segmento no son necesarias ni deseables. Si estos casos ocurren con frecuencia, la función hash debe arreglarse. ^[10]

Hay algunas implementaciones ^[11] que ofrecen un rendimiento excelente tanto en el tiempo como en el espacio, con un número medio de elementos por cubo que oscila entre 5 y 100.

Encadenamiento independiente con listas enlazadas

Las tablas hash encadenadas con listas vinculadas son populares porque solo requieren estructuras de datos básicas con algoritmos simples y pueden usar funciones hash simples que no son adecuadas para otros métodos. ^{[ cita requerida ]}

El costo de una operación de mesa es el de escanear las entradas del cubo seleccionado para la clave deseada. Si la distribución de claves es suficientemente uniforme , el costo promedio de una búsqueda depende solo del número promedio de claves por depósito, es decir, es aproximadamente proporcional al factor de carga.

Por esta razón, las tablas hash encadenadas siguen siendo efectivas incluso cuando el número de entradas de la tabla n es mucho mayor que el número de ranuras. Por ejemplo, una tabla hash encadenada con 1000 ranuras y 10,000 claves almacenadas (factor de carga 10) es de cinco a diez veces más lenta que una tabla de 10,000 ranuras (factor de carga 1); pero aún 1000 veces más rápido que una lista secuencial simple.

Para el encadenamiento por separado, el peor de los casos es cuando todas las entradas se insertan en el mismo depósito, en cuyo caso la tabla hash es ineficaz y el costo es el de buscar en la estructura de datos del depósito. Si esta última es una lista lineal, es posible que el procedimiento de búsqueda tenga que escanear todas sus entradas, por lo que el costo del peor de los casos es proporcional al número n de entradas en la tabla.

Las cadenas de cangilones a menudo se buscan secuencialmente usando el orden en que se agregaron las entradas al cangilón. Si el factor de carga es grande y es más probable que aparezcan algunas claves que otras, entonces reorganizar la cadena con una heurística de movimiento al frente puede ser eficaz. Vale la pena considerar estructuras de datos más sofisticadas, como árboles de búsqueda equilibrados, solo si el factor de carga es grande (alrededor de 10 o más), o si es probable que la distribución de hash sea muy no uniforme, o si se debe garantizar un buen rendimiento incluso en el peor de los casos. Sin embargo, usar una tabla más grande y / o una mejor función hash puede ser incluso más efectivo en esos casos. ^{[ cita requerida ]}

Las tablas hash encadenadas también heredan las desventajas de las listas enlazadas. Al almacenar claves y valores pequeños, la sobrecarga de espacio del nextpuntero en cada registro de entrada puede ser significativa. Una desventaja adicional es que atravesar una lista vinculada tiene un rendimiento de caché deficiente , lo que hace que la caché del procesador sea ineficaz.

Encadenamiento separado con celdas de encabezado de lista

Colisión de hash mediante encadenamiento separado con registros principales en la matriz de cubos.

Algunas implementaciones de encadenamiento almacenan el primer registro de cada cadena en la propia matriz de ranuras. ^[4] El número de recorridos del puntero se reduce en uno en la mayoría de los casos. El propósito es aumentar la eficiencia de la caché del acceso a la tabla hash.

La desventaja es que un balde vacío ocupa el mismo espacio que un balde con una sola entrada. Para ahorrar espacio, estas tablas hash suelen tener tantas ranuras como entradas almacenadas, lo que significa que muchas ranuras tienen dos o más entradas. ^{[ cita requerida ]}

Separar el encadenamiento con otras estructuras

En lugar de una lista, se puede utilizar cualquier otra estructura de datos que admita las operaciones necesarias. Por ejemplo, mediante el uso de un árbol de búsqueda binario autoequilibrado , el tiempo teórico del peor de los casos de las operaciones comunes de la tabla hash (inserción, eliminación, búsqueda) se puede reducir a O (log n ) en lugar de O ( n ). Sin embargo, esto introduce una complejidad adicional en la implementación y puede causar un rendimiento aún peor para tablas hash más pequeñas, donde el tiempo dedicado a insertar y equilibrar el árbol es mayor que el tiempo necesario para realizar una búsqueda lineal en todos los elementos de una lista. . ^{[3] [12]}Un ejemplo del mundo real de una tabla hash que utiliza un árbol de búsqueda binario autoequilibrado para depósitos es la HashMapclase en la versión 8 de Java . ^[13]

La variante llamada tabla hash de matriz utiliza una matriz dinámica para almacenar todas las entradas que contienen hash en la misma ranura. ^{[14] [15] [16]} Cada entrada recién insertada se agrega al final de la matriz dinámica que se asigna a la ranura. El tamaño de la matriz dinámica se cambia de manera exacta , lo que significa que solo se aumenta en tantos bytes como sea necesario. Se descubrió que técnicas alternativas, como hacer crecer la matriz por tamaños de bloque o páginas, mejoran el rendimiento de la inserción, pero a un costo de espacio. Esta variación hace un uso más eficiente del almacenamiento en caché de la CPU y el búfer de búsqueda de traducción(TLB), porque las entradas de las ranuras se almacenan en posiciones de memoria secuenciales. También prescinde de los nextpunteros que requieren las listas enlazadas, lo que ahorra espacio. A pesar de los frecuentes cambios de tamaño de la matriz, los gastos generales de espacio en los que incurre el sistema operativo, como la fragmentación de la memoria, eran pequeños. ^{[ cita requerida ]}

Una elaboración de este enfoque es el llamado hash perfecto dinámico , ^[17] donde un cubo que contiene k entradas se organiza como una tabla hash perfecta con k ² ranuras. Si bien usa más memoria ( n ² ranuras para n entradas, en el peor de los casos y n × k ranuras en el caso promedio), esta variante ha garantizado un tiempo de búsqueda constante en el peor de los casos y un tiempo amortizado bajo para la inserción. También es posible utilizar un árbol de fusión para cada cubeta, logrando un tiempo constante para todas las operaciones con alta probabilidad. ^[18]

Abrir direccionamiento

Artículo principal: direccionamiento abierto

Colisión hash resuelta mediante direccionamiento abierto con sondeo lineal (intervalo = 1). Tenga en cuenta que "Ted Baker" tiene un hash único, pero sin embargo chocó con "Sandra Dee", que previamente había chocado con "John Smith".

En otra estrategia, llamada direccionamiento abierto, todos los registros de entrada se almacenan en la propia matriz de cubos. Cuando se debe insertar una nueva entrada, se examinan los cubos, comenzando con la ranura con hash y siguiendo una secuencia de sondeo , hasta que se encuentra una ranura desocupada. Al buscar una entrada, los depósitos se escanean en la misma secuencia, hasta que se encuentra el registro de destino o se encuentra una ranura de matriz no utilizada, lo que indica que no existe tal clave en la tabla. ^[19] El nombre "direccionamiento abierto" se refiere al hecho de que la ubicación ("dirección") del artículo no está determinada por su valor hash. (Este método también se llama hash cerrado ; no debe confundirse con "hash abierto" o "direccionamiento cerrado" que generalmente significa encadenamiento separado.)

Las secuencias de sondas bien conocidas incluyen:

• Sondeo lineal , en el que el intervalo entre sondas es fijo (normalmente 1). Debido a la buena utilización de la memoria caché de la CPU y al alto rendimiento, este algoritmo se usa más ampliamente en las arquitecturas informáticas modernas en implementaciones de tablas hash. ^[20]
• Sondeo cuadrático , en el que el intervalo entre sondas se incrementa sumando las salidas sucesivas de un polinomio cuadrático al valor inicial dado por el cálculo hash original.
• Doble hash , en el que el intervalo entre sondas se calcula mediante una segunda función hash

Un inconveniente de todos estos esquemas de direccionamiento abiertos es que el número de entradas almacenadas no puede exceder el número de ranuras en la matriz de cubos. De hecho, incluso con buenas funciones hash, su rendimiento se degrada drásticamente cuando el factor de carga crece más allá de 0,7 aproximadamente. Para muchas aplicaciones, estas restricciones exigen el uso de redimensionamiento dinámico, con sus costos asociados. ^{[ cita requerida ]}

Los esquemas de direccionamiento abiertos también imponen requisitos más estrictos a la función hash: además de distribuir las claves de manera más uniforme en los depósitos, la función también debe minimizar la agrupación de valores hash que son consecutivos en el orden de la sonda. Usando encadenamiento separado, la única preocupación es que demasiados objetos se mapean con el mismo valor hash; si son adyacentes o cercanos es completamente irrelevante. ^{[ cita requerida ]}

El direccionamiento abierto solo ahorra memoria si las entradas son pequeñas (menos de cuatro veces el tamaño de un puntero) y el factor de carga no es demasiado pequeño. Si el factor de carga es cercano a cero (es decir, hay muchos más depósitos que entradas almacenadas), el direccionamiento abierto es un desperdicio incluso si cada entrada tiene solo dos palabras .

Este gráfico compara el número medio de fallos de caché de CPU necesarios para buscar elementos en tablas hash grandes (que superan con creces el tamaño de la caché) con el encadenamiento y el sondeo lineal. El sondeo lineal funciona mejor debido a una mejor localidad de referencia , aunque a medida que la tabla se llena, su rendimiento se degrada drásticamente.

El direccionamiento abierto evita la sobrecarga de tiempo de asignar cada nuevo registro de entrada y se puede implementar incluso en ausencia de un asignador de memoria. También evita la indirección adicional necesaria para acceder a la primera entrada de cada depósito (es decir, normalmente la única). También tiene una mejor localidad de referencia , particularmente con palpado lineal. Con tamaños de registro pequeños, estos factores pueden producir un mejor rendimiento que el encadenamiento, especialmente para las búsquedas. Las tablas hash con direccionamiento abierto también son más fáciles de serializar porque no usan punteros. ^{[ cita requerida ]}

Por otro lado, el direccionamiento abierto normal es una mala elección para elementos grandes, porque estos elementos llenan líneas de caché de CPU completas (anulando la ventaja de caché) y se desperdicia una gran cantidad de espacio en grandes ranuras de mesa vacías. Si la tabla de direccionamiento abierta solo almacena referencias a elementos (almacenamiento externo), utiliza un espacio comparable al encadenamiento incluso para registros grandes, pero pierde su ventaja de velocidad. ^{[ cita requerida ]}

En términos generales, el direccionamiento abierto se usa mejor para tablas hash con registros pequeños que se pueden almacenar dentro de la tabla (almacenamiento interno) y que quepan en una línea de caché. Son particularmente adecuados para elementos de una palabra o menos. Si se espera que la tabla tenga un factor de carga alto, los registros son grandes o los datos son de tamaño variable, las tablas hash encadenadas suelen funcionar igual o mejor. ^{[ cita requerida ]}

Hash combinado

Un híbrido de encadenamiento y direccionamiento abierto, enlaces hash fusionados entre cadenas de nodos dentro de la propia tabla. ^[19] Al igual que el direccionamiento abierto, logra el uso de espacio y ventajas (algo disminuidas) de caché sobre el encadenamiento. Al igual que el encadenamiento, no presenta efectos de agrupamiento; de hecho, la mesa se puede llenar de manera eficiente a una alta densidad. A diferencia del encadenamiento, no puede tener más elementos que espacios de mesa.

Hash de cuco

Otra solución alternativa de direccionamiento abierto es el hash de cuco, lo que garantiza un tiempo constante de búsqueda y eliminación en el peor de los casos, y un tiempo amortizado constante para las inserciones (con baja probabilidad de que se encuentre el peor de los casos). Utiliza dos o más funciones hash, lo que significa que cualquier par clave / valor podría estar en dos o más ubicaciones. Para la búsqueda, se utiliza la primera función hash; si no se encuentra la clave / valor, se utiliza la segunda función hash, y así sucesivamente. Si ocurre una colisión durante la inserción, la clave se vuelve a aplicar hash con la segunda función hash para asignarla a otro depósito. Si se utilizan todas las funciones hash y todavía hay una colisión, entonces la clave con la que chocó se elimina para dejar espacio para la nueva clave, y la clave anterior se vuelve a hacer hash con una de las otras funciones hash, que la asigna a otra. Cubeta. Si esa ubicación también resulta en una colisión,luego, el proceso se repite hasta que no hay colisión o el proceso atraviesa todos los cubos, momento en el que se cambia el tamaño de la tabla. Combinando múltiples funciones hash con múltiples celdas por depósito, se puede lograr una utilización de espacio muy alta.^{[ cita requerida ]}

Hash de rayuela

Otra solución alternativa de direccionamiento abierto es el hash rayuela , ^[21] que combina los enfoques del hash de cuco y el sondeo lineal , pero parece, en general, evitar sus limitaciones. En particular, funciona bien incluso cuando el factor de carga supera el 0,9. El algoritmo es adecuado para implementar una tabla hash concurrente de tamaño variable .

El algoritmo hash rayuela funciona definiendo un vecindario de cubos cerca del cubo hash original, donde siempre se encuentra una entrada determinada. Por lo tanto, la búsqueda se limita al número de entradas en esta vecindad, que es logarítmica en el peor de los casos, constante en promedio y con la alineación adecuada de la vecindad generalmente requiere un error de caché. Al insertar una entrada, primero se intenta agregarla a un depósito en el vecindario. Sin embargo, si todos los depósitos de esta vecindad están ocupados, el algoritmo recorre los depósitos en secuencia hasta que se encuentra una ranura abierta (un depósito desocupado) (como en el sondeo lineal). En ese punto, dado que el balde vacío está fuera del vecindario, los artículos se desplazan repetidamente en una secuencia de saltos. (Esto es similar al hash de cuco,pero con la diferencia de que, en este caso, el espacio vacío se mueve al vecindario, en lugar de que los elementos se muevan con la esperanza de encontrar finalmente un espacio vacío). Cada salto acerca el espacio abierto al vecindario original, sin invalidar el propiedad del vecindario de cualquiera de los cubos a lo largo del camino. Al final, la ranura abierta se ha movido al vecindario y la entrada que se está insertando se puede agregar a ella.^{[ cita requerida ]}

Hash de Robin Hood

Una variación de la resolución de colisión con doble hash es el hash de Robin Hood. ^{[22] [23]} La idea es que una nueva llave puede desplazar una llave ya insertada, si su conteo de sondas es mayor que el de la llave en la posición actual. El efecto neto de esto es que reduce los peores tiempos de búsqueda en la tabla. Esto es similar a las tablas hash ordenadas ^[24] excepto que el criterio para golpear una clave no depende de una relación directa entre las claves. Dado que tanto el peor de los casos como la variación en el número de sondas se reducen drásticamente, una variación interesante es sondear la tabla comenzando en el valor esperado de la sonda exitosa y luego expandir desde esa posición en ambas direcciones. ^[25]El hash externo de Robin Hood es una extensión de este algoritmo donde la tabla se almacena en un archivo externo y cada posición de la tabla corresponde a una página de tamaño fijo o depósito con registros B. ^[26]

Hash de 2 opciones

El hash de 2 opciones emplea dos funciones hash diferentes, h ₁ ( x ) y h ₂ ( x ), para la tabla hash. Ambas funciones hash se utilizan para calcular dos ubicaciones de tabla. Cuando se inserta un objeto en la tabla, se coloca en la ubicación de la mesa que contiene menos objetos (siendo el valor predeterminado la ubicación de la tabla h ₁ ( x ) si hay igualdad en el tamaño del cubo). El hash de 2 opciones emplea el principio del poder de dos opciones. ^[27]

Cambio de tamaño dinámico

Cuando se realiza una inserción de tal manera que el número de entradas en una tabla hash excede el producto del factor de carga y la capacidad actual, entonces la tabla hash deberá volver a procesarse . ^{[9] El} refrito incluye aumentar el tamaño de la estructura de datos subyacente ^[9] y asignar elementos existentes a nuevas ubicaciones de depósito. En algunas implementaciones, si la capacidad inicial es mayor que el número máximo de entradas dividido por el factor de carga, nunca se realizarán operaciones de refrito. ^[9]

Para limitar la proporción de memoria desperdiciada debido a depósitos vacíos, algunas implementaciones también reducen el tamaño de la tabla, seguido de un refrito, cuando se eliminan elementos. Desde el punto de vista de las compensaciones entre el espacio y el tiempo, esta operación es similar a la desasignación en matrices dinámicas.

Cambiar el tamaño copiando todas las entradas

Un enfoque común es activar automáticamente un cambio de tamaño completo cuando el factor de carga excede algún umbral r _máx . Luego, se asigna una nueva tabla más grande , cada entrada se elimina de la tabla anterior y se inserta en la nueva tabla. Cuando se han eliminado todas las entradas de la tabla anterior, la tabla anterior se devuelve al grupo de almacenamiento gratuito. Asimismo, cuando el factor de carga cae por debajo de un segundo umbral r _min , todas las entradas se mueven a una nueva tabla más pequeña.

Para las tablas hash que se encogen y crecen con frecuencia, el cambio de tamaño hacia abajo se puede omitir por completo. En este caso, el tamaño de la tabla es proporcional al número máximo de entradas que alguna vez estuvieron en la tabla hash al mismo tiempo, en lugar del número actual. La desventaja es que el uso de la memoria será mayor y, por lo tanto, el comportamiento de la caché puede ser peor. Para un mejor control, se puede proporcionar una operación de "encogimiento para ajustar" que hace esto solo a pedido.

Si el tamaño de la tabla aumenta o disminuye en un porcentaje fijo en cada expansión, el costo total de estos cambios de tamaño, amortizado en todas las operaciones de inserción y eliminación, sigue siendo una constante, independiente del número de entradas n y del número m de operaciones realizadas. .

Por ejemplo, considere una tabla que se creó con el tamaño mínimo posible y se duplica cada vez que la relación de carga excede algún umbral. Si se insertan m elementos en esa tabla, el número total de reinserciones adicionales que ocurren en todos los cambios de tamaño dinámicos de la tabla es como máximo m  - 1. En otras palabras, el cambio de tamaño dinámico duplica aproximadamente el costo de cada operación de inserción o eliminación.

Alternativas a la repetición de todo a la vez

Algunas implementaciones de tablas hash, especialmente en sistemas en tiempo real , no pueden pagar el precio de ampliar la tabla hash de una sola vez, porque pueden interrumpir las operaciones de tiempo crítico. Si no se puede evitar el cambio de tamaño dinámico, una solución es realizar el cambio de tamaño gradualmente.

Las tablas hash basadas en disco casi siempre utilizan alguna alternativa al refrito de una sola vez, ya que el costo de reconstruir toda la tabla en el disco sería demasiado alto.

Cambio de tamaño incremental

Una alternativa para agrandar la tabla de una vez es realizar el refrito gradualmente:

• Durante el cambio de tamaño, asigne la nueva tabla hash, pero mantenga la tabla anterior sin cambios.
• En cada operación de búsqueda o eliminación, verifique ambas tablas.
• Realice operaciones de inserción solo en la nueva tabla.
• En cada inserción, mueva también r elementos de la tabla anterior a la tabla nueva.
• Cuando se eliminen todos los elementos de la tabla anterior, desasignela.

Para asegurarse de que la tabla anterior se copia completamente antes de que la tabla nueva necesite ser ampliada, es necesario aumentar el tamaño de la tabla en un factor de al menos ( r + 1) / r durante el cambio de tamaño.

Teclas monotónicas

Si se sabe que las claves se almacenarán en un orden monotónico creciente (o decreciente), entonces se puede lograr una variación de hash consistente .

Dada alguna clave inicial k ₁ , una clave posterior k _i divide el dominio de clave [ k ₁ , ∞) en el conjunto {[ k ₁ , k _i ), [ k _i , ∞) }. En general, repetir este proceso da una partición más fina {[ k ₁ , k _{i 0} ), [ k _{i 0} , k _{i 1} ), ..., [ k _{i n - 1} , k _{i n} ), [ k _{i n}, ∞) } para alguna secuencia de claves que aumentan monótonamente ( k _{i 0} , ..., k _{i n} ) , donde n es el número de refinamientos . El mismo proceso se aplica, mutatis mutandis , a las teclas decrecientes monótonamente. Al asignar a cada subintervalo de esta partición una función hash o tabla hash diferente (o ambas), y al refinar la partición cada vez que se cambia el tamaño de la tabla hash, este enfoque garantiza que el hash de cualquier clave, una vez emitido, nunca cambiará, incluso cuando el se cultiva la tabla hash.

Dado que es común aumentar el número total de entradas duplicando, solo habrá O (log ( N )) subintervalos para verificar, y el tiempo de búsqueda binaria para la redirección será O (log (log ( N ))).

Hash lineal

El hash lineal ^[28] es un algoritmo de tabla hash que permite la expansión incremental de la tabla hash. Se implementa utilizando una sola tabla hash, pero con dos posibles funciones de búsqueda.

Hash para tablas hash distribuidas

Otra forma de disminuir el costo del cambio de tamaño de la tabla es elegir una función hash de tal manera que los hash de la mayoría de los valores no cambien cuando se cambia el tamaño de la tabla. Estas funciones hash son frecuentes en tablas hash distribuidas y basadas en disco , donde la repetición es prohibitivamente costosa. El problema de diseñar un hash de modo que la mayoría de los valores no cambien cuando se cambia el tamaño de la tabla se conoce como el problema de la tabla hash distribuida . Los cuatro enfoques más populares son el hash de encuentro , el hash consistente , el algoritmo de red direccionable de contenido y la distancia Kademlia .

Rendimiento

Análisis de velocidad

En el modelo más simple, la función hash está completamente sin especificar y la tabla no cambia de tamaño. Con una función hash ideal, una tabla de tamaño con direccionamiento abierto no tiene colisiones y mantiene elementos con una sola comparación para una búsqueda exitosa, mientras que una tabla de tamaño con encadenamiento y claves tiene las colisiones y comparaciones mínimas para la búsqueda. Con la peor función hash posible, cada inserción provoca una colisión y las tablas hash degeneran en búsqueda lineal, con comparaciones amortizadas por inserción y hasta comparaciones para una búsqueda exitosa.${\displaystyle k}$${\displaystyle k}$${\displaystyle k}$${\displaystyle n}$${\displaystyle max(0,n-k)}$${\displaystyle \Theta (1+{\frac {n}{k}})}$${\displaystyle \Theta (n)}$${\displaystyle n}$

Agregar un refrito a este modelo es sencillo. Al igual que en una matriz dinámica , el cambio de tamaño geométrico por un factor de implica que solo se insertan claves o más veces, de modo que el número total de inserciones está delimitado por encima , que es . Al usar el refrito para mantener , las tablas que usan encadenamiento y direccionamiento abierto pueden tener elementos ilimitados y realizar una búsqueda exitosa en una sola comparación para la mejor opción de función hash.${\displaystyle b}$${\displaystyle {\frac {n}{b^{i}}}}$${\displaystyle i}$${\displaystyle {\frac {bn}{b-1}}}$${\displaystyle \Theta (n)}$${\displaystyle n<k}$

En modelos más realistas, la función hash es una variable aleatoria sobre una distribución de probabilidad de funciones hash, y el rendimiento se calcula en promedio sobre la elección de la función hash. Cuando esta distribución es uniforme , el supuesto se denomina "hash uniforme simple" y se puede demostrar que el hash con encadenamiento requiere comparaciones en promedio para una búsqueda fallida, y el hash con direccionamiento abierto lo requiere . ^[29] Ambos límites son constantes, si mantenemos ' usando el cambio de tamaño de la tabla, donde es una constante fija menor que 1.${\displaystyle \Theta \left(1+{\frac {n}{k}}\right)}$${\displaystyle \Theta \left({\frac {1}{1-n/k}}\right)}$${\displaystyle {\frac {n}{k}}<c}$${\displaystyle c}$

Dos factores afectan significativamente la latencia de las operaciones en una tabla hash: ^[30]

• Falta caché. Con el aumento del factor de carga, el rendimiento de búsqueda e inserción de tablas hash se puede degradar mucho debido al aumento de la falta de caché promedio.
• Costo de cambio de tamaño. Cambiar el tamaño se convierte en una tarea que consume mucho tiempo cuando las tablas hash se vuelven masivas.

En los programas sensibles a la latencia, se requiere que el consumo de tiempo de las operaciones tanto en el promedio como en el peor de los casos sea pequeño, estable e incluso predecible. La tabla hash K ^[31] está diseñada para un escenario general de aplicaciones de baja latencia, con el objetivo de lograr operaciones de costo estable en una tabla de gran tamaño en crecimiento.

Utilización de la memoria

A veces, es necesario minimizar el requisito de memoria para una tabla. Una forma de reducir el uso de memoria en los métodos de encadenamiento es eliminar algunos de los punteros de encadenamiento o reemplazarlos con algún tipo de punteros abreviados.

Donald Knuth introdujo otra técnica ^{[ cita requerida ]} y se llama cociente . Para esta discusión asume que la clave, o una versión reversible-hash de esa clave, es un número entero m de {0, 1, 2, ..., M-1} y el número de cubetas es N . m se divide por N para producir un cociente q y un resto r . El resto r se usa para seleccionar el cubo; en el balde sólo es necesario almacenar el cociente q . Esto ahorra log ₂ (N) bits por elemento, lo que puede ser muy significativo en algunas aplicaciones.

El cociente funciona fácilmente con el encadenamiento de tablas hash o con tablas hash de cuco simples. Para aplicar la técnica con tablas hash ordinarias de direccionamiento abierto, John G. Cleary introdujo un método ^[32] en el que se incluyen dos bits (un bit virgen y un bit de cambio ) en cada segmento para permitir que el índice del segmento original ( r ) sea reconstruido.

En el esquema que se acaba de describir, se utilizan log ₂ (M / N) + 2 bits para almacenar cada clave. Es interesante notar que el almacenamiento mínimo teórico sería log ₂ (M / N) + 1.4427 bits donde 1.4427 = log ₂ (e).

Funciones

Ventajas

• La principal ventaja de las tablas hash sobre otras estructuras de datos de tablas es la velocidad. Esta ventaja es más evidente cuando el número de entradas es grande. Las tablas hash son particularmente eficientes cuando se puede predecir el número máximo de entradas, de modo que la matriz de cubos se puede asignar una vez con el tamaño óptimo y nunca cambiar de tamaño.
• Si el conjunto de pares clave-valor es fijo y se conoce de antemano (por lo que no se permiten inserciones y eliminaciones), se puede reducir el costo promedio de búsqueda eligiendo cuidadosamente la función hash, el tamaño de la tabla de depósito y las estructuras de datos internos. En particular, se puede diseñar una función hash que esté libre de colisiones, o incluso perfecta. En este caso, no es necesario almacenar las claves en la tabla.

Inconvenientes

• Aunque las operaciones en una tabla hash toman un tiempo constante en promedio, el costo de una buena función hash puede ser significativamente más alto que el ciclo interno del algoritmo de búsqueda para una lista secuencial o árbol de búsqueda. Por lo tanto, las tablas hash no son efectivas cuando el número de entradas es muy pequeño. (Sin embargo, en algunos casos, el alto costo de calcular la función hash se puede mitigar guardando el valor hash junto con la clave).
• Para ciertas aplicaciones de procesamiento de cadenas, como la revisión ortográfica , las tablas hash pueden ser menos eficientes que los intentos , los autómatas finitos o las matrices Judy . Además, si no hay demasiadas claves posibles para almacenar, es decir, si cada clave se puede representar con un número suficientemente pequeño de bits, entonces, en lugar de una tabla hash, se puede usar la clave directamente como índice en una matriz. de valores. Tenga en cuenta que en este caso no hay colisiones.
• Las entradas almacenadas en una tabla hash se pueden enumerar de manera eficiente (a un costo constante por entrada), pero solo en algún orden pseudoaleatorio. Por lo tanto, no existe una forma eficaz de localizar una entrada cuya clave esté más cerca de una clave determinada. Enumerar todas las n entradas en algún orden específico generalmente requiere un paso de clasificación separado, cuyo costo es proporcional a log ( n ) por entrada. En comparación, los árboles de búsqueda ordenados tienen un costo de búsqueda e inserción proporcional a log ( n ), pero permiten encontrar la clave más cercana al mismo costo y la enumeración ordenada de todas las entradas a un costo constante por entrada. Sin embargo, se puede hacer un LinkingHashMap para crear una tabla hash con una secuencia no aleatoria. ^[33]
• Si las claves no se almacenan (porque la función hash no tiene colisiones), puede que no haya una manera fácil de enumerar las claves que están presentes en la tabla en un momento dado.
• Aunque el costo promedio por operación es constante y bastante pequeño, el costo de una sola operación puede ser bastante alto. En particular, si la tabla hash utiliza un cambio de tamaño dinámico , una operación de inserción o eliminación puede llevar ocasionalmente un tiempo proporcional al número de entradas. Esto puede ser un serio inconveniente en aplicaciones interactivas o en tiempo real.
• Las tablas hash en general exhiben una localidad de referencia deficiente , es decir, los datos a los que se accede se distribuyen aparentemente al azar en la memoria. Debido a que las tablas hash provocan patrones de acceso que saltan, esto puede desencadenar fallas en la caché del microprocesador que provocan retrasos prolongados. Las estructuras de datos compactas, como las matrices buscadas con búsqueda lineal, pueden ser más rápidas si la tabla es relativamente pequeña y las claves son compactas. El punto de rendimiento óptimo varía de un sistema a otro.
• Las tablas hash se vuelven bastante ineficaces cuando hay muchas colisiones. Si bien es muy poco probable que surjan por casualidad distribuciones de hash extremadamente desiguales, un adversario malintencionado con conocimiento de la función hash puede proporcionar información a un hash que crea el peor de los casos al causar colisiones excesivas, lo que da como resultado un rendimiento muy deficiente, por ejemplo, un ataque de denegación de servicio . ^{[34] [35] [36]} En aplicaciones críticas, se puede utilizar una estructura de datos con mejores garantías en el peor de los casos; sin embargo, puede ser preferible el hash universal o una función de hash con clave , que evitan que el atacante prediga qué entradas causan el peor comportamiento de los casos. ^{[37] [38]}
  • La función hash utilizada por la tabla hash en la caché de la tabla de enrutamiento de Linux se cambió con la versión 2.4.2 de Linux como una contramedida contra tales ataques. ^[39] La construcción de hash ad hoc de clave corta se actualizó más tarde para usar un "jhash" y luego SipHash . ^[40]

Usos

Esta sección no cita ninguna fuente . Por favor, ayuda a mejorar esta sección mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado . ( Julio de 2013 ) ( Obtenga información sobre cómo y cuándo eliminar este mensaje de plantilla )

Matrices asociativas

Artículo principal: matriz asociativa

Las tablas hash se usan comúnmente para implementar muchos tipos de tablas en memoria. Se utilizan para implementar matrices asociativas (matrices cuyos índices son cadenas arbitrarias u otros objetos complicados), especialmente en lenguajes de programación interpretados como Ruby , Python y PHP .

Cuando se almacena un nuevo elemento en un multimapa y se produce una colisión de hash, el multimapa almacena incondicionalmente ambos elementos.

Cuando se almacena un nuevo elemento en una matriz asociativa típica y se produce una colisión de hash, pero las claves reales en sí son diferentes, la matriz asociativa también almacena ambos elementos. Sin embargo, si la clave del nuevo elemento coincide exactamente con la clave de un elemento antiguo, la matriz asociativa normalmente borra el elemento antiguo y lo sobrescribe con el nuevo elemento, por lo que cada elemento de la tabla tiene una clave única.

Indexación de bases de datos

Las tablas hash también se pueden utilizar como estructuras de datos basadas en disco e índices de bases de datos (como en dbm ), aunque los árboles B son más populares en estas aplicaciones. En los sistemas de bases de datos de múltiples nodos, las tablas hash se utilizan comúnmente para distribuir filas entre nodos, lo que reduce el tráfico de red para las uniones hash .

Caches

Artículo principal: Caché (informática)

Las tablas hash se pueden usar para implementar cachés , tablas de datos auxiliares que se usan para acelerar el acceso a los datos que se almacenan principalmente en medios más lentos. En esta aplicación, las colisiones de hash se pueden manejar descartando una de las dos entradas que chocan, generalmente borrando el elemento antiguo que está almacenado actualmente en la tabla y sobrescribiéndolo con el nuevo elemento, por lo que cada elemento de la tabla tiene un valor de hash único.

Conjuntos

Además de recuperar la entrada que tiene una clave determinada, muchas implementaciones de tablas hash también pueden indicar si dicha entrada existe o no.

Por lo tanto, esas estructuras se pueden utilizar para implementar una estructura de datos de conjunto , ^[41] que simplemente registra si una clave determinada pertenece a un conjunto específico de claves. En este caso, la estructura se puede simplificar eliminando todas las partes que tienen que ver con los valores de entrada. El hash se puede utilizar para implementar conjuntos tanto estáticos como dinámicos.

Representación de objetos

Varios lenguajes dinámicos, como Perl , Python , JavaScript , Lua y Ruby , usan tablas hash para implementar objetos . En esta representación, las claves son los nombres de los miembros y métodos del objeto, y los valores son punteros al miembro o método correspondiente.

Representación de datos única

Artículo principal: Pasantía de cuerdas

Algunos programas pueden utilizar tablas hash para evitar la creación de varias cadenas de caracteres con el mismo contenido. Para ese propósito, todas las cadenas en uso por el programa se almacenan en un grupo de cadenas único implementado como una tabla hash, que se comprueba cada vez que se debe crear una nueva cadena. Esta técnica se introdujo en los intérpretes Lisp con el nombre de hash consing y se puede utilizar con muchos otros tipos de datos ( árboles de expresión en un sistema de álgebra simbólica, registros en una base de datos, archivos en un sistema de archivos, diagramas de decisión binarios, etc.) .

Tabla de transposición

Artículo principal: tabla de transposición

Una tabla de transposición a una tabla hash compleja que almacena información sobre cada sección que se ha buscado. ^[42]

Implementaciones

En lenguajes de programación

Muchos lenguajes de programación proporcionan funcionalidad de tabla hash, ya sea como matrices asociativas integradas o como módulos de biblioteca estándar . En C ++ 11 , por ejemplo, la unordered_mapclase proporciona tablas hash para claves y valores de tipo arbitrario.

El Java lenguaje de programación (incluyendo la variante que se utiliza en Android ) incluye los HashSet, HashMap, LinkedHashSet, y LinkedHashMap genéricos colecciones. ^[43]

En PHP 5 y 7, el motor Zend 2 y el motor Zend 3 (respectivamente) utilizan una de las funciones hash de Daniel J. Bernstein para generar los valores hash utilizados en la gestión de las asignaciones de punteros de datos almacenados en una tabla hash. En el código fuente de PHP, está etiquetado como DJBX33A(Daniel J. Bernstein, Times 33 with Addition).

La implementación de la tabla hash incorporada de Python , en forma de dicttipo, así como el tipo de hash de Perl (%) se utilizan internamente para implementar espacios de nombres y, por lo tanto, deben prestar más atención a la seguridad, es decir, a los ataques de colisión. Los conjuntos de Python también usan hash internamente, para una búsqueda rápida (aunque almacenan solo claves, no valores). ^[44] CPython 3.6+ usa una variante ordenada por inserción de la tabla hash, implementada dividiendo el almacenamiento de valor en una matriz y haciendo que la tabla hash vainilla solo almacene un conjunto de índices. ^[45]

En .NET Framework , el soporte para tablas hash se proporciona a través de las clases genéricas Hashtabley no genéricas Dictionary, que almacenan pares clave-valor , y la HashSetclase genérica , que almacena solo valores.

En Ruby, la tabla hash utiliza el modelo de direccionamiento abierto de Ruby 2.4 en adelante. ^{[46] [47]}

En la biblioteca estándar de Rust , las estructuras genéricas HashMapy HashSetusan sondeo lineal con robo de cubos de Robin Hood.

ANSI Smalltalk define las clases Set/ IdentitySety Dictionary/ IdentityDictionary. Todo implementaciones de Smalltalk proporcionan versiones adicionales (aún no estandarizados) de WeakSet, WeakKeyDictionaryy WeakValueDictionary.

Las variables de matriz Tcl son tablas hash y los diccionarios Tcl son valores inmutables basados ​​en hashes. La funcionalidad también está disponible como funciones de biblioteca C Tcl_InitHashTable et al. (para tablas hash genéricas) y Tcl_NewDictObj et al. (para valores de diccionario). El rendimiento ha sido evaluado de forma independiente como extremadamente competitivo. ^[48]

El Wolfram Idioma soporta tablas hash desde la versión 10. Se llevan a cabo bajo el nombre Association.

Common Lisp proporciona la hash-tableclase para mapeos eficientes. A pesar de su denominación, el estándar de lenguaje no exige la adherencia real a ninguna técnica de hash para las implementaciones. ^[49]

Historia

La idea de hash surgió de forma independiente en diferentes lugares. En enero de 1953, Hans Peter Luhn escribió un memorando interno de IBM que usaba hash con encadenamiento. ^[50] Gene Amdahl , Elaine M. McGraw , Nathaniel Rochester y Arthur Samuel implementaron un programa usando hash aproximadamente al mismo tiempo. El direccionamiento abierto con sondeo lineal (paso a paso relativamente primordial) se le atribuye a Amdahl, pero Ershov (en Rusia) tuvo la misma idea. ^[50]

Ver también

• Algoritmo de búsqueda de cadenas de Rabin-Karp
• Hash estable
• Hash consistente
• Hash extensible
• Eliminación perezosa
• Hash de Pearson
• PhotoDNA
• Estructura de datos de búsqueda
• Tabla hash concurrente
• Record (ciencias de la computación)

Estructuras de datos relacionadas

Hay varias estructuras de datos que utilizan funciones hash pero no pueden considerarse casos especiales de tablas hash:

• Filtro Bloom , una estructura de datos de memoria eficiente diseñada para búsquedas aproximadas en tiempo constante; utiliza funciones hash y puede verse como una tabla hash aproximada.
• Tabla hash distribuida (DHT), una tabla dinámica resistente distribuida en varios nodos de una red.
• Trie mapeado en matriz hash , una estructura de trie , similar al trie mapeado en matriz , pero donde cada clave tiene un hash primero.

Referencias

1. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009). Introducción a los algoritmos (3ª ed.). Instituto de Tecnología de Massachusetts. págs. 253–280. ISBN  978-0-262-03384-8.
2. Charles E. Leiserson , Amortized Algorithms, Table Doubling, Potential Method Archivado el 7 de agosto de 2009, en la Wayback Machine Lecture 13, curso MIT 6.046J / 18.410J Introducción a los algoritmos — Otoño de 2005
3. Knuth, Donald (1998). El arte de la programación informática . 3: Clasificación y búsqueda (2ª ed.). Addison-Wesley. págs. 513–558. ISBN  978-0-201-89685-5.
4. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Capítulo 11: Tablas hash". Introducción a los algoritmos (2ª ed.). MIT Press y McGraw-Hill. pp.  221 -252. ISBN 978-0-262-53196-2.
5. "Implementación de Hashcode JDK HashMap" . Archivado desde el original el 21 de mayo de 2017.
6. Pearson, Karl (1900). "Sobre el criterio de que un sistema dado de desviaciones de lo probable en el caso de un sistema correlacionado de variables es tal que puede suponerse razonablemente que ha surgido de un muestreo aleatorio". Revista filosófica . Serie 5. 50 (302). págs. 157-175. doi : 10.1080 / 14786440009463897 .
7. Plackett, Robin (1983). "Karl Pearson y la prueba de chi-cuadrado". Revista Estadística Internacional (Instituto Internacional de Estadística (ISI)) . 51 (1). págs. 59–72. doi : 10.2307 / 1402731 . JSTOR 1402731 .  
8. Wang, Thomas (marzo de 1997). "Tabla Prime Double Hash" . Archivado desde el original el 3 de septiembre de 1999 . Consultado el 10 de mayo de 2015 .
9. Javadoc para HashMap en Java 10 https://docs.oracle.com/javase/10/docs/api/java/util/HashMap.html
10. "Tabla de hash de CS" . everythingcomputerscience.com .
11. Jaco Geldenhuys; Antti Valmari. "Estructura de datos casi óptima para la memoria" . Biblioteca digital ACM . Archivado desde el original el 29 de julio de 2020 . Consultado el 21 de febrero de 2021 .
12. Probst, Mark (30 de abril de 2010). "Búsqueda lineal vs binaria" . Archivado desde el original el 20 de noviembre de 2016 . Consultado el 20 de noviembre de 2016 .
13. "Cómo funciona un HashMap en JAVA" . coding-geek.com. Archivado desde el original el 19 de noviembre de 2016.
14. Askitis, Nikolas; Zobel, Justin (octubre de 2005). Resolución de colisiones consciente de la caché en tablas de hash de cadenas . Actas de la 12ª Conferencia Internacional, Procesamiento de cadenas y recuperación de información (SPIRE 2005) . 3772/2005. págs. 91-102. doi : 10.1007 / 11575832_11 . ISBN  978-3-540-29740-6.
15. Askitis, Nikolas; Sinha, Ranjan (2010). "Ingeniería escalable, caché y eficientes intentos de espacio para cadenas". El diario VLDB . 17 (5): 633–660. doi : 10.1007 / s00778-010-0183-9 . ISSN 1066-8888 . S2CID 432572 .   
16. Askitis, Nikolas (2009). Tablas hash rápidas y compactas para claves enteras (PDF) . Actas de la 32ª Conferencia de Ciencias de la Computación de Australasia (ACSC 2009) . 91 . págs. 113-122. ISBN  978-1-920682-72-9. Archivado desde el original (PDF) el 16 de febrero de 2011 . Consultado el 13 de junio de 2010 .
17. Erik Demaine, Jeff Lind. 6.897: Estructuras de datos avanzadas. Laboratorio de Informática e Inteligencia Artificial del MIT. Primavera de 2003. "Copia archivada" (PDF) . Archivado (PDF) desde el original el 15 de junio de 2010 . Consultado el 30 de junio de 2008 .
18. Willard, Dan E. (2000). "Examinando geometría computacional, árboles de van Emde Boas y hashing desde la perspectiva del árbol de fusión". Revista SIAM de Computación . 29 (3): 1030–1049. doi : 10.1137 / S0097539797322425 . Señor 1740562 . .
19. Tenenbaum, Aaron M .; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Estructuras de datos utilizando C . Prentice Hall. págs. 456–461, pág. 472. ISBN  978-0-13-199746-2.
20. Pagh, Rasmus ; Rodler, Flemming Friche (2001). "Cuco Hashing". Algoritmos - ESA 2001 . Apuntes de conferencias en Ciencias de la Computación. 2161 . págs. 121-133. CiteSeerX 10.1.1.25.4189 . doi : 10.1007 / 3-540-44676-1_10 . ISBN  978-3-540-42493-2.
21. Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Rayuela Hashing". DISC '08: Actas del 22º simposio internacional de Computación Distribuida . Berlín, Heidelberg: Springer-Verlag. págs. 350–364. CiteSeerX 10.1.1.296.8742 . 
22. Celis, Pedro (1986). Hash de Robin Hood (PDF) (Informe técnico). Departamento de Ciencias de la Computación, Universidad de Waterloo. CS-86-14. Archivado (PDF) desde el original el 17 de julio de 2014.
23. Goossaert, Emmanuel (2013). "Hash de Robin Hood" . Archivado desde el original el 21 de marzo de 2014.
24. Amble, Ole; Knuth, Don (1974). "Tablas hash ordenadas" . Revista informática . 17 (2): 135. doi : 10.1093 / comjnl / 17.2.135 .
25. Viola, Alfredo (octubre de 2005). "Distribución exacta de los desplazamientos individuales en el hashing de palpado lineal". Transacciones sobre algoritmos (TALG) . 1 (2): 214–242. doi : 10.1145 / 1103963.1103965 . S2CID 11183559 . 
26. Celis, Pedro (marzo de 1988). Hashing de Robin Hood externo (informe técnico). Departamento de Ciencias de la Computación, Universidad de Indiana. TR246.
27. Mitzenmacher, Michael; Richa, Andréa W .; Sitaraman, Ramesh (2001). "El poder de dos elecciones aleatorias: un estudio de técnicas y resultados" (PDF) . Universidad de Harvard . Archivado (PDF) desde el original el 25 de marzo de 2015 . Consultado el 10 de abril de 2015 .
28. Litwin, Witold (1980). "Hash lineal: una nueva herramienta para el direccionamiento de archivos y tablas". Proc. VI Jornada sobre Bases de Datos Muy Grandes . págs. 212-223.
29. Doug Dunham. CS 4521 Lecture Notes Archivado el 22 de julio de 2009 en Wayback Machine . Universidad de Minnesota Duluth. Teoremas 11.2, 11.6. Última modificación el 21 de abril de 2009.
30. Andy Ke. Dentro de la latencia de las operaciones de la tabla hash Última modificación el 30 de diciembre de 2019.
31. Andy Ke. La tabla hash K, un diseño para aplicaciones de baja latencia Archivado el 21 de febrero de 2021 en Wayback Machine Última modificación el 20 de diciembre de 2019.
32. Secretaria (1984). "Tablas hash compactas con palpado lineal bidireccional" . IEEE Transactions on Computers (9): 828–834. doi : 10.1109 / TC.1984.1676499 . S2CID 195908955 . Archivado desde el original el 26 de octubre de 2020 . Consultado el 21 de febrero de 2021 . 
33. "LinkedHashMap (Java Platform SE 7)" . docs.oracle.com . Archivado desde el original el 18 de septiembre de 2020 . Consultado el 1 de mayo de 2020 .
34. Ataques de denegación de servicio eficientes de Alexander Klink y Julian Wälde en plataformas de aplicaciones web. Archivado el 16 de septiembre de 2016 en Wayback Machine , 28 de diciembre de 2011, 28º Congreso de Comunicación del Caos. Berlín, Alemania.
35. Mike Lennon "La vulnerabilidad de la tabla hash permite ataques DDoS a gran escala" Archivado el 19 de septiembre de 2016 en Wayback Machine . 2011.
36. "Endurecimiento de la función hash de Perl" . 6 de noviembre de 2013. Archivado desde el original el 16 de septiembre de 2016.
37. Crosby y Wallach.Denegación de servicio a través de ataques de complejidad algorítmica Archivado el 4 de marzo de 2016 en Wayback Machine . cita: "las modernas técnicas de hash universales pueden producir un rendimiento comparable al de las funciones hash habituales y, al mismo tiempo, ser probadamente seguras contra estos ataques". "Las funciones hash universales ... son ... una solución adecuada para entornos adversarios ... en sistemas de producción".
38. Aumasson, Jean-Philippe; Bernstein, Daniel J .; Boßlet, Martin (8 de noviembre de 2012). DoS de inundación de hash recargado: ataques y defensas (PDF) . Foro de seguridad de aplicaciones - Suiza occidental 2012 .
39. Bar-Yosef, Noa; Lana, Avishai (2007). Ataques de complejidad algorítmica remota contra tablas hash aleatorias Proc. Congreso Internacional de Seguridad y Criptografía (SECRYPT) (PDF) . pag. 124. Archivado (PDF) desde el original el 16 de septiembre de 2014.
40. "inet: cambia el generador de ID de IP a siphash · torvalds / linux @ df45370" . GitHub .
41. "Establecer (Java Platform SE 7)" . docs.oracle.com . Archivado desde el original el 12 de noviembre de 2020 . Consultado el 1 de mayo de 2020 .
42. "Tabla de transposición - wiki de programación de ajedrez" . chessprogramming.org . Archivado desde el original el 14 de febrero de 2021 . Consultado el 1 de mayo de 2020 .
43. "Lección: Implementaciones (Tutoriales de Java ™> Colecciones)" . docs.oracle.com . Archivado desde el original el 18 de enero de 2017 . Consultado el 27 de abril de 2018 .
44. "Python: Lista vs Dict para tabla de búsqueda" . stackoverflow.com . Archivado desde el original el 2 de diciembre de 2017 . Consultado el 27 de abril de 2018 .
45. Dimitris Fasarakis Hilliard. "¿Los diccionarios están ordenados en Python 3.6+?" . Desbordamiento de pila .
46. Dmitriy Vasin (19 de junio de 2018). "¿Sabes cómo funciona la tabla hash? (Ejemplos de Ruby)" . anadea.info . Consultado el 3 de julio de 2019 .
47. Jonan Scheffler (25 de diciembre de 2016). "Lanzamiento de Ruby 2.4: hashes más rápidos, enteros unificados y mejor redondeo" . heroku.com . Archivado desde el original el 3 de julio de 2019 . Consultado el 3 de julio de 2019 .
48. Ala, Eric. "Hash Table Shootout 2: auge de las máquinas de intérpretes" . LuaHashMap: Un fácil utilizar la biblioteca tabla hash para C . Software PlayControl. Archivado desde el original el 14 de octubre de 2013 . Consultado el 24 de octubre de 2019 . ¿Tcl ganó? En cualquier caso, estos puntos de referencia mostraron que estas implementaciones de intérpretes tienen implementaciones hash muy buenas y son competitivas con nuestro punto de referencia de referencia de STL unordered_map. Particularmente en el caso de Tcl y Lua, eran extremadamente competitivos y, a menudo, estaban dentro del 5% -10% de unordered_map cuando no lo superaban. (El 2019-10-24, el sitio original todavía tiene el texto, pero las cifras parecen estar rotas, mientras que están intactas en el archivo).
49. "CLHS: Clase de sistema HASH-TABLE" . lispworks.com/documentation/HyperSpec/Front/index.htm . Archivado desde el original el 22 de octubre de 2019 . Consultado el 18 de mayo de 2020 .
50. Mehta, Dinesh P .; Sahni, Sartaj (28 de octubre de 2004). Manual de estructuras de datos y aplicaciones . pag. 9-15. ISBN 978-1-58488-435-4.

Lectura adicional

• Tamassia, Roberto; Goodrich, Michael T. (2006). "Capítulo nueve: mapas y diccionarios". Estructuras de datos y algoritmos en Java: [actualizado para Java 5.0] (4ª ed.). Hoboken, Nueva Jersey: Wiley. págs.  369 –418. ISBN 978-0-471-73884-8.
• McKenzie, BJ; Harries, R .; Bell, T. (febrero de 1990). "Selección de un algoritmo hash". Práctica y experiencia de software . 20 (2): 209–224. doi : 10.1002 / spe.4380200207 . hdl : 10092/9691 . S2CID  12854386 .

Enlaces externos

Wikimedia Commons tiene medios relacionados con tablas hash .

Wikilibros tiene un libro sobre el tema: Estructuras de datos / Tablas hash

• Una función hash para la búsqueda de tablas hash de Bob Jenkins.
• Funciones hash de Paul Hsieh
• Diseño de tablas hash compactas y eficientes para Java
• Entrada NIST en tablas hash
• Conferencia sobre tablas hash del CS106A de Stanford
• Estructuras de datos abiertos - Capítulo 5 - Tablas hash , Pat Morin
• Introducción a los algoritmos del MIT : Hashing 1 Video de la conferencia OCW del MIT
• Introducción a los algoritmos del MIT : Hashing 2 Video de la conferencia OCW del MIT