Hash table

Overview

An associative array stores a set of (key, value) pairs and allows insertion, deletion, and lookup (search), with the constraint of unique keys. In the hash table implementation of associative arrays, an array ${\displaystyle A}$ of length ${\displaystyle m}$ is partially filled with ${\displaystyle n}$ elements, where ${\displaystyle m\ge n}$. A key ${\displaystyle x}$ is hashed using a hash function ${\displaystyle h}$ to compute an index location ${\displaystyle A[h(x)]}$ in the hash table, where ${\displaystyle h(x)<m}$. At this index, both the key and its associated value are stored. Storing the key alongside the value ensures that lookups can verify the key at the index to retrieve the correct value, even in the presence of collisions. Under reasonable assumptions, hash tables have better time complexity bounds on search, delete, and insert operations in comparison to self-balancing binary search trees.

Load factor

The efficiency of a hash table depends on the load factor (${\displaystyle \alpha }$), defined as the ratio of the number of stored elements to the number of available slots, with lower load factors generally yielding faster operations. Load factor is a critical statistic of a hash table, and is defined as follows: $${\displaystyle \text{load factor}(\alpha )=\frac{n}{m},}$$ where

• ${\displaystyle n}$ is the number of key-value pairs in the hash table.
• ${\displaystyle m}$ is the number of buckets.

The performance of the hash table deteriorates in relation to the load factor ${\displaystyle \alpha }$. In the limit of large ${\displaystyle m}$ and ${\displaystyle n}$, each bucket statistically has a Poisson distribution with expectation ${\displaystyle \lambda =\alpha }$ for an ideally random hash function.

The implementation of a hash table typically ensures that the load factor ${\displaystyle \alpha }$ remains below a certain constant, ${\displaystyle {\alpha }_{max}}$. This helps maintain good performance. Therefore, a common approach is to resize or "rehash" the hash table whenever the load factor ${\displaystyle \alpha }$ reaches ${\displaystyle {\alpha }_{max}}$. Similarly the table may also be resized if the load factor drops below ${\displaystyle {\alpha }_{max}/4}$.

Load factor for open addressing

With open addressing, each slot of the bucket array holds exactly one item. Therefore an open-addressed hash table cannot have a load factor greater than 1.

The performance of open addressing becomes very bad when the load factor approaches 1. Therefore a hash table that uses open addressing must be resized or rehashed if the load factor ${\displaystyle \alpha }$ approaches 1.

With open addressing, acceptable figures of max load factor ${\displaystyle {\alpha }_{max}}$ should range around 0.6 to 0.75.

Load factor for separate chaining

With separate chaining hash tables, each slot of the bucket array stores a pointer to a list or array of data.

Separate chaining hash tables suffer gradually declining performance as the load factor grows, unlike the sharply decreasing performance of open addressing hash tables around ${\displaystyle \alpha =1}$. There is not a fixed point with respect to load factor beyond which resizing is absolutely needed.

With separate chaining, the value of ${\displaystyle {\alpha }_{max}}$ that gives best performance is typically between 1 and 3.

Hash function

A hash function ${\displaystyle h:U\to \{0,...,m-1\}}$ maps the universe ${\displaystyle U}$ of keys to indices or slots within the table, that is, ${\displaystyle h(x)\in \{0,...,m-1\}}$ for ${\displaystyle x\in U}$. The conventional implementations of hash functions are based on the integer universe assumption that all elements of the table stem from the universe ${\displaystyle U=\{0,...,u-1\}}$, where the bit length of ${\displaystyle u}$ is confined within the word size of a computer architecture.

A hash function ${\displaystyle h}$ is said to be perfect for a given set ${\displaystyle S}$ if it is injective on ${\displaystyle S}$, that is, if each element ${\displaystyle x\in S}$ maps to a different value in ${\displaystyle 0,...,m-1}$. A perfect hash function can be created if all the keys are known ahead of time.

Integer universe assumption

The schemes of hashing used in integer universe assumption include hashing by division, hashing by multiplication, universal hashing, dynamic perfect hashing, and static perfect hashing. However, hashing by division is the commonly used scheme.

Hashing by division

The scheme in hashing by division is as follows: $${\displaystyle h(x)=xmodm,}$$ where ${\displaystyle h(x)}$ is the hash value of ${\displaystyle x\in S}$ and ${\displaystyle m}$ is the size of the table.

Hashing by multiplication

The scheme in hashing by multiplication is as follows: $${\displaystyle h(x)=\lfloor m((xA)mod1)\rfloor }$$ Where ${\displaystyle A}$ is a non-integer real-valued constant and ${\displaystyle m}$ is the size of the table. An advantage of the hashing by multiplication is that the ${\displaystyle m}$ is not critical. Although any value ${\displaystyle A}$ produces a hash function, Donald Knuth suggests using the golden ratio.

String hashing

Commonly a string is used as a key to the hash function. The third edition of The C++ Programming Language describes a simple hash function in which an unsigned integer that is initially zero is repeatedly left shifted one bit and then xor'ed with the integer value of the next character. This hash value is then taken modulo the table size. If the left shift is not circular, then the string length should be at least eight bits less than the size of the unsigned integer in bits. Another common way to hash a string to an integer is with a polynomial rolling hash function.

Choosing a hash function

Uniform distribution of the hash values is a fundamental requirement of a hash function. 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.

For open addressing schemes, the hash function should also avoid runs, the mapping of two or more keys to consecutive slots. Such runs 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 run behavior.

K-independent hashing offers a way to prove a certain hash function does not have bad keysets for a given type of hashtable. A number of K-independence 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.

Collision resolution

A 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 hash to the same array index. However, this is not always the case and impossible to guarantee for unseen given data. 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

In separate chaining, the process involves building a linked list of key–value pairs for each search array index. The collided items are chained together through a single linked list, which can be traversed during lookup of a specific key. Collision resolution through chaining with linked lists is a common method of implementation of hash tables. Let ${\displaystyle T}$ be the hash table, ${\displaystyle x}$ be an element ${\displaystyle (k,v)}$, and ${\displaystyle k}$ be its key. The operations involved are as follows:

Chained-Hash-Insert(<i id="mwAbY">T</i>, <i id="mwAbc">x</i>) <i id="mwAbg">insert</i> <i id="mwAbk">x</i> <i id="mwAbo">at the head of linked list</i> <i id="mwAbs">T</i>[<i id="mwAbw">h</i>(<i id="mwAb0">k</i>)] Chained-Hash-Search(<i id="mwAb4">T</i>, <i id="mwAb8">k</i>) <i id="mwAcA">search for an element with key</i> <i id="mwAcE">k</i> <i id="mwAcI">in linked list</i> <i id="mwAcM">T</i>[<i id="mwAcQ">h</i>(<i id="mwAcU">k</i>)] Chained-Hash-Delete(<i id="mwAcY">T</i>, <i id="mwAcc">x</i>) <i id="mwAcg">delete</i> <i id="mwAck">x</i> <i id="mwAco">from the linked list</i> <i id="mwAcs">T</i>[<i id="mwAcw">h</i>(<i id="mwAc0">k</i>)]

If the element is comparable either numerically or lexically, and inserted into the list by maintaining the total order, it results in faster termination of unsuccessful searches.

Other data structures for separate chaining

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 ${\displaystyle O(\log n)}$, although it introduces additional complexities.

In dynamic perfect hashing, two-level hash tables are used to reduce the look-up complexity to be a guaranteed ${\displaystyle O(1)}$ in the worst case. In this technique, the buckets of ${\displaystyle k}$ entries are organized as perfect hash tables with ${\displaystyle 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 bucket also result in constant time for all operations with high probability.

Caching and locality of reference

Linked lists in separate chaining may not be cache-conscious due to spatial locality—locality of reference—when the nodes of the linked list are scattered across memory, thus the list traversal during insert and search may entail CPU cache inefficiencies.

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

Open addressing

Open addressing is another collision resolution technique in which every entry record is stored in the bucket array itself, and the hash resolution is performed through probing. 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 an unsuccessful search.

Well-known probe sequences include:

• Linear probing, in which the interval between probes is fixed (usually 1).
• Quadratic probing, in which the interval between probes is increased by adding the successive outputs of a quadratic polynomial to the value given by the original hash computation.
• Double hashing, in which the interval between probes is computed by a secondary hash function.

The performance of open addressing may be slower compared to separate chaining since the probe sequence increases when the load factor ${\displaystyle \alpha }$ approaches 1. The probing results in an infinite loop if the load factor reaches 1, in the case of a completely filled table. The average cost of linear probing depends on the hash function's ability to distribute the elements uniformly throughout the table to avoid runs, since formation of runs would result in increased search time.

Caching and locality of reference

Since the slots are located in successive locations, linear probing could lead to better utilization of CPU cache due to locality of references resulting in reduced memory latency.

Other collision resolution techniques based on open addressing

Coalesced hashing

Coalesced hashing is a hybrid of both separate chaining and open addressing. When an element being inserted is hashed to an occupied bucket, the element is instead inserted into the largest-indexed available slot in the hash table, and the original bucket is linked to that slot using a next pointer. Coalesced hashing is ideally suited for fixed memory allocation.

Cuckoo hashing

Cuckoo hashing is a form of open addressing collision resolution which guarantees ${\displaystyle O(1)}$ worst-case lookup complexity and constant amortized time for insertions. Collisions are 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

Hopscotch hashing is an open addressing based algorithm which combines the elements of cuckoo hashing, linear probing and separate 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 is well suited for implementing resizable concurrent hash tables. The neighbourhood characteristic of hopscotch hashing guarantees the 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 ${\displaystyle k}$ and ${\displaystyle 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 ${\displaystyle 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.

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. It is named after Robin Hood, a mythical heroic outlaw who stole from the rich to give to the poor.

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 long run 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 ${\displaystyle x}$ be the key to be inserted, ${\displaystyle x.\text{psl}}$ be the (incremental) PSL length of ${\displaystyle x}$, ${\displaystyle T}$ be the hash table and ${\displaystyle j}$ be the index, the insertion procedure is as follows:

• If ${\displaystyle x.\text{psl}\le T[j].\text{psl}}$: the iteration goes into the next bucket without attempting an external probe.
• If ${\displaystyle x.\text{psl}>T[j].\text{psl}}$: insert the item ${\displaystyle x}$ into the bucket ${\displaystyle j}$; swap ${\displaystyle x}$ with ${\displaystyle T[j]}$—let it be ${\displaystyle x^{\prime }}$; continue the probe from the ${\displaystyle (j+1)}$th bucket to insert ${\displaystyle x^{\prime }}$; 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 ${\displaystyle 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. The items cannot simply be copied over into the same indices since the hash function depends on the table size. If a hash table becomes "too empty" after deleting some elements, resizing may be performed 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 simple, but computationally expensive.

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 at 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 ${\displaystyle h_{\text{old}}}$ and ${\displaystyle h_{\text{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 ${\displaystyle \mathrm{A}\mathrm{d}\mathrm{d}(\mathrm{k}\mathrm{e}\mathrm{y})}$, ${\displaystyle \mathrm{G}\mathrm{e}\mathrm{t}(\mathrm{k}\mathrm{e}\mathrm{y})}$ and ${\displaystyle \mathrm{D}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{t}\mathrm{e}(\mathrm{k}\mathrm{e}\mathrm{y})}$ through a ${\displaystyle \mathrm{L}\mathrm{o}\mathrm{o}\mathrm{k}\mathrm{u}\mathrm{p}(\mathrm{k}\mathrm{e}\mathrm{y},\text{command})}$ wrapper such that each element in the bucket gets rehashed and its procedure involve as follows:

• Clean ${\displaystyle \mathrm{T}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}[h_{\text{old}}(\mathrm{k}\mathrm{e}\mathrm{y})]}$ bucket.
• Clean ${\displaystyle \mathrm{T}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}[h_{\text{new}}(\mathrm{k}\mathrm{e}\mathrm{y})]}$ bucket.
• The command gets executed.

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.

Performance

The performance of a hash table is dependent on the hash function's ability in generating quasi-random numbers (${\displaystyle \sigma }$) for entries in the hash table where ${\displaystyle K}$, ${\displaystyle n}$ and ${\displaystyle h(x)}$ denotes the key, number of buckets and the hash function such that ${\displaystyle \sigma =h(K)\mathrm{\%}n}$. If the hash function generates the same ${\displaystyle \sigma }$ for distinct keys (${\displaystyle K_1\ne K_2,h(K_1)=h(K_2)}$), this results in a collision. The constant time complexity (${\displaystyle O(1)}$) of various operations 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's ability to disperse the indices. However, construction of such a hash function is practically infeasible, that being so, implementations depend on case-specific collision resolution techniques in achieving higher performance.

The best performance is obtained in the case that the hash function distributes the elements of the universe uniformly, and the elements stored in the table are drawn at random from the universe. In this case, in hashing with chaining, the expected time for a successful search is $1+\frac{\alpha }{2}+\mathrm{\Theta }\left(\frac{1}{m}\right)$, and the expected time for an unsuccessful search is $e^{-\alpha }+\alpha +\mathrm{\Theta }\left(\frac{1}{m}\right)$.

Applications

Associative arrays

Hash tables are commonly used to implement many types of in-memory tables. They are used to implement associative arrays.

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.

Caches

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

Hash tables can be used in the implementation of the set data structure, which can store unique values without any particular order; sets are typically used in testing the membership of a value in a collection, rather than element retrieval. Hash tables are used as sets by omitting the stored value for each key and merely tracking whether the key is present.

Transposition table

Transposition tables, which store previously seen positions and associated evaluations in a search tree, such as a game tree, are typically implemented as hash tables.

Implementations

Many programming languages provide hash table functionality, either as built-in associative arrays or as standard library modules.

• In JavaScript, an "object" is a mutable collection of key–value pairs (called "properties"), where each key is either a string or a guaranteed-unique "symbol"; any other value, when used as a key, is first coerced to a string. Aside from the seven "primitive" data types, every value in JavaScript is an object. ECMAScript 2015 also added the Map data structure, which accepts arbitrary values as keys.
• C++11 includes unordered_map in its standard library for storing keys and values of arbitrary types.
• Go's built-in map implements a map type in the form of a type, which is often (but not guaranteed to be) a hash table.
• Java programming language includes the HashSet, HashMap, LinkedHashSet, and LinkedHashMap generic collections.
• Python's built-in dict implements a hash table in the form of a type.
• Ruby's built-in Hash uses the open addressing model from Ruby 2.4 onwards.
• Rust programming language includes HashMap, HashSet as part of the Rust Standard Library.
• The .NET standard library includes HashSet and Dictionary, so it can be used from languages such as C# and VB.NET.