Hash table

Not to be confused with Hash list or Hash tree.

"Rehash" redirects here. For the South Park episode, see Rehash (South Park). For the IRC command, see List of Internet Relay Chat commands § REHASH.

Hash table
Type	Unordered associative array
Invented	1953
Time complexity in big O notation Operation Average Worst case Search O(1) O(n) Insert O(1) O(n) Delete O(1) O(n) Space complexity Space O(n) O(n)

A small phone book as a hash table

In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map 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.

Ideally, the hash function will assign each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions where the hash function generates the same index for more than one key. Such collisions are typically accommodated in some way.

In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key–value pairs, at (amortized) constant average cost per operation.

In many situations, hash tables turn out to be on average more efficient than search trees or any other table lookup structure. For this reason, they are widely used in many kinds of computer software, particularly for associative arrays, database indexing, caches, and sets.

History

The idea of hashing arose independently in different places. In January 1953, Hans Peter Luhn wrote an internal IBM memorandum that used hashing with chaining. Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester, and Arthur Samuel implemented a program using hashing at about the same time. Open addressing with linear probing (relatively prime stepping) is credited to Amdahl, but Ershov (in Russia) had the same idea.

Hashing

Main article: Hash function

The advantage of using hashing is that the table address of a record can be directly computed from the key. Hashing implies a function $h$, when applied to a key $k$, produces a hash $M$. However, since $M$ could be potentially large, the hash result should be mapped to finite entries in the hash table—or slots—several methods can be used to map the keys into the size of hash table $N$. The most common method is the division method, in which modular arithmetic is used in computing the slot.

$h(k)\ =\ M\ \operatorname {mod} \ N$

This is often done in two steps,

${\text{Hash}}={\text{Hash-Function(Key)}}$

${\text{Index}}={\text{Hash}}\ \%\ {\text{Hash-Table-Size}}$

Choosing a hash function

A basic requirement is that the function should provide a uniform distribution of hash values. A non-uniform distribution increases the number of collisions and the cost of resolving them. Uniformity is sometimes difficult to ensure by design, but may be evaluated empirically using statistical tests, e.g., a Pearson's chi-squared test for discrete uniform distributions.

The distribution needs to be uniform only for table sizes that occur in the application. In particular, if one uses dynamic resizing with exact doubling and halving of the table size, then the hash function needs to be uniform only when the size is a power of two. Here the index can be computed as some range of bits of the hash function. On the other hand, some hashing algorithms prefer to have the size be a prime number. The modulus operation may provide some additional mixing; this is especially useful with a poor hash function.

For open addressing schemes, the hash function should also avoid clustering, the mapping of two or more keys to consecutive slots. Such clustering may cause the lookup cost to skyrocket, even if the load factor is low and collisions are infrequent. The popular multiplicative hash is claimed to have particularly poor clustering behavior.

Cryptographic hash functions are believed to provide good hash functions for any table size, either by modulo reduction or by bit masking. They may also be appropriate if there is a risk of malicious users trying to sabotage a network service by submitting requests designed to generate a large number of collisions in the server's hash tables. However, the risk of sabotage can also be avoided by cheaper methods (such as applying a secret salt to the data). A drawback of cryptographic hashing functions is that they are often slower to compute, which means that in cases where the uniformity for any size is not necessary, a non-cryptographic hashing function might be preferable.

K-independent hashing offers a way to prove a certain hash function doesn't have bad keysets for a given type of hashtable. A number of such results are known for collision resolution schemes such as linear probing and cuckoo hashing. Since K-independence can prove a hash function works, one can then focus on finding the fastest possible such hash function.

Universal hash function is an approach of choosing a hash function randomly in a way that the hash function is independent of the keys that are to be hashed by the function. The possibility of collision between two distinct keys from a set is no more than $1/m$ where $m$ is cardinality.

Perfect hash function

Main article: Perfect hash function

If all keys are known ahead of time, a perfect hash function can be used to create a perfect hash table that has no collisions. If minimal perfect hashing is used, every location in the hash table can be used as well.

Perfect hashing allows for constant time lookups in all cases. This is in contrast to most chaining and open addressing methods, where the time for lookup is low on average, but may be very large, O(n), for instance when all the keys hash to a few values.

Example

In the following C code, minimal perfect hashing is used to quickly find the integer exponent x of any 32-bit integer k, where k = 2^x:

  static const uint8_t hashTable[32] = {  // map hash code to exponent value
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
  };
  
  uint8_t hashFunction(uint32_t k)  // map key to hash code
  {
    return ((uint32_t)(k * 0x077CB531U)) >> 27;
  }
  
  uint8_t getExponent(uint32_t k)  // for the given key k=2^x, return x
  {
    uint8_t hashCode = hashFunction(k);
    return hashTable[hashCode];
  }

The constant 0x077CB531U is one of several possible 32-bit de Bruijn sequences. The hash function multiplies k by the de Bruijn sequence (using arithmetic modulo 2³²), thus producing a 32-bit product in which — due to the de Bruijn sequence — the sequence of the 5 MSBs is unique for each value of k. The 5 MSBs are shifted into the LSB positions to produce a hash code in range 0 to 31. The associated hash table value (selected by the hash code) is the exponent x.

Key statistics

A critical statistic for a hash table is the load factor, defined as

${\text{load factor}}\ (\alpha )={\frac {n}{k}}$,

where

• $n$ is the number of entries occupied in the hash table.
• $k$ is the number of buckets.

The performance of the hash table worsens in relation to the load factor ($\alpha$) i.e. as $\alpha$ approaches 1. Hence, it's essential to resize—or "rehash"—the hash table when the load factor exceeds an ideal value. It's also efficient to resize the hash table if the size is smaller—which is usually done when load factor drops below $\alpha _{max}/4$. Generally, a load factor of 0.6 and 0.75 is an acceptable figure.

Collision resolution

See also: 2-choice hashing

The search algorithm that uses hashing consists of two parts. The first part is computing a hash function which transforms the search key into an array index. The ideal case is such that no two search keys hashes to the same array index, however, this is not always the case, since it's theoretically impossible. Hence the second part of the algorithm is collision resolution. The two common methods for collision resolution are separate chaining and open addressing.

Separate chaining

Hash collision resolved by separate chaining

Hash collision by separate chaining with head records in the bucket array.

Hashing is an example of space-time tradeoff. If there exists a condition where the memory is infinite, single memory access using the key as an index in a (potentially huge) array would retrieve the value—which also implies possible key values are huge. On the other hand, if time is infinite, the values can be stored in minimum possible memory and a linear search through the array can be used to retrieve the element. In separate chaining, the process involves building a linked list with key-value pair for each search array indices. The collided items are chained together through a single linked list, which can be traversed to access the item with a unique search key. Collision resolution through chaining i.e. with a linked list is a common method of implementation. Let $T$ and $x$ be the hash table and the node respectively, the operation involves as follows:

Chained-Hash-Insert(T, x) insert $x$ at the head of linked list $T[h(x.key)]$ Chained-Hash-Search(T, k) search for an element with key $k$ in linked list $T[h(k)]$ Chained-Hash-Delete(T, x) delete $x$ from the linked list $T[h(x.key)]$

If the keys of the elements are ordered, it's efficient to insert the item by maintaining the order when the key is comparable either numerically or lexically, thus resulting in faster insertions and unsuccessful searches. However, the standard method of using a linked list is not cache-conscious since there is little spatial locality—locality of reference—since the nodes of the list are scattered across the memory, hence doesn't make efficient use of CPU cache.

Separate chaining with other structures

If the keys are ordered, it could be efficient to use "self-organizing" concepts such as using a self-balancing binary search tree, through which the theoretical worst case could be brought down to $O(\log {n})$, although it introduces additional complexities.

In cache-conscious variants, a dynamic array found to be more cache-friendly is used in the place where a linked list or self-balancing binary search trees is usually deployed for collision resolution through separate chaining, since the contiguous allocation patten of the array could be exploited by hardware-cache prefetchers—such as translation lookaside buffer—resulting in reduced access time and memory consumption.

In dynamic perfect hashing, two level hash tables are used to reduce the look-up complexity to be a guaranteed $O(1)$ in the worst case. In this technique, the buckets of $k$ entries are organized as perfect hash tables with $k^{2}$ slots providing constant worst-case lookup time, and low amortized time for insertion. A study shows array based separate chaining to be 97% more performant when compared to the standard linked list method under heavy load.

Techniques such as using fusion tree for each buckets also result in constant time for all operations with high probability.

Open addressing

Main article: Open addressing

Hash collision resolved by open addressing with linear probing (interval=1). Note that "Ted Baker" has a unique hash, but nevertheless collided with "Sandra Dee", that had previously collided with "John Smith".

This graph compares the average number of CPU cache misses required to look up elements in large hash tables (far exceeding size of the cache) with chaining and linear probing. Linear probing performs better due to better locality of reference, though as the table gets full, its performance degrades drastically.

In another strategy, called open addressing, all entry records are stored in the bucket array itself. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found. When searching for an entry, the buckets are scanned in the same sequence, until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. The name "open addressing" refers to the location ("address") of the item is not determined by its hash value. (This method is also called closed hashing; it should not be confused with "open hashing" or "closed addressing" which usually means separate chaining.)

Well-known probe sequences include:

• Linear probing, in which the interval between probes is fixed (usually 1). Since the slots are located in successive locations, linear probing could lead to better utilization of CPU cache due to locality of references.
• Quadratic probing, in which the interval between probes is increased by adding the successive outputs of a quadratic polynomial to the starting value given by the original hash computation
• Double hashing, in which the interval between probes is computed by a second hash function

In practice, the performance of open addressing is slower than separate chaining when used in conjunction with an array of buckets for collision resolution, since a longer sequence of array indices may need to be tried to find a given element when the load factor approaches 1. The load factor must be maintained below 1 since if it reaches 1—the case of a completely full table—a search miss would go into an infinite loop through the table. The average cost of linear probing depends on the chosen hash function's ability to distribute the keys uniformly throughout the table to avoid clustering, since formation of clusters would result in increased search time leading to inefficiency.

Coalesced hashing

Main article: Coalesced hashing

Coalesced hashing is a hybrid of both separate chaining and open addressing in which the buckets or nodes link within the table. The algorithm is ideally suited for fixed memory allocation. This method is similar to separate chaining in that it gives a pointer parameter to each bucket that tracks the location of the next collision node, creating a traceable chain of each node that collided at the original index. It also fits under the open addressing umbrella as well since, every element inserted is not particularly located at the index which the hash function initially assigned it to. This is not a trait found in separate chaining. The collision in coalesced hashing is resolved by identifying the largest-indexed empty slot on the hash table, then the colliding value is inserted into that slot. The bucket's pointer is linked to the inserted node's location which contains its colliding hash address.

The performance of coalesced hashing is one of the best amongst all the variants. In a comparative study titled "Implementations for Coalesced Hashing", it was found by Jeffrey Scott Vitter that on average, coalesced hashing out performed other methods like linear probing, double hashing, and Separate Chaining especially when the hash table is fuller than 60%. However, the worst case for deletion using coalesced hashing is extremely costly and is it's most notorious con. Besides following a potentially long chain of pointers, once a deletion occurs, the pointers will need to be reassigned to account for the removal of an element from the hash table. This can prove to be an extremely complicated process.

Cuckoo hashing

Main article: Cuckoo hashing

Cuckoo hashing is a form of open addressing collision resolution technique which provides guarantees $O(1)$ worst-case lookup complexity and constant amortized time for insertions. The collision is resolved through maintaining two hash tables, each having its own hashing function, and collided slot gets replaced with the given item, and the preoccupied element of the slot gets displaced into the other hash table. The process continues until every key has its own spot in the empty buckets of the tables; if the procedure enters into infinite loop—which is identified through maintaining a threshold loop counter—both hash tables get rehashed with newer hash functions and the procedure continues.

Hopscotch hashing

Main article: Hopscotch hashing

Hopscotch hashing is an open addressing based algorithm which combines the elements of cuckoo hashing, linear probing and chaining through the notion of a neighbourhood of buckets—the subsequent buckets around any given occupied bucket, also called a "virtual" bucket. The algorithm is designed to deliver better performance when the load factor of the hash table grows beyond 90%; it also provides high throughput in concurrent settings, thus well suited for implementing resizable concurrent hash table. The neighbourhood characteristic of hopscotch hashing guarantees a property that, the cost of finding the desired item from any given buckets within the neighbourhood is very close to the cost of finding it in the bucket itself; the algorithm attempts to be an item into its neighbourhood—with a possible cost involved in displacing other items.

Each bucket within the hash table includes an additional "hop-information"—an H-bit bit array for indicating the relative distance of the item which was originally hashed into the current virtual bucket within H-1 entries. Let $k$ and $Bk$ be the key to be inserted and bucket to which the key is hashed into respectively; several cases are involved in the insertion procedure such that the neighbourhood property of the algorithm is vowed: if $Bk$ is empty, the element is inserted, and the leftmost bit of bitmap is set to 1; if not empty, linear probing is used for finding an empty slot in the table, the bitmap of the bucket gets updated followed by the insertion; if the empty slot is not within the range of the neighbourhood, i.e. H-1, subsequent swap and hop-info bit array manipulation of each bucket is performed in accordance with its neighbourhood invariant properties.

Hopscotch hashing is non-cyclical, meaning it cannot be caught in an infinite loop like in cuckoo hashing. For this reason it works better than cuckoo hashing when the hash table is fuller, or the load factor is smaller. While with cuckoo hashing the success of a insertion after collision is dependent on the hash function, with hopscotch hashing this is not the case. A simple hash function can attain the same results as complex one without major performance differences.

Robin Hood hashing

Robin hood hashing is an open addressing based collision resolution algorithm; the collisions are resolved through favouring the displacement of the element that is farthest—or longest probe sequence length (PSL)—from its "home location" i.e. the bucket to which the item was hashed into. Although robin hood hashing does not change the theoretical search cost, it significantly affects the variance of the distribution of the items on the buckets, i.e. dealing with cluster formation in the hash table. Each node within the hash table that uses robin hood hashing should be augmented to store an extra PSL value. Let $x$ be the key to be inserted, $x.psl$ be the (incremental) PSL length of $x$, $T$ be the hash table and $j$ be the index, the insertion procedure is as follows:

• If $x.psl\ \leq \ T[j].psl$: the iteration goes into the next bucket without attempting an external probe.
• If $x.psl\ >\ T[j].psl$: insert the item $x$ into the bucket $j$; swap $x$ with $T[j]$—let it be $x'$; continue the probe from the $j+1$st bucket to insert $x'$; repeat the procedure until every element is inserted.

Dynamic resizing

Repeated insertions cause the number of entries in a hash table to grow, which consequently increases the load factor; to maintain the amortized $O(1)$ performance of the lookup and insertion operations, a hash table is dynamically resized and the items of the tables are rehashed into the buckets of the new hash table, since the items cannot be copied over as varying table sizes results in different hash value due to modulo operation. Resizing may be performed on hash tables with fewer entries compared to its size to avoid excessive memory usage.

Resizing by moving all entries

Generally, a new hash table with a size double that of the original hash table gets allocated privately and every item in the original hash table gets moved to the newly allocated one by computing the hash values of the items followed by the insertion operation. Rehashing is computationally expensive despite its simplicity.

Alternatives to all-at-once rehashing

Some hash table implementations, notably in real-time systems, cannot pay the price of enlarging the hash table all at once, because it may interrupt time-critical operations. If one cannot avoid dynamic resizing, a solution is to perform the resizing gradually to avoid storage blip—typically of size 50% of new table's size—during rehashing and to avoid memory fragmentation that triggers heap compaction due to deallocation of large memory blocks caused by the old hash table. In such case, the rehashing operation is done incrementally through extending prior memory block allocated for the old hash table such that the buckets of the hash table remain unaltered. A common approach for amortized rehashing involves maintaining two hash functions $h_{old}$ and $h_{new}$. The process of rehashing a bucket's items in accordance with the new hash function is termed as cleaning, which is implemented through command pattern by encapsulating the operations such as $Add(key)$, $Get(key)$ and $Delete(key)$ through a $Lookup(key,{\bf {{command})}}$ wrapper such that each element in the bucket gets rehashed and its procedure involve as follows:

• Clean $Table[h_{old}(key)]$ bucket.
• Clean $Table[h_{new}(key)]$ bucket.
• The command gets executed.

Linear hashing

Main article: Linear hashing

Linear hashing is an implementation of the hash table which enables dynamic growths or shrinks of the table one bucket at a time.

Hashing for distributed hash tables

Main article: distributed hash table

Another way to decrease the cost of table resizing is to choose a hash function in such a way that the hashes of most values do not change when the table is resized. Such hash functions are prevalent in disk-based and distributed hash tables, where rehashing is prohibitively costly. The problem of designing a hash such that most values do not change when the table is resized is known as the distributed hash table problem. The four most popular approaches are rendezvous hashing, consistent hashing, the content addressable network algorithm, and Kademlia distance.

Performance

The performance of a hash table is dependent on the hash function's ability in generating quasi-random numbers ($\sigma$) for entries in the hash table where $K$, $n$ and $h(x)$ denotes the key, number of buckets and the hash function such that $\sigma \ =\ h(K)\ \%\ n$. If the hash function generates same $\sigma$ for distinct keys ($K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})$), this results in collision, which should be dealt with in several ways. The constant time complexity ($O(1)$) of the operation in a hash table is presupposed on the condition that the hash function doesn't generate colliding indices; thus, the performance of the hash table is directly proportional to the chosen hash function ability to disperse the indice. However, construction of such a hash function is practically unfeasible, that being so, implementations depend on case-specific collision resolution techniques in achieving higher performance.

Uses

Associative arrays

Main article: Associative array

Hash tables are commonly used to implement many types of in-memory tables. They are used to implement associative arrays (arrays whose indices are arbitrary strings or other complicated objects), especially in interpreted programming languages like Ruby, Python, and PHP.

When storing a new item into a multimap and a hash collision occurs, the multimap unconditionally stores both items.

When storing a new item into a typical associative array and a hash collision occurs, but the actual keys themselves are different, the associative array likewise stores both items. However, if the key of the new item exactly matches the key of an old item, the associative array typically erases the old item and overwrites it with the new item, so every item in the table has a unique key.

Database indexing

Hash tables may also be used as disk-based data structures and database indices (such as in dbm) although B-trees are more popular in these applications. In multi-node database systems, hash tables are commonly used to distribute rows amongst nodes, reducing network traffic for hash joins.

Caches

Main article: Cache (computing)

Hash tables can be used to implement caches, auxiliary data tables that are used to speed up the access to data that is primarily stored in slower media. In this application, hash collisions can be handled by discarding one of the two colliding entries—usually erasing the old item that is currently stored in the table and overwriting it with the new item, so every item in the table has a unique hash value.

Sets

Besides recovering the entry that has a given key, many hash table implementations can also tell whether such an entry exists or not.

Those structures can therefore be used to implement a set data structure, which merely records whether a given key belongs to a specified set of keys. In this case, the structure can be simplified by eliminating all parts that have to do with the entry values. Hashing can be used to implement both static and dynamic sets.

Object representation

Several dynamic languages, such as Perl, Python, JavaScript, Lua, and Ruby, use hash tables to implement objects. In this representation, the keys are the names of the members and methods of the object, and the values are pointers to the corresponding member or method.

Unique data representation

Main article: String interning

Hash tables can be used by some programs to avoid creating multiple character strings with the same contents. For that purpose, all strings in use by the program are stored in a single string pool implemented as a hash table, which is checked whenever a new string has to be created. This technique was introduced in Lisp interpreters under the name hash consing, and can be used with many other kinds of data (expression trees in a symbolic algebra system, records in a database, files in a file system, binary decision diagrams, etc.).

Transposition table

Main article: Transposition table

A transposition table to a complex Hash Table which stores information about each section that has been searched.

Implementations

In programming languages

Many programming languages provide hash table functionality, either as built-in associative arrays or as standard library modules. In C++11, for example, the unordered_map class provides hash tables for keys and values of arbitrary type.

The Java programming language (including the variant which is used on Android) includes the HashSet, HashMap, LinkedHashSet, and LinkedHashMap generic collections.

In PHP 5 and 7, the Zend 2 engine and the Zend 3 engine (respectively) use one of the hash functions from Daniel J. Bernstein to generate the hash values used in managing the mappings of data pointers stored in a hash table. In the PHP source code, it is labelled as DJBX33A (Daniel J. Bernstein, Times 33 with Addition).

Python's built-in hash table implementation, in the form of the dict type, as well as Perl's hash type (%) are used internally to implement namespaces and therefore need to pay more attention to security, i.e., collision attacks. Python sets also use hashes internally, for fast lookup (though they store only keys, not values). CPython 3.6+ uses an insertion-ordered variant of the hash table, implemented by splitting out the value storage into an array and having the vanilla hash table only store a set of indices.

In the .NET Framework, support for hash tables is provided via the non-generic Hashtable and generic Dictionary classes, which store key–value pairs, and the generic HashSet class, which stores only values.

In Ruby the hash table uses the open addressing model from Ruby 2.4 onwards.

In Rust's standard library, the generic HashMap and HashSet structs use linear probing with Robin Hood bucket stealing.

ANSI Smalltalk defines the classes Set / IdentitySet and Dictionary / IdentityDictionary. All Smalltalk implementations provide additional (not yet standardized) versions of WeakSet, WeakKeyDictionary and WeakValueDictionary.

Tcl array variables are hash tables, and Tcl dictionaries are immutable values based on hashes. The functionality is also available as C library functions Tcl_InitHashTable et al. (for generic hash tables) and Tcl_NewDictObj et al. (for dictionary values). The performance has been independently benchmarked as extremely competitive.

The Wolfram Language supports hash tables since version 10. They are implemented under the name Association.

Common Lisp provides the hash-table class for efficient mappings. In spite of its naming, the language standard does not mandate the actual adherence to any hashing technique for implementations.

See also

• Rabin–Karp string search algorithm
• Stable hashing
• Consistent hashing
• Extendible hashing
• Lazy deletion
• Pearson hashing
• PhotoDNA
• Search data structure
• Concurrent hash table
• Record (computer science)
• Bloom filter
• Distributed hash table
• Hash array mapped trie

Further reading

• Tamassia, Roberto; Goodrich, Michael T. (2006). "Chapter Nine: Maps and Dictionaries". Data structures and algorithms in Java : [updated for Java 5.0] (4th ed.). Hoboken, NJ: Wiley. pp. 369–418. ISBN 978-0-471-73884-8.
• McKenzie, B. J.; Harries, R.; Bell, T. (February 1990). "Selecting a hashing algorithm". Software: Practice and Experience. 20 (2): 209–224. doi:10.1002/spe.4380200207. hdl:10092/9691. S2CID 12854386.

External links

• A Hash Function for Hash Table Lookup by Bob Jenkins.
• Hash functions by Paul Hsieh
• Design of Compact and Efficient Hash Tables for Java
• NIST entry on hash tables
• Lecture on Hash Tables from Stanford's CS106A
• Open Data Structures – Chapter 5 – Hash Tables, Pat Morin
• MIT's Introduction to Algorithms: Hashing 1 MIT OCW lecture Video
• MIT's Introduction to Algorithms: Hashing 2 MIT OCW lecture Video