BREAKING NEWS
Hash table

## Summary

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.

Hash table
TypeUnordered associative array
Invented1953
Time complexity in big O notation
Algorithm Space Average Worst case Θ(n)[1] O(n) Θ(1) O(n) Θ(1) O(n) Θ(1) O(n)
A small phone book as a hash table

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.[2][3][4]

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.[5]: 458

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.[6]: 15  Around the same time, Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester, and Arthur Samuel of IBM Research implemented hashing for the IBM 701 assembler.[7]: 124  Open addressing with linear probing is credited to Amdahl, although Ershov independently had the same idea.[7]: 124-125  The term "open addressing" was coined by W. Wesley Peterson on his article which discusses the problem of search in large files.[6]: 15

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.[6]: 15  The word "hashing" was first published by an article by Robert Morris.[7]: 126  A theoretical analysis of linear probing was submitted originally by Konheim and Weiss.[6]: 15

## Overview

A hash table is an implementation of set abstract data type, which is used for storing a set ${\displaystyle S}$  of ${\displaystyle n=|S|}$  elements in an associative array ${\displaystyle A}$  of length ${\displaystyle m}$ , where ${\displaystyle m\geq n}$ , with better time complexity bounds on search, delete, and insert operations in comparison to self-balancing binary search trees.[6]: 1  A value ${\displaystyle x}$  gets stored at an index location ${\displaystyle A[h(x)]}$ , where ${\displaystyle h}$  is a hash function, and ${\displaystyle h(x) .[6]: 2

A load factor ${\displaystyle \alpha }$  is a critical statistic of a hash table, and is defined as follows:[1]

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

where

• ${\displaystyle n}$  is the number of entries occupied in the hash table.
• ${\displaystyle k}$  is the number of buckets.

The performance of the hash table deteriorates in relation to the load factor ${\displaystyle \alpha }$ .[6]: 2  Therefore a hash table is resized or rehashed if the load factor ${\displaystyle \alpha }$  approaches 1.[8] A table is also resized if the load factor drops below ${\displaystyle \alpha _{max}/4}$ .[8] Acceptable figures of load factor ${\displaystyle \alpha }$  include 0.6 and 0.75.[9][10]: 110

## Hash function

A hash function ${\displaystyle h}$  maps the universe ${\displaystyle U}$  of keys ${\displaystyle h:U\rightarrow \{0,...,m-1\}}$  to array indices or slots within the table for each ${\displaystyle h(x)\in {0,...,m-1}}$  where ${\displaystyle x\in S}$  and ${\displaystyle m . 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.[6]: 2

A perfect hash function ${\displaystyle h}$  is defined as an injective function such that each element ${\displaystyle x}$  in ${\displaystyle S}$  maps to a unique value in ${\displaystyle {0,...,m-1}}$ .[11][12] A perfect hash function can be created if all the keys are known ahead of time.[11]

### 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.[6]: 2  However, hashing by division is the commonly used scheme.[13]: 264 [10]: 110

#### Hashing by division

The scheme in hashing by division is as follows:[6]: 2

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

Where ${\displaystyle M}$  is the hash digest of ${\displaystyle x\in S}$  and ${\displaystyle n}$  is the size of the table.

#### Hashing by multiplication

The scheme in hashing by multiplication is as follows:[6]: 2-3

${\displaystyle h(k)=\lfloor nMA\rfloor \operatorname {mod} \ n}$

Where ${\displaystyle M}$  is a real-valued constant. An advantage of the hashing by multiplication is that the ${\displaystyle m}$  is not critical.[6]: 2-3  Although any value real value ${\displaystyle A}$  produces a hash function, Donald Knuth suggests using the golden ratio.[6]: 3

## 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.[14]: 515  Hence the second part of the algorithm is collision resolution. The two common methods for collision resolution are separate chaining and open addressing.[5]: 458

### 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 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.[5]: 464  Collision resolution through chaining with linked list is a common method of implementation of hash tables. Let ${\displaystyle T}$  and ${\displaystyle x}$  be the hash table and the node respectively, the operation involves as follows:[13]: 258

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

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 the unsuccessful searches.[14]: 520-521

#### 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.[14]: 521

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.[15] A study shows array based separate chaining to be 97% more performant when compared to the standard linked list method under heavy load.[16]: 99

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

#### Caching and locality of reference

The linked list of separate chaining implementation may not be cache-conscious due to spatial localitylocality 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.[16]: 91

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.[18][19][20]

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.

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 an unsuccessful search.[21]

Well-known probe sequences include:

• Linear probing, in which the interval between probes is fixed (usually 1).[22]
• 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.[23]: 272
• Double hashing, in which the interval between probes is computed by a secondary hash function.[23]: 272-273

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.[8][16]: 93  The probing results in an infinite loop if the load factor reaches 1, in the case of a completely filled table.[5]: 471  The average cost of linear probing depends on the hash function's ability to distribute the elements uniformly throughout the table to avoid clustering, since formation of clusters would result in increased search time.[5]: 472

#### 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.[22]

#### Other collision resolution techniques based on open addressing

##### Coalesced hashing

Coalesced hashing is a hybrid of both separate chaining and open addressing in which the buckets or nodes link within the table.[24]: 6–8  The algorithm is ideally suited for fixed memory allocation.[24]: 4  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.[24]: 8

##### Cuckoo hashing

Cuckoo hashing is a form of open addressing collision resolution technique which guarantees ${\displaystyle 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.[25]: 124–125

##### 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.[26]: 351–352  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.[26]: 350  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.[26]: 352

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.[26]: 352  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:[26]: 352-353  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.[26]: 353

##### 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.[27]: 12  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,[28]: 2  i.e. dealing with cluster formation in the hash table.[29] Each node within the hash table that uses robin hood hashing should be augmented to store an extra PSL value.[30] Let ${\displaystyle x}$  be the key to be inserted, ${\displaystyle x.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:[27]: 12-13 [31]: 5

• If ${\displaystyle x.psl\ \leq \ T[j].psl}$ : the iteration goes into the next bucket without attempting an external probe.
• If ${\displaystyle x.psl\ >\ T[j].psl}$ : insert the item ${\displaystyle x}$  into the bucket ${\displaystyle j}$ ; swap ${\displaystyle x}$  with ${\displaystyle T[j]}$ —let it be ${\displaystyle x'}$ ; continue the probe from the ${\displaystyle j+1}$ st bucket to insert ${\displaystyle 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 ${\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,[8] since the items cannot be copied over as varying table sizes results in different hash value due to modulo operation.[32] Resizing may be performed on hash tables with fewer entries compared to its size to avoid excessive memory usage.[33]

### 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.[34]: 478–479

### 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.[35]: 2–3  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_{old}}$  and ${\displaystyle 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 ${\displaystyle Add(key)}$ , ${\displaystyle Get(key)}$  and ${\displaystyle Delete(key)}$  through a ${\displaystyle Lookup(key,{\text{command}})}$  wrapper such that each element in the bucket gets rehashed and its procedure involve as follows:[35]: 3

• Clean ${\displaystyle Table[h_{old}(key)]}$  bucket.
• Clean ${\displaystyle Table[h_{new}(key)]}$  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.[36]

## 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)\ \%\ n}$ . If the hash function generates same ${\displaystyle \sigma }$  for distinct keys (${\displaystyle 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 (${\displaystyle 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.[37]: 1  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.[37]: 2

## Applications

### Associative arrays

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

### 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.[38]

### 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.[39][40]

### 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.[41]

### Transposition table

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

## 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 unordered_map in its standard library for storing keys and values of arbitrary types.[43]

Java programming language includes the HashSet, HashMap, LinkedHashSet, and LinkedHashMap generic collections.[44]

Python's built-in dict implements a hash table in the form of a type.[45]

Ruby the hash table uses the open addressing model from Ruby 2.4 onwards.[46]

## References

1. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). Introduction to Algorithms (3rd ed.). Massachusetts Institute of Technology. pp. 253–280. ISBN 978-0-262-03384-8.
2. ^ Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Archived August 7, 2009, at the Wayback Machine Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms—Fall 2005
3. ^ Knuth, Donald (1998). The Art of Computer Programming. Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 978-0-201-89685-5.
4. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. 221–252. ISBN 978-0-262-53196-2.
5. Sedgewick, Robert; Wayne, Kevin (2011). Algorithms. Vol. 1 (4 ed.). Addison-Wesley Professional – via Princeton University, Department of Computer Science.
6. Mehta, Dinesh P.; Sahni, Sartaj (October 28, 2004). "9: Hash Tables". Handbook of Datastructures and Applications (1 ed.). Taylor & Francis. doi:10.1201/9781420035179. ISBN 978-1-58488-435-4.
7. ^ a b c Konheim, Alan G. (June 21, 2010). Hashing in Computer Science: Fifty Years of Slicing and Dicing. John Wiley & Sons, Inc. doi:10.1002/9780470630617. ISBN 9780470630617.
8. ^ a b c d Mayers, Andrew (2008). "CS 312: Hash tables and amortized analysis". Cornell University, Department of Computer Science. Archived from the original on April 26, 2021. Retrieved October 26, 2021 – via cs.cornell.edu.
9. ^ Maurer, W.D.; Lewis, T.G. (March 1, 1975). "Hash Table Methods". ACM Computing Surveys. Journal of the ACM. 1 (1): 14. doi:10.1145/356643.356645.
10. ^ a b Owolabi, Olumide (February 1, 2003). "Empirical studies of some hashing functions". Information and Software Technology. Department of Mathematics and Computer Science, University of Port Harcourt. 45 (2). doi:10.1016/S0950-5849(02)00174-X – via ScienceDirect.
11. ^ a b Lu, Yi; Prabhakar, Balaji; Bonomi, Flavio (2006), "Perfect Hashing for Network Applications", 2006 IEEE International Symposium on Information Theory: 2774–2778, doi:10.1109/ISIT.2006.261567
12. ^ Belazzougui, Djamal; Botelho, Fabiano C.; Dietzfelbinger, Martin (2009), "Hash, displace, and compress" (PDF), Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings (PDF), Lecture Notes in Computer Science, vol. 5757, Berlin: Springer, pp. 682–693, CiteSeerX 10.1.1.568.130, doi:10.1007/978-3-642-04128-0_61, MR 2557794
13. ^ a b Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). "Chapter 11: Hash Tables". Introduction to Algorithms (2nd ed.). Massachusetts Institute of Technology. ISBN 978-0-262-53196-2.
14. ^ a b c Donald E. Knuth (April 24, 1998). The Art of Computer Programming: Volume 3: Sorting and Searching. Addison-Wesley Professional. ISBN 978-0-201-89685-5.
15. ^ Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003. "Archived copy" (PDF). Archived (PDF) from the original on June 15, 2010. Retrieved June 30, 2008.{{cite web}}: CS1 maint: archived copy as title (link)
16. ^ a b c Askitis, Nikolas; Zobel, Justin (2005). "Cache-Conscious Collision Resolution in String Hash Tables". International Symposium on String Processing and Information Retrieval. Springer Science+Business Media. doi:10.1007/11575832_1. ISBN 978-3-540-29740-6.
17. ^ Willard, Dan E. (2000). "Examining computational geometry, van Emde Boas trees, and hashing from the perspective of the fusion tree". SIAM Journal on Computing. 29 (3): 1030–1049. doi:10.1137/S0097539797322425. MR 1740562..
18. ^ Askitis, Nikolas; Sinha, Ranjan (2010). "Engineering scalable, cache and space efficient tries for strings". The VLDB Journal. 17 (5): 634. doi:10.1007/s00778-010-0183-9. ISSN 1066-8888. S2CID 432572.
19. ^ Askitis, Nikolas; Zobel, Justin (October 2005). Cache-conscious Collision Resolution in String Hash Tables. Proceedings of the 12th International Conference, String Processing and Information Retrieval (SPIRE 2005). Vol. 3772/2005. pp. 91–102. doi:10.1007/11575832_11. ISBN 978-3-540-29740-6.
20. ^ Askitis, Nikolas (2009). Fast and Compact Hash Tables for Integer Keys (PDF). Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009). Vol. 91. pp. 113–122. ISBN 978-1-920682-72-9. Archived from the original (PDF) on February 16, 2011. Retrieved June 13, 2010.
21. ^ Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C. Prentice Hall. pp. 456–461, p. 472. ISBN 978-0-13-199746-2.
22. ^ a b Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithms — ESA 2001. Lecture Notes in Computer Science. Vol. 2161. pp. 121–133. CiteSeerX 10.1.1.25.4189. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.
23. ^ a b c Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), "11 Hash Tables", Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 221–252, ISBN 0-262-03293-7.
24. ^ a b c Vitter, Jeffery S.; Chen, Wen-Chin (1987). The design and analysis of coalesced hashing. New York, United States: Oxford University Press. ISBN 978-0-19-504182-8 – via Archive.org.
25. ^ Pagh, Rasmus; Rodler, Flemming Friche (2001). "Cuckoo Hashing". Algorithms — ESA 2001. Lecture Notes in Computer Science. Vol. 2161. CiteSeerX 10.1.1.25.4189. doi:10.1007/3-540-44676-1_10. ISBN 978-3-540-42493-2.
26. Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Hopscotch Hashing". International Symposium on Distributed Computing. Distributed Computing. Berlin, Heidelberg: Springer Publishing. 5218. doi:10.1007/978-3-540-87779-0_24. ISBN 978-3-540-87778-3 – via Springer Link.
27. ^ a b Celis, Pedro (1986). Robin Hood Hashing (PDF). Ontario, Canada: University of Waterloo, Dept. of Computer Science. ISBN 031529700X. OCLC 14083698. Archived (PDF) from the original on November 1, 2021. Retrieved November 2, 2021.
28. ^ Poblete, P.V.; Viola, A. (August 14, 2018). "Analysis of Robin Hood and Other Hashing Algorithms Under the Random Probing Model, With and Without Deletions". Combinatorics, Probability and Computing. Cambridge University Press. 28 (4). doi:10.1017/S0963548318000408. ISSN 1469-2163. Retrieved November 1, 2021 – via Cambridge Core.
29. ^ Clarkson, Michael (2014). "Lecture 13: Hash tables". Cornell University, Department of Computer Science. Archived from the original on October 7, 2021. Retrieved November 1, 2021 – via cs.cornell.edu.
30. ^ Gries, David (2017). "JavaHyperText and Data Structure: Robin Hood Hashing" (PDF). Cornell University, Department of Computer Science. Archived (PDF) from the original on April 26, 2021. Retrieved November 2, 2021 – via cs.cornell.edu.
31. ^ Celis, Pedro (March 28, 1988). External Robin Hood Hashing (PDF) (Technical report). Bloomington, Indiana: Indiana University, Department of Computer Science. 246. Archived (PDF) from the original on November 2, 2021. Retrieved November 2, 2021.
32. ^ Goddard, Wayne (2021). "Chater C5: Hash Tables" (PDF). Clemson University. pp. 15–16. Archived (PDF) from the original on November 9, 2021. Retrieved November 9, 2021 – via people.cs.clemson.edu.
33. ^ Devadas, Srini; Demaine, Erik (February 25, 2011). "Intro to Algorithms: Resizing Hash Tables" (PDF). Massachusetts Institute of Technology, Department of Computer Science. Archived (PDF) from the original on May 7, 2021. Retrieved November 9, 2021 – via MIT OpenCourseWare.
34. ^ Thareja, Reema (October 13, 2018). "Hashing and Collision". Data Structures Using C (2 ed.). Oxford University Press. ISBN 9780198099307.
35. ^ a b Friedman, Scott; Krishnan, Anand; Leidefrost, Nicholas (March 18, 2003). "Hash Tables for Embedded and Real-time systems" (PDF). All Computer Science and Engineering Research. Washington University in St. Louis. doi:10.7936/K7WD3XXV. Archived (PDF) from the original on June 9, 2021. Retrieved November 9, 2021 – via Northwestern University, Department of Computer Science.
36. ^ Litwin, Witold (1980). "Linear hashing: A new tool for file and table addressing" (PDF). Proc. 6th Conference on Very Large Databases. Carnegie Mellon University. pp. 212–223. Archived (PDF) from the original on May 6, 2021. Retrieved November 10, 2021 – via cs.cmu.edu.
37. ^ a b Dijk, Tom Van (2010). "Analysing and Improving Hash Table Performance" (PDF). Netherlands: University of Twente. Archived (PDF) from the original on November 6, 2021. Retrieved December 31, 2021.
38. ^ Lech Banachowski. "Indexes and external sorting". pl:Polsko-Japońska Akademia Technik Komputerowych. Archived from the original on March 26, 2022. Retrieved March 26, 2022.
39. ^ Zhong, Liang; Zheng, Xueqian; Liu, Yong; Wang, Mengting; Cao, Yang (February 2020). "Cache hit ratio maximization in device-to-device communications overlaying cellular networks". China Communications. 17 (2): 232–238. doi:10.23919/jcc.2020.02.018. ISSN 1673-5447. S2CID 212649328.
40. ^ Bottommley, James (January 1, 2004). "Understanding Caching". Linux Journal. Archived from the original on December 4, 2020. Retrieved April 16, 2022.
41. ^ Jill Seaman (2014). "Set & Hash Tables". Texas State University. Archived from the original (PDF) on March 26, 2022. Retrieved March 26, 2022.
42. ^ "Transposition Table - Chessprogramming wiki". chessprogramming.org. Archived from the original on February 14, 2021. Retrieved May 1, 2020.
43. ^ "Programming language C++ - Technical Specification" (PDF). International Organization for Standardization. pp. 812–813. Archived from the original (PDF) on January 21, 2022. Retrieved February 8, 2022.
44. ^ "Lesson: Implementations (The Java™ Tutorials > Collections)". docs.oracle.com. Archived from the original on January 18, 2017. Retrieved April 27, 2018.
45. ^ Zhang, Juan; Jia, Yunwei (2019). "Redis rehash optimization based on machine learning". Journal of Physics: Conference Series. 1453: 3.
46. ^ Jonan Scheffler (December 25, 2016). "Ruby 2.4 Released: Faster Hashes, Unified Integers and Better Rounding". heroku.com. Archived from the original on July 3, 2019. Retrieved July 3, 2019.