hash estático

El hash estático es una forma de hash en la que las búsquedas se realizan en un conjunto de diccionario finalizado (todos los objetos del diccionario son finales y no cambian).

Uso [1]

Solicitud

Dado que el hash estático requiere que la base de datos , sus objetos y la referencia sigan siendo los mismos, sus aplicaciones son limitadas. Las bases de datos que contienen información que rara vez cambia también son elegibles, ya que solo requeriría una repetició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 importantes para el personal de una organización, etc.

hash perfecto

El hash perfecto es un modelo de hash en el que cualquier conjunto de 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 "hashing FKS". ^[2] ${\displaystyle n}$

hash FKS

El hashing FKS utiliza una tabla hash con dos niveles en la que el nivel superior contiene depósitos, cada uno de los cuales contiene su propia tabla hash. El hashing FKS requiere que, si se producen colisiones, lo hagan sólo en el nivel superior. ${\displaystyle n}$

Implementación

El nivel superior contiene una función hash creada aleatoriamente, que se ajusta a las limitaciones de una función hash de Carter y Wegman del hash universal . Una vez hecho esto, el nivel superior contendrá cubos etiquetados . Siguiendo este patrón, todos los depósitos contienen una tabla hash de tamaño y una función hash respectiva . La función hash se decidirá estableciendo funciones y recorriéndolas aleatoriamente hasta que no haya colisiones. Esto se puede hacer en tiempo constante. ${\displaystyle h(x)}$ ${\displaystyle n}$ ${\displaystyle k_{1},k_{2},k_{3},...,k_{n}}$ ${\displaystyle s_{i}}$ ${\displaystyle h_{i}(x)}$ ${\displaystyle s_{i}}$ ${\displaystyle k_{i}^{2}}$

Actuación

Debido a que hay pares de elementos, de los cuales tienen una probabilidad de colisión igual a , se puede esperar que el hashing FKS tenga estrictamente menos colisiones. Basado en este hecho y en que cada una fue seleccionada de manera que el número de colisiones sea como máximo , el tamaño de cada tabla en el nivel inferior no será mayor que . ${\displaystyle n \choose 2}$ ${\displaystyle 1/n}$ ${\displaystyle n/2}$ ${\displaystyle h(x)}$ ${\displaystyle n/2}$ ${\displaystyle 2n}$

Ver también

• Función hash
• Hash dinámico perfecto

Referencias

1. Daniel Roche (2013). SI486D: Aleatoriedad en Computación, Unidad Hashing. Academia Naval de los Estados Unidos, Departamento de Ciencias de la Computación.
2. Michael Fredman; János Komlós; Endre Szemerédi (1984). Almacenamiento de una tabla dispersa con O(1) tiempo de acceso al peor caso. Revista de la ACM (Volumen 31, Número 3).