hash estático
Static Hashing es otra forma del problema hash que permite a los usuarios realizar búsquedas en un conjunto de diccionarios finalizado (todos los objetos en el diccionario son definitivos y no cambian).
Dado que el hashing estático requiere que la base de datos , sus objetos y referencias permanezcan iguales, sus aplicaciones son limitadas. Las bases de datos que contienen información que rara vez cambia también son elegibles, ya que solo requerirían una actualización completa de toda la base de datos en raras ocasiones. Ejemplos de esto incluyen conjuntos de palabras y definiciones de idiomas específicos, conjuntos de datos significativos para el personal de una organización, etc.
El hashing perfecto es un modelo de hashing en el que cualquier conjunto de n elementos se puede almacenar en una tabla hash de igual tamaño y se pueden realizar búsquedas en tiempo constante. Fue descubierto y discutido específicamente por Fredman, Komlos y Szemeredi (1984) y por lo tanto ha sido apodado "FKS Hashing". [2]
FKS Hashing hace uso de una tabla hash con dos niveles en los que el nivel superior contiene n cubos, cada uno de los cuales contiene su propia tabla hash. El hashing FKS requiere que si ocurren colisiones, deben hacerlo solo en el nivel superior.
El nivel superior contiene una función hash creada aleatoriamente, h(x), que se ajusta a las restricciones de una función hash de Carter y Wegman, vista en Universal hashing . Una vez hecho esto, el nivel superior contendrá n cubos etiquetados como k 1 , k 2 , k 3 , ..., k n . Siguiendo este patrón, todos los cubos tienen una tabla hash de tamaño s i y una función hash respectiva, h i (x). La función hash se decidirá configurando s i a k i 2 y pasando aleatoriamente por las funciones hasta que no haya colisiones. Esto se puede hacer en tiempo constante.
Debido a que hay pares de elementos, de los cuales tienen una probabilidad de colisión igual a 1/n, el hashing FKS puede esperar tener estrictamente menos de n/2 colisiones. En base a este hecho y a que cada h(x) se seleccionó de modo que el número de colisiones fuera como máximo n/2, el tamaño de cada tabla en el nivel inferior no será mayor que 2n.
