Hashing

Además de buscar todos los objetos en un rango, el árbol B puede encontrar el predecesor o sucesor de un elemento en el conjunto de las claves, mediante una modificación simple del algoritmo de búsqueda. Cuando estas capacidades no son necesarias y sólo se desea poder encontrar un elemento insertado, podemos diseñar estructuras basadas en hashing que, bajo ciertos supuestos razonables, permitan buscar haciendo $O(1)$ accesos al disco en promedio. Para esto bastaría con implementar una tabla normal de hashing en disco. Sin embargo, una tabla normal de hashing requiere o bien conocer de antemano la cantidad de elementos que se almacenarán, para dar un tamaño adecuado a la tabla, o bien incrementar periódicamente el tamaño de la tabla. Esto tiene un costo importante y es especialmente indeseable en memoria externa, que es mucho más lenta. Asimismo, en memoria externa, donde los datos son mucho más masivos y posiblemente persistentes, es menos probable que se tenga una idea aproximada del tamaño de datos que se deberán manejar.

Presentaremos dos esquemas de hashing que buscan ofrecer costo de operación $O(\lceil t/B\rceil)$ basándose en una función de hashing $h(\cdot)$ clásica que produzca $O(t)$ colisiones ($t = O(1)$ si la función está bien diseñada).

📄️ Hashing Extendible

Este esquema de hashing funciona, en promedio, cuando se almacenan $N = O(MB)$

📄️ Hashing Lineal

El hashing lineal provee algunas ventajas sobre el extendible. Para comenzar,