[Enciclopedia Online Gratuita] Diccionario de Internet y Tecnologías de la Información y la Comunicación (TIC):
- Detalles
-
Categoría: INTERNET
ıllı Lineal hashing : que es, definición y significado, descargar videos y fotos.
Lineal hashing es un algoritmo activo de tabla hash inventado por Witold Litwin (mil novecientos ochenta),? y después popularizado por Paul Larson. Lineal hashing deja la expansión de la tabla hash un espacio al unísono.
La usual expansión de solo un espacio puede supervisar de forma muy eficiente la cantidad de colisión de cadenas. El costo de la expansión de una tabla hash se extiende por cada operación de inserción en la tabla hash, en vez de ser incurridos todos a la vez? en consecuencia, lineal hashing es muy conveniente para aplicaciones interactivas.
En primer sitio, la tabla hash inicial se configura con un número arbitrario de cubos. De los próximos valores debe sostenerse un registro:
- Nundefined : El número inicial de cubos.
- Lundefined : El nivel actual, que es un número entero que señala en una escala logarítmica más o menos cuántos cubos la tabla ha crecido. Este es en un comienzo 0{\displaystyle cero .
- Sundefined : Un puntero que apunta a un cubo. En un inicio apunta a la primera cubeta en la tabla.
Las choques de los cubos pueden ser manejados en una pluralidad de formas, mas es propio de tener espacio para 2 elementos de cada cubo y agregar más cubos toda vez que un cubo se desborda. Más de 2 elementos pueden ser empleados en el momento en que se depura la aplicación. Las direcciones se calculan de la próxima manera:
- Aplicar una función hash para la clave y llamar al resultado Hundefined .
- Si Hmod(N*2L)undefined es una dirección que viene ya antes de Sundefined , la dirección es Hmod(N*2L+1)undefined .
- Si Hmod(N*2L)undefined es Sundefined o bien una dirección que viene tras Sundefined , la dirección es Hmod(N*2L)undefined .
Para añadir un cubo:
- Asignar un nuevo cubo al final de la tabla.
- Si Sundefined apunta al N*2Lundefined º cubo en la tabla, reiniciar Sundefined y también acrecienta Lundefined .
- De lo opuesto acrecentar Sundefined .
El efecto de todo esto es que la tabla se divide en 3 secciones; la sección ya antes de Sundefined, la sección de Sundefined a N*2Lundefined, y la sección tras N*2Lundefined. Las primeras y últimas secciones se guardan usando Hmod(N*2L)undefined y la sección central se guarda usando Hmod(N*2L)undefined. Toda vez que Sundefined alcances N*2Lundefined de la tabla se ha duplicado en tamaño.
Puntos para reflexionar
- Cubos llenos no necesariamente se apartaron y se requiere un espacio de contención para cubos con desbordamiento temporal. En almacenaje externo, esto podría representar un segundo fichero.
- No se dividen necesariamente todos y cada uno de los cubos
- Cada cubo se va a dividir tarde que temprano, y de esta forma todos y cada uno de los desbordamientos se recobrarán.
- El puntero para la división s decide qué balde dividirs es independiente del cubo desbordadoA nivel i, s es entre 0 y dos ^ iS se acrecienta y si está al final, se pone a 0.Desde que un cubo en s se divide entonces s se acrecienta, solo los cubos ya antes de s tienen el segundo espacio de hash duplicado.Un buen número seudo azaroso x grande se consigue primero, y después es bit- enmascarado con (dos ^ i) -1 o bien (dos ^ (i + 1)) -1, mas este último solo se aplica si x fue bit-enmascarado ya antes con (dos ^ i) - 1 y es menor que S, con lo que la gama más extensa de valores de hash solo se aplican a cubos que han sido divididos.Ejem. Para bit-disfrazar un número, utilice x & ciento once, en donde & es el operador AND, ciento once es binario siete, donde siete = ocho - 1 y ocho es dos ^ tres y i = tres.¿Y si s aterriza en un cubo que tiene 1 o bien más cubos totalmente desbordados? La división solo reducirá el número de cubo desbordados por 1, y los cubos de desbordamiento sobrantes deberán ser recreados para poder ver cuál de los nuevos dos cubos, o bien a sus cubos de desbordados, las entradas de los desbordados pertenecen.
- H i (k) = h (k) mod (dos ^ i n)
- H i + 1 duplica el rango de h i
Algoritmo para introducir 'k' y revisar la condición de desbordamiento
- B = h 0 (k)
- Si b <puntero de división entonces
- B = h 1 (k)
Buscando en la tabla hash para 'k'
- B = h 0 (k)
- Si b <puntero de división entonces
- B = h 1 (k)
- Leer balde b y buscar allí
Griswold y Townsend? discutió la adopción de lineal hashing en el idioma Icono. Charlaron de las opciones alternativas de implementación de matriz activa algoritmo usado en el lineal hashing, y presentaron comparaciones de desempeño usando una lista de Icon de aplicaciones de referencia.
ELIGE TU TEMA DE INTERÉS:
