En informática , una función hash perfecta para un conjunto S es una función hash que asigna distintos elementos en S a un conjunto de números enteros, sin colisiones . En términos matemáticos, es una función inyectiva .
Se pueden usar 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 tiene muchas de las mismas aplicaciones que otras funciones hash, pero con la ventaja de que no es necesario implementar una resolución de colisión . Además, si las claves no son los datos, no es necesario almacenar las claves en la tabla de búsqueda, lo que ahorra espacio.
Solicitud
Se puede usar 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 . [1]
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 que es proporcional al tamaño de S. La construcción original de Fredman, Komlós & Szemerédi (1984) utilizan un esquema de dos niveles para mapear un conjunto S de n elementos a un rango de índices O ( n ) , y luego mapear 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
Si k se elige al azar, 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 mapear cada miembro x de S en el rango asociado con g ( x ) . [1]
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 mapea el subconjunto correspondiente de S en el 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. [1]
La función hash en sí misma requiere espacio de almacenamiento O ( n ) para almacenar k , py 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 ax . Se puede usar una versión modificada de este esquema de dos niveles con un mayor número de valores en el nivel superior para construir una función hash perfecta que mapee S en un rango más pequeño de longitud n + o ( n ) . [1]
Límites inferiores del espacio
El uso de O ( n ) palabras de información para almacenar la función de Fredman, Komlós & 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 proporcional a el tamaño de S . [2]
Extensiones
Hash perfecto dinámico
El uso de una función hash perfecta es mejor en situaciones en las que hay un conjunto grande que se consulta con frecuencia, S , que rara vez se actualiza. Esto se debe a que cualquier modificación del conjunto S puede hacer 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 , [3] pero estos métodos son relativamente complicados 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 manera más formal de expresar esto es: Let j y k sean elementos de un conjunto finito S . Entonces F es una función hash perfecta mínima si y solo si F ( j ) = F ( k ) implica j = k ( inyectividad ) y existe un número entero a tal que el rango de F es a .. a + | S | - 1 . Se ha demostrado que un esquema de hash perfecto mínimo de propósito general requiere al menos 1,44 bits / clave. [4] Los mejores esquemas de hash perfectos mínimos conocidos actualmente se pueden representar usando menos de 1.56 bits / clave si se les da suficiente tiempo. [5]
Conservación de pedidos
Una función hash perfecta mínima F es la preservación del orden si las claves se dan en algún orden a 1 , a 2 , ..., a n y para cualquier clave a j y a k , j < k implica F ( a j )
Construcciones relacionadas
Una alternativa simple 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 sola ubicación) pero lo hace de tal manera que las claves se pueden asignar una a una a las ubicaciones en las que se han mapeado. Las búsquedas con este esquema son más lentas, porque se deben verificar varias ubicaciones, pero, sin embargo, toman un tiempo constante en el peor de los casos. [9]
Referencias
- ↑ a b c d 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", Diario de la ACM , 31 (3): 538, doi : 10.1145 / 828.1884 , MR 0819156
- ^ Fredman, Michael L .; Komlós, János (1984), "Sobre el tamaño de los sistemas de separación y las familias de funciones hash perfectas", SIAM Journal on Algebraic and Discrete Methods , 5 (1): 61–68, doi : 10.1137 / 0605009 , MR 0731857.
- ^ Dietzfelbinger, Martin; Karlin, Anna ; Mehlhorn, Kurt ; Meyer auf der Heide, Friedhelm; Rohnert, Hans; Tarjan, Robert E. (1994), "Hash perfecto dinámico: límites superior e inferior", SIAM Journal on Computing , 23 (4): 738–761, doi : 10.1137 / S0097539791194094 , MR 1283572.
- ^ Belazzougui, Djamal; Botelho, Fabiano C .; Dietzfelbinger, Martin (2009), "Hash, desplazar y comprimir" (PDF) , Algorithms — ESA 2009: 17th Annual European Symposium, Copenhague, Dinamarca, 7-9 de septiembre de 2009, Actas (PDF) , Lecture Notes in Computer Science , 5757 , Berlín: Springer, págs. 682–693, CiteSeerX 10.1.1.568.130 , doi : 10.1007 / 978-3-642-04128-0_61 , MR 2557794.
- ^ Esposito, Emmanuel; Mueller Graf, Thomas; Vigna, Sebastiano (2020), "RecSplit: Minimal Perfect Hashing via Recursive Splitting", Actas de 2020 del Simposio sobre ingeniería de algoritmos y experimentos (ALENEX) , Actas , págs. 175-185, arXiv : 1910.06416 , doi : 10.1137 / 1.9781611976007. 14.
- ^ Jenkins, Bob (14 de abril de 2009), "order-preserving minimal perfect hashing", en negro, Paul E. (ed.), Dictionary of Algorithms and Data Structures , Instituto Nacional de Estándares y Tecnología de EE. UU. , Consultado el 5 de marzo de 2013
- ^ 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, 26pp, doi : 10.1145 / 1963190.2025378.
- ^ Fox, Edward A .; Chen, Qi Fan; Daoud, Amjad M .; Heath, Lenwood S. (julio de 1991), "Order-preserving minimal perfect hash functions and information retrieval" (PDF) , ACM Transactions on Information Systems , Nueva York, NY, EE. UU .: ACM, 9 (3): 281–308, doi : 10.1145 / 125187.125200.
- ^ Pagh, Rasmus ; Rodler, Flemming Friche (2004), "Cuckoo hashing", Journal of Algorithms , 51 (2): 122-144, doi : 10.1016 / j.jalgor.2003.12.002 , MR 2050140.
Otras lecturas
- Richard J. Cichelli. Funciones de hash perfectas mínimas 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 teclas muy grandes" . 16a Conferencia de la 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: Buscando 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.
- Douglas C. Schmidt, GPERF: Un generador de funciones hash perfecto , Informe C ++, SIGS, Vol. 10, No. 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) de Bob Jenkins
- cmph : C Minimal Perfect Hashing Library, implementaciones de código abierto para muchos hash perfectos (mínimos) (funciona para conjuntos grandes)
- Sux4J : hash perfecto mínimo monótono de código abierto en Java
- MPHSharp : métodos hash perfectos en C #
- BBHash : función hash perfecta mínima en C ++ de solo encabezado
- Perfect :: Hash , generador de hash perfecto en Perl que hace código C. Tiene una sección de "estado de la técnica" que vale la pena examinar.