Tabla de picadillo

Matriz asociativa para almacenar pares clave-valor

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

En informática , una tabla hash , también conocida como mapa hash o conjunto hash , es una estructura de datos que implementa una matriz asociativa , también llamada diccionario, que es un tipo de datos abstracto que asigna claves a valores . ^[2] Una tabla hash utiliza una función hash para calcular un índice , también llamado código hash , en una matriz de depósitos 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. Estas colisiones normalmente se adaptan de alguna manera.

En una tabla hash bien dimensionada, la complejidad del tiempo promedio para cada búsqueda es independiente de la cantidad 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 por operación. ^{[3] [4] [5]}

El hashing es un ejemplo de compensación espacio-temporal . Si la memoria es infinita, la clave completa se puede utilizar directamente como índice para localizar su valor con un único acceso a la memoria. Por otro lado, si se dispone de tiempo infinito, los valores se pueden almacenar sin tener en cuenta sus claves y se puede utilizar una búsqueda binaria o lineal para recuperar el elemento. ^{[6] : 458}

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

Historia

La idea del hash surgió de forma independiente en diferentes lugares. En enero de 1953, Hans Peter Luhn escribió un memorando interno de IBM que utilizaba hash con encadenamiento. El primer ejemplo de discurso abierto fue propuesto por AD Linh, basándose en el memorando de Luhn. ^{[7] : 15} Casi al mismo tiempo, Gene Amdahl , Elaine M. McGraw , Nathaniel Rochester y Arthur Samuel de IBM Research implementaron hash para el ensamblador IBM 701 . ^{[8] : 124} El direccionamiento abierto con sondeo lineal se atribuye a Amdahl, aunque Andrey Ershov, de forma independiente, tuvo la misma idea. ^{[8] : 124-125} El término "direccionamiento abierto" fue acuñado por W. Wesley Peterson en su artículo que analiza el problema de la búsqueda en archivos grandes. ^{[7] : 15}

El primer trabajo publicado sobre hash con encadenamiento se atribuye a Arnold Dumey , quien discutió la idea de utilizar el módulo restante como primo como función hash. ^{[7] : 15} La palabra "hashing" se publicó por primera vez en un artículo de Robert Morris. ^{[8] : 126} Konheim y Weiss presentaron originalmente un análisis teórico del sondeo lineal. ^{[7] : 15}

Descripción general

Una matriz asociativa almacena un conjunto de pares (clave, valor) y permite la inserción, eliminación y búsqueda, con la restricción de claves únicas . En la implementación de la tabla hash de matrices asociativas, una matriz de longitud se llena parcialmente con elementos, donde . Un valor se almacena en una ubicación de índice , donde hay una función hash y . ^{[7] : 2} Bajo suposiciones razonables, las tablas hash tienen mejores límites de complejidad temporal en las operaciones de búsqueda, eliminación e inserción en comparación con los árboles de búsqueda binarios autoequilibrados . ^{[7] : 1} ${\displaystyle A}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m\geq n}$ ${\displaystyle x}$ ${\displaystyle A[h(x)]}$ ${\displaystyle h}$ ${\displaystyle h(x)<m}$

Las tablas hash también se usan comúnmente para implementar conjuntos, omitiendo el valor almacenado para cada clave y simplemente rastreando si la clave está presente. ^{[7] : 1}

Factor de carga

Un factor de carga es una estadística crítica de una tabla hash y se define de la siguiente manera: ^[1] ${\displaystyle \alpha }$

$${\displaystyle {\text{load factor}}\ (\alpha )={\frac {n}{m}},}$$

• ${\displaystyle n}$es el número de entradas ocupadas en la tabla hash.
• ${\displaystyle m}$es el número de cubos.

El rendimiento de la tabla hash se deteriora en relación con el factor de carga . ^{[7] : 2} ${\displaystyle \alpha }$

Para mantener un buen rendimiento, el software se asegura de que el factor de carga nunca exceda una constante . ^[9] ${\displaystyle \alpha }$ ${\displaystyle \alpha _{\max }}$

Por lo tanto, una tabla hash cambia de tamaño o se repite cada vez que el factor de carga alcanza . ^[9] ${\displaystyle \alpha }$ ${\displaystyle \alpha _{\max }}$

También se cambia el tamaño de una tabla si el factor de carga cae por debajo de . ^[9] ${\displaystyle \alpha _{\max }/4}$

Factor de carga para encadenamiento separado

Con tablas hash de encadenamiento separadas, cada ranura de la matriz de depósitos almacena un puntero a una lista o matriz de datos. ^[10]

Las tablas hash de encadenamiento separadas sufren una disminución gradual del rendimiento a medida que crece el factor de carga, y no hay un punto fijo más allá del cual sea absolutamente necesario cambiar el tamaño. ^[9]

Con encadenamiento separado, el valor que proporciona el mejor rendimiento suele estar entre 1 y 3. ^[9] ${\displaystyle \alpha _{\max }}$

Factor de carga para direccionamiento abierto

Con direccionamiento abierto, cada ranura del conjunto de depósitos contiene exactamente un elemento. Por lo tanto, una tabla hash con direcciones abiertas no puede tener un factor de carga mayor que 1. ^[10]

El rendimiento del direccionamiento abierto se vuelve muy malo cuando el factor de carga se acerca a 1. ^[9]

Por lo tanto, una tabla hash que utiliza direccionamiento abierto debe cambiarse de tamaño o repetirse si el factor de carga se aproxima a 1. ^[9] ${\displaystyle \alpha }$

Con direccionamiento abierto, las cifras aceptables del factor de carga máximo deben oscilar entre 0,6 y 0,75. ^{[11] [12] : 110} ${\displaystyle \alpha _{\max }}$

Función hash

Una función hash asigna el universo de claves a índices de matriz o espacios dentro de la tabla para cada lugar y . Las implementaciones convencionales de funciones hash se basan en la suposición del universo entero de que todos los elementos de la tabla provienen del universo , donde la longitud de bits está confinada dentro del tamaño de palabra de una arquitectura de computadora . ^{[7] : 2} ${\displaystyle h}$ ${\displaystyle U}$ ${\displaystyle h:U\rightarrow \{0,...,m-1\}}$ ${\displaystyle h(x)\in {0,...,m-1}}$ ${\displaystyle x\in S}$ ${\displaystyle m<n}$ ${\displaystyle U=\{0,...,u-1\}}$ ${\displaystyle u}$

Una función hash perfecta se define como una función inyectiva tal que cada elemento en se asigna a un valor único en . ^{[13] [14]} Se puede crear una función hash perfecta si se conocen todas las claves de antemano. ^[13] ${\displaystyle h}$ ${\displaystyle x}$ ${\displaystyle S}$ ${\displaystyle {0,...,m-1}}$

Suposición de universo entero

Los esquemas de hash utilizados en el supuesto de universo entero incluyen hash por división, hash por multiplicación, hash universal , hash perfecto dinámico y hash perfecto estático . ^{[7] : 2} Sin embargo, el hash por división es el esquema comúnmente utilizado. ^{[15] : 264  [12] : 110}

Hashing por división

El esquema en hash por división es el siguiente: ^{[7] : 2}

$${\displaystyle h(x)\ =\ M\,{\bmod {\,}}m}$$

${\displaystyle M}$ ${\displaystyle x\in S}$ ${\displaystyle m}$

Hashing por multiplicación

El esquema de hash por multiplicación es el siguiente: ^{[7] : 2–3}

$${\displaystyle h(x)=\lfloor m{\bigl (}(MA){\bmod {1}}{\bigr )}\rfloor }$$

constante de valor real^{[7] : 2–3}Donald Knuthproporción áurea^{[7] : 3} ${\displaystyle A}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle A}$

Elegir una función hash

La distribución uniforme de los valores hash es un requisito fundamental de una función hash. Una distribución no uniforme aumenta el número de colisiones y el coste de resolverlas. A veces es difícil garantizar la uniformidad mediante el diseño, pero se puede evaluar empíricamente mediante pruebas estadísticas, por ejemplo, la prueba de chi-cuadrado de Pearson para distribuciones uniformes discretas. ^{[16] [17]}

La distribución debe ser uniforme solo para los tamaños de tabla que aparecen en la aplicación. En particular, si se utiliza el cambio de tamaño dinámico con la duplicación exacta y la 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 hash prefieren que el tamaño sea un número primo . ^[18]

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. Esta 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 tiene un comportamiento de agrupación particularmente pobre. ^{[18] [4]}

El hash independiente de K ofrece una forma de demostrar que una determinada función hash no tiene conjuntos de claves incorrectos para un tipo determinado de tabla hash. Se conocen varios resultados de independencia K para esquemas de resolución de colisiones, como el sondeo lineal y el hash cuco. Dado que la independencia K puede demostrar que una función hash funciona, uno puede concentrarse en encontrar la función hash más rápida posible. ^[19]

Resolución de colisiones

Un algoritmo de búsqueda que utiliza hash consta de dos partes. La primera parte es calcular una función hash que transforma la clave de búsqueda en un índice de matriz . El caso ideal es tal que no haya dos claves de búsqueda que lleguen al mismo índice de matriz. Sin embargo, este no es siempre el caso y es imposible garantizarlo en el caso de datos proporcionados que no se ven. ^{[20] : 515} Por lo tanto, la segunda parte del algoritmo es la resolución de colisiones. Los dos métodos comunes para la resolución de colisiones son el encadenamiento separado y el direccionamiento abierto. ^{[6] : 458}

Encadenamiento separado

Colisión de hash resuelta mediante encadenamiento separado

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

En el encadenamiento separado, el proceso implica crear una lista vinculada con un par clave-valor para cada índice de matriz de búsqueda. Los elementos en colisión se encadenan a través de una única lista vinculada, que se puede recorrer para acceder al elemento con una clave de búsqueda única. ^{[6] : 464} La resolución de colisiones mediante el encadenamiento con una lista vinculada es un método común de implementación de tablas hash. Sea y la tabla hash y el nodo respectivamente, la operación implica la siguiente: ^{[15] : 258} ${\displaystyle T}$ ${\displaystyle x}$

Chained-Hash-Insert( T , k ) inserta  x  al principio de la lista enlazada  T [ h ( k )]Chained-Hash-Search( T , k ) busca un elemento con clave  k  en la lista enlazada  T [ h ( k )]Chained-Hash-Delete ( T , k ) elimina  x  de la lista vinculada  T [ h ( k )]

Si el elemento es comparable numérica o léxicamente y se inserta en la lista manteniendo el orden total , las búsquedas fallidas se terminan más rápidamente. ^{[20] : 520–521}

Otras estructuras de datos para encadenamiento separado

Si las claves están ordenadas , podría ser eficaz utilizar conceptos " autoorganizados ", como el uso de un árbol de búsqueda binario autoequilibrado , mediante el cual se podría reducir el peor de los casos teóricos , aunque introduce complejidades adicionales. ^{[20] : 521} ${\displaystyle O(\log {n})}$

En el hashing perfecto dinámico , se utilizan tablas hash de dos niveles para reducir la complejidad de la búsqueda y garantizarla en el peor de los casos. En esta técnica, los depósitos de entradas se organizan como tablas hash perfectas con ranuras que proporcionan un tiempo de búsqueda constante en el peor de los casos y un tiempo amortizado bajo para la inserción. ^[21] Un estudio muestra que el encadenamiento separado basado en matrices tiene un 97% más de rendimiento en comparación con el método estándar de lista vinculada bajo carga pesada. ^{[22] : 99} ${\displaystyle O(1)}$ ${\displaystyle k}$ ${\displaystyle k^{2}}$

Técnicas como el uso de árboles de fusión para cada segmento también dan como resultado un tiempo constante para todas las operaciones con una alta probabilidad. ^[23]

Almacenamiento en caché y localidad de referencia.

La lista enlazada de la implementación de encadenamiento separado puede no ser consciente de la caché debido a la localidad espacial ( localidad de referencia ) cuando los nodos de la lista enlazada están dispersos en la memoria, por lo que el recorrido de la lista durante la inserción y la búsqueda puede implicar ineficiencias en la caché de la CPU . ^{[22] : 91}

En las variantes de resolución de colisiones que tienen en cuenta el caché mediante encadenamiento separado, se utiliza una matriz dinámica que se considera más compatible con la caché en el lugar donde generalmente se implementa una lista vinculada o árboles de búsqueda binarios autoequilibrados, ya que el patrón de asignación contigua de la matriz podría ser explotado por captadores previos de caché de hardware , como el búfer de búsqueda de traducción , lo que resultaría en una reducción del tiempo de acceso y el consumo de memoria. ^{[24] [25] [26]}

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 aun así chocó con "Sandra Dee", que previamente había chocado con "John Smith".

Este gráfico compara el número promedio de errores de caché de CPU necesarios para buscar elementos en tablas hash grandes (que superan con creces el tamaño del caché) con encadenamiento y 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 es otra técnica de resolución de colisiones en la que cada registro de entrada se almacena en la propia matriz del depósito y la resolución hash se realiza mediante sondeo . Cuando es necesario insertar una nueva entrada, se examinan los depósitos, comenzando con la ranura hash y avanzando en alguna 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 una búsqueda fallida. ^[27]

Las secuencias de sondas bien conocidas incluyen:

• Sondeo lineal , en el que el intervalo entre sondeos es fijo (normalmente 1). ^[28]
• Sondeo cuadrático , en el que el intervalo entre sondeos aumenta sumando las salidas sucesivas de un polinomio cuadrático al valor dado por el cálculo hash original. ^{[29] : 272}
• Doble hash , en el que el intervalo entre sondas se calcula mediante una función hash secundaria. ^{[29] : 272–273}

El rendimiento del direccionamiento abierto puede ser más lento en comparación con el encadenamiento separado, ya que la secuencia de sondeo aumenta cuando el factor de carga se acerca a 1. ^{[9] [22] : 93} El sondeo da como resultado un bucle infinito si el factor de carga alcanza 1, en el caso de una mesa completamente llena. ^{[6] : 471} El costo promedio del sondeo lineal depende de la capacidad de la función hash para distribuir los elementos uniformemente en toda la tabla para evitar la agrupación , ya que la formación de agrupaciones daría como resultado un mayor tiempo de búsqueda. ^{[6] : 472} ${\displaystyle \alpha }$

Almacenamiento en caché y localidad de referencia.

Dado que las ranuras están ubicadas en ubicaciones sucesivas, el sondeo lineal podría conducir a una mejor utilización de la caché de la CPU debido a la localidad de las referencias, lo que resulta en una latencia de memoria reducida . ^[28]

Otras técnicas de resolución de colisiones basadas en direccionamiento abierto

hash fusionado

El hashing fusionado es un híbrido de encadenamiento separado y direccionamiento abierto en el que los depósitos o nodos se vinculan dentro de la tabla. ^{[30] : 6–8} El algoritmo es ideal para la asignación de memoria fija . ^{[30] : 4} La colisión en el hash fusionado se resuelve identificando la ranura vacía indexada más grande en la tabla hash, luego el valor en colisión se inserta en esa ranura. El depósito también está vinculado a la ranura del nodo insertado que contiene su dirección hash de colisión. ^{[30] : 8}

hashing de cuco

El hashing cuco es una forma de técnica de resolución de colisiones de direccionamiento abierto que garantiza una complejidad de búsqueda en el peor de los casos y un tiempo amortizado constante para las inserciones. La colisión se resuelve manteniendo dos tablas hash, cada una con su propia función hash, y la ranura colisionada se reemplaza con el elemento dado, y el elemento ocupado de la ranura se desplaza a la otra tabla hash. El proceso continúa hasta que cada llave tiene su propio lugar en los cubos vacíos de las mesas; Si el procedimiento entra en un bucle infinito , que se identifica manteniendo un contador de bucle de umbral, ambas tablas hash se repiten con funciones hash más nuevas y el procedimiento continúa. ^{[31] : 124-125} ${\displaystyle O(1)}$

hash de rayuela

El hashing Hopscotch es un algoritmo abierto basado en direccionamiento que combina los elementos del hash cuco , el sondeo lineal y el encadenamiento a través de la noción de una vecindad de depósitos: los depósitos subsiguientes alrededor de cualquier depósito ocupado determinado, también llamado depósito "virtual". ^{[32] : 351–352} El algoritmo está diseñado para ofrecer un mejor rendimiento cuando el factor de carga de la tabla hash crece más allá del 90%; también proporciona un alto rendimiento en configuraciones concurrentes , por lo que es muy adecuado para implementar tablas hash concurrentes de tamaño variable . ^{[32] : 350} La característica de vecindad del hash de rayuela garantiza una propiedad en la que el costo de encontrar el elemento deseado en cualquier depósito determinado dentro de la vecindad es muy cercano al costo de encontrarlo en el propio depósito; el algoritmo intenta ser un elemento en su vecindario, con un posible costo involucrado en el desplazamiento de otros elementos. ^{[32] : 352}

Cada depósito dentro de la tabla hash incluye una "información de salto" adicional: una matriz de bits H para indicar la distancia relativa del elemento que originalmente se incluyó en el depósito virtual actual dentro de las entradas H -1. ^{[32] : 352} Sea y la clave que se insertará y el depósito al que se aplicará el hash de la clave, respectivamente; En el procedimiento de inserción intervienen varios casos en los que se garantiza la propiedad de vecindad del algoritmo: ^{[32] : 352–353} si está vacío, el elemento se inserta y el bit más a la izquierda del mapa de bits se establece en 1; si no está vacío, se utiliza un sondeo lineal para encontrar una ranura vacía en la tabla, el mapa de bits del depósito se actualiza seguido de la inserción; si la ranura vacía no está dentro del rango de la vecindad, es decir , H -1, la manipulación posterior de la matriz de bits de intercambio y de información de salto de cada depósito se realiza de acuerdo con sus propiedades invariantes de vecindad . ^{[32] : 353} ${\displaystyle k}$ ${\displaystyle Bk}$ ${\displaystyle Bk}$

Hash de Robin Hood

El hashing Robin Hood es un algoritmo de resolución de colisiones basado en direccionamiento abierto; las colisiones se resuelven favoreciendo el desplazamiento del elemento que está más lejos (o la longitud de secuencia de sonda (PSL) más larga) de su "ubicación inicial", es decir, el depósito al que se envió el elemento. ^{[33] : 12} Aunque el hash de Robin Hood no cambia el costo de búsqueda teórico , afecta significativamente la variación de la distribución de los elementos en los depósitos, ^{[34] : 2} es decir, se ocupa de la formación de grupos en la tabla hash. ^[35] Cada nodo dentro de la tabla hash que utiliza hash Robin Hood debe aumentarse para almacenar un valor PSL adicional. ^[36] Sea la clave a insertar, sea la longitud (incremental) de PSL de , sea la tabla hash y sea el índice, el procedimiento de inserción es el siguiente: ^{[33] : 12–13  [37] : 5} ${\displaystyle x}$ ${\displaystyle x.psl}$ ${\displaystyle x}$ ${\displaystyle T}$ ${\displaystyle j}$

• Si : la iteración pasa al siguiente depósito sin intentar una sonda externa. ${\displaystyle x.psl\ \leq \ T[j].psl}$
• Si : inserte el artículo en el cubo ; intercambiar con —déjalo ser ; continúe la sonda desde el primer cubo para insertar ; repita el procedimiento hasta que se inserten todos los elementos. ${\displaystyle x.psl\ >\ T[j].psl}$ ${\displaystyle x}$ ${\displaystyle j}$ ${\displaystyle x}$ ${\displaystyle T[j]}$ ${\displaystyle x'}$ ${\displaystyle j+1}$ ${\displaystyle x'}$

Cambio de tamaño dinámico

Las inserciones repetidas hacen que crezca el número de entradas en una tabla hash, lo que en consecuencia aumenta el factor de carga; Para mantener el rendimiento amortizado de las operaciones de búsqueda e inserción, se cambia el tamaño de una tabla hash dinámicamente y los elementos de las tablas se repiten en los depósitos de la nueva tabla hash, ^[9] ya que los elementos no se pueden copiar como resultado de diferentes tamaños de tabla. en valor hash diferente debido a la operación del módulo . ^[38] Si una tabla hash queda "demasiado vacía" después de eliminar algunos elementos, se puede realizar un cambio de tamaño para evitar el uso excesivo de memoria . ^[39] ${\displaystyle O(1)}$

Cambiar el tamaño moviendo todas las entradas

Generalmente, una nueva tabla hash con un tamaño que duplica el de la tabla hash original se asigna de forma privada y cada elemento de la tabla hash original se mueve a la recién asignada calculando los valores hash de los elementos seguidos de la operación de inserción. El refrito es simple, pero computacionalmente costoso. ^{[40] : 478–479}

Alternativas al refrito 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 vez, porque puede interrumpir operaciones en las que el tiempo es 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 para evitar interrupciones en el almacenamiento (generalmente al 50% del tamaño de la nueva tabla) durante el refrishing y para evitar la fragmentación de la memoria que desencadena la compactación del montón debido a la desasignación de grandes bloques de memoria causada por la antigua tabla hash. ^{[41] : 2–3} En tal caso, la operación de repetición se realiza de forma incremental mediante la extensión del bloque de memoria anterior asignado para la tabla hash anterior, de modo que los depósitos de la tabla hash permanezcan inalterados. Un enfoque común para el refrito amortizado implica mantener dos funciones hash y . El proceso de repetir los elementos de un depósito de acuerdo con la nueva función hash se denomina limpieza , que se implementa a través de un patrón de comando al encapsular las operaciones como , y a través de un contenedor de manera que cada elemento en el depósito se repite y su procedimiento involucra como sigue: ^{[41] : 3} ${\displaystyle h_{\text{old}}}$ ${\displaystyle h_{\text{new}}}$ ${\displaystyle \mathrm {Add} (\mathrm {key} )}$ ${\displaystyle \mathrm {Get} (\mathrm {key} )}$ ${\displaystyle \mathrm {Delete} (\mathrm {key} )}$ ${\displaystyle \mathrm {Lookup} (\mathrm {key} ,{\text{command}})}$

• Balde limpio . ${\displaystyle \mathrm {Table} [h_{\text{old}}(\mathrm {key} )]}$
• Balde limpio . ${\displaystyle \mathrm {Table} [h_{\text{new}}(\mathrm {key} )]}$
• El comando se ejecuta.

hash lineal

El hash lineal es una implementación de la tabla hash que permite crecimientos o reducciones dinámicas de la tabla, un segmento a la vez. ^[42]

Actuación

El rendimiento de una tabla hash depende de la capacidad de la función hash para generar números cuasi aleatorios ( ) para las entradas en la tabla hash donde , y denota la clave, el número de depósitos y la función hash tal que . Si la función hash genera lo mismo para claves distintas ( ), esto da como resultado una colisión , que se trata de varias maneras. La complejidad temporal constante ( ) de la operación en una tabla hash se presupone con la condición de que la función hash no genere índices en colisión; por tanto, el rendimiento de la tabla hash es directamente proporcional a la capacidad de la función hash elegida para dispersar los índices. ^{[43] : 1} Sin embargo, la construcción de dicha función hash es prácticamente inviable , por lo que las implementaciones dependen de técnicas de resolución de colisiones específicas de cada caso para lograr un mayor rendimiento. ^{[43] : 2} ${\displaystyle \sigma }$ ${\displaystyle K}$ ${\displaystyle n}$ ${\displaystyle h(x)}$ ${\displaystyle \sigma \ =\ h(K)\ \%\ n}$ ${\displaystyle \sigma }$ ${\displaystyle K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})}$ ${\displaystyle O(1)}$

Aplicaciones

matrices asociativas

Las tablas hash se utilizan comúnmente para implementar muchos tipos de tablas en memoria. Se utilizan para implementar matrices asociativas . ^[29]

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. ^[44]

cachés

Las tablas hash se pueden utilizar para implementar cachés , tablas de datos auxiliares que se utilizan para acelerar el acceso a los datos que se almacenan principalmente en medios más lentos. En esta aplicación, las colisiones hash se pueden manejar descartando una de las dos entradas en conflicto; generalmente borrando el elemento antiguo que está actualmente almacenado en la tabla y sobrescribiéndolo con el nuevo elemento, de modo que cada elemento en la tabla tenga un valor hash único. ^{[45] [46]}

Conjuntos

Las tablas hash se pueden utilizar en la implementación de una estructura de datos establecida , que puede almacenar valores únicos sin ningún orden en particular; set se utiliza normalmente para probar la pertenencia de un valor a la colección, en lugar de la recuperación de elementos. ^[47]

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. ^[48]

Implementaciones

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 JavaScript , un "objeto" es una colección mutable de pares clave-valor (llamados "propiedades"), donde cada clave es una cadena o un "símbolo" único garantizado; cualquier otro valor, cuando se usa como clave, primero se convierte en una cadena. Aparte de los siete tipos de datos "primitivos", cada valor en JavaScript es un objeto. ^[49] ECMAScript 2015 también agregó la Mapestructura de datos, que acepta valores arbitrarios como claves. ^[50]

C++ 11 incluye unordered_mapen su biblioteca estándar el almacenamiento de claves y valores de tipos arbitrarios . ^[51]

La función incorporada de Gomap implementa una tabla hash en forma de tipo . ^[52]

El lenguaje de programación Java incluye las colecciones HashSet, HashMap, LinkedHashSety LinkedHashMap genéricas . ^[53]

La función incorporada de Pythondict implementa una tabla hash en forma de tipo . ^[54]

La función integrada de RubyHash utiliza el modelo de direccionamiento abierto desde Ruby 2.4 en adelante. ^[55]

El lenguaje de programación Rust incluye HashMap, HashSetcomo parte de la biblioteca estándar de Rust. ^[56]

La biblioteca estándar .NETHashSet incluye y Dictionary, ^{[57] [58]} por lo que puede usarse desde lenguajes como C# y VB.NET . ^[59]

Ver también

• Filtro de floración
• hash consistente
• tabla hash distribuida
• hash extensible
• Trie mapeado de matriz hash
• Eliminación perezosa
• hash de Pearson
• FotoADN
• Algoritmo de búsqueda de cadenas Rabin-Karp
• Estructura de datos de búsqueda
• Hash estable
• Tabla hash sucinta

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. Mehlhorn, Kurt ; Sanders, Peter (2008), "4 tablas hash y matrices asociativas", Algoritmos y estructuras de datos: la caja de herramientas básica (PDF) , Springer, págs. 81–98
3. Leiserson, Charles E. (otoño de 2005). "Conferencia 13: Algoritmos amortizados, duplicación de tablas, método potencial". curso MIT 6.046J/18.410J Introducción a los Algoritmos . Archivado desde el original el 7 de agosto de 2009.
4. Knuth, Donald (1998). El arte de la programación informática . vol. 3: Clasificación y búsqueda (2ª ed.). Addison-Wesley. págs. 513–558. ISBN 978-0-201-89685-5.
5. 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. págs. 221-252. ISBN 978-0-262-53196-2.
6. Sedgewick, Robert ; Wayne, Kevin (2011). Algoritmos. vol. 1 (4 ed.). Addison-Wesley Professional - a través de la Universidad de Princeton , Departamento de Ciencias de la Computación.
7. Mehta, Dinesh P.; Sahni, Sartaj (28 de octubre de 2004). "9: Tablas hash". En Mehta, Dinesh P.; Mehta, Dinesh P.; Sahni, Sartaj (eds.). Manual de estructuras y aplicaciones de datos (1 ed.). Taylor y Francisco . doi :10.1201/9781420035179. ISBN 978-1-58488-435-4.
8. Konheim, Alan G. (21 de junio de 2010). Hashing en informática: cincuenta años de cortar y cortar en cubitos. John Wiley & Sons, Inc. doi : 10.1002/9780470630617. ISBN  9780470630617.
9. Mayers, Andrew (2008). "CS 312: Tablas hash y análisis amortizado". Universidad de Cornell , Departamento de Ciencias de la Computación. Archivado desde el original el 26 de abril de 2021 . Consultado el 26 de octubre de 2021 a través de cs.cornell.edu.
10. James S. Plank y Brad Vander Zanden. "Apuntes de la conferencia CS140 - Hashing".
11. Maurer, WD; Lewis, TG (1 de marzo de 1975). "Métodos de tabla hash". Encuestas de Computación ACM . Revista de la ACM . 1 (1): 14. doi :10.1145/356643.356645. S2CID  17874775.
12. Owolabi, Olumide (1 de febrero de 2003). "Estudios empíricos de algunas funciones hash". Tecnología de la información y software . Departamento de Matemáticas e Informática, Universidad de Port Harcourt. 45 (2): 109-112. doi :10.1016/S0950-5849(02)00174-X - vía ScienceDirect .
13. Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006). Hashing perfecto para aplicaciones de red . 2006 Simposio internacional IEEE sobre teoría de la información. págs. 2774–2778. doi :10.1109/ISIT.2006.261567. ISBN 1-4244-0505-X. S2CID  1494710.
14. Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martín (2009). "Hash, desplazar y comprimir" (PDF) . Algoritmos: ESA 2009: 17.º Simposio europeo anual, Copenhague, Dinamarca, 7 al 9 de septiembre de 2009, Actas . Apuntes de conferencias sobre informática . vol. 5757. Berlín: Springer. págs. 682–693. CiteSeerX 10.1.1.568.130 . doi :10.1007/978-3-642-04128-0_61. SEÑOR  2557794. 
15. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001). "Capítulo 11: Tablas hash". Introducción a los algoritmos (2ª ed.). Instituto de Tecnología de Massachusetts . ISBN 978-0-262-53196-2.
16. 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): 157–175. doi :10.1080/14786440009463897.
17. Plackett, Robin (1983). "Karl Pearson y la prueba de chi cuadrado". Revista estadística internacional . 51 (1): 59–72. doi :10.2307/1402731. JSTOR  1402731.
18. 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 .
19. Wegman, Mark N .; Carter, J. Lawrence (1981). "Nuevas funciones hash y su uso en autenticación e igualdad de conjuntos" (PDF) . Revista de Ciencias de la Computación y de Sistemas . 22 (3): 265–279. doi : 10.1016/0022-0000(81)90033-7 . Versión conferencia en FOCS'79 . Consultado el 9 de febrero de 2011 .
20. Donald E. Knuth (24 de abril de 1998). El arte de la programación informática: Volumen 3: Clasificación y búsqueda. Profesional de Addison-Wesley. ISBN 978-0-201-89685-5.
21. Demaine, Erik; Lind, Jeff (primavera de 2003). "Conferencia 2" (PDF) . 6.897: Estructuras de datos avanzadas. Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT . Archivado (PDF) desde el original el 15 de junio de 2010 . Consultado el 30 de junio de 2008 .
22. Askitis, Nikolas; Zobel, Justin (2005). Resolución de colisiones consciente de la caché en tablas hash de cadenas. Simposio internacional sobre procesamiento de cadenas y recuperación de información. Springer Ciencia + Medios comerciales . págs. 91-102. doi :10.1007/11575832_1. ISBN 978-3-540-29740-6.
23. Willard, Dan E. (2000). "Examen de la geometría computacional, los árboles de van Emde Boas y el hash desde la perspectiva del árbol de fusión". Revista SIAM de Computación . 29 (3): 1030–1049. doi :10.1137/S0097539797322425. SEÑOR  1740562..
24. Askitis, Nikolas; Sinha, Ranjan (2010). "Ingeniería de intentos escalables, eficientes en caché y espacio para cadenas". La revista VLDB . 17 (5): 634. doi :10.1007/s00778-010-0183-9. ISSN  1066-8888. S2CID  432572.
25. Askitis, Nikolas; Zobel, Justin (octubre de 2005). "Resolución de colisiones consciente de la caché en tablas hash de cadenas". Actas de la 12ª Conferencia Internacional, Procesamiento de cadenas y recuperación de información (SPIRE 2005) . vol. 3772/2005. págs. 91-102. doi :10.1007/11575832_11. ISBN 978-3-540-29740-6.
26. Askitis, Nikolas (2009). "Tablas hash rápidas y compactas para claves enteras" (PDF) . Actas de la 32ª Conferencia de Informática de Australasia (ACSC 2009) . vol. 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 .
27. Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Estructuras de datos usando C. Prentice Hall. págs. 456–461, pág. 472.ISBN​ 978-0-13-199746-2.
28. Pagh, Rasmus ; Rodler, Flemming Friche (2001). "Hashing de cuco". Algoritmos: ESA 2001 . Apuntes de conferencias sobre informática. vol. 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.
29. Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2001), "11 tablas hash", Introducción a los algoritmos (2ª ed.), MIT Press y McGraw-Hill , págs. 221-252, ISBN 0-262-03293-7.
30. Vitter, Jeffery S.; Chen, Wen-Chin (1987). "El diseño y análisis del hash fusionado ". Nueva York, Estados Unidos: Oxford University Press . ISBN 978-0-19-504182-8– vía Archive.org .
31. Pagh, Rasmus ; Rodler, Flemming Friche (2001). "Hashing de cuco". Algoritmos: ESA 2001 . Apuntes de conferencias sobre informática. vol. 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.
32. Herlihy, Maurice; Shavit, Nir; Tzafrir, Morán (2008). Hashing de rayuela. Simposio Internacional sobre Computación Distribuida. Computación distribuída. vol. 5218. Berlín, Heidelberg: Springer Publishing . págs. 350–364. doi :10.1007/978-3-540-87779-0_24. ISBN 978-3-540-87778-3– vía Enlace Springer.
33. Celis, Pedro (1986). Hashing de Robin Hood (PDF) . Ontario, Canadá: Universidad de Waterloo , Departamento de Ciencias de la Computación. ISBN 031529700X. OCLC  14083698. Archivado (PDF) desde el original el 1 de noviembre de 2021 . Consultado el 2 de noviembre de 2021 .
34. Poblete, PV; Viola, A. (14 de agosto de 2018). "Análisis de Robin Hood y otros algoritmos hash bajo el modelo de sondeo aleatorio, con y sin eliminaciones". Combinatoria, Probabilidad y Computación . Prensa de la Universidad de Cambridge . 28 (4): 600–617. doi :10.1017/S0963548318000408. ISSN  1469-2163. S2CID  125374363 . Consultado el 1 de noviembre de 2021 a través de Cambridge Core.
35. Clarkson, Michael (2014). "Conferencia 13: Tablas hash". Universidad de Cornell , Departamento de Ciencias de la Computación. Archivado desde el original el 7 de octubre de 2021 . Consultado el 1 de noviembre de 2021 a través de cs.cornell.edu.
36. Gries, David (2017). "JavaHyperText y estructura de datos: Robin Hood Hashing" (PDF) . Universidad de Cornell , Departamento de Ciencias de la Computación. Archivado (PDF) desde el original el 26 de abril de 2021 . Consultado el 2 de noviembre de 2021 a través de cs.cornell.edu.
37. Celis, Pedro (28 de marzo de 1988). Hashing Robin Hood externo (PDF) (Reporte técnico). Bloomington, Indiana: Universidad de Indiana , Departamento de Ciencias de la Computación. 246. Archivado (PDF) desde el original el 3 de noviembre de 2021 . Consultado el 2 de noviembre de 2021 .
38. Goddard, Wayne (2021). "Capítulo C5: Tablas Hash" (PDF) . Universidad de Clemson . págs. 15-16 . Consultado el 4 de diciembre de 2023 .
39. Devadas, Srini; Demaine, Erik (25 de febrero de 2011). "Introducción a los algoritmos: cambio de tamaño de las tablas hash" (PDF) . Instituto de Tecnología de Massachusetts , Departamento de Ciencias de la Computación. Archivado (PDF) desde el original el 7 de mayo de 2021 . Consultado el 9 de noviembre de 2021 a través de MIT OpenCourseWare .
40. Thareja, Reema (13 de octubre de 2018). "Hashing y colisión". Estructuras de datos utilizando C (2 ed.). Prensa de la Universidad de Oxford . ISBN 9780198099307.
41. Friedman, Scott; Krishnan, Anand; Leidefrost, Nicholas (18 de marzo de 2003). "Tablas hash para sistemas integrados y en tiempo real" (PDF) . Toda la investigación en ingeniería y ciencias de la computación . Universidad de Washington en San Luis . doi :10.7936/K7WD3XXV. Archivado (PDF) desde el original el 9 de junio de 2021 . Consultado el 9 de noviembre de 2021 a través del Departamento de Ciencias de la Computación de la Universidad Northwestern .
42. Litwin, Witold (1980). "Hashing lineal: una nueva herramienta para direccionar archivos y tablas" (PDF) . Proc. VI Congreso sobre Bases de Datos de Muy Gran Tamaño . Universidad de Carnegie mellon . págs. 212-223. Archivado (PDF) desde el original el 6 de mayo de 2021 . Consultado el 10 de noviembre de 2021 a través de cs.cmu.edu.
43. Dijk, Tom Van (2010). "Análisis y mejora del rendimiento de la tabla hash" (PDF) . Países Bajos : Universidad de Twente . Archivado (PDF) desde el original el 6 de noviembre de 2021 . Consultado el 31 de diciembre de 2021 .
44. Lech Banachowski. "Índices y clasificación externa". pl:Polsko-Japońska Akademia Technik Komputerowych. Archivado desde el original el 26 de marzo de 2022 . Consultado el 26 de marzo de 2022 .
45. Zhong, Liang; Zheng, Xueqian; Liu, Yong; Wang, Mengting; Cao, Yang (febrero de 2020). "Maximización de la tasa de aciertos de caché en comunicaciones de dispositivo a dispositivo superpuestas a redes celulares". Comunicaciones de China . 17 (2): 232–238. doi :10.23919/jcc.2020.02.018. ISSN  1673-5447. S2CID  212649328.
46. Bottommley, James (1 de enero de 2004). "Comprensión del almacenamiento en caché". Diario de Linux . Archivado desde el original el 4 de diciembre de 2020 . Consultado el 16 de abril de 2022 .
47. Jill Seaman (2014). "Establecer y tablas hash" (PDF) . Universidad Estatal de Texas . Archivado desde el original el 1 de abril de 2022 . Consultado el 26 de marzo de 2022 .{{cite web}}: Mantenimiento CS1: bot: estado de la URL original desconocido ( enlace )
48. "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 .
49. "Tipos de datos y estructuras de datos de JavaScript: JavaScript | MDN". desarrollador.mozilla.org . Consultado el 24 de julio de 2022 .
50. "Mapa - JavaScript | MDN". desarrollador.mozilla.org . 20 de junio de 2023 . Consultado el 15 de julio de 2023 .
51. "Lenguaje de programación C++ - Especificación técnica" (PDF) . Organización Internacional de Normalización . págs. 812–813. Archivado desde el original (PDF) el 21 de enero de 2022 . Consultado el 8 de febrero de 2022 .
52. "La especificación del lenguaje de programación Go". ir.dev . Consultado el 1 de enero de 2023 .
53. "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 .
54. Zhang, Juan; Jia, Yunwei (2020). "Optimización del refrito de Redis basada en aprendizaje automático". Revista de Física: Serie de conferencias . 1453 (1): 3. Código bibliográfico : 2020JPhCS1453a2048Z. doi : 10.1088/1742-6596/1453/1/012048 . S2CID  215943738.
55. 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 .
56. "doc.rust-lang.org". Archivado desde el original el 8 de diciembre de 2022 . Consultado el 14 de diciembre de 2022 .prueba
57. "Clase HashSet (System.Collections.Generic)". aprender.microsoft.com . Consultado el 1 de julio de 2023 .
58. dotnet-bot. "Clase de diccionario (System.Colections.Generic)". aprender.microsoft.com . Consultado el 16 de enero de 2024 .
59. "Ejemplo de VB.NET HashSet". Perlas de red de puntos .

Otras lecturas

• Tamasia, 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). "Seleccionar un algoritmo hash". Software: práctica y experiencia . 20 (2): 209–224. doi :10.1002/spe.4380200207. hdl : 10092/9691 . S2CID  12854386.

enlaces externos

• Entrada NIST en tablas hash
• Estructuras de datos abiertas – Capítulo 5 – Tablas hash, Pat Morin
• Introducción a los algoritmos del MIT: vídeo de la conferencia Hashing 1 MIT OCW
• Introducción a los algoritmos del MIT: video de la conferencia Hashing 2 MIT OCW