Dynamic perfect hashing | EPFL Graph Search

Are you an EPFL student looking for a semester project?

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

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.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (2)

Related concepts (3)

Related courses (1)

Related lectures (10)

CS-322: Introduction to database systems

This course provides a deep understanding of the concepts behind data management systems. It covers fundamental data management topics such as system architecture, data models, query processing and op

The physical mechanisms underlying the dynamic fragmentation of heterogeneous brittle materials are explored through numerical simulations. The use of computational facilities, rather than experimental or fundamental sciences, ensures the accurate tracking ...

EPFL2010

Fast And Space Efficient Trie Searches

Searching and traversing m-way trees using tries is a well known and broadly used technique. Three algorithms are presented, two have constant insert, search and delete cost, are faster than Hash Trees and can be searched twice as quickly cas Ternary Searc ...

2000

Hash collision

In computer science, a hash collision or hash clash is when two pieces of data in a hash table share the same hash value. The hash value in this case is derived from a hash function which takes a data input and returns a fixed length of bits. Although hash algorithms have been created with the intent of being collision resistant, they can still sometimes map different data to the same hash (by virtue of the pigeonhole principle). Malicious users can take advantage of this to mimic, access, or alter data.

Hash table

In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an index, also called a hash code, into an array of buckets or slots, from which the desired value can be found. During lookup, the key is hashed and the resulting hash indicates where the corresponding value is stored.

Hash function

A hash function is any function that can be used to map data of arbitrary size to fixed-size values, though there are some hash functions that support variable length output. The values returned by a hash function are called hash values, hash codes, digests, or simply hashes. The values are usually used to index a fixed-size table called a hash table. Use of a hash function to index a hash table is called hashing or scatter storage addressing.

Hash Tables: Rehashing for Improved Performance CS-108: Practice of object-oriented programming

Explores optimizing hash tables through rehashing for improved performance.

Forced Oscillations and Resonance

Explores forced oscillations, resonance, steady state response, and the combination of modes for multiple oscillators.

Hashing and Sorting CS-322: Introduction to database systems

Covers hashing, sorting, extendible hashing, linear hashing, and external sorting.