Hash table

Not to be confused withHash listorHash tree.

"Rehash" redirects here. For theSouth Parkepisode, seeRehash (South Park).

Hash table
Type	Unorderedassociative array
Invented	1953
Time complexityinbig O notation Operation Average Worst case Search Θ(1) O(n) Insert Θ(1) O(n) Delete Θ(1) O(n) Space complexity Space Θ(n) O(n)

A small phone book as a hash table

Incomputing,ahash tableis adata structurethat implements anassociative array,also called adictionaryor simplymap;an associative array is anabstract data typethat mapskeystovalues.A hash table uses ahash functionto compute anindex,also called ahash code,into an array ofbucketsorslots,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. A map implemented by a hash table is called ahash map.

Most hash table designs employ animperfect hash function.Hash collisions,where the hash function generates the same index for more than one key, therefore typically must be accommodated in some way.

In a well-dimensioned hash table, the average time complexity for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions ofkey–value pairs,atamortizedconstant average cost per operation.

Hashing is an example of aspace-time tradeoff.Ifmemoryis infinite, the entire key can be used directly as an index to locate its value with a single memory access. On the other hand, if infinite time is available, values can be stored without regard for their keys, and abinary searchorlinear searchcan be used to retrieve the element.

In many situations, hash tables turn out to be on average more efficient thansearch treesor any othertablelookup structure. For this reason, they are widely used in many kinds of computersoftware,particularly forassociative arrays,database inde xing,caches,andsets.

History

The idea of hashing arose independently in different places. In January 1953,Hans Peter Luhnwrote an internalIBMmemorandum that used hashing with chaining. The first example ofopen addressingwas proposed by A. D. Linh, building on Luhn's memorandum.Around the same time,Gene Amdahl,Elaine M. McGraw,Nathaniel Rochester,andArthur SamuelofIBM Researchimplemented hashing for theIBM 701assembler.Open addressing with linear probing is credited to Amdahl, althoughAndrey Ershovindependently had the same idea.The term "open addressing" was coined byW. Wesley Petersonin his article which discusses the problem of search in large files.

The firstpublishedwork on hashing with chaining is credited toArnold Dumey,who discussed the idea of using remainder modulo a prime as a hash function.The word "hashing" was first published in an article by Robert Morris.Atheoretical analysisof linear probing was submitted originally by Konheim and Weiss.

Overview

Anassociative arraystores asetof (key, value) pairs and allows insertion, deletion, and lookup (search), with the constraint ofunique keys.In the hash table implementation of associative arrays, an array$A$of length$m$is partially filled with$n$elements, where$m\geq n$.A value$x$gets stored at an index location$A[h(x)]$,where$h$is a hash function, and$h(x)<m$.Under reasonable assumptions, hash tables have bettertime complexitybounds on search, delete, and insert operations in comparison toself-balancing binary search trees.

Hash tables are also commonly used to implement sets, by omitting the stored value for each key and merely tracking whether the key is present.

Load factor

Aload factor$\ Alpha$is a critical statistic of a hash table, and is defined as follows: $${\text{load factor}}\ (\ Alpha )={\frac {n}{m}},$$ where

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

The performance of the hash table deteriorates in relation to the load factor$\ Alpha$.

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

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, and no fixed point beyond which resizing is absolutely needed.

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

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 addressingmustbe resized orrehashedif the load factor$\ Alpha$approaches 1.

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

Hash function

Ahash function$h:U\rightarrow \{0,...,m-1\}$maps the universe$U$of keys to indices or slots within the table, that is,$h(x)\in \{0,...,m-1\}$for$x\in U$.The conventional implementations of hash functions are based on theinteger universe assumptionthat all elements of the table stem from the universe$U=\{0,...,u-1\}$,where thebit lengthof$u$is confined within theword sizeof acomputer architecture.

A hash function$h$is said to beperfectfor a given set$S$if it isinjectiveon$S$,that is, if each element$x\in S$maps to a different value in${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 ininteger universe assumptioninclude hashing by division, hashing by multiplication,universal hashing,dynamic perfect hashing,andstatic perfect hashing.However, hashing by division is the commonly used scheme.

Hashing by division

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

Hashing by multiplication

The scheme in hashing by multiplication is as follows: $$h(x)=\lfloor m{\bigl (}(xA){\bmod {1}}{\bigr )}\rfloor$$ Where$A$is a non-integerreal-valued constantand$m$is the size of the table. An advantage of the hashing by multiplication is that the$m$is not critical.Although any value$A$produces a hash function,Donald Knuthsuggests using thegolden ratio.

Choosing a hash function

Uniform distributionof 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., aPearson's chi-squared testfor 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 apower 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 aprime number.

Foropen addressingschemes, the hash function should also avoidclustering,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.

K-independent hashingoffers 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

See also:2-choice hashing

A search algorithm that uses hashing consists of two parts. The first part is computing ahash functionwhich transforms the search key into anarray index.The ideal case is such that no two search keys hashes to the same array index. However, this is not always the case and is 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

Hash collision resolved by separate chaining

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

In separate chaining, the process involves building alinked listwithkey–value pairfor each search array index. 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 with linked list is a common method of implementation of hash tables. Let$T$and$x$be the hash table and the node respectively, the operation involves as follows:

Chained-Hash-Insert(T,k)
insertxat the head of linked listT[h(k)]

Chained-Hash-Search(T,k)
search for an element with keykin linked listT[h(k)]

Chained-Hash-Delete(T,k)
deletexfrom the linked listT[h(k)]

If the element is comparable eithernumericallyorlexically,and inserted into the list by maintaining thetotal order,it results in faster termination of the unsuccessful searches.

Other data structures for separate chaining

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

Indynamic 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 asperfect hash tableswith$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 usingfusion treefor each buckets also result in constant time for all operations with high probability.

Caching and locality of reference

The linked list of separate chaining implementation may not becache-consciousdue tospatial locality—locality of reference—when the nodes of the linked list are scattered across memory, thus the list traversal during insert and search may entailCPU cacheinefficiencies.

Incache-conscious variantsof collision resolution through separate chaining, adynamic arrayfound to be morecache-friendlyis used in the place where a linked list or self-balancing binary search trees is usually deployed, since thecontiguous allocationpattern of the array could be exploited byhardware-cache prefetchers—such astranslation lookaside buffer—resulting in reduced access time and memory consumption.

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 betterlocality of reference,though as the table gets full, its performance degrades drastically.

Open addressingis another collision resolution technique in which every entry record is stored in the bucket array itself, and the hash resolution is performed throughprobing.When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in someprobe 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$\ Alpha$approaches 1.The probing results in aninfinite loopif the load factor reaches 1, in the case of a completely filled table.Theaverage costof linear probing depends on the hash function's ability todistributethe elementsuniformlythroughout the table to avoidclustering,since formation of clusters 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 ofCPU cachedue tolocality of referencesresulting in reducedmemory latency.

Other collision resolution techniques based on open addressing

Coalesced hashing

Main article:Coalesced hashing

Coalesced hashingis a hybrid of both separate chaining and open addressing in which the buckets or nodes link within the table.The algorithm is ideally suited forfixed memory allocation.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 is also linked to the inserted node's slot which contains its colliding hash address.

Cuckoo hashing

Main article:Cuckoo hashing

Cuckoo hashingis a form of open addressing collision resolution technique which 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 intoinfinite 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 hashingis an open addressing based algorithm which combines the elements ofcuckoo hashing,linear probingand chaining through the notion of aneighbourhoodof 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 inconcurrent settings,thus well suited for implementing resizableconcurrent 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" —anH-bitbit arrayfor indicating therelative distanceof the item which was originally hashed into the current virtual bucket withinH-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 issetto 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 theneighbourhood,i.e.H-1, subsequent swap and hop-info bit array manipulation of each bucket is performed in accordance with its neighbourhoodinvariant 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 longestprobe 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 thetheoretical search cost,it significantly affects thevarianceof thedistributionof the items on the buckets,i.e. dealing withclusterformation 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 arerehashedinto the buckets of the new hash table,since the items cannot be copied over as varying table sizes results in different hash value due tomodulo operation.If a hash table becomes "too empty" after deleting some elements, resizing may be performed to avoid excessivememory usage.

Resizing by moving all entries

Generally, a new hash table with a size double that of the original hash table getsallocatedprivately 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 inreal-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 avoidmemory fragmentationthat triggersheap compactiondue to deallocation of largememory blockscaused 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_{\text{old}}$and$h_{\text{new}}$.The process of rehashing a bucket's items in accordance with the new hash function is termed ascleaning,which is implemented throughcommand patternby encapsulating the operations such as$\mathrm {Add} (\mathrm {key} )$,$\mathrm {Get} (\mathrm {key} )$and$\mathrm {Delete} (\mathrm {key} )$through a$\mathrm {Lookup} (\mathrm {key},{\text{command}})$wrappersuch that each element in the bucket gets rehashed and its procedure involve as follows:

• Clean$\mathrm {Table} [h_{\text{old}}(\mathrm {key} )]$bucket.
• Clean$\mathrm {Table} [h_{\text{new}}(\mathrm {key} )]$bucket.
• Thecommandgets executed.

Linear hashing

Main article:Linear hashing

Linear hashingis 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 generatingquasi-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 the same$\sigma$for distinct keys ($K_{1}\neq K_{2},\ h(K_{1})\ =\ h(K_{2})$), this results incollision,which is dealt with in a variety of 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 isdirectly proportionalto the chosen hash function's ability todispersethe indices.However, construction of such a hash function ispractically infeasible,that being so, implementations depend oncase-specificcollision resolution techniquesin achieving higher performance.

Applications

Associative arrays

Main article:Associative array

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

Database inde xing

Hash tables may also be used asdisk-based data structures anddatabase indices(such as indbm) althoughB-treesare more popular in these applications.

Caches

Main article:Cache (computing)

Hash tables can be used to implementcaches,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

Main article:Set data structure

Hash tables can be used in the implementation ofset data structure,which can store unique values without any particular order; set is typically used in testing the membership of a value in the collection, rather than element retrieval.

Transposition table

Main article:Transposition table

Atransposition tableto a complex Hash Table which stores information about each section that has been searched.

Implementations

Many programming languages provide hash table functionality, either as built-in associative arrays or asstandard librarymodules.

InJavaScript,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 firstcoercedto a string. Aside from the seven "primitive" data types, every value in JavaScript is an object.ECMAScript 2015 also added theMapdata structure, which accepts arbitrary values as keys.

C++11includesunordered_mapin its standard library for storing keys and values ofarbitrary types.

Go's built-inmapimplements a hash table in the form of atype.

Javaprogramming language includes theHashSet,HashMap,LinkedHashSet,andLinkedHashMapgenericcollections.

Python's built-indictimplements a hash table in the form of atype.

Ruby's built-inHashuses the open addressing model from Ruby 2.4 onwards.

Rustprogramming language includesHashMap,HashSetas part of the Rust Standard Library.

The.NETstandard library includesHashSetandDictionary,so it can be used from languages such asC#andVB.NET.

See also

• Bloom filter
• Consistent hashing
• Distributed hash table
• Extendible hashing
• Hash array mapped trie
• Lazy deletion
• Pearson hashing
• PhotoDNA
• Rabin–Karp string search algorithm
• Search data structure
• Stable hashing
• Succinct hash table

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.ISBN978-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.S2CID12854386.

External links

• NISTentry onhash tables
• Open Data Structures – Chapter 5 – Hash Tables,Pat Morin
• MIT's Introduction to Algorithms: Hashing 1MIT OCW lecture Video
• MIT's Introduction to Algorithms: Hashing 2MIT OCW lecture Video