Hashing Lineal

El hashing lineal provee algunas ventajas sobre el extendible. Para comenzar, requiere almacenar sólo $O(1)$ datos en memoria, por lo que puede manejar conjuntos arbitrariamente grandes de datos. Segundo, permite controlar el porcentaje de llenado de los bloques, o bien el costo promedio de búsqueda (pero no ambos).

Pensemos primero que el archivo de hashing en disco tuviera siempre $2^t$ páginas. Un elemento $y$ está guardado en la página número $h(y) \!\!\mod 2^t$ (es decir, los $t$ bits más bajos de $h(y)$). Si algunas páginas rebalsan durante las inserciones, les creamos una lista enlazada de páginas de rebalse. Si, luego de un rebalse, notamos que el costo de búsqueda (es decir, 1 más el largo promedio de las listas de rebalse) se ha hecho demasiado alto, expandimos la tabla. Expandir significa duplicar su tamaño a $2^{t+1}$. Cada página $i$, con $0 \le i < 2^t$, se recorre y sus elementos $y$ se reinsertan en la página $h(y) \!\!\mod 2^{t+1}$. Esto significa que una parte de los elementos se quedan en la página $i$, mientras que otros se insertan en la página $i+2^t$.

El hashing lineal funciona de esa forma, pero realiza el proceso de expansión de manera gradual. En general, el archivo contiene $p$ páginas, con $2^t \le p < 2^{t+1}$. Inicialmente tenemos $p=1$ páginas y $t=0$. Las páginas $0 \le i < p-2^t$ ya fueron expandidas, y repartidas entre las páginas $i$ e $i+2^t$, mientras que las páginas $p-2^t \le i < 2^t$ aún no han sido expandidas.

Para buscar un elemento $y$ en el caso general, se calcula $k \leftarrow h(y) \!\!\mod 2^{t+1}$. Si $k < p$, entonces se lee la página $k$ (y su posible lista de rebalse) para buscar la clave $y$ en ella, secuencialmente. Si $k \ge p$, sin embargo, la página $k$ aún no ha sido creada por el proceso de expansión, por lo cual el proceso de lectura debe realizarse en cambio en la página $k \leftarrow k - 2^t$.

Cuando se cumple una determinada condición (por ejemplo, el costo promedio de búsqueda supera un cierto valor permitido), expandimos la siguiente página, es decir, la página $p-2^t$ (¡que no es necesariamente la que produjo el rebalse que llevó a exceder el costo promedio de búsqueda permitido!). Esta página se lee y sus elementos $y$ se reinsertan en las páginas $h(y) \!\!\mod 2^{t+1}$, es decir, se reparten entre la misma $p-2^t$ y la nueva página $p$, que se agrega al final del archivo. Al terminar la expansión, hacemos $p \leftarrow p+1$, y si resulta que $p=2^{t+1}$, entonces hemos completado una expansión y nos preparamos para la siguiente: $t \leftarrow t+1$. Para eliminar un valor, éste se busca en la tabla y simplemente se elimina. En caso de estar en una lista de rebalse, puede usarse su espacio para mover un elemento desde la última página de la lista, de modo de poder liberar apenas se pueda esta última página y reducir así el tiempo promedio de búsqueda. Si se eliminan suficientes elementos, puede resultar que la tabla pueda contraerse sin que se exceda el costo promedio de búsqueda máximo permitido. Para realizar una contracción, primero se hace $t \leftarrow t-1$ si $p=2^t$, y luego se hace $p \leftarrow p-1$. Luego, se agregan todos los elementos de la página $p$ a la página $p-2^t$, procediendo a eliminar la página $p$. Note que esto puede hacer rebalsar la página $p-2^t$, o alargar su lista de rebalse.

Note que una expansión o una contracción no necesariamente cambiarán la condición que las disparó acerca del costo promedio de búsqueda. En general es preferible, para evitar que una inserción o borrado disparen muchas expansiones o contracciones, realizar de todas maneras una sola, y dejar que la siguiente operación dispare nuevamente una expansión o contracción, hasta que la situación se resuelva.

Se pueden usar otros criterios en vez del máximo costo promedio de búsqueda. Por ejemplo, puede permitirse un mínimo porcentaje de llenado de las páginas, de modo de contraer cuando éste se hace demasiado bajo (y expandir cuando es posible sin violar el criterio). Este criterio se contrapone al de mantener un costo de búsqueda máximo, por lo que sólo se puede controlar uno de los dos (o puede usarse una combinación de criterios). En general el hashing lineal se comporta mejor que el extendible, aunque no suele garantizar un solo acceso por lectura.