En informática , el hash perfecto dinámico es una técnica de programación para resolver colisiones en una estructura de datos de tabla hash . [1] [2] [3] Aunque consume más memoria que sus contrapartes de tabla hash, [ cita requerida ] esta técnica es útil para situaciones en las que se deben realizar consultas, inserciones y eliminaciones rápidas en un gran conjunto de elementos.
Detalles
Caso estático
Esquema FKS
El problema del hash estático óptimo fue resuelto por primera vez en general por Fredman, Komlós y Szemerédi. [4] En su artículo de 1984, [1] detallan un esquema de tabla hash de dos niveles en el que cada cubo de la tabla hash (de primer nivel) corresponde a una tabla hash de segundo nivel separada. Las claves se hash dos veces: el primer valor hash se asigna a un determinado depósito en la tabla hash de primer nivel; el segundo valor hash da la posición de esa entrada en la tabla hash de segundo nivel de ese depósito. Se garantiza que la tabla del segundo nivel estará libre de colisiones (es decir, un hash perfecto ) en el momento de la construcción. En consecuencia, se garantiza que el coste de búsqueda será O (1) en el peor de los casos . [2]
En el caso estático, se nos da un conjunto con un total de x entradas, cada una con una clave única, de antemano. Fredman, Komlós y Szemerédi eligen una tabla hash de primer nivel con cubos de tamaño s = 2 (x-1) . [2]
Para construir, las entradas x se separan en contenedores s mediante la función hash de nivel superior, donde s = 2 (x-1) . Luego, para cada cubo con k entradas, se asigna una tabla de segundo nivel con k 2 ranuras, y su función hash se selecciona al azar de un conjunto de funciones hash universal para que esté libre de colisiones (es decir, una función hash perfecta ) y se almacene junto a la tabla hash. Si la función hash seleccionada aleatoriamente crea una tabla con colisiones, se selecciona aleatoriamente una nueva función hash hasta que se pueda garantizar una tabla libre de colisiones. Finalmente, con el hash sin colisiones, las k entradas se transfieren a la tabla de segundo nivel.
El tamaño cuadrático del espacio k 2 asegura que la creación aleatoria de una mesa con colisiones sea poco frecuente e independiente del tamaño de k , lo que proporciona un tiempo de construcción lineal amortizado. Aunque cada tabla de segundo nivel requiere espacio cuadrático, si las claves insertadas en la tabla hash de primer nivel se distribuyen uniformemente , la estructura en su conjunto ocupa el espacio O ( n ) esperado , ya que los tamaños de cubos son pequeños con alta probabilidad . [1]
La función hash de primer nivel se elige específicamente para que, para el conjunto específico de x valores clave únicos, el espacio total T utilizado por todas las tablas hash de segundo nivel tenga el espacio O ( n ) esperado , y más específicamente T Fredman, Komlós y Szemerédi demostraron que dada una familia de hash universal de funciones hash, al menos la mitad de esas funciones tienen esa propiedad. [2]
Caso dinámico
Dietzfelbinger y col. presentar un algoritmo de diccionario dinámico que, cuando un conjunto de n elementos se agrega de forma incremental al diccionario, las consultas de membresía siempre se ejecutan en tiempo constante y, por lo tanto, O (1) en el peor de los casos, el almacenamiento total requerido es O (n) (lineal) y O (1) tiempo de inserción y eliminación amortizado esperado ( tiempo constante amortizado ).
En el caso dinámico, cuando se inserta una clave en la tabla hash, si su entrada en su subtabla respectiva está ocupada, se dice que ocurre una colisión y la subtabla se reconstruye en función de su nuevo recuento total de entradas y función hash seleccionada al azar. Debido a que el factor de carga de la tabla de segundo nivel se mantiene bajo (1 / k ), la reconstrucción es poco frecuente y el costo amortizado esperado de inserciones es O (1). [2] De manera similar, el costo amortizado esperado de las eliminaciones es O (1). [2]
Además, los tamaños finales de la tabla de nivel superior o cualquiera de las subtablas no se pueden conocer en el caso dinámico. Un método para mantener el espacio O ( n ) esperado de la tabla es provocar una reconstrucción completa cuando se haya producido un número suficiente de inserciones y eliminaciones. Según los resultados de Dietzfelbinger et al., [2] siempre que el número total de inserciones o eliminaciones supere el número de elementos en el momento de la última construcción, el costo amortizado esperado de inserción y eliminación sigue siendo O (1) con un refrito completo tomado en consideración.
La implementación del hashing perfecto dinámico por Dietzfelbinger et al. utiliza estos conceptos, así como la eliminación diferida , y se muestra en el pseudocódigo a continuación.
Implementación de pseudocódigo
Localizar
la función Locate ( x ) es j : = h ( x ) si (la posición h j ( x ) de la subtabla T j contiene x (no borrada)) return ( x está en S ) end if else return ( x no está en S ) terminar el otro fin
Insertar
Durante la inserción de una nueva entrada x en j , se incrementa el contador de operaciones globales, count .
Si x existe en j , pero está marcado como eliminado, la marca se elimina.
Si x existe en j o en la subtabla T j , y no está marcado como eliminado, entonces se dice que ocurre una colisión y la tabla de segundo nivel del j- ésimo depósito T j se reconstruye con una función hash diferente seleccionada al azar h j .
la función Insertar ( x ) es cuenta = cuenta + 1; si ( cuenta > M ) FullRehash ( x ); end if else j = h ( x ); si (La posición h j (x) de la subtabla T j contiene x ) si ( x está marcado como eliminado) eliminar el marcador de eliminación; end if end if else b j = b j + 1; si ( b j <= m j ) si la posición h j ( x ) de T j está vacía almacenar x en la posición h j ( x ) de T j ; end if else Ponga todos los elementos no marcados de T j en la lista L j ; Agregue x a la lista L j ; b j = longitud de L j ; repetir h j = función elegida al azar en H sj ; hasta que h j sea inyectable sobre los elementos de L j ; para todo y en la lista L j, almacene y en la posición h j ( y ) de T j ; end for end else end if else m j = 2 * max {1, m j }; s j = 2 * metro j * ( metro j - 1); si la suma total de todos s j ≤ 32 * M 2 / s ( M ) + 4 * M Asigne s j celdas para T j ; Ponga todos los elementos no marcados de T j en la lista L j ; Agregue x a la lista L j ; b j = longitud de L j ; repetir h j = función elegida al azar en H sj ; hasta que h j sea inyectable sobre los elementos de L j ; para todo y en la lista L j, almacene y en la posición h j ( y ) de T j ; end for end if else FullRehash ( x ); terminar si no terminar si no terminar si no terminar
Borrar
La eliminación de x simplemente marca x como eliminado sin eliminación y el recuento de incrementos . En el caso de inserciones y eliminaciones, si el recuento alcanza un umbral M, se reconstruye toda la tabla, donde M es un múltiplo constante del tamaño de S al comienzo de una nueva fase . Aquí la fase se refiere al tiempo entre reconstrucciones completas. Tenga en cuenta que aquí el -1 en "Delete ( x )" es una representación de un elemento que no está en el conjunto de todos los elementos U posibles .
la función Delete ( x ) es count = count + 1; j = h ( x ); si la posición h j ( x ) de la subtabla Tj contiene x, marque x como eliminado; end if else return (x no es miembro de S); end else if ( cuenta > = M ) FullRehash (-1); finaliza si finaliza
Reconstrucción completa
Una reconstrucción completa de la mesa de S inicia por primera vez mediante la eliminación de todos los elementos marcados como eliminado, y luego poner el siguiente valor umbral M a alguna constante múltiplo del tamaño de S . Una función hash, que divide S en subconjuntos s ( M ), donde el tamaño del subconjunto j es s j , se elige repetidamente al azar hasta que:
Finalmente, para cada subtabla T j, se elige repetidamente al azar una función hash h j de H sj hasta que h j se inyecta en los elementos de T j . El tiempo esperado para una reconstrucción completa de la tabla de S con tamaño n es O ( n ). [2]
la función FullRehash ( x ) es Ponga todos los elementos sin marcar de T en la lista L ; si ( x está en U ) append x a L ; finaliza si cuenta = longitud de la lista L ; M = (1 + c ) * max { cuenta , 4}; repetir h = función elegida al azar en H s (M) ; para todo j < s ( M ) formar una lista L j para h ( x ) = j ; b j = longitud de L j ; m j = 2 * b j ; s j = 2 * metro j * ( metro j - 1); terminar para hasta que la suma total de todos s j ≤ 32 * M 2 / s ( M ) + 4 * M para todos j < s ( M ) Asignar espacio s j para la subtabla T j ; repetir h j = función elegida al azar en H sj ; hasta que h j sea inyectable sobre los elementos de la lista L j ; fin para para todo x en la lista L j almacenar x en la posición h j ( x ) de T j ; fin por fin
Ver también
Referencias
- ^ a b c Fredman, ML, Komlós, J. y Szemerédi, E. 1984. Almacenamiento de una tabla dispersa con 0 (1) tiempo de acceso en el peor de los casos. J. ACM 31, 3 (junio de 1984), 538-544 http://portal.acm.org/citation.cfm?id=1884#
- ^ a b c d e f g h Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H. y Tarjan, RE 1994. "Dynamic Perfect Hashing: Upper and Límites inferiores " Archivado el 4 de marzo de 2016 en la Wayback Machine . SIAM J. Comput. 23, 4 (agosto de 1994), 738-761. http://portal.acm.org/citation.cfm?id=182370 doi : 10.1137 / S0097539791194094
- ^ Erik Demaine, Jeff Lind. 6.897: Estructuras de datos avanzadas . Laboratorio de Informática e Inteligencia Artificial del MIT. Primavera de 2003.
- ^ Sí, Chee. "Construcción universal para el esquema FKS" . Universidad de Nueva York . Universidad de Nueva York . Consultado el 15 de febrero de 2015 .[ enlace muerto permanente ]