Lineal hashing

Lineal hashing es un algoritmo dinámico de tabla hash inventado por Witold Litwin (1980),[1]​ y más tarde popularizado por Paul Larson. Lineal hashing permite la expansión de la tabla hash un espacio a la vez.

La frecuente expansión de solo un espacio puede controlar de manera muy eficaz la cantidad de colisión de cadenas. El costo de la expansión de una tabla hash se propaga por cada operación de inserción en la tabla hash, en lugar de ser incurridos todos a la vez[2]​ por lo tanto, lineal hashing es muy adecuado para aplicaciones interactivas.

Detalles del AlgoritmoEditar

En primer lugar, la tabla hash inicial se configura con un número arbitrario de cubos. De los siguientes valores debe mantenerse un registro:

  •  : El número inicial de cubos.
  •  : El nivel actual, que es un número entero que indica en una escala logarítmica aproximadamente cuántos cubos la tabla ha crecido. Este es en un principio  .
  •  : Un puntero que apunta a un cubo. Inicialmente apunta a la primera cubeta en la tabla.

Las colisiones de los cubos pueden ser manejados en una variedad de maneras, pero es típico de tener espacio para dos elementos de cada cubo y añadir más cubos cada vez que un cubo se desborda. Más de dos elementos pueden ser utilizados una vez que se depura la aplicación. Las direcciones se calculan de la siguiente manera:

  • Aplicar una función hash para la clave y llamar al resultado  .
  • Si   es una dirección que viene antes de  , la dirección es  .
  • Si   es   o una dirección que viene después de  , la dirección es  .

Para agregar un cubo:

  • Asignar un nuevo cubo al final de la tabla.
  • Si   apunta al   º cubo en la tabla, resetear   e incrementa  .
  • De lo contrario incrementar  .

El efecto de todo esto es que la tabla se divide en tres secciones; la sección antes de  , la sección de   a  , y la sección después de  . Las primeras y últimas secciones se almacenan utilizando   y la sección central se almacena utilizando  . Cada vez que   alcances   de la tabla se ha duplicado en tamaño.

Puntos para reflexionarEditar

  • Cubos llenos no necesariamente se separaron y se requiere un espacio de contención para cubos con desbordamiento temporal. En almacenamiento externo, esto podría significar un segundo archivo.
  • No se dividen necesariamente todos los cubos
  • Cada cubo se dividirá tarde o temprano, y así todos los desbordamientos se recuperarán.
  • El puntero para la división s decide qué balde dividir
    • s es independiente del cubo desbordado
    • A nivel i, s es entre 0 y 2 ^ i
    • S se incrementa y si está al final, se pone a 0.
    • Desde que un cubo en s se divide entonces s se incrementa, solo los cubos antes de s tienen el segundo espacio de hash duplicado.
    • Un buen número seudo aleatorio x grande se obtiene primero, y luego es bit- enmascarado con (2 ^ i) -1 o (2 ^ (i + 1)) -1, pero este último solo se aplica si x fue bit-enmascarado antes con (2 ^ i) - 1 y es menor que S, por lo que la gama más amplia de valores de hash solo se aplican a cubos que ya han sido divididos.
    • Ejem. Para bit-enmascarar un número, utilice x & 0111, en donde & es el operador AND, 111 es binario 7, donde 7 = 8 - 1 y 8 es 2 ^ 3 y i = 3.
    • ¿Y si s aterriza en un cubo que tiene 1 o más cubos completamente desbordados? La división solo reducirá el número de cubo desbordados por 1, y los cubos de desbordamiento restantes tendrán que ser recreados para ver cuál de los nuevos 2 cubos, o a sus cubos de desbordados, las entradas de los desbordados pertenecen.
  • H i (k) = h (k) mod (2 ^ i n)
  • H i + 1 duplica el rango de h i

Algoritmo para insertar 'k' y comprobar la condición de desbordamientoEditar

  • B = h 0 (k)
  • Si b <puntero de división entonces
  • B = h 1 (k)

Buscando en la tabla hash para 'k'Editar

  • B = h 0 (k)
  • Si b <puntero de división entonces
  • B = h 1 (k)
  • Leer balde b y buscar allí

Adopción en sistemas de lenguajeEditar

Griswold y Townsend[3]​ discutió la adopción de lineal hashing en el idioma Icono. Hablaron de las alternativas de implementación de matriz dinámica algoritmo utilizado en el lineal hashing, y presentaron comparaciones de rendimiento utilizando una lista de Icon de aplicaciones de referencia.

Adopción en sistemas de bases de datosEditar

Lineal Hashing  se utiliza en el sistema de base de datos BDB Berkeley, que a su vez es utilizado por muchos sistemas de software como OpenLDAP, utilizando una aplicación C derivado del artículo MCCA y publicado por primera vez en Usenet en 1988 por Esmond Pitt.

ReferenciasEditar

  1. Litwin, Witold (1980), «Lineal hash: Una nueva herramienta para el archivo y la tabla de direccionamiento» (PDF), Proc. Sexta Conferencia de las bases de datos muy grandes .
  2. Larson, Per-Åke (04 1988), «Dinámico Hash Tables», Comunicaciones del ACM 31 (4): 446-457, doi:10.1145/42.404,42410 .
  3. Griswold, William G.; Townsend, Gregg M. (04 1993), «El Diseño e Implementación de Dinámica Hashing de Conjuntos y Tablas en Icon», Software - Práctica y Experiencia 23 (4): trescientos cincuenta y uno hasta trescientos sesenta y siete .

Enlaces externosEditar

Véase tambiénEditar