Función hash perfecta

En informática , una función hash perfecta $h$ para un conjunto $S$ es una función hash que asigna elementos distintos de $S$ a un conjunto de $m$ enteros, sin colisiones . En términos matemáticos, es una función inyectiva .

Las funciones hash perfectas pueden utilizarse para implementar una tabla de búsqueda con un tiempo de acceso constante en el peor de los casos . Una función hash perfecta, al igual que cualquier otra función hash , puede utilizarse para implementar tablas hash , con la ventaja de que no es necesario implementar la resolución de colisiones . Además, si las claves no están presentes en los datos y se sabe que las claves consultadas serán válidas, no es necesario almacenarlas en la tabla de búsqueda, lo que ahorra espacio.

Las desventajas de las funciones hash perfectas radican en que $S$ debe conocerse para su construcción. Las funciones hash perfectas no dinámicas deben reconstruirse si $S$ cambia. Para $S$ que cambia con frecuencia , se pueden utilizar funciones hash perfectas dinámicas, aunque a costa de un mayor espacio. ^{[ 1 ]} El espacio requerido para almacenar la función hash perfecta es de $O (n),$ donde $n$ es el número de claves en la estructura.

Los parámetros de rendimiento importantes para las funciones hash perfectas son el tiempo de evaluación, que debe ser constante, el tiempo de construcción y el tamaño de la representación.

Solicitud

Una función hash perfecta con valores en un rango limitado puede utilizarse para operaciones de búsqueda eficientes, colocando las claves de $S$ (u otros valores asociados) en una tabla de búsqueda indexada por la salida de la función. A continuación, se puede comprobar si una clave está presente en $S$ o buscar un valor asociado a esa clave, buscándolo en su celda de la tabla. Cada búsqueda de este tipo requiere un tiempo constante en el peor de los casos . ^{[ 2 ]} Con el hash perfecto, los datos asociados pueden leerse o escribirse con un único acceso a la tabla. ^{[ 3 ]}

Rendimiento de las funciones hash perfectas

Los parámetros de rendimiento importantes para un hashing perfecto son el tamaño de la representación, el tiempo de evaluación, el tiempo de construcción y, además, el requisito de rango. ${\frac {m}{n}}$ (número promedio de cubetas por clave en la tabla hash). ^{[ 4 ]} El tiempo de evaluación puede ser tan rápido como $O (1)$ , lo cual es óptimo. ^{[ 2 ]}^{[ 4 ]} El tiempo de construcción debe ser al menos $O (n)$ , porque cada elemento en $S$ debe ser considerado, y $S$ contiene $n$ elementos. Este límite inferior se puede alcanzar en la práctica. ^{[ 4 ]}

El límite inferior para el tamaño de la representación depende de $m$ y $n$ . Sea $m = (1+ ε) n$ y $h$ una función hash perfecta. Una buena aproximación para el límite inferior es $\log e-\varepsilon \log {\frac {1+\varepsilon }{\varepsilon }}$ Bits por elemento. Para un hash perfecto mínimo, $ε = 0$ , el límite inferior es $log e \approx 1,44$ bits por elemento. ^{[ 4 ]}

Construcción

Una función hash perfecta para un conjunto específico $S$ que se puede evaluar en tiempo constante y con valores en un rango pequeño, se puede encontrar mediante un algoritmo aleatorio en un número de operaciones proporcional al tamaño de S. La construcción original de Fredman, Komlós y Szemerédi (1984) utiliza un esquema de dos niveles para mapear un conjunto $S$ de $n$ elementos a un rango de $O (n)$ índices, y luego mapear cada índice a un rango de valores hash. El primer nivel de su construcción elige un primo grande $p$ (mayor que el tamaño del universo del que se extrae $S$ ) y un parámetro $k$ , y mapea cada elemento $x$ de $S$ al índice

g(x)=(kx{\bmod {p}}){\bmod {n}}.

Si $k$ se elige aleatoriamente, es probable que este paso tenga colisiones, pero es probable que el número de elementos $n i$ que se asignan simultáneamente al mismo índice $i$ sea pequeño. El segundo nivel de su construcción asigna rangos disjuntos de $O (n i 2)$ enteros a cada índice $i$ . Utiliza un segundo conjunto de funciones modulares lineales, una para cada índice $i$ , para asignar cada miembro $x$ de $S$ al rango asociado con $g (x)$ . ^{[ 2 ]}

Como demuestran Fredman, Komlós y Szemerédi (1984) , existe una elección del parámetro $k$ tal que la suma de las longitudes de los rangos para los $n$ valores diferentes de $g (x)$ es $O (n)$ . Además, para cada valor de $g (x)$ , existe una función modular lineal que asigna el subconjunto correspondiente de $S$ al rango asociado con ese valor. Tanto $k$ como las funciones de segundo nivel para cada valor de $g (x)$ se pueden encontrar en tiempo polinomial eligiendo valores aleatoriamente hasta encontrar uno que funcione. ^{[ 2 ]}

La función hash en sí requiere un espacio de almacenamiento $O (n)$ para almacenar $k$ , $p$ y todas las funciones modulares lineales de segundo nivel. El cálculo del valor hash de una clave $x$ dada se puede realizar en tiempo constante calculando $g (x)$ , buscando la función de segundo nivel asociada con $g (x)$ y aplicando esta función a $x$ . Una versión modificada de este esquema de dos niveles con un mayor número de valores en el nivel superior se puede utilizar para construir una función hash perfecta que mapee $S$ en un rango más pequeño de longitud $n + o (n)$ . ^{[ 2 ]}

Un método más reciente para construir una función hash perfecta es descrito por Belazzougui, Botelho y Dietzfelbinger (2009) como "hash, desplazamiento y compresión". Aquí, una función hash de primer nivel $g$ también se utiliza para mapear elementos a un rango de $r$ enteros. Un elemento $x \in S$ se almacena en el Bucket $B g(x)$ . ^{[ 4 ]}

Luego, en orden descendente de tamaño, los elementos de cada cubeta se procesan mediante una función hash de una secuencia de funciones hash completamente aleatorias e independientes $($ $Φ₁$ $, Φ₂, Φ₃, ...)$ , comenzando con $Φ₁ .$ $Si la función hash no produce colisiones para la cubeta y los valores resultantes aún no están ocupados por elementos de otras cubetas, se elige la función para$ esa cubeta. De lo contrario, se prueba la siguiente función hash de la secuencia. ^{[ 4 ]}

Para evaluar la función hash perfecta $h (x)$ , basta con guardar la asignación σ del índice del cubo $g (x)$ sobre la función hash correcta en la secuencia, lo que resulta en $h(x) = Φ σ(g(x))$ . ^{[ 4 ]}

Finalmente, para reducir el tamaño de la representación, los ( $σ(i)) 0 \leq i < r$ se comprimen en una forma que aún permite la evaluación en $O (1)$ . ^{[ 4 ]}

Este enfoque requiere un tiempo lineal en $n$ para la construcción y un tiempo de evaluación constante. El tamaño de la representación es de orden $O (n)$ y depende del rango alcanzado. Por ejemplo, con $m = 1,23 n,$ Belazzougui, Botelho y Dietzfelbinger (2009) lograron un tamaño de representación entre 3,03 bits/clave y 1,40 bits/clave para su conjunto de ejemplo de 10 millones de entradas, con valores más bajos que requieren un mayor tiempo de cálculo. El límite inferior de espacio en este escenario es de 0,88 bits/clave. ^{[ 4 ]}

Pseudocódigo

El algoritmo hash, displace y compress es (1) Dividir S en cubetas  $B i := g -1 ({i}) \cap S,0 \leq i < r$  (2) Ordenar las cubetas B _i en orden descendente según el tamaño |B _i | (3) Inicializar el arreglo T[0...m-1] con ceros. (4) para todo i ∈[r], en el orden de (2), hacer (5) para l ← 1,2,... (6) repetir formando K _i← {  $Φ$ _l (x)|x ∈ B _i } (6) hasta que |K _i |=|B _i | y K _i∩ {j|T[j]=1}= ∅ (7) sea σ(i):= el exitoso l (8) para todo j ∈ K _isea T[j]:= 1 (9) Transformar (σ _i ) _{0 ≤ i<r} en forma comprimida, manteniendo un acceso  $O (1)$  .

límites inferiores del espacio

El uso de $O (n)$ palabras de información para almacenar la función de Fredman, Komlós y Szemerédi (1984) es casi óptimo: cualquier función hash perfecta que se pueda calcular en tiempo constante requiere al ^menos un número de bits que es proporcional al tamaño de $S.$ [ ^{5 ]}

Para funciones hash perfectas mínimas, el límite inferior del espacio teórico de la información es

\log _{2}e\approx 1.44

bits/clave. ^{[ 4 ]}

Para funciones hash perfectas, primero se supone que el rango de $h$ está acotado por $n$ como $m = (1+ ε) n$ . Con la fórmula dada por Belazzougui, Botelho y Dietzfelbinger (2009) y para un universo $U\supseteq S$ cuyo tamaño $| U | = u$ tiende hacia el infinito, los límites inferiores del espacio son

\log _{2}e-\varepsilon \log {\frac {1+\varepsilon }{\varepsilon }}

bits/clave, menos $log(n)$ bits en total. ^{[ 4 ]}

Extensiones

Hash perfecto dinámico

El uso de una función hash perfecta es óptimo en situaciones donde existe un conjunto grande, $S$ , que se consulta con frecuencia y que rara vez se actualiza. Esto se debe a que cualquier modificación del conjunto $S$ puede provocar que la función hash deje de ser perfecta para el conjunto modificado. Las soluciones que actualizan la función hash cada vez que se modifica el conjunto se conocen como hash perfecto dinámico ^{[ 1 ]} , pero estos métodos son relativamente complejos de implementar.

Función hash perfecta mínima

Una función hash perfecta mínima es una función hash perfecta que asigna $n$ claves a $n$ enteros consecutivos, generalmente los números del $0$ al $n - 1$ o del $1$ al $n$ . Una forma más formal de expresar esto es: Sean $j$ y $k$ elementos de un conjunto finito $S.$ Entonces $h$ es una función hash perfecta mínima si y solo si $h (j) = h (k)$ implica $j = k$ ( inyectividad ) y existe un entero $a$ tal que el rango de $h$ es $a .. a + | S | - 1.$ Se ha demostrado que un esquema hash perfecto mínimo de propósito general requiere al menos $\log _{2}e\approx 1.44$ bits/clave. ^{[ 4 ]} Suponiendo que $S$ es un conjunto de tamaño $n$ que contiene enteros en el rango $[1,2^{o(n)}]$ , se sabe cómo construir eficientemente una función hash perfecta mínima explícita a partir de $S$ a $\{1,2,\ldots ,n\}$ que utiliza el espacio $n\log _{2}e+o(n)$ bits y que admite un tiempo de evaluación constante. ^{[ 6 ]} En la práctica, existen esquemas de hash perfectos mínimos que utilizan aproximadamente 1,56 bits/clave si se les da suficiente tiempo. ^{[ 7 ]}^{[ 8 ]}

Hash k-perfecto

Una función hash es $k$ -perfecta si, como máximo, $k$ elementos de $S$ se asignan al mismo valor en el rango. El algoritmo de "hash, desplazamiento y compresión" permite construir funciones hash $k$ -perfectas al permitir hasta $k$ colisiones. Los cambios necesarios para lograrlo son mínimos y se destacan en el pseudocódigo adaptado a continuación:

(4) para todo i ∈[r], en el orden de (2), hacer (5) para l ← 1,2,... (6) repetir formando K _i← {  $Φ$ _l (x)|x ∈ B _i } (6) hasta que |K _i |=|B _i | y K _i∩ {j| T[j]=k }= ∅ (7) sea σ(i):= el exitoso l (8) para todo j ∈ K _iestablece T[j] ← T[j]+1

Preservación del orden

Una función hash perfecta mínima $F$ preserva el orden si las claves se dan en algún orden $a 1, a 2, ..., a n$ y para cualesquiera claves $a j$ y $a k$ , $j < k$ implica $F (a j) < F (a k)$ . ^{[ 9 ]} En este caso, el valor de la función es simplemente la posición de cada clave en el orden ordenado de todas las claves. Una implementación simple de funciones hash perfectas mínimas que preservan el orden con tiempo de acceso constante es usar una función hash perfecta (ordinaria) para almacenar una tabla de búsqueda de las posiciones de cada clave. Esta solución utiliza $O(n\log n)$ bits, lo cual es óptimo en el entorno donde la función de comparación para las claves puede ser arbitraria. ^{[ 10 ]} Sin embargo, si las claves $a 1, a 2, ..., a n$ son enteros extraídos de un universo $\{1,2,\ldots ,U\}$ , entonces es posible construir una función hash que preserve el orden utilizando únicamente $O(n\log \log \log U)$ bits de espacio. ^{[ 11 ]} Además, se sabe que este límite es óptimo. ^{[ 12 ]}

Construcciones relacionadas

Si bien las tablas hash bien dimensionadas tienen un tiempo promedio amortizado de O(1) (tiempo constante promedio amortizado) para búsquedas, inserciones y eliminaciones, la mayoría de los algoritmos de tablas hash sufren de tiempos en el peor de los casos que pueden ser mucho mayores. Un tiempo en el peor de los casos de O(1) (tiempo constante incluso en el peor de los casos) sería mejor para muchas aplicaciones (incluidos los enrutadores de red y las cachés de memoria ). ^{[ 13 ]}^{: 41}

Pocos algoritmos de tabla hash admiten un tiempo de búsqueda O(1) en el peor de los casos (tiempo de búsqueda constante incluso en el peor de los casos). Los pocos que lo hacen incluyen: hash perfecto; hash perfecto dinámico ; hash cuckoo ; hash hopscotch ; y hash extensible . ^{[ 13 ]}^{: 42–69}

Una alternativa sencilla al hash perfecto, que también permite actualizaciones dinámicas, es el hash cuckoo . Este esquema asigna claves a dos o más ubicaciones dentro de un rango (a diferencia del hash perfecto, que asigna cada clave a una sola ubicación), pero lo hace de tal manera que las claves se pueden asignar uno a uno a las ubicaciones a las que se han asignado. Las búsquedas con este esquema son más lentas, porque se deben verificar múltiples ubicaciones, pero aun así toman un tiempo constante en el peor de los casos. ^{[ 14 ]}

Referencias

^ Dietzfelbinger , Martín; Karlín, Anna ; Mehlhorn, Kurt ; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (1994), "Hashing dinámico perfecto: límites superiores e inferiores", SIAM Journal on Computing , 23 (4): 738– 761, doi : 10.1137/S0097539791194094 , MR 1283572 .
1 2 3 4 5 Fredman, Michael L .; Komlós, János ; Szemerédi, Endre (1984), "Almacenamiento de una tabla dispersa con $O$ $(1)$ tiempo de acceso en el peor de los casos", Journal of the ACM , 31 (3): 538, doi : 10.1145/828.1884 , MR 0819156 , S2CID 5399743
↑ Lu, 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
1 2 3 4 5 6 7 8 9 10 11 12 Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), "Hash, displace, and compress" (PDF) , Algorithms - ESA 2009 (PDF) , 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 , ISBN 978-3-642-04127-3, MR 2557794 .
↑ Fredman, Michael L. ; Komlós, János (1984), "Sobre el tamaño de los sistemas separadores y familias de funciones hash perfectas", SIAM Journal on Algebraic and Discrete Methods , 5 (1): 61– 68, doi : 10.1137/0605009 , MR 0731857 .
↑ Hagerup, Torben; Tholey, Torsten (2001), "Efficient Minimal Perfect Hashing in Nearly Minimal Space" , STACS 2001 , Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 317–326 , doi : 10.1007/3-540-44693-1_28 , ISBN 978-3-540-41695-1, consultado el 12 de noviembre de 2023{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
↑ Esposito, Emmanuel; Mueller Graf, Thomas; Vigna, Sebastiano (2020), "RecSplit: Hashing perfecto mínimo mediante división recursiva", Actas del Simposio sobre Ingeniería y Experimentos de Algoritmos (ALENEX) de 2020 , Actas , págs. 175–185 , arXiv : 1910.06416 , doi : 10.1137/1.9781611976007.14 .
↑ minimal-perfect-hash (GitHub)
↑ Jenkins, Bob (14 de abril de 2009), "hashing perfecto mínimo que preserva el orden", en Black, Paul E. (ed.), Diccionario de algoritmos y estructuras de datos , Instituto Nacional de Estándares y Tecnología de EE. UU. , consultado el 5 de marzo de 2013.
↑ Fox, Edward A.; Chen, Qi Fan; Daoud, Amjad M.; Heath, Lenwood S. (julio de 1991), "Funciones hash perfectas mínimas que preservan el orden y recuperación de información" (PDF) , ACM Transactions on Information Systems , 9 (3), Nueva York, NY, EE. UU.: ACM: 281–308 , doi : 10.1145/125187.125200 , S2CID 53239140 .
↑ Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus ; Vigna, Sebastiano (noviembre de 2008), "Teoría y práctica del hash perfecto mínimo monótono", Journal of Experimental Algorithmics , 16 , art. n.º 3.2, 26 págs., doi : 10.1145/1963190.2025378 , S2CID 2367401 .
↑ Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (enero de 2023), "Límites ajustados para el hash perfecto mínimo monótono" , Actas del Simposio Anual ACM-SIAM de 2023 sobre Algoritmos Discretos (SODA) , Filadelfia, PA: Society for Industrial and Applied Mathematics, págs. 456–476 , arXiv : 2207.10556 , doi : 10.1137/1.9781611977554.ch20 , ISBN 978-1-61197-755-4, consultado el 27 de abril de 2023{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )
1 2 Timothy A. Davis. "Capítulo 5 Hashing" : subsección "Tablas hash con acceso O(1) en el peor de los casos"
^ Pagh, Rasmus ; Rodler, Flemming Friche (2004), "Cuckoo hash", Journal of Algorithms , 51 (2): 122– 144, doi : 10.1016/j.jalgor.2003.12.002 , MR 2050140 .

Lecturas adicionales

Richard J. Cichelli. Funciones hash perfectas mínimas simplificadas , Communications of the ACM, vol. 23, número 1, enero de 1980.
Thomas H. Cormen , Charles E. Leiserson , Ronald L. Rivest y Clifford Stein . Introducción a los algoritmos , tercera edición. Prensa del MIT, 2009. ISBN 978-0262033848. Sección 11.5: Hashing perfecto, págs. 267, 277 – 282.
Fabiano C. Botelho, Rasmus Pagh y Nivio Ziviani. "Hashing perfecto para aplicaciones de gestión de datos" .
Fabiano C. Botelho y Nivio Ziviani . "Hash externo perfecto para conjuntos de claves muy grandes" . 16ª Conferencia ACM sobre Gestión de la Información y el Conocimiento (CIKM07), Lisboa, Portugal, noviembre de 2007.
Djamal Belazzougui, Paolo Boldi, Rasmus Pagh y Sebastiano Vigna. «Hashing perfecto mínimo monótono: búsqueda en una tabla ordenada con O(1) accesos» . En Actas del 20.º Simposio Anual ACM-SIAM sobre Matemáticas Discretas (SODA), Nueva York, 2009. ACM Press.
Marshall D. Brain y Alan L. Tharp. «Hashing casi perfecto de grandes conjuntos de palabras». Software—Práctica y experiencia, vol. 19(10), 967-078, octubre de 1989. John Wiley & Sons.
Douglas C. Schmidt, GPERF: Un generador de funciones hash perfecto , Informe de C++, SIGS, Vol. 10, No. 10, noviembre/diciembre de 1998.
Hans-Peter Lehmann, Thomas Mueller, Rasmus Pagh, Giulio Ermanno Pibiri, Peter Sanders, Sebastiano Vigna, Stefan Walzer, "Modern Minimal Perfect Hashing: A Survey", arXiv : 2506.06536 , junio de 2025. Analiza los avances posteriores a 1997 en este campo.

Enlaces externos

gperf es un generador de hash perfecto de código abierto escrito en C y C++ (muy rápido, pero solo funciona para conjuntos pequeños).
Hash perfecto mínimo (algoritmo de Bob) por Bob Jenkins
cmph : Biblioteca de hash perfecto mínimo en C, implementaciones de código abierto para muchos hashes perfectos (mínimos) (funciona para conjuntos grandes).
Sux4J : función hash perfecta mínima monótona de código abierto en Java
MPHSharp : métodos de hash perfectos en C#
BBHash : función hash perfecta mínima en C++ de solo cabecera
Perfect::Hash , generador de hash perfecto en Perl que genera código C. Incluye una sección de "técnicas previas" que vale la pena consultar.

[DynamicPerfectHashing-1] Dietzfelbinger , Martín; Karlín, Anna ; Mehlhorn, Kurt ; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (1994), "Hashing dinámico perfecto: límites superiores e inferiores", SIAM Journal on Computing , 23 (4): 738– 761, doi : 10.1137/S0097539791194094 , MR 1283572 .

[inventor-2] 1 2 3 4 5 Fredman, Michael L .; Komlós, János ; Szemerédi, Endre (1984), "Almacenamiento de una tabla dispersa con $O$ $(1)$ tiempo de acceso en el peor de los casos", Journal of the ACM , 31 (3): 538, doi : 10.1145/828.1884 , MR 0819156 , S2CID 5399743

[3] Lu, 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

[CHD-4] 1 2 3 4 5 6 7 8 9 10 11 12 Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), "Hash, displace, and compress" (PDF) , Algorithms - ESA 2009 (PDF) , 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 , ISBN 978-3-642-04127-3, MR 2557794 .

[5] Fredman, Michael L. ; Komlós, János (1984), "Sobre el tamaño de los sistemas separadores y familias de funciones hash perfectas", SIAM Journal on Algebraic and Discrete Methods , 5 (1): 61– 68, doi : 10.1137/0605009 , MR 0731857 .

[6] Hagerup, Torben; Tholey, Torsten (2001), "Efficient Minimal Perfect Hashing in Nearly Minimal Space" , STACS 2001 , Berlín, Heidelberg: Springer Berlin Heidelberg, pp. 317–326 , doi : 10.1007/3-540-44693-1_28 , ISBN 978-3-540-41695-1, consultado el 12 de noviembre de 2023{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )

[RecSplit-7] Esposito, Emmanuel; Mueller Graf, Thomas; Vigna, Sebastiano (2020), "RecSplit: Hashing perfecto mínimo mediante división recursiva", Actas del Simposio sobre Ingeniería y Experimentos de Algoritmos (ALENEX) de 2020 , Actas , págs. 175–185 , arXiv : 1910.06416 , doi : 10.1137/1.9781611976007.14 .

[8] -perfect-hash (GitHub)

[9] Jenkins, Bob (14 de abril de 2009), "hashing perfecto mínimo que preserva el orden", en Black, Paul E. (ed.), Diccionario de algoritmos y estructuras de datos , Instituto Nacional de Estándares y Tecnología de EE. UU. , consultado el 5 de marzo de 2013.

[10] Fox, Edward A.; Chen, Qi Fan; Daoud, Amjad M.; Heath, Lenwood S. (julio de 1991), "Funciones hash perfectas mínimas que preservan el orden y recuperación de información" (PDF) , ACM Transactions on Information Systems , 9 (3), Nueva York, NY, EE. UU.: ACM: 281–308 , doi : 10.1145/125187.125200 , S2CID 53239140 .

[11] Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus ; Vigna, Sebastiano (noviembre de 2008), "Teoría y práctica del hash perfecto mínimo monótono", Journal of Experimental Algorithmics , 16 , art. n.º 3.2, 26 págs., doi : 10.1145/1963190.2025378 , S2CID 2367401 .

[12] Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (enero de 2023), "Límites ajustados para el hash perfecto mínimo monótono" , Actas del Simposio Anual ACM-SIAM de 2023 sobre Algoritmos Discretos (SODA) , Filadelfia, PA: Society for Industrial and Applied Mathematics, págs. 456–476 , arXiv : 2207.10556 , doi : 10.1137/1.9781611977554.ch20 , ISBN 978-1-61197-755-4, consultado el 27 de abril de 2023{{citation}}: CS1 mantenimiento: parámetro de trabajo con ISBN ( enlace )

[davis-13] 1 2 Timothy A. Davis. "Capítulo 5 Hashing" : subsección "Tablas hash con acceso O(1) en el peor de los casos"

[14] Pagh, Rasmus ; Rodler, Flemming Friche (2004), "Cuckoo hash", Journal of Algorithms , 51 (2): 122– 144, doi : 10.1016/j.jalgor.2003.12.002 , MR 2050140 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

menos

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]