Hashing extensible

$${\displaystyle h(k_{4})=011110}$$

Ahora, se debe insertar k ₄ , y tiene los dos primeros bits como 01..(1110), y usando una profundidad de 2 bits en el directorio, esto se asigna de 01 al Cubo A. El Cubo A está lleno (tamaño máximo 1), por lo que debe dividirse; como hay más de un puntero al Cubo A, no hay necesidad de aumentar el tamaño del directorio.

Lo que se necesita es información sobre:

1. El tamaño de la clave que mapea el directorio (la profundidad global), y
2. El tamaño de la clave que previamente ha mapeado el cubo (la profundidad local)

Para distinguir los dos casos de acción:

1. Duplicar el directorio cuando un depósito se llena
2. Crear un nuevo depósito y redistribuir las entradas entre el depósito antiguo y el nuevo.

Al examinar el caso inicial de una estructura hash extensible, si cada entrada de directorio apunta a un bucket, entonces la profundidad local debería ser igual a la profundidad global.

El número de entradas del directorio es igual a 2 ^{de profundidad global} , y el número inicial de cubetas es igual a 2 ^{de profundidad local} .

Por lo tanto, si la profundidad global = profundidad local = 0, entonces 2 ⁰ = 1, por lo que un directorio inicial de un puntero a un cubo.

Volvamos a los dos casos de acción; si el cubo está lleno:

1. Si la profundidad local es igual a la profundidad global, entonces solo hay un puntero al bucket, y no hay otros punteros de directorio que puedan mapearse al bucket, por lo que el directorio debe duplicarse.
2. Si la profundidad local es menor que la profundidad global, entonces existe más de un puntero desde el directorio al bucket, y el bucket puede dividirse.

La clave 01 apunta al Cubo A, y la profundidad local del Cubo A de 1 es menor que la profundidad global del directorio de 2, lo que significa que las claves hasheadas al Cubo A solo han usado un prefijo de 1 bit (es decir, 0), y el cubo necesita tener su contenido dividido usando claves de 1 + 1 = 2 bits de longitud; en general, para cualquier profundidad local d donde d es menor que D, la profundidad global, entonces d debe incrementarse después de una división del cubo, y el nuevo d se usa como el número de bits de la clave de cada entrada para redistribuir las entradas del cubo anterior en los nuevos cubos.

Ahora, $${\displaystyle h(k_{4})=011110}$$ Se intenta de nuevo, con 2 bits 01.., y ahora la clave 01 apunta a un nuevo cubo, pero aún hay${\displaystyle k_{2}}$en él (${\displaystyle h(k_{2})=010110}$y también comienza con 01).

Si​${\displaystyle k_{2}}$Si hubiera sido 000110, con la clave 00, no habría habido problema, porque${\displaystyle k_{2}}$⁠ habría permanecido en el nuevo cubo A' y el cubo D habría estado vacío.

(Este habría sido, con diferencia, el caso más probable cuando los depósitos son de tamaño superior a 1 y es extremadamente improbable que los depósitos recién divididos se desborden, a menos que todas las entradas se volvieran a combinar en un solo depósito. Pero para enfatizar la importancia de la información de profundidad, el ejemplo se desarrollará lógicamente hasta el final).

Por lo tanto, el Cubo D debe dividirse, pero una comprobación de su profundidad local, que es 2, es la misma que la profundidad global, que también es 2, por lo que el directorio debe dividirse de nuevo para poder almacenar claves con suficiente detalle, por ejemplo, de 3 bits.

1. El cubo D debe dividirse porque está lleno.
2. Como la profundidad local de D es igual a la profundidad global, el directorio debe duplicarse para aumentar el detalle de bits de las claves.
3. La profundidad global ha aumentado a 3 después de la división del directorio.
4. La nueva entrada${\displaystyle k_{4}}$⁠ se vuelve a cambiar la clave con una profundidad global de 3 bits y termina en D que tiene una profundidad local de 2, que ahora se puede incrementar a 3 y D se puede dividir en D' y E.
5. El contenido del cubo dividido D ,${\displaystyle k_{2}}$⁠ , se ha vuelto a cambiar la clave con 3 bits y termina en D'.
6. Se vuelve a intentar con K4 y termina en E, que tiene una ranura libre.

Ahora,${\displaystyle h(k_{2})=010110}$está en D y${\displaystyle h(k_{4})=011110}$Se intenta de nuevo, con 3 bits 011.., y apunta al cubo D que ya contiene ⁠${\displaystyle k_{2}}$⁠ así que está lleno; la profundidad local de D es 2 pero ahora la profundidad global es 3 después de la duplicación del directorio, por lo que ahora D se puede dividir en los buckets D' y E, el contenido de D, ⁠${\displaystyle k_{2}}$tiene su ${\displaystyle h(k_{2})}$Se volvió a intentar con una nueva máscara de bits de profundidad global de 3 y${\displaystyle k_{2}}$⁠ termina en D', luego la nueva entrada ⁠${\displaystyle k_{4}}$Se vuelve a intentar con${\displaystyle h(k_{4})}$Se aplica una máscara de bits utilizando el nuevo conteo global de bits de profundidad de 3, lo que da como resultado 011, que ahora apunta a un nuevo cubo E que está vacío. Por lo tanto ,${\displaystyle k_{4}}$⁠ va en el Cubo E.