Hispanopedia Wiki
Articulo de referencia

Tabla hash

\n {{cite book\n |last1=Cormen |first1=Thomas H. |author1-link=Thomas H. Cormen\n |last2=Leiserson |first2=Charles E. |author2-link=Charles E. Leiserson\n |last3=Rivest |first3=...

Hispanopedia WikiContenido en espanolLectura gratuita

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

En informática , una tabla hash es una estructura de datos que implementa un array asociativo , también llamado diccionario o simplemente mapa ; un array asociativo es un tipo de dato abstracto que asigna claves a valores . [ 3 ] Una tabla hash utiliza una función hash para calcular un índice , también llamado código hash , en un array de cubetas o ranuras , desde donde se puede encontrar el valor deseado. Durante la búsqueda, la clave se hashea y el hash resultante indica dónde se almacena el valor correspondiente. Un mapa implementado por una tabla hash se llama mapa hash .

La mayoría de los diseños de tablas hash emplean una función hash imperfecta . Por lo tanto, las colisiones de hash , donde la función hash genera el mismo índice para más de una clave, generalmente deben manejarse de alguna manera. Las estrategias comunes para manejar colisiones de hash incluyen el encadenamiento, que almacena múltiples elementos en la misma ranura usando listas enlazadas, y el direccionamiento abierto, que busca la siguiente ranura disponible según una secuencia de sondeo. [ 4 ]

En una tabla hash bien dimensionada, la complejidad temporal promedio 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 , con un costo promedio constante amortizado por operación. [ 5 ] [ 4 ] : 513–558 [ 6 ]

El hashing es un ejemplo de compensación entre espacio y tiempo . Si la memoria es infinita, la clave completa se puede usar directamente como índice para localizar su valor con un solo 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 usar una búsqueda binaria o lineal para recuperar el elemento. [ 7 ] : 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 . [ 8 ] Muchos lenguajes de programación proporcionan estructuras de tablas hash integradas, como los diccionarios de Python , HashMap de Java , unordered_map de C++ y los mapas de Go , que abstraen la complejidad del hashing para el programador. [ 9 ]

Historia

La idea del hashing surgió de forma independiente en diferentes lugares. En enero de 1953, Hans Peter Luhn escribió un memorándum interno de IBM que utilizaba hashing con encadenamiento. El primer ejemplo de direccionamiento abierto fue propuesto por AD Linh, basándose en el memorándum de Luhn. [ 4 ] : 547 Casi al mismo tiempo, Gene Amdahl , Elaine M. McGraw , Nathaniel Rochester y Arthur Samuel de IBM Research implementaron el hashing para el ensamblador IBM 701. [ 10 ] : 124 El direccionamiento abierto con sondeo lineal se atribuye a Amdahl, aunque Andrey Ershov tuvo la misma idea de forma independiente. [ 10 ] : 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. [ 11 ] : 15

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

Descripción general

Un array asociativo 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 tablas hash de arrays asociativos, un arrayA{\displaystyle A}de longitudmetro{\displaystyle m}está parcialmente lleno denorte{\displaystyle n}elementos, dondemetro≥norte{\displaystyle m\geq n}Una claveincógnita{\displaystyle x}se aplica una función hashh{\displaystyle h}para calcular una ubicación de índiceA[h(incógnita)]{\displaystyle A[h(x)]}en la tabla hash, dondeh(incógnita)<metro{\displaystyle h(x)<m}La eficiencia de una tabla hash depende del factor de carga, definido como la relación entre el número de elementos almacenados y el número de ranuras disponibles; generalmente, los factores de carga más bajos producen operaciones más rápidas. [ 12 ] En este índice, se almacenan tanto la clave como su valor asociado. Almacenar la clave junto con el valor garantiza que las búsquedas puedan verificar la clave en el índice para recuperar el valor correcto, incluso en presencia de colisiones. Bajo supuestos 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 binaria autoequilibrados . [ 11 ] : 1

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

Factor de carga

Un factor de cargaα{\displaystyle \alpha }es una estadística crítica de una tabla hash y se define de la siguiente manera: [ 2 ]factor de carga (α)=nortemetro,{\displaystyle {\text{factor de carga}}\ (\alpha )={\frac {n}{m}},} dónde

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

El rendimiento de la tabla hash se deteriora en relación con el factor de carga.α{\displaystyle \alpha }. [ 11 ] : 2 En el límite de grandemetro{\displaystyle m}ynorte{\displaystyle n}, cada cubo estadísticamente tiene una distribución de Poisson con esperanzaλ=α{\displaystyle \lambda =\alpha }para una función hash idealmente aleatoria .

El software normalmente garantiza que el factor de cargaα{\displaystyle \alpha }permanece por debajo de cierta constante,αmáximo{\displaystyle \alpha _{\max }}Esto ayuda a mantener un buen rendimiento. Por lo tanto, un enfoque común es redimensionar o "recalcular" la tabla hash siempre que el factor de cargaα{\displaystyle \alpha }alcanzaαmáximo{\displaystyle \alpha _{\max }}. De manera similar, la tabla también puede redimensionarse si el factor de carga cae por debajo deαmáximo/4{\displaystyle \alpha _{\max }/4}. [ 13 ]

Factor de carga para encadenamiento separado

Con tablas hash encadenadas separadas, cada ranura del arreglo de cubetas almacena un puntero a una lista o arreglo de datos. [ 14 ]

Las tablas hash de encadenamiento separadas sufren una disminución gradual del rendimiento a medida que aumenta el factor de carga, y no existe un punto fijo más allá del cual sea absolutamente necesario redimensionarlas. [ 13 ]

Con encadenamiento separado, el valor deαmáximo{\displaystyle \alpha _{\max }}El valor que ofrece el mejor rendimiento suele estar entre 1 y 3. [ 13 ]

Factor de carga para direccionamiento abierto

Con el direccionamiento abierto, cada ranura del arreglo de cubetas contiene exactamente un elemento. Por lo tanto, una tabla hash con direccionamiento abierto no puede tener un factor de carga mayor que 1. [ 14 ]

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

Por lo tanto, una tabla hash que utiliza direccionamiento abierto debe redimensionarse o recalcularse si el factor de cargaα{\displaystyle \alpha }aproximaciones 1. [ 13 ]

Con direccionamiento abierto, cifras aceptables de factor de carga máximoαmáximo{\displaystyle \alpha _{\max }}debería oscilar entre 0,6 y 0,75. [ 15 ] [ 16 ] : 110

Función hash

Una función hashh:U→{0,...,metro−1}{\displaystyle h:U\rightarrow \{0,...,m-1\}}mapea el universoU{\displaystyle U}de claves a índices o ranuras dentro de la tabla, es decir,h(incógnita)∈{0,...,metro−1}{\displaystyle h(x)\in \{0,...,m-1\}}paraincógnita∈U{\displaystyle x\in U}Las implementaciones convencionales de las funciones hash se basan en la suposición del universo entero de que todos los elementos de la tabla provienen del universo entero.U={0,...,tú−1}{\displaystyle U=\{0,...,u-1\}}, donde la longitud de bits detú{\displaystyle u}está confinado dentro del tamaño de palabra de una arquitectura de computadora . [ 11 ] : 2

Una función hashh{\displaystyle h}Se dice que es perfecto para un conjunto determinado.S{\displaystyle S}si es inyectable enS{\displaystyle S}, es decir, si cada elementoincógnita∈S{\displaystyle x\in S}asigna a un valor diferente en0,...,metro−1{\displaystyle {0,...,m-1}}. [ 17 ] [ 18 ] Se puede crear una función hash perfecta si todas las claves se conocen de antemano. [ 17 ]

Suposición de universo entero

Los esquemas de hash utilizados en la suposición del universo entero incluyen el hash por división, el hash por multiplicación, el hash universal , el hash perfecto dinámico y el hash perfecto estático . [ 11 ] : 2 Sin embargo, el hash por división es el esquema más utilizado. [ 19 ] : 264 [ 16 ] : 110

Hashing por división

El esquema de hash por división es el siguiente: [ 11 ] : 2h(incógnita) = incógnitamodmetro,{\displaystyle h(x)\ =\ x\,{\bmod {\,}}m,} dóndeh(incógnita){\displaystyle h(x)}es el valor hash deincógnita∈S{\displaystyle x\in S}ymetro{\displaystyle m}es el tamaño de la mesa.

Hashing por multiplicación

El esquema de hash por multiplicación es el siguiente: [ 11 ] : 2–3h(incógnita)=⌊metro((incógnitaA)mod1)⌋{\displaystyle h(x)=\lfloor m{\bigl (}(xA){\bmod {1}}{\bigr )}\rfloor } DóndeA{\displaystyle A}es una constante real no entera ymetro{\displaystyle m}es el tamaño de la tabla. Una ventaja del hash por multiplicación es que elmetro{\displaystyle m}no es crítico. [ 11 ] : 2–3 Aunque cualquier valorA{\displaystyle A}produce una función hash, Donald Knuth sugiere usar la proporción áurea . [ 11 ] : 3

Hash de cadenas

Comúnmente se usa una cadena como clave para la función hash. La tercera edición de The C++ Programming Language describe una función hash simple en la que un entero sin signo que inicialmente es cero se desplaza repetidamente un bit a la izquierda y luego se combina con el valor entero del siguiente carácter. Este valor hash se toma luego módulo el tamaño de la tabla. [ 20 ] Si el desplazamiento a la izquierda no es circular, entonces la longitud de la cadena debe ser al menos ocho bits menor que el tamaño del entero sin signo en bits. Otra forma común de convertir una cadena en un entero es con una función hash rodante polinómica .

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, resulta difícil garantizar la uniformidad mediante el diseño, pero puede evaluarse empíricamente utilizando pruebas estadísticas, por ejemplo, una prueba de chi-cuadrado de Pearson para distribuciones uniformes discretas. [ 21 ] [ 22 ]

La distribución debe ser uniforme únicamente para los tamaños de tabla que se dan en la aplicación. En particular, si se utiliza el redimensionamiento dinámico con duplicación y reducción a la mitad exactas del tamaño de la tabla, la función hash debe ser uniforme solo cuando el tamaño sea una potencia de dos . En este caso, 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 . [ 23 ]

Para esquemas de direccionamiento abierto , la función hash también debe evitar las rachas , es decir, la asignación de dos o más claves a ranuras consecutivas. Estas rachas pueden provocar un aumento desorbitado del coste de búsqueda, incluso si el factor de carga es bajo y las colisiones son poco frecuentes. Se afirma que la popular función hash multiplicativa tiene un comportamiento particularmente deficiente en cuanto a rachas. [ 23 ] [ 4 ]

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

Resolución de colisiones

Un algoritmo de búsqueda que utiliza funciones hash consta de dos partes. La primera parte consiste en calcular una función hash que transforma la clave de búsqueda en un índice de matriz . Lo ideal es que dos claves de búsqueda no generen el mismo índice de matriz. Sin embargo, esto no siempre ocurre y es imposible de garantizar para datos desconocidos. [ 4 ] : ​​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. [ 7 ] : 458

encadenamiento separado

La colisión de hash se resuelve mediante encadenamiento separado.
Colisión de hash por encadenamiento separado con registros de cabecera en el array de cubetas

En el encadenamiento separado, el proceso implica la construcción de una lista enlazada con pares clave-valor para cada índice de la matriz de búsqueda. Los elementos que colisionan se encadenan a través de una única lista enlazada, que se puede recorrer para acceder al elemento con una clave de búsqueda única. [ 7 ] : 464 La resolución de colisiones mediante encadenamiento con lista enlazada es un método común de implementación de tablas hash. SeaT{\displaystyle T}yincógnita{\displaystyle x}Sea la tabla hash y el nodo respectivamente, la operación implica lo siguiente: [ 19 ] : 258

Chained-Hash-Insert( T , k ) inserta x al principio de la lista enlazada T [ h ( k )] Búsqueda hash encadenada( 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 enlazada T [ h ( k )]

Si el elemento es comparable numérica o léxicamente , y se inserta en la lista manteniendo el orden total , se produce una finalización más rápida de las búsquedas infructuosas. [ 4 ] : 520–521

Otras estructuras de datos para encadenamiento separado

Si las claves están ordenadas , podría ser eficiente utilizar conceptos de " autoorganización " como el uso de un árbol de búsqueda binaria autoequilibrado , a través del cual el peor caso teórico podría reducirse aO(registro⁡norte){\displaystyle O(\log {n})}, aunque introduce complejidades adicionales. [ 4 ] : 521

En el hash perfecto dinámico , se utilizan tablas hash de dos niveles para reducir la complejidad de búsqueda y garantizar la precisión.O(1){\displaystyle O(1)}en el peor de los casos. En esta técnica, los cubos dek{\displaystyle k}Las entradas están organizadas como tablas hash perfectas conk2{\displaystyle k^{2}}ranuras que proporcionan un tiempo de búsqueda constante en el peor de los casos y un tiempo amortizado bajo para la inserción. [ 25 ] Un estudio muestra que el encadenamiento separado basado en matrices es un 97 % más eficiente en comparación con el método de lista enlazada estándar bajo carga pesada. [ 26 ] : 99

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

Almacenamiento en caché y localidad de referencia

La implementación de encadenamiento de listas enlazadas separadas 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 tanto, el recorrido de la lista durante la inserción y la búsqueda puede implicar ineficiencias de la caché de la CPU . [ 26 ] : 91

En variantes de resolución de colisiones con optimización de caché mediante encadenamiento separado, se utiliza una matriz dinámica que resulta más amigable con la caché en el lugar donde normalmente se implementan listas enlazadas o árboles de búsqueda binaria autoequilibrados, ya que el patrón de asignación contigua de la matriz puede ser aprovechado por los prefetchers de caché de hardware —como el búfer de búsqueda lateral de traducción— lo que resulta en un tiempo de acceso y un consumo de memoria reducidos. [ 28 ] [ 29 ] [ 30 ]

Dirección abierta

Se resolvió la colisión de hash mediante direccionamiento abierto con sondeo lineal (intervalo=1). Nótese que "Ted Baker" tiene un hash único, pero aun así colisionó con "Sandra Dee", que previamente había colisionado con "John Smith".

El direccionamiento abierto es otra técnica de resolución de colisiones en la que cada registro de entrada se almacena en el propio array de cubetas, y la resolución del hash se realiza mediante sondeo . Cuando se debe insertar una nueva entrada, se examinan las cubetas, comenzando por la ranura hash y procediendo en una secuencia de sondeo , hasta que se encuentra una ranura desocupada. Al buscar una entrada, las cubetas se escanean en la misma secuencia, hasta que se encuentra el registro objetivo o se encuentra una ranura del array sin usar, lo que indica una búsqueda fallida. [ 31 ]

Las secuencias de sonda más conocidas incluyen:

  • Sondeo lineal , en el que el intervalo entre sondas es fijo (normalmente 1). [ 32 ]
  • Sondeo cuadrático , en el que el intervalo entre sondeos se incrementa sumando las salidas sucesivas de un polinomio cuadrático al valor dado por el cálculo hash original. [ 33 ] : 272
  • Doble hash , en el que el intervalo entre sondeos se calcula mediante una función hash secundaria. [ 33 ] : 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α{\displaystyle \alpha }aproximaciones 1. [ 13 ] [ 26 ] : 93 El sondeo da como resultado un bucle infinito si el factor de carga alcanza 1, en el caso de una tabla completamente llena. [ 7 ] : 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 rachas , ya que la formación de rachas daría como resultado un mayor tiempo de búsqueda. [ 7 ] : 472

Almacenamiento en caché y localidad de referencia

Dado que las ranuras se encuentran 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 . [ 32 ]

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

Hashing coalescente

El hash coalescente es un híbrido de encadenamiento separado y direccionamiento abierto en el que los cubos o nodos se enlazan dentro de la tabla. [ 34 ] : 6–8 El algoritmo es ideal para la asignación de memoria fija . [ 34 ] : 4 La colisión en el hash coalescente se resuelve identificando la ranura vacía con el índice más alto en la tabla hash, luego el valor que colisiona se inserta en esa ranura. El cubo también se enlaza a la ranura del nodo insertado que contiene su dirección hash que colisiona. [ 34 ] : 8

Hashing de cuco

El hash Cuckoo es una forma de técnica de resolución de colisiones de direccionamiento abierto que garantizaO(1){\displaystyle O(1)}Complejidad de búsqueda en el peor de los casos y tiempo amortizado constante para las inserciones. La colisión se resuelve mediante el mantenimiento de 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 clave tenga su propio lugar en los cubos vacíos de las tablas; si el procedimiento entra en un bucle infinito —que se identifica mediante el mantenimiento de un contador de bucle umbral— ambas tablas hash se vuelven a hashear con nuevas funciones hash y el procedimiento continúa. [ 35 ] : 124–125

Rayuela

El hash Hopscotch es un algoritmo basado en direccionamiento abierto que combina elementos del hash Cuckoo , sondeo lineal y encadenamiento mediante la noción de vecindario de cubetas: las cubetas subsiguientes alrededor de cualquier cubeta ocupada, también llamada cubeta "virtual". [ 36 ] : 351–352 El algoritmo está diseñado para ofrecer un mejor rendimiento cuando el factor de carga de la tabla hash supera el 90%; también proporciona un alto rendimiento en entornos concurrentes , por lo que resulta idóneo para implementar tablas hash concurrentes redimensionables . [ 36 ] : 350 La característica de vecindario del hash Hopscotch garantiza que el coste de encontrar el elemento deseado en cualquier cubeta dentro del vecindario es muy similar al coste de encontrarlo en la propia cubeta; el algoritmo intenta colocar un elemento en su vecindario, con un posible coste asociado al desplazamiento de otros elementos. [ 36 ] : 352

Cada cubeta dentro de la tabla hash incluye una "información de salto" adicional: una matriz de bits de H bits para indicar la distancia relativa del elemento que fue originalmente hasheado en la cubeta virtual actual dentro de H − 1 entradas. [ 36 ] : 352 Let  k{\displaystyle k}yBk{\displaystyle Bk}sean la clave que se va a insertar y el cubo en el que se aplica el hash a la clave, respectivamente; en el procedimiento de inserción intervienen varios casos, de modo que se garantiza la propiedad de vecindad del algoritmo: [ 36 ] : 352–353 siBk{\displaystyle Bk}Si está vacío, se inserta el elemento y el bit más a la izquierda del mapa de bits se establece en 1; si no está vacío, se utiliza el sondeo lineal para encontrar una ranura vacía en la tabla, se actualiza el mapa de bits del cubo y se inserta; si la ranura vacía no está dentro del rango del vecindario, es decir , H  −  1, se realiza la manipulación posterior de la matriz de bits de intercambio e información de salto de cada cubo de acuerdo con sus propiedades invariantes de vecindario . [ 36 ] : 353

Robin Hood haciendo hashing

El hash 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 con la longitud de secuencia de sondeo más larga , PSL) de su "ubicación de origen", es decir, el cubo al que se le asignó el elemento mediante hash. [ 37 ] : 12 Recibe su nombre de Robin Hood , un mítico forajido heroico que robaba a los ricos para dárselo a los pobres.

Aunque el hash Robin Hood no cambia el costo de búsqueda teórico , afecta significativamente la varianza de la distribución de los elementos en los cubos, [ 38 ] : 2 es decir, lidiar con la formación de largas carreras en la tabla hash. [ 39 ] Cada nodo dentro de la tabla hash que usa el hash Robin Hood debe ser aumentado para almacenar un valor PSL adicional. [ 40 ] Seaincógnita{\displaystyle x}sea ​​la llave que se inserte,incógnita.psl{\displaystyle x{.}{\text{psl}}}sea ​​la longitud (incremental) de PSL deincógnita{\displaystyle x},T{\displaystyle T}sea ​​la tabla hash yj{\displaystyle j}Sea el índice, el procedimiento de inserción es el siguiente: [ 37 ] : 12–13 [ 41 ] : 5

  • Siincógnita.psl ≤ T[j].psl{\displaystyle x{.}{\text{psl}}\ \leq \ T[j]{.}{\text{psl}}}: la iteración pasa al siguiente cubo sin intentar una sonda externa.
  • Siincógnita.psl > T[j].psl{\displaystyle x{.}{\text{psl}}\ >\ T[j]{.}{\text{psl}}}: insertar el artículoincógnita{\displaystyle x}en el cuboj{\displaystyle j}; intercambioincógnita{\displaystyle x}conT[j]{\displaystyle T[j]}-déjalo serincógnita′{\displaystyle x'}; continuar la sondeo desde el(j+1){\displaystyle (j+1)}el cubo para insertarincógnita′{\displaystyle x'}; repita el procedimiento hasta que se hayan insertado todos los elementos.

Redimensionamiento dinámico

Las inserciones repetidas hacen que el número de entradas en una tabla hash crezca, lo que en consecuencia aumenta el factor de carga; para mantener el amortizadoO(1){\displaystyle O(1)}Para realizar las operaciones de búsqueda e inserción, una tabla hash se redimensiona dinámicamente y los elementos de las tablas se vuelven a hashear en los cubetas de la nueva tabla hash, [ 13 ] ya que los elementos no se pueden copiar, pues los diferentes tamaños de tabla dan como resultado diferentes valores hash debido a la operación de módulo . [ 42 ] Si una tabla hash se vuelve "demasiado vacía" después de eliminar algunos elementos, se puede realizar un redimensionamiento para evitar un uso excesivo de memoria . [ 43 ]

Cambiar el tamaño moviendo todas las entradas

Generalmente, se asigna de forma privada una nueva tabla hash con un tamaño que duplica el de la tabla hash original, y cada elemento de la tabla hash original se mueve a la nueva tabla hash mediante el cálculo de los valores hash de los elementos, seguido de la operación de inserción. El rehashing es sencillo, pero computacionalmente costoso. [ 44 ] : 478–479

Alternativas a la repetición de todo a la vez

Algunas implementaciones de tablas hash, especialmente en sistemas en tiempo real , no pueden permitirse el coste de ampliar la tabla hash de una sola vez, ya que esto podría interrumpir operaciones críticas en tiempo real. Si no se puede evitar el redimensionamiento dinámico, una solución consiste en realizarlo gradualmente para evitar picos de almacenamiento —normalmente al 50 % del tamaño de la nueva tabla— durante el rehashing 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. [ 45 ] : 2–3 En tal caso, la operación de rehashing se realiza de forma incremental mediante la extensión del bloque de memoria previamente asignado para la antigua tabla hash, de modo que los cubetas de la tabla hash permanezcan inalterados. Un enfoque común para el rehashing amortizado implica el mantenimiento de dos funciones hash.hviejo{\displaystyle h_{\text{old}}}yhnuevo{\displaystyle h_{\text{new}}}El proceso de re-hash de los elementos de un bucket de acuerdo con la nueva función hash se denomina limpieza , que se implementa a través del patrón de comando encapsulando operaciones comoAdd(kmiy){\displaystyle \mathrm {Add} (\mathrm {key} )},GRAMOmit(kmiy){\displaystyle \mathrm {Get} (\mathrm {key} )}yDmilmitmi(kmiy){\displaystyle \mathrm {Delete} (\mathrm {key} )}a través de unLooktúpag(kmiy,dominio){\displaystyle \mathrm {Lookup} (\mathrm {key} ,{\text{command}})}envoltorio tal que cada elemento en el cubo se vuelve a hashear y su procedimiento implica lo siguiente: [ 45 ] : 3

  • LimpioTablmi[hviejo(kmiy)]{\displaystyle \mathrm {Table} [h_{\text{old}}(\mathrm {key} )]}balde.
  • LimpioTablmi[hnuevo(kmiy)]{\displaystyle \mathrm {Table} [h_{\text{new}}(\mathrm {key} )]}balde.
  • El comando se ejecuta.

Hashing lineal

El hash lineal es una implementación de la tabla hash que permite el crecimiento o la reducción dinámica de la tabla, un cubo a la vez. [ 46 ]

Actuación

El rendimiento de una tabla hash depende de la capacidad de la función hash para generar números cuasialeatorios (σ{\displaystyle \sigma }) para entradas en la tabla hash dondeK{\displaystyle K},norte{\displaystyle n}yh(incógnita){\displaystyle h(x)}denota la clave, el número de cubetas y la función hash tal queσ = h(K) % norte{\displaystyle \sigma \ =\ h(K)\ \%\ n}. Si la función hash genera el mismoσ{\displaystyle \sigma }para claves distintas (K1≠K2, h(K1) = h(K2){\displaystyle K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})}), esto resulta en una colisión , que se maneja de diversas maneras. La complejidad temporal constante (O(1){\displaystyle O(1)}) de la operación en una tabla hash se presupone bajo la condición de que la función hash no genere índices que colisionen; por lo tanto, el rendimiento de la tabla hash es directamente proporcional a la capacidad de la función hash elegida para dispersar los índices. [ 47 ] : 1 Sin embargo, la construcción de tal función hash es prácticamente inviable , por lo que las implementaciones dependen de técnicas de resolución de colisiones específicas para cada caso para lograr un mayor rendimiento. [ 47 ] : 2

El mejor rendimiento se obtiene cuando la función hash distribuye uniformemente los elementos del universo y los elementos almacenados en la tabla se extraen aleatoriamente del universo. En este caso, en el hashing con encadenamiento, el tiempo esperado para una búsqueda exitosa es1+α2+Θ(1metro){\textstyle 1+{\frac {\alpha }{2}}+\Theta \left({\frac {1}{m}}\right)}y el tiempo esperado para una búsqueda infructuosa esmi−α+α+Θ(1metro){\textstyle e^{-\alpha }+\alpha +\Theta \left({\frac {1}{m}}\right)}. [ 48 ]

Aplicaciones

Matrices asociativas

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

Indexación de bases de datos

Las tablas hash también pueden usarse 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. [ 49 ]

Cachés

Las tablas hash se pueden usar para implementar cachés , tablas de datos auxiliares que se utilizan para acelerar el acceso a datos almacenados principalmente en medios más lentos. En esta aplicación, las colisiones de hash se pueden manejar descartando una de las dos entradas que colisionan; generalmente se borra el elemento antiguo que está almacenado en la tabla y se sobrescribe con el nuevo, de modo que cada elemento de la tabla tenga un valor hash único. [ 50 ] [ 51 ]

Conjuntos

Las tablas hash se pueden utilizar en la implementación de la estructura de datos de conjuntos , que puede almacenar valores únicos sin ningún orden en particular; los conjuntos se utilizan normalmente para comprobar la pertenencia de un valor a la colección, en lugar de para recuperar elementos. [ 52 ]

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. [ 53 ]

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, se convierte primero a una cadena. Aparte de los siete tipos de datos "primitivos", cada valor en JavaScript es un objeto. [ 54 ] ECMAScript 2015 también agregó la Mapestructura de datos, que acepta valores arbitrarios como claves. [ 55 ]
  • C++11 incluye unordered_mapen su biblioteca estándar para almacenar claves y valores de tipos arbitrarios . [ 56 ]
  • La implementación integrada de Gomap implementa un tipo de mapa en forma de un tipo , que a menudo es (pero no está garantizado que sea) una tabla hash. [ 57 ]
  • El lenguaje de programación Java incluye las colecciones HashSet, HashMap, LinkedHashSet, y LinkedHashMapgenéricas . [ 58 ]
  • La implementación integrada de Pythondict implementa una tabla hash en forma de un tipo . [ 59 ]
  • El operador integrado de RubyHash utiliza el modelo de direccionamiento abierto desde Ruby 2.4 en adelante. [ 60 ]
  • El lenguaje de programación Rust incluye HashMap, HashSetcomo parte de la biblioteca estándar de Rust. [ 61 ]
  • La biblioteca estándar .NET incluye HashSety Dictionary, [ 62 ] [ 63 ] por lo que puede usarse desde lenguajes como C# y VB.NET . [ 64 ]

Véase también

Notas

  1. ↑ Existen enfoques con una complejidad temporal esperada en el peor de los casos de O(log 2 (1 - α ) −1 ) donde α es el factor de carga. [ 1 ]

Referencias

  1. ↑ Martin Farach-Colton; Andrew Krapivin; William Kuszmaul. Límites óptimos para el direccionamiento abierto sin reordenamiento . 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). arXiv : 2501.02305 . doi : 10.1109/FOCS61266.2024.00045 .
  2. 1 2 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009). Introducción a los algoritmos (3.ª ed.). Instituto Tecnológico de Massachusetts. págs. 253–280 . ISBN   978-0-262-03384-8.
  3. ↑ Mehlhorn, Kurt ; Sanders, Peter (2008). «Tablas hash y matrices asociativas» (PDF) . Algoritmos y estructuras de datos . Springer. págs. 81–98 . doi : 10.1007/978-3-540-77978-0_4 . ISBN  978-3-540-77977-3.
  4. 1 2 3 4 5 6 7 Knuth, Donald E. (24 de abril de 1998). El arte de la programación informática: Volumen 3: Ordenación y búsqueda (2.ª ed.). Addison-Wesley Professional . ISBN  978-0-201-89685-5.
  5. ↑ Leiserson, Charles E. (Otoño de 2005). "Clase 13: Algoritmos amortizados, duplicación de tablas, método potencial" . Curso MIT 6.046J/18.410J Introducción a los algoritmos . Archivado del original el 7 de agosto de 2009.
  6. ↑ 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.
  7. 1 2 3 4 5 Sedgewick, Robert ; Wayne, Kevin (2011). Algoritmos . Vol. 1 (4.ª ed.). Addison-Wesley Professional – vía Princeton University , Departamento de Ciencias de la Computación.  
  8. ↑ Silberschatz, A.; Korth, HF; Sudarshan, S. (2020). Conceptos de sistemas de bases de datos (7.ª ed.). McGraw-Hill . 
  9. ↑ Goodrich, MT; Tamassia, R.; Goldwasser, MH (2014). Estructuras de datos y algoritmos en Java (6.ª ed.). Wiley . 
  10. 123Konheim, Alan G. (2010). Hashing in Computer Science. doi:10.1002/9780470630617. ISBN 978-0-470-34473-6.
  11. 123456789101112Mehta, Dinesh P.; Mehta, Dinesh P.; Sahni, Sartaj, eds. (2004). Handbook of Data Structures and Applications. doi:10.1201/9781420035179. ISBN 978-0-429-14701-2.
  12. ↑Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
  13. 1234567Mayers, Andrew (2008). "CS 312: Hash tables and amortized analysis". Cornell University, Department of Computer Science. Archived from the original on April 26, 2021. Retrieved October 26, 2021– via cs.cornell.edu.
  14. 12 James S. Plank and Brad Vander Zanden. "CS140 Lecture notes -- Hashing".
  15. ↑Maurer, W. D.; Lewis, T. G. (March 1975). "Hash Table Methods". ACM Computing Surveys. 7 (1): 5–19. doi:10.1145/356643.356645. S2CID 17874775.
  16. 12Owolabi, Olumide (February 2003). "Empirical studies of some hashing functions". Information and Software Technology. 45 (2): 109–112. doi:10.1016/S0950-5849(02)00174-X.
  17. 12Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006). Perfect Hashing for Network Applications. 2006 IEEE International Symposium on Information Theory. pp. 2774–2778. doi:10.1109/ISIT.2006.261567. ISBN 1-4244-0505-X. S2CID 1494710.
  18. ↑ Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009). "Hash, displace, and compress" (PDF) . Algorithms—ESA 2009: 17th Annual European Symposium, Copenhague, Dinamarca, 7–9 de septiembre de 2009, Proceedings . Lecture Notes in Computer Science . Vol. 5757. Berlín: Springer. pp. 682–693 . CiteSeerX 10.1.1.568.130 . doi : 10.1007/978-3-642-04128-0_61 . MR 2557794 .    
  19. 1 2 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 Tecnológico de Massachusetts . ISBN  978-0-262-53196-2.
  20. ↑ Stroustrup, Bjarne (1997). El lenguaje de programación C++ Tercera edición . Reading, Massachusetts: Addison-Wesley. pág. 503. ISBN  0-201-88954-4.
  21. ↑ Pearson, Karl (1900). "Sobre el criterio de que un sistema dado de desviaciones de lo probable en el caso de un sistema de variables correlacionadas es tal que se puede suponer razonablemente que surgió de un muestreo aleatorio" . Philosophical Magazine . Serie 5. 50 (302): 157– 175. doi : 10.1080/14786440009463897 .
  22. ↑ Plackett, Robin (1983). "Karl Pearson y la prueba de chi-cuadrado". International Statistical Review . 51 (1): 59– 72. doi : 10.2307/1402731 . JSTOR 1402731 . 
  23. 1 2 Wang, Thomas (marzo de 1997). "Prime Double Hash Table" . Archivado del original el 3 de septiembre de 1999. Recuperado el 10 de mayo de 2015 .
  24. ↑ Wegman, Mark N.; Carter, J. Lawrence (junio de 1981). "Nuevas funciones hash y su uso en autenticación e igualdad de conjuntos" . Journal of Computer and System Sciences . 22 (3): 265– 279. Bibcode : 1981JCoSS..22..265W . doi : 10.1016/0022-0000(81)90033-7 .
  25. ↑ Demaine, Erik; Lind, Jeff (Primavera de 2003). "Clase 2" (PDF) . 6.897: Estructuras de datos avanzadas. Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT . Archivado (PDF) del original el 15 de junio de 2010. Recuperado el 30 de junio de 2008 .
  26. 1 2 3 Culpepper, J. Shane; Moffat, Alistair (2005). "Códigos de bytes mejorados con propiedades de prefijo restringidas". Procesamiento de cadenas y recuperación de información . Notas de clase en ciencias de la computación. Vol. 3772. págs. 1–12 . doi : 10.1007/11575832_1 . ISBN   978-3-540-29740-6.
  27. ↑ Willard, Dan E. (2000). "Examinando la geometría computacional, los árboles de van Emde Boas y el hashing desde la perspectiva del árbol de fusión". SIAM Journal on Computing . 29 (3): 1030– 1049. doi : 10.1137/S0097539797322425 . MR 1740562 . .
  28. ↑ Askitis, Nikolas; Sinha, Ranjan (octubre de 2010). "Ingeniería de tries escalables, eficientes en caché y espacio para cadenas". The VLDB Journal . 19 (5): 633– 660. doi : 10.1007/s00778-010-0183-9 .
  29. ↑ Askitis, Nikolas; Zobel, Justin (octubre de 2005). «Resolución de colisiones con optimización de caché en tablas hash de cadenas». Actas de la 12.ª Conferencia Internacional sobre 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.
  30. ↑ Askitis, Nikolas (2009). «Tablas hash rápidas y compactas para claves enteras» (PDF) . Actas de la 32.ª Conferencia Australiana de Ciencias de la Computación (ACSC 2009) . Vol. 91. págs. 113–122 . ISBN   978-1-920682-72-9Archivado del original (PDF) el 16 de febrero de 2011. Consultado el 13 de junio de 2010 .
  31. ^ 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.
  32. 1 2 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.
  33. 1 2 3 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.
  34. 1 2 3 Vitter, Jeffery S.; Chen, Wen-Chin (1987). El diseño y análisis del hash coalescido . Nueva York, Estados Unidos: Oxford University Press . ISBN 978-0-19-504182-8– vía Archive.org .
  35. ^ 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.
  36. 1 2 3 4 5 6 Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Hopscotch Hashing". Computación distribuida . Notas de clase en ciencias de la computación. Vol. 5218. págs. 350–364 . doi : 10.1007/978-3-540-87779-0_24 . ISBN   978-3-540-87778-3.
  37. ^ Celis , Pedro (1986). Hashing de Robin Hood (PDF) . Ontario, Canadá: Universidad de Waterloo , Departamento de Ciencias de la Computación. ISBN 978-0-315-29700-5. OCLC 14083698 . Archivado (PDF) del original el 1 de noviembre de 2021 . Recuperado el 2 de noviembre de 2021 . 
  38. ↑ Poblete, PV; Viola, A. (julio de 2019). "Análisis de Robin Hood y otros algoritmos de hash bajo el modelo de sondeo aleatorio, con y sin eliminaciones" . Combinatoria, probabilidad y computación . 28 (4): 600– 617. doi : 10.1017/S0963548318000408 . S2CID 125374363 . 
  39. ↑ Clarkson, Michael (2014). "Clase 13: Tablas hash" . Universidad de Cornell , Departamento de Ciencias de la Computación. Archivado del original el 7 de octubre de 2021. Recuperado el 1 de noviembre de 2021 a través de cs.cornell.edu.
  40. ↑ Gries, David (2017). "JavaHyperText and Data Structure: Robin Hood Hashing" (PDF) . Universidad de Cornell , Departamento de Ciencias de la Computación. Archivado (PDF) del original el 26 de abril de 2021. Recuperado el 2 de noviembre de 2021 a través de cs.cornell.edu.
  41. ↑ Celis, Pedro (28 de marzo de 1988). Hashing Robin Hood externo (PDF) (Informe técnico). Bloomington, Indiana: Universidad de Indiana , Departamento de Ciencias de la Computación. 246. Archivado (PDF) del original el 3 de noviembre de 2021. Recuperado el 2 de noviembre de 2021 .
  42. ↑ Goddard, Wayne (2021). "Capítulo C5: Tablas hash" (PDF) . Universidad de Clemson . págs. 15–16 . Recuperado el 4 de diciembre de 2023 . 
  43. ↑ Devadas, Srini; Demaine, Erik (25 de febrero de 2011). "Introducción a los algoritmos: redimensionamiento de tablas hash" (PDF) . Instituto Tecnológico de Massachusetts , Departamento de Ciencias de la Computación. Archivado (PDF) del original el 7 de mayo de 2021. Recuperado el 9 de noviembre de 2021 a través de MIT OpenCourseWare .
  44. ↑ Thareja, Reema (2014). "Hashing y colisión". Estructuras de datos usando C. Oxford University Press. págs. 464–488 . ISBN  978-0-19-809930-7.
  45. 1 2 Friedman, Scott; Krishnan, Anand; Leidefrost, Nicholas (18 de marzo de 2003). "Tablas hash para sistemas embebidos y en tiempo real" (PDF) . All Computer Science and Engineering Research . Washington University in St. Louis . doi : 10.7936/K7WD3XXV . Archivado (PDF) del original el 9 de junio de 2021. Recuperado el 9 de noviembre de 2021 – a través de Northwestern University , Departamento de Ciencias de la Computación.
  46. ↑ Litwin, Witold (1980). "Hashing lineal: una nueva herramienta para el direccionamiento de archivos y tablas" (PDF) . Actas de la 6.ª Conferencia sobre Bases de Datos Muy Grandes . Universidad Carnegie Mellon . págs. 212–223 . Archivado (PDF) del original el 6 de mayo de 2021. Recuperado el 10 de noviembre de 2021 a través de cs.cmu.edu. 
  47. 1 2 Dijk, Tom Van (2010). "Análisis y mejora del rendimiento de las tablas hash" (PDF) . Países Bajos : Universidad de Twente . Archivado (PDF) del original el 6 de noviembre de 2021. Recuperado el 31 de diciembre de 2021 .
  48. ↑ Baeza-Yates, Ricardo; Poblete, Patricio V. (1999). «Capítulo 2: Búsqueda». En Atallah (ed.). Algoritmos y teoría de la computación: manual . CRC Press. pp. 2–6 . ISBN  0849326494.
  49. ↑ 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 .
  50. ↑ 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". China Communications . 17 (2): 232– 238. Bibcode : 2020CComm..17b.232Z . doi : 10.23919/jcc.2020.02.018 . S2CID 212649328 . 
  51. ↑ Bottommley, James (1 de enero de 2004). "Understanding Caching" . Linux Journal . Archivado del original el 4 de diciembre de 2020. Recuperado el 16 de abril de 2022 .
  52. ↑ Jill Seaman (2014). "Set & Hash Tables" (PDF) . Universidad Estatal de Texas . Archivado del original el 1 de abril de 2022. Recuperado el 26 de marzo de 2022 .{{cite web}}: CS1 maint: bot: estado de la URL original desconocido ( enlace )
  53. ↑ "Tabla de transposición - Wiki de programación de ajedrez" . chessprogramming.org . Archivado del original el 14 de febrero de 2021. Consultado el 1 de mayo de 2020 .
  54. ↑ "Tipos de datos y estructuras de datos de JavaScript - JavaScript | MDN" . developer.mozilla.org . Consultado el 24 de julio de 2022 .
  55. ↑ "Mapa - JavaScript | MDN" . developer.mozilla.org . 20 de junio de 2023 . Consultado el 15 de julio de 2023 .
  56. ↑ "Lenguaje de programación C++ - Especificación técnica" (PDF) . Organización Internacional de Normalización . págs. 812–813 . Archivado del original (PDF) el 21 de enero de 2022. Consultado el 8 de febrero de 2022 . 
  57. ↑ "Especificación del lenguaje de programación Go" . go.dev . Consultado el 1 de enero de 2023 .
  58. ↑ "Lección: Implementaciones (Tutoriales de Java™ > Colecciones)" . docs.oracle.com . Archivado del original el 18 de enero de 2017. Consultado el 27 de abril de 2018 .
  59. ↑ Zhang, Juan; Jia, Yunwei (2020). "Optimización de rehash de Redis basada en aprendizaje automático" . Journal of Physics: Conference Series . 1453 (1): 3. Bibcode : 2020JPhCS1453a2048Z . doi : 10.1088/1742-6596/1453/1/012048 . S2CID 215943738 . 
  60. ↑ Jonan Scheffler (25 de diciembre de 2016). "Ruby 2.4 lanzado: hashes más rápidos, enteros unificados y mejor redondeo" . heroku.com . Archivado del original el 3 de julio de 2019. Consultado el 3 de julio de 2019 .
  61. ↑ "doc.rust-lang.org" . Archivado del original el 8 de diciembre de 2022. Consultado el 14 de diciembre de 2022 .
  62. ↑ "Clase HashSet (System.Collections.Generic)" . learn.microsoft.com . Consultado el 1 de julio de 2023 .
  63. ↑ dotnet-bot. "Clase de diccionario (System.Collections.Generic)" . learn.microsoft.com . Consultado el 16 de enero de 2024 .
  64. ↑ "Ejemplo de HashSet en VB.NET" . Dot Net Perls .

Lecturas adicionales

  • 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, NJ: Wiley. pp. 369–418 . ISBN  978-0-471-73884-8.
  • McKenzie, BJ; Harries, R.; Bell, T. (febrero de 1990). "Selección de un algoritmo de hash". Software: Practice and Experience . 20 (2): 209– 224. doi : 10.1002/spe.4380200207 . hdl : 10092/9691 . S2CID 12854386 . 
  • Entrada del NIST sobre tablas hash
  • Estructuras de datos abiertas – Capítulo 5 – Tablas hash , Pat Morin
  • Introducción a los algoritmos del MIT: Hashing 1 (Vídeo de la conferencia OCW del MIT)
  • Introducción a los algoritmos del MIT: Hashing 2 (Vídeo de la conferencia OCW del MIT)
Obtenido de " https://en.wikipedia.org/w/index.php?title=Hash_table&oldid=1352708183 "
Lecturas relacionadas
6 articulos
Ciencias de la ComputaciónCiencias de la ComputaciónÁreas fundamentales de la informática La informática es el estudio de la computación , la información y la automatización . [1] [2] [3] La informát...Data structureA data structure known as a hash table . In computer science , a data structure is a data organization and storage format that is usually chosen fo...{\displaystyle (clave, valor)}Matriz asociativaEn informática , una matriz asociativa , un mapa , una tabla de símbolos o un diccionario es un tipo de datos abstracto que almacena una colección ...Tipo de datos abstractoTipo de datos abstractoEn informática , un tipo abstracto de datos ( ADT ) es un modelo matemático para los tipos de datos , definido por su comportamiento ( semántica ) ...Clave únicaEn los sistemas de gestión de bases de datos relacionales , una clave única es una clave candidata . Todas las claves candidatas de una relación pu...Valor (informática)Valor (informática)En informática y programación de software , un valor es la representación de alguna entidad que puede ser manipulada por un programa. Los miembros ...