Hashing estático

Dado que el hash 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 cambia con poca frecuencia también son aptas, ya que solo requeriría un rehash completo 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 importantes para el personal de una organización, etc. ^{[ 1 ]}

El hash perfecto es un modelo de hash en el que cualquier conjunto de${\displaystyle n}$Los elementos se pueden almacenar en una tabla hash de igual tamaño y se pueden realizar búsquedas en tiempo constante. Fue descubierto y analizado específicamente por Fredman, Komlos y Szemeredi (1984) y, por lo tanto, se le ha apodado "hashing FKS". ^{[ 2 ]}

El nivel superior contiene una función hash creada aleatoriamente,${\displaystyle h(x)}$, que se ajusta a las restricciones de una función hash de Carter y Wegman del hash universal . Habiendo hecho esto, el nivel superior deberá contener${\displaystyle n}$cubos etiquetados${\displaystyle k_{1},k_{2},k_{3},...,k_{n}}$Siguiendo este patrón, todos los cubos contienen una tabla hash de tamaño${\displaystyle s_{i}}$y una función hash respectiva${\displaystyle h_{i}(x)}$La función hash se decidirá mediante la configuración${\displaystyle s_{i}}$a${\displaystyle k_{i}^{2}}$y recorriendo aleatoriamente las funciones hasta que no haya colisiones. Esto se puede hacer en tiempo constante.

Porque hay${\displaystyle n \choose 2}$pares de elementos, de los cuales tienen una probabilidad de colisión igual a${\displaystyle 1/n}$, el hash FKS puede esperar tener estrictamente menos de${\displaystyle n/2}$colisiones. Basándose en este hecho y en que cada${\displaystyle h(x)}$se seleccionó de manera que el número de colisiones fuera como máximo${\displaystyle n/2}$, el tamaño de cada mesa en el nivel inferior no será mayor que${\displaystyle 2n}$.