Hash dinámico perfecto

Técnica de programación para resolver valores hash duplicados en una estructura de datos de tabla hash

En informática , el hash dinámico perfecto es una técnica de programación para resolver colisiones en una estructura de datos de tabla hash . ^{[1] [2] [3]} Si bien consume más memoria que sus contrapartes de tabla hash, ^{[ cita necesaria ]} 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 segmento de la tabla hash (de primer nivel) corresponde a una tabla hash separada de segundo nivel. Las claves se procesan dos veces: el primer valor hash se asigna a un determinado depósito en la tabla hash de primer nivel; el segundo valor hash proporciona la posición de esa entrada en la tabla hash de segundo nivel de ese depósito. Se garantiza que la tabla de segundo nivel estará libre de colisiones (es decir, hash perfecto ) durante la construcción. En consecuencia, se garantiza que el costo de búsqueda será O(1) en el peor de los casos . ^[2]

En el caso estático, se nos proporciona de antemano un conjunto con un total de x entradas, cada una con una clave única. Fredman, Komlós y Szemerédi eligen una tabla hash de primer nivel con depósitos de tamaño. ^[2] ${\displaystyle s=2(x-1)}$

Para construir, x entradas se separan en s depósitos mediante la función hash de nivel superior, donde . Luego, para cada depósito con k entradas, se asigna una tabla de segundo nivel con 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 almacena junto con el tabla de picadillo. 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 convierten en hash en la tabla de segundo nivel. ${\displaystyle s=2(x-1)}$ ${\displaystyle k^{2}}$

El tamaño cuadrático del espacio garantiza que la creación aleatoria de una tabla con colisiones sea poco frecuente e independiente del tamaño de k , lo que proporciona un tiempo de construcción amortizado lineal. Aunque cada tabla de segundo nivel requiere espacio cuadrático, si las claves insertadas en la tabla hash de primer nivel están distribuidas uniformemente , la estructura en su conjunto ocupa el espacio esperado, ya que los tamaños de los depósitos son pequeños con alta probabilidad . ^[1] ${\displaystyle k^{2}}$ ${\displaystyle O(n)}$

La función hash de primer nivel se elige específicamente de modo 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 esperado, y más específicamente . Fredman, Komlós y Szemerédi demostraron que dada una familia de funciones hash universal , al menos la mitad de esas funciones tienen esa propiedad. ^[2] ${\displaystyle O(n)}$ ${\displaystyle T<s+4\cdot x}$

Caso dinámico

Dietzfelbinger et al. Presentar un algoritmo de diccionario dinámico que, cuando se agrega incrementalmente un conjunto de n elementos al diccionario, las consultas de membresía siempre se ejecutan en tiempo constante y, por lo tanto, en el peor de los casos, el almacenamiento total requerido es (lineal) y el tiempo de inserción y eliminación amortizado esperado. ( tiempo constante amortizado ). ${\displaystyle O(1)}$ ${\displaystyle O(n)}$ ${\displaystyle O(1)}$

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 la función hash seleccionada aleatoriamente. Debido a que el factor de carga de la tabla de segundo nivel se mantiene bajo , la reconstrucción es poco frecuente y el costo esperado amortizado de las inserciones es . ^[2] De manera similar, el costo esperado amortizado de las eliminaciones es . ^[2] ${\displaystyle 1/k}$ ${\displaystyle O(1)}$ ${\displaystyle O(1)}$

Además, en el caso dinámico no se pueden conocer los tamaños finales de la tabla de nivel superior o de cualquiera de las subtablas. Un método para mantener el espacio esperado de la tabla es solicitar 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 exceda el número de elementos en el momento de la última construcción, el costo amortizado esperado de inserción y eliminación permanece teniendo en cuenta la repetición completa. ${\displaystyle O(n)}$ ${\displaystyle O(1)}$

La implementación del hash dinámico perfecto de 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 Localizar ( x ) es  j  : = h ( x ) si (la posición h j ( x ) de la subtabla T j contiene x (no eliminada)) regresa ( x está en S ) finaliza si  no  regresa ( x no está en S ) fin de lo contrario 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, entonces se elimina la marca.

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 T _j ^del jésimo depósito se reconstruye con una función hash h _j diferente seleccionada aleatoriamente .

la función Insertar ( x ) es  contar = contar + 1; si ( cuenta > M ) Rehash completo( x ); terminar si  no  j = h( x ); if (La posición h j (x) de la subtabla T j contiene x ) if ( x está marcado como eliminado) eliminar el marcador de eliminación; terminar si  terminar si  más  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 hj ( x ) de Tj ; 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 inyectivo 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 ; fin por  fin  si no fin si  más  m j = 2 * max{1, m j }; s j = 2 * m j * ( m j - 1); si la suma total de todos s j ≤ 32 * M 2 / s ( M ) + 4 * M Asigne s j celdas para T j ; Coloque 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 inyectivo 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 ; fin por  fin si  no es así FullRehash( x ); fin más  fin más  fin más fin más  fin más fin

Borrar

La eliminación de x simplemente marca x como eliminado sin eliminación e incrementa el recuento . 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 "Eliminar ( x ) " es una representación de un elemento que no está en el conjunto de todos los elementos posibles U.

la función Eliminar ( x ) es  contar = contar + 1; j = h( x ); si la posición h j ( x ) de la subtabla Tj contiene x , marque x como eliminado; terminar si  no  regresa (x no es miembro de S); terminar  si no ( cuenta >= M ) Rehash completo(-1); terminar si terminar

Reconstrucción completa

Una reconstrucción completa de la tabla de S primero comienza eliminando todos los elementos marcados como eliminados y luego estableciendo el siguiente valor umbral M en algún múltiplo constante del tamaño de S. Una función hash, que divide S en s ( M ) subconjuntos, donde el tamaño del subconjunto j es s _j , se elige repetidamente al azar hasta que:

${\displaystyle \sum _{0\leq j\leq s(M)}s_{j}\leq {\frac {32M^{2}}{s(M)}}+4M.}$

Finalmente, para cada subtabla T _j se elige repetidamente y al azar una función hash h _j de H _sj hasta que h _j sea inyectiva sobre 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 poner todos los elementos no marcados de T en la lista L ; si ( x está en U ) añadir x a L ; finalizar si  cuenta = longitud de la lista L ; M = (1 + c ) * máx{ 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 * m j * ( m j - 1); finaliza hasta  que la suma total de todos los s j ≤ 32 * M 2 / s ( M ) + 4 * M  para todos los j < s ( M ) Asigne espacio s j para la subtabla T j ; repetir  h j = función elegida al azar en H sj ; hasta que  h j sea inyectivo sobre los elementos de la lista L j ; finaliza for  for all x en la lista L j almacena x en la posición h j ( x ) de T j ; fin por fin

Ver también

• hash perfecto

Referencias

1. 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#
2. Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H. y Tarjan, RE 1994. "Hashing perfecto dinámico: límites superiores e inferiores" Archivado el 3 de 2016 -04 en la Wayback Machine . SIAM J. Computación. 23, 4 (agosto de 1994), 738-761. http://portal.acm.org/citation.cfm?id=182370 doi :10.1137/S0097539791194094
3. Erik Demaine, Jeff Lind. 6.897: Estructuras de datos avanzadas. Laboratorio de Ciencias de la Computación e Inteligencia Artificial del MIT. Primavera de 2003.
4. Sí, Chee. "Construcción universal para el proyecto FKS". Universidad de Nueva York . Universidad de Nueva York . Consultado el 15 de febrero de 2015 .^{[ enlace muerto permanente ]}