Función hash perfecta

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

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

Las desventajas de las funciones hash perfectas son que es necesario conocer $S para la construcción de la función hash perfecta.$ Las funciones hash perfectas no dinámicas deben reconstruirse si $S$ cambia. Para cambios frecuentes $de S, se pueden utilizar$ funciones hash dinámicas perfectas a costa de espacio adicional. ^[1] El requisito de espacio para almacenar la función hash perfecta está en $O (n)$ donde $n$ es el número de claves en la estructura.

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

Solicitud

Se puede utilizar una función hash perfecta con valores en un rango limitado para operaciones de búsqueda eficientes, colocando claves de $S$ (u otros valores asociados) en una tabla de búsqueda indexada por la salida de la función. Luego, se puede probar si una clave está presente en $S$ o buscar un valor asociado con esa clave, buscándolo en su celda de la tabla. Cada una de estas búsquedas lleva un tiempo constante en el peor de los casos . ^[2] Con un hash perfecto, los datos asociados se pueden leer o escribir con un único acceso a la tabla. ^[3]

Rendimiento de funciones hash perfectas.

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

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 Bits por elemento. Para un hash perfecto mínimo, $ε = 0$ , el límite inferior es $log e \approx 1,44$ bits por elemento. ^[4] $\log e-\varepsilon \log {\frac {1+\varepsilon }{\varepsilon }}$

Construcción

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

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

Si $k$ se elige al azar, es probable que este paso tenga colisiones, pero es probable que el número de elementos $ni$ $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 muestran 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 al azar hasta encontrar uno que funcione. ^[2]

La función hash en sí requiere espacio de almacenamiento $O (n)$ para almacenar $k$ , $p$ y todas las funciones modulares lineales de segundo nivel. Calcular el valor hash de una clave $x$ determinada 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$ . Se puede utilizar una versión modificada de este esquema de dos niveles con una mayor cantidad de valores en el nivel superior para construir una función hash perfecta que asigne $S$ a un rango más pequeño de longitud $n + o (n)$ . ^[2]

Belazzougui, Botelho y Dietzfelbinger (2009) describen un método más reciente para construir una función hash perfecta como "hash, desplazar y comprimir". Aquí también se utiliza una función hash de primer nivel $g$ para asignar 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 depósito se procesan mediante una función hash de una secuencia de funciones hash independientes completamente aleatorias $(Φ 1, Φ 2, Φ 3, ...)$ , comenzando con $Φ 1$ . Si la función hash no produce ninguna colisión para el depósito y los valores resultantes aún no están ocupados por otros elementos de otros depósitos, se elige la función para ese depósito. De lo contrario, se prueba la siguiente función hash de la secuencia. ^[4]

Para evaluar la función hash perfecta $h (x)$ solo hay que guardar el mapeo σ del índice del depósito $g (x)$ en la función hash correcta en la secuencia, lo que da como resultado $h(x) = Φ σ(g(x))$ . ^[4]

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

Este enfoque necesita un tiempo lineal en $n$ para la construcción y un tiempo de evaluación constante. El tamaño de la representación está en $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, y los valores más bajos necesitan un mayor tiempo de cálculo. El límite inferior del espacio en este escenario es 0,88 bits/clave. ^[4]

Pseudocódigo

El algoritmo de  hash, desplazamiento y compresión  es
(1) Dividir S en depósitos  $B i := g -1 ({i})\capS,0 \leq i < r$ 
(2) Ordenar los depósitos B _i en orden descendente según el tamaño |B _yo |(3) Inicializar la matriz T[0...m-1] con 0(4) para todo i  ∈[r], en el orden desde (2), haga
(5) para l  ←  1,2,...(6) repetir formando K _i  ←  {  $Φ$ _l (x)|x  ∈  B _i }(6) hasta |K _i |=|B _i | y K _i ∩{j|T[j]=1}=  ∅(7) sea σ(i):= el l exitoso(8) para todo j  ∈  K _i sea T[j]:=  1(9) Transforme (σ _i ) _0≤i<r en forma comprimida, conservando el 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 pueda calcularse en tiempo constante requiere al menos un número de bits que sea proporcional a el 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\aproximadamente 1,44

bits/llave. ^[4]

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

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

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

Extensiones

Identidad de la dirección de memoria

Un ejemplo trivial pero generalizado de hash perfecto está implícito en el espacio de direcciones de la memoria (virtual) de una computadora. Dado que cada byte de memoria virtual es una ubicación de almacenamiento distinta, única y directamente direccionable, el valor de la dirección inicial donde se almacena cualquier objeto en la memoria puede considerarse un hash perfecto de facto de ese objeto en todo el rango de direcciones de memoria. ^[6]

Hash dinámico perfecto

Usar una función hash perfecta es mejor en situaciones donde hay un conjunto grande consultado con frecuencia, $S$ , que rara vez se actualiza. Esto se debe a que cualquier modificación del conjunto $S$ puede provocar que la función hash ya no sea perfecta para el conjunto modificado. Las soluciones que actualizan la función hash cada vez que se modifica el conjunto se conocen como hash dinámico perfecto , ^[1] pero estos métodos son relativamente complicados de implementar.

Función hash mínima perfecta

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 algún conjunto finito $S.$ Entonces $h$ es una función hash perfecta mínima si y sólo si $h (j) = h (k)$ implica $j = k$ ( inyectividad ) y existe un número entero $a$ tal que el rango de $h$ es $a .. a + | S | - 1$ . Se ha demostrado que un esquema de hash perfecto mínimo de propósito general requiere al menos bits/clave. ^[4] Suponiendo que es un conjunto de tamaño que contiene números enteros en el rango , se sabe cómo construir eficientemente una función hash perfecta mínima explícita desde a que utilice bits de espacio y que admita un tiempo de evaluación constante. ^[7] En la práctica, existen esquemas de hash perfectos mínimos que utilizan aproximadamente 1,56 bits/clave si se les da suficiente tiempo. ^[8] $\log _{2}e\aproximadamente 1,44$ $S$ $n$ $[1,2^{o(n)}]$ $S$ $\{1,2,\ldots,n\}$ $n\log _ {2}e+o(n)$

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 "hash, desplazar y comprimir" se puede utilizar para construir $k$ funciones hash perfectas permitiendo hasta $k$ colisiones. Los cambios necesarios para lograr esto son mínimos y están subrayados en el pseudocódigo adaptado a continuación:

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

Conservación del pedido

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

Construcciones relacionadas

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

Pocos algoritmos de tabla hash admiten el 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 sí incluyen: hash perfecto; hash perfecto dinámico ; hashing de cuco ; hash de rayuela ; y hash extensible . ^[13]^{: 42–69}

Una alternativa sencilla al hash perfecto, que también permite actualizaciones dinámicas, es el hash cuco . 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 única ubicación), pero lo hace de tal manera que las claves se pueden asignar uno a uno a las ubicaciones a las que han sido asignadas. mapeado. 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

^ ab 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 superior e inferior", SIAM Journal on Computing , 23 (4): 738–761, doi :10.1137/S0097539791194094, MR 1283572.
^ abcde 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", Simposio internacional IEEE sobre teoría de la información de 2006 , págs. 2774–2778, doi :10.1109/ISIT.2006.261567, ISBN 1-4244-0505-X, S2CID 1494710
^ abcdefghijkl Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), "Hash, desplazar y comprimir" (PDF) , Algoritmos - ESA 2009 (PDF) , Lecture Notes in Computer Science , vol. 5757, Berlín: Springer, págs. 682–693, CiteSeerX 10.1.1.568.130 , doi :10.1007/978-3-642-04128-0_61, ISBN 978-3-642-04127-3, señor 2557794.
^ Fredman, Michael L .; Komlós, János (1984), "Sobre el tamaño de los sistemas de separación y familias de funciones hash perfectas", Revista SIAM sobre métodos algebraicos y discretos , 5 (1): 61–68, doi :10.1137/0605009, SEÑOR 0731857.
^ Witold Litwin; Tadeusz Morzy; Gottfried Vossen (19 de agosto de 1998). Avances en Bases de Datos y Sistemas de Información. Springer Ciencia + Medios comerciales . pag. 254.ISBN _ 9783540649243.
^ Hagerup, Torben; Tholey, Torsten (2001), "Hash perfecto mínimo y eficiente en un espacio casi mínimo", STACS 2001 , Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 317–326, doi :10.1007/3-540-44693-1_28, ISBN 978-3-540-41695-1, recuperado el 12 de noviembre de 2023
^ Espósito, Emmanuel; Müller Graf, Thomas; Vigna, Sebastiano (2020), "RecSplit: Minimal Perfect Hashing via Recursive Splitting", 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.978161197600 7. 14.
^ Jenkins, Bob (14 de abril de 2009), "hash 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 3 de marzo de 2013. 05
^ Zorro, Edward A.; Chen, Qi Fan; Daoud, Amjad M.; Heath, Lenwood S. (julio de 1991), "Recuperación de información y funciones hash perfectas mínimas que preservan el orden" (PDF) , ACM Transactions on Information Systems , Nueva York, NY, EE. UU.: ACM, 9 (3): 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. No. 3.2, 26 páginas, doi :10.1145/1963190.2025378, S2CID 2367401.
^ Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (enero de 2023), "Tight Bounds for Monotone Minimal Perfect Hashing", Actas del Simposio anual ACM-SIAM de 2023 sobre algoritmos discretos (SODA) , Filadelfia, PA: Sociedad de Matemáticas Industriales y Aplicadas, págs. , arXiv : 2207.10556 , doi :10.1137/1.9781611977554.ch20, ISBN 978-1-61197-755-4, recuperado el 27 de abril de 2023
^ ab 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.

Otras lecturas

Richard J. Cichelli. Funciones hash mínimas y perfectas simplificadas , Comunicaciones del 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: Hash 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. "Hash perfecto mínimo monótono: búsqueda en una tabla ordenada con accesos O (1)". En actas del vigésimo simposio anual ACM-SIAM sobre matemáticas discretas (SODA), Nueva York, 2009. ACM Press.
Marshall D. Brain y Alan L. Tharp. "Hash casi perfecto de conjuntos de palabras grandes". 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 C++, SIGS, vol. 10, N° 10, noviembre/diciembre de 1998.

enlaces externos

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