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 .
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
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
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
Un factor de carga es una estadística crítica de una tabla hash y se define de la siguiente manera: [1]
El rendimiento de la tabla hash se deteriora en relación con el factor de carga . [7] : 2
Para mantener un buen rendimiento, el software se asegura de que el factor de carga nunca exceda una constante . [9]
Por lo tanto, una tabla hash cambia de tamaño o se repite cada vez que el factor de carga alcanza . [9]
También se cambia el tamaño de una tabla si el factor de carga cae por debajo de . [9]
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]
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]
Con direccionamiento abierto, las cifras aceptables del factor de carga máximo deben oscilar entre 0,6 y 0,75. [11] [12] : 110
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
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]
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
El esquema en hash por división es el siguiente: [7] : 2
El esquema de hash por multiplicación es el siguiente: [7] : 2–3
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]
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
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
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
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
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
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]
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]
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:
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
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]
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
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
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
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
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]
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
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
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]
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
Las tablas hash se utilizan comúnmente para implementar muchos tipos de tablas en memoria. Se utilizan para implementar matrices asociativas . [29]
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]
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]
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]
Una tabla de transposición a una tabla Hash compleja que almacena información sobre cada sección que se ha buscado. [48]
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 Map
estructura de datos, que acepta valores arbitrarios como claves. [50]
C++ 11 incluye unordered_map
en 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
, LinkedHashSet
y 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
, HashSet
como 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]
{{cite web}}
: Mantenimiento CS1: bot: estado de la URL original desconocido ( enlace )