Hash table
In computing, a hash table, also known as hash map, is a data structure that implements a set 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 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 of key–value pairs, at amortized constant average cost per operation. Hashing is an example of a space-time tradeoff. If memory is 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 time is infinite, values can be stored without regard for their keys, and a binary search or linear search can be used to retrieve the element. 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. Open addressing was later proposed by A. D. Linh building on Luhn's paper. Around the same time, Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester, and Arthur Samuel of IBM Research implemented hashing for the IBM 701 assembler. Open addressing with linear probing is credited to Amdahl, although Ershov independently had the same idea. The term "open addressing" was coined by W. Wesley Peterson on his article which discusses the problem of search in large files. The first published work on hashing with chaining is credited to Arnold Dumey, who discussed the idea of using  remainder module a prime as a hash function. The word "hashing" was first published by an article by Robert Morris. A theoretical analysis of linear probing was submitted originally by Konheim and Weiss. Overview. A hash table is an implementation of set abstract data type, which is used for storing a set formula_1 of formula_2 elements in an associative array formula_3 of length formula_4, where formula_5, with better time complexity bounds on search, delete, and insert operations in comparasion to self-balancing binary search trees. A value formula_6 gets stored at an index location formula_7, where formula_8 is a hash  function, and formula_9. Hash function. The conventional implementations of hash functions are based on the "integer universe assumption" that all elements of the table stem from the universe formula_10, where the bit length of formula_11 is confined within the word size of a computer architecture; thus, the hash function formula_8 maps formula_13 for each formula_14 where formula_15. A perfect hash function formula_8 is defined as an injective function such that each element formula_6 in formula_1 maps to a unique value in formula_19. 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: Where formula_21 is the hash digest of formula_15 and formula_23 is the size of the table. Hashing by multiplication. The scheme in hashing by multiplication is as follows: Where formula_21 is a real-valued constant. An advantage of the hashing by multiplication is that the formula_4 is not critical. Although any value real  value formula_3 produces a hash function, Donald Knuth suggests using the golden ratio. Load factor. A "load factor" formula_28 is a critical statistic of a hash table, and is defined as follows: where The performance of the hash table deteriorates in relation to the load factor formula_28. Therefore a hash table is resized or "rehashed" if the load factor formula_28 approaches 1. A table is also resized if the load factor drops below formula_34. Acceptable figures of load factor formula_28 include 0.6 and 0.75. 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 hashes to the same array index, however, this is not always the case, and is impossible to preclude 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 with key-value pair for 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 i.e. with a linked list is a common method of implementation. Let formula_36 and formula_6 be the hash table and the node respectively, the operation involves as follows: 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 termination of insertions and unsuccessful searches. Note that this type of linked list is typically not cache-conscious. There is little spatial locality —locality of reference—when the nodes of the list are scattered across memory, so list traversal during insert or find operations may entail CPU cache inefficiencies. 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 formula_38, 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 pattern 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 formula_39 in the worst case. In this technique, the buckets of formula_31 entries are organized as perfect hash tables with formula_41 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. Open addressing is another collision resolution technique in which every entry records are 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 that there is no such key in the table. Well-known probe sequences include: The performance of open addressing may be slower compared to 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. 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. 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. Cuckoo hashing is a form of open addressing collision resolution technique which guarantees formula_39 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. 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 formula_31 and formula_44 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 formula_44 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. 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 formula_6 be the key to be inserted, formula_47 be the (incremental) PSL length of formula_6, formula_36 be the hash table and formula_50 be the index, the insertion procedure is as follows: 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 formula_39 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 formula_61 and formula_62. 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 formula_63, formula_64 and formula_65 through a formula_66 wrapper such that each element in the bucket gets rehashed and its procedure involve as follows: 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 (formula_69) for entries in the hash table where formula_70, formula_23 and formula_72 denotes the key, number of buckets and the hash function such that formula_73. If the hash function generates same formula_69 for distinct keys (formula_75), this results in "collision", which should be dealt with in several ways. The constant time complexity (formula_39) 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. 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 set 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. 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. C++11 includes codice_1 in its standard library for storing keys and values of arbitary types. Java programming language includes the codice_2, codice_3, codice_4, and codice_5 generic collections. Python's built-in codice_6 implements  a hash table in the form of a type. Ruby the hash table uses the open addressing model from Ruby 2.4 onwards.