Tabla de picadillo

${displaystyle M}$

${displaystyle xin S}$

${displaystyle n}$

Hashing por multiplicación

El esquema en hash por multiplicación es el siguiente:

$${displaystyle h(k)=lfloor n{bigl (}(MA){bmod {1}{bigr)}rfloor }$$

${displaystyle A}$

${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. La uniformidad a veces es difícil de garantizar por diseño, pero se puede evaluar empíricamente mediante pruebas estadísticas, por ejemplo, una prueba de chi-cuadrado de Pearson para distribuciones uniformes discretas.

La distribución debe ser uniforme solo para los tamaños de tabla que se producen en la aplicación. En particular, si se usa 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.

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. Dicho agrupamiento 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 agrupamiento particularmente pobre.

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

Resolución de colisiones

Un algoritmo de búsqueda que utiliza hashing 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 hay dos claves de búsqueda con el mismo índice de matriz. Sin embargo, este no es siempre el caso y es imposible garantizar datos dados que no se ven. 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.

Encadenamiento separado

Colisión Hash resuelta por cadena separada

Colisión Hash por encadenamiento separado con registros de cabeza en la matriz de cubos.

En cadenas separadas, el proceso implica construir una lista vinculada con un par de valor clave para cada índice de array de búsqueda. Los elementos colisionados están encadenados a través de una sola lista conectada, que se puede atravesar para acceder al artículo con una llave de búsqueda única. La resolución de colisión mediante la encadenamiento con la lista vinculada es un método común de aplicación de tablas de hash. Vamos ${displaystyle T}$ y ${displaystyle x}$ ser la tabla de hash y el nodo respectivamente, la operación implica lo siguiente:

Chained-Hash-Insert(T, k)
 insertar x en el jefe de la lista vinculada T[h()k)

Chained-Hash-SearchT, k)
 búsqueda de un elemento con clave k in linked list T[h()k)

Chained-Hash-Delete(T, k)
 Borrador x de la lista enlazada T[h()k)

Si el elemento es comparable ya sea numérica o léxicamente, y se inserta en la lista manteniendo el orden total, resulta en una terminación más rápida de las búsquedas fallidas.

Otras estructuras de datos para encadenamiento separado

Si se ordenan las teclas, podría ser eficiente utilizar conceptos "autoorganizar" como el uso de un árbol de búsqueda binaria auto-balanceante, a través del cual el peor caso teórico podría ser reducido a ${displaystyle O(log {n}}$, aunque introduce complejidades adicionales.

En el corte dinámico perfecto, se utilizan tablas de dos niveles para reducir la complejidad de la búsqueda para ser una garantía ${displaystyle O(1)}$ en el peor caso. En esta técnica, los cubos de ${displaystyle k}$ entradas se organizan como tablas de hash perfectas ${displaystyle k^{2}$ ranuras que proporcionan el tiempo de búsqueda de la peor maleta constante, y tiempo amortizado bajo para la inserción. Un estudio muestra que el encadenamiento separado basado en arrays es 97% más performant cuando se compara con el método de lista ligada estándar bajo carga pesada.

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

Almacenamiento en caché y localidad de referencia

La lista vinculada de la implementación de encadenamiento independiente puede no tener en cuenta la memoria caché debido a la localidad espacial (localidad de referencia) cuando los nodos de la lista vinculada 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 memoria caché de la CPU.

En las variantes conscientes de la memoria caché, se utiliza una matriz dinámica que se considera más compatible con la memoria caché en el lugar donde generalmente se implementa una lista vinculada o árboles de búsqueda binarios autoequilibrados para la resolución de colisiones a través de un encadenamiento separado, ya que el patrón de asignación contigua de la matriz podría ser explotada por captadores previos de caché de hardware, como el búfer de búsqueda de traducción, lo que da como resultado una reducción del tiempo de acceso y el consumo de memoria.

Direccionamiento abierto

Colisión de Hash resuelta por el abordaje abierto con probing lineal (interval=1). Tenga en cuenta que "Ted Baker" tiene un hash único, pero sin embargo chocó con "Sandra Dee", que anteriormente había colisionado con "John Smith".

Este gráfico compara el número promedio de faltas de caché de CPU requeridas para buscar elementos en tablas de hash grandes (mucho tamaño superior del caché) con encadenamiento y probación lineal. La prueba lineal funciona mejor debido a una mejor localización 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 matriz de cubos y la resolución de hash se realiza mediante sondeo. Cuando se debe insertar una nueva entrada, se examinan los cubos, comenzando con la ranura codificada y procediendo en alguna secuencia de sondeo, hasta que se encuentra una ranura desocupada. Al buscar una entrada, los cubos 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.

Las secuencias de sonda bien conocidas incluyen:

• Probación lineal, en la que se fija el intervalo entre sondas (normalmente 1).
• Probación cuadrática, en la que se aumenta el intervalo entre sondas añadiendo las salidas sucesivas de un polinomio cuadrático al valor dado por la computación de hash original.
• Doble escobilla, en la que el intervalo entre sondas es computado por una función de hash secundaria.

El rendimiento del abordaje abierto puede ser más lento en comparación con el encadenamiento separado ya que la secuencia de la sonda aumenta cuando el factor de carga ${displaystyle alpha }$ enfoques 1. El probing resulta en un bucle infinito si el factor de carga alcanza 1, en el caso de una tabla completamente llena. El coste medio de la probación lineal depende de la capacidad de la función hash de distribuir los elementos uniformemente a lo largo de la tabla para evitar la agrupación, ya que la formación de los racimos daría lugar a un mayor tiempo de búsqueda.

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 memoria caché de la CPU debido a la localidad de las referencias, lo que resulta en una latencia de memoria reducida.

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

Hashing combinado

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. El algoritmo es ideal para la asignación de memoria fija. La colisión en el hashing fusionado se resuelve identificando la ranura vacía indexada más grande en la tabla hash, luego el valor de la 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 en colisión.

Hashing de cuco

Cuckoo hashing es una forma de técnica de resolución de colisión abierta que garantiza ${displaystyle O(1)}$ complejidad de búsqueda peor y tiempo amortizado constante para las inserciones. La colisión se resuelve mediante el mantenimiento de dos tablas de hash, cada una con su propia función de encogimiento, y la ranura colisionada se reemplaza con el elemento dado, y el elemento ocupado de la ranura se desplaza en la otra tabla de hash. El proceso continúa hasta que cada llave 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 bucles umbral, ambas tablas de hash se rehacen con nuevas funciones de hash y el procedimiento continúa.

Hopscotch hash

Hopscotch hashing es un algoritmo basado en direccionamiento abierto que combina los elementos de cuckoo hashing, sondeo lineal y encadenamiento a través de la noción de un vecindario de cubos: los cubos subsiguientes alrededor de cualquier cubo ocupado dado, también llamado un "virtual" Cubeta. 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 una tabla hash concurrente redimensionable. La característica de vecindad del hash de rayuela garantiza una propiedad en la que el costo de encontrar el artículo deseado de cualquier cubeta dada dentro de la vecindad es muy cercano al costo de encontrarlo en la cubeta misma; el algoritmo intenta ser un artículo en su vecindario, con un posible costo involucrado en el desplazamiento de otros artículos.

Cada cubo dentro de la tabla del hash incluye una "información adicional de Hop"—an H-bit bit array para indicar la distancia relativa del artículo que originalmente fue clavado en el actual cubo virtual dentro H-1 entradas. Vamos ${displaystyle k}$ y ${displaystyle Bk!$ ser la clave para ser insertada y cubo a la que se ha reducido la clave respectivamente; varios casos están involucrados en el procedimiento de inserción de tal manera que se jura la propiedad vecinal del algoritmo: si ${displaystyle Bk!$ está vacío, el elemento se inserta, y el bitmap más izquierdo se establece a 1; si no está vacío, el probing lineal se utiliza para encontrar una ranura vacía en la tabla, el bitmap del cubo se actualiza seguido por la inserción; si la ranura vacía no está dentro de la gama de la barrio, i.e. H-1, posterior swap y manipulación de bits hop-info de cada cubo se realiza de acuerdo con sus propiedades invariantes del vecindario.

Hashing de Robin Hood

Robin hood hashing es un algoritmo de resolución de colisión basado en el abordaje abierto; las colisiones se resuelven favoreciendo el desplazamiento del elemento que es más lejano o más largo longitud de secuencia de sonda (PSL)—desde su "ubicación casera" es decir, el cubo al que el objeto fue aplastado. Aunque la piratería de capucha no cambia el costo teórico de búsqueda, afecta significativamente la variabilidad de la distribución de los elementos en los cubos, es decir, tratar con la formación de racimo en la tabla de hah. Cada nodo dentro de la tabla de hash que utiliza el corte de capucha robin debe aumentarse para almacenar un valor PSL extra. Vamos ${displaystyle x}$ ser la clave que se inserta, ${displaystyle x.psl}$ ser la longitud de PSL (incremental) ${displaystyle x}$, ${displaystyle T}$ ser la mesa del hash ${displaystyle j}$ ser el índice, el procedimiento de inserción es el siguiente:

• Si ${displaystyle x.psl\leq T[j].psl}$: la iteración entra en el siguiente cubo sin intentar una sonda externa.
• Si ${displaystyle x.psl } T[j].psl}$: insertar el elemento ${displaystyle x}$ en el cubo ${displaystyle j}$; swap ${displaystyle x}$ con ${displaystyle T[j]}$Que sea ${displaystyle x'}$; continuar la sonda de la ${displaystyle j+1}$st cubo para insertar ${displaystyle x'}$; repetir el procedimiento hasta que se inserte cada elemento.

Cambio de tamaño dinámico

Las inserciones repetidas causan que el número de entradas en una tabla de hash crezca, lo que aumenta el factor de carga; mantener el amortizado ${displaystyle O(1)}$ rendimiento de las operaciones de búsqueda e inserción, una tabla de hash es redimensionada dinámicamente y los elementos de las tablas son rehashed en los cubos de la nueva tabla de hash, ya que los elementos no pueden ser copiados sobre como diferentes tamaños de mesa resulta en diferente valor de hash debido a la operación de modulo. Si una tabla de hash se vuelve "demasiado vacía" después de borrar algunos elementos, el tamaño se puede realizar para evitar el uso excesivo de la memoria.

Cambiar el tamaño moviendo todas las entradas

Por lo general, una nueva tabla hash con el doble de tamaño que 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 computacionalmente costoso a pesar de su simplicidad.

Alternativas al refrito todo a la vez

Algunas implementaciones de tablas de precipitaciones, en particular en sistemas en tiempo real, no pueden pagar el precio de ampliar la tabla de precipitaciones a la vez, porque puede interrumpir operaciones de tiempo crítico. Si no se puede evitar el redimensionamiento dinámico, una solución es realizar el redimensionamiento gradualmente para evitar el desbloqueo de almacenamiento (normalmente en el 50% del tamaño de la nueva tabla) durante el rehashing y evitar la fragmentación de memoria que activa la compactación de heap debido a la confección de grandes bloques de memoria causados por la vieja tabla de hash. En tal caso, la operación de reajuste se realiza gradualmente mediante la ampliación del bloque de memoria anterior asignado a la vieja tabla de hash de tal manera que los cubos de la tabla de hash permanecen sin alterar. Un enfoque común para el reajuste amortizado implica mantener dos funciones de hash ${displaystyle h_{text{old}}$ y ${displaystyle ¿Qué?$. El proceso de rehashing los elementos de un cubo de acuerdo con la nueva función de hash se denomina como limpieza, que se implementa mediante el patrón de mando encapsulando las operaciones como ${displaystyle mathrm {Add} (mathrm {key}}$, ${displaystyle mathrm {Get} (mathrm {key}}$ y ${displaystyle mathrm {Delete} (mathrm {key}}$ a ${displaystyle mathrm {Lookup} (mathrm {key}{text{command}) }$ envoltorio tal que cada elemento en el cubo se rehashed y su procedimiento implica lo siguiente:

• Limpio ${displaystyle mathrm {Table} [h_{text{old} {mathrm {key}]}}$ cubo.
• Limpio ${displaystyle mathrm {Table} [h_{text{new}(mathrm {key})}}$ cubo.
• El comando es ejecutado.

Hashing lineal

El hashing lineal es una implementación de la tabla hash que permite crecimientos o disminuciones dinámicas de la tabla un cubo a la vez.

Rendimiento

El rendimiento de una tabla de hash depende de la capacidad de la función hash para generar números de cuasi-arreba (${displaystyle sigma }$) para entradas en la tabla de hash donde ${displaystyle K}$, ${displaystyle n}$ y ${displaystyle h(x)}$ denota la clave, el número de cubos y la función hash tal que ${displaystyle sigma = h(K)$. Si la función hash genera la misma ${displaystyle sigma }$ para teclas distintas (${displaystyle K_{1}neq K_{2}, h(K_{1}) = h(K_{2}}$), esto resulta en colisión, que debe tratarse de varias maneras. La complejidad constante del tiempo (${displaystyle O(1)}$) de la operación en una tabla de hash se presupone en la condición de que la función hash no genera índices de colisión; por lo tanto, el rendimiento de la tabla hash es directamente proporcional a la capacidad de función hash elegida para dispersar los índices. Sin embargo, la construcción de esa función de precipitación 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.

Aplicaciones

Matrices asociativas

Las tablas hash se usan comúnmente para implementar muchos tipos de tablas en memoria. Se utilizan para implementar arreglos asociativos.

Indización de bases de datos

Las tablas hash también se pueden usar 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.

Cachés

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

Conjuntos

Las tablas hash se pueden usar en la implementación de una estructura de datos establecida, que puede almacenar valores únicos sin ningún orden en particular; set se usa típicamente para probar la membresía de un valor en la colección, en lugar de la recuperación de elementos.

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.

Implementaciones

En lenguajes de programación

Muchos lenguajes de programación proporcionan funcionalidad de tabla hash, ya sea como matrices asociativas integradas o como módulos de biblioteca estándar.

En JavaScript, todos los valores excepto 7 "primitive" tipos de datos se denomina "objeto", que utiliza números enteros, cadenas o "símbolos" únicos garantizados; valores primitivos como claves para un mapa hash. ECMAScript 6 también agregó estructuras de datos Map y Set.

C++11 incluye unordered_map en su biblioteca estándar para almacenar claves y valores de tipos arbitrarios.

El mapa integrado de Go implementa una tabla hash en forma de tipo.

El lenguaje de programación Java incluye las colecciones genéricas HashSet, HashMap, LinkedHashSet y LinkedHashMap.

El dict integrado de Python implementa una tabla hash en forma de tipo.

El Hash integrado de Ruby utiliza el modelo de direccionamiento abierto de Ruby 2.4 en adelante.

El lenguaje de programación Rust incluye HashMap, HashSet como parte de la biblioteca estándar de Rust.