Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Dynamic perfect hashing
Résumé
In computer science, dynamic perfect hashing is a programming technique for resolving collisions in a hash table data structure.
While more memory-intensive than its hash table counterparts, this technique is useful for situations where fast queries, insertions, and deletions must be made on a large set of elements.
static hashing#FKS Hashing
The problem of optimal static hashing was first solved in general by Fredman, Komlós and Szemerédi. In their 1984 paper, they detail a two-tiered hash table scheme in which each bucket of the (first-level) hash table corresponds to a separate second-level hash table. Keys are hashed twice—the first hash value maps to a certain bucket in the first-level hash table; the second hash value gives the position of that entry in that bucket's second-level hash table. The second-level table is guaranteed to be collision-free (i.e. perfect hashing) upon construction. Consequently, the look-up cost is guaranteed to be O(1) in the worst-case.
In the static case, we are given a set with a total of x entries, each one with a unique key, ahead of time.
Fredman, Komlós and Szemerédi pick a first-level hash table with size buckets.
To construct, x entries are separated into s buckets by the top-level hashing function, where . Then for each bucket with k entries, a second-level table is allocated with slots, and its hash function is selected at random from a universal hash function set so that it is collision-free (i.e. a perfect hash function) and stored alongside the hash table. If the hash function randomly selected creates a table with collisions, a new hash function is randomly selected until a collision-free table can be guaranteed. Finally, with the collision-free hash, the k entries are hashed into the second-level table.
The quadratic size of the space ensures that randomly creating a table with collisions is infrequent and independent of the size of k, providing linear amortized construction time.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.