text:
Hash table
From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Not to be confused with Hash list or Hash tree.
"Rehash" redirects here. For the South Park episode, see Rehash (South Park). For the IRC command, see List of Internet Relay Chat commands § REHASH.
Hash table
Type
Unordered associative array
Invented
1953
Time complexity in big O notation
Algorithm
Average Worst case
Space
O(n)[1] O(n)
Search
O(1) O(n)
Insert
O(1) O(n)
Delete
O(1) O(n)
A small phone book as a hash table
In computing, a hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
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 must be accommodated in some way.
In a well-dimensioned hash table, the average cost (number of instructions) for each lookup is independent of the number of elements stored in the table. Many hash table designs also allow arbitrary insertions and deletions of key-value pairs, at (amortized[2]) constant average cost per operation.[3][4]
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.
Contents
1 Hashing
1.1 Choosing a hash function
1.2 Perfect hash function
2 Key statistics
3 Collision resolution
3.1 Separate chaining
3.1.1 Separate chaining with linked lists
3.1.2 Separate chaining with list head cells
3.1.3 Separate chaining with other structures
3.2 Open addressing
3.2.1 Coalesced hashing
3.2.2 Cuckoo hashing
3.2.3 Hopscotch hashing
3.3 Robin Hood hashing
3.4 2-choice hashing
4 Dynamic resizing
4.1 Resizing by copying all entries
4.2 Alternatives to all-at-once rehashing
4.2.1 Incremental resizing
4.2.2 Monotonic keys
4.2.3 Linear hashing
4.2.4 Hashing for distributed hash tables
5 Performance analysis
6 Features
6.1 Advantages
6.2 Drawbacks
7 Uses
7.1 Associative arrays
7.2 Database indexing
7.3 Caches
7.4 Sets
7.5 Object representation
7.6 Unique data representation
7.7 Transposition table
8 Implementations
8.1 In programming languages
9 History
10 See also
10.1 Related data structures
11 References
12 Further reading
13 External links
Hashing[edit]
Main article: Hash function
The idea of hashing is to distribute the entries (key/value pairs) across an array of buckets. Given a key, the algorithm computes an index that suggests where the entry can be found:
index = f(key, array_size)

Often this is done in two steps:
hash = hashfunc(key)
index = hash % array_size

In this method, the hash is independent of the array size, and it is then reduced to an index (a number between 0 and array_size − 1) using the modulo operator (%).
In the case that the array size is a power of two, the remainder operation is reduced to masking, which improves speed, but can increase problems with a poor hash function.[5]
Choosing a hash function[edit]
A good hash function and implementation algorithm are essential for good hash table performance, but may be difficult to achieve.[citation needed][6]
A basic requirement is that the function should provide a uniform distribution of hash values. A non-uniform distribution increases the number of collisions and the cost of resolving them. Uniformity is sometimes difficult to ensure by design, but may be evaluated empirically using statistical tests, e.g., a Pearson's chi-squared test for discrete uniform distributions.[7][8]
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.[9] The modulus operation may provide some additional mixing; this is especially useful with a poor hash function.
For open addressing schemes, the hash function should also avoid clustering, the mapping of two or more keys to consecutive slots. Such clustering may cause the lookup cost to skyrocket, even if the load factor is low and collisions are infrequent. The popular multiplicative hash[3] is claimed to have particularly poor clustering behavior.[9]
Cryptographic hash functions are believed to provide good hash functions for any table size, either by modulo reduction or by bit masking[citation needed]. They may also be appropriate if there is a risk of malicious users trying to sabotage a network service by submitting requests designed to generate a large number of collisions in the server's hash tables. However, the risk of sabotage can also be avoided by cheaper methods (such as applying a secret salt to the data, or using a universal hash function). A drawback of cryptographic hashing functions is that they are often slower to compute, which means that in cases where the uniformity for any size is not necessary, a non-cryptographic hashing function might be preferable.[citation needed]
Perfect hash function[edit]
If all keys are known ahead of time, a perfect hash function can be used to create a perfect hash table that has no collisions. If minimal perfect hashing is used, every location in the hash table can be used as well.
Perfect hashing allows for constant time lookups in all cases. This is in contrast to most chaining and open addressing methods, where the time for lookup is low on average, but may be very large, O(n), for instance when all the keys hash to a few values.
Key statistics[edit]
A critical statistic for a hash table is the load factor, defined as
load factor = n k , {\displaystyle {\text{load factor}}={\frac {n}{k}},}
where
n is the number of entries occupied in the hash table.
k is the number of buckets.
As the load factor grows larger, the hash table becomes slower, and it may even fail to work (depending on the method used). The expected constant time property of a hash table assumes that the load factor is kept below some bound. For a fixed number of buckets, the time for a lookup grows with the number of entries and therefore the desired constant time is not achieved. As a real-world example, the default load factor for a HashMap in Java 10 is 0.75, which "offers a good tradeoff between time and space costs."[10]
Second to that, one can examine the variance of number of entries per bucket. For example, two tables both have 1,000 entries and 1,000 buckets; one has exactly one entry in each bucket, the other has all entries in the same bucket. Clearly the hashing is not working in the second one.
A low load factor is not especially beneficial. As the load factor approaches 0, the proportion of unused areas in the hash table increases, but there is not necessarily any reduction in search cost. This results in wasted memory.
Collision resolution[edit]
Hash collisions are practically unavoidable when hashing a random subset of a large set of possible keys. For example, if 2,450 keys are hashed into a million buckets, even with a perfectly uniform random distribution, according to the birthday problem there is approximately a 95% chance of at least two of the keys being hashed to the same slot.
Therefore, almost all hash table implementations have some collision resolution strategy to handle such events. Some common strategies are described below. All these methods require that the keys (or pointers to them) be stored in the table, together with the associated values.[citation needed]
Separate chaining[edit]
Hash collision resolved by separate chaining.
In the method known as separate chaining, each bucket is independent, and has some sort of list of entries with the same index. The time for hash table operations is the time to find the bucket (which is constant) plus the time for the list operation.
In a good hash table, each bucket has zero or one entries, and sometimes two or three, but rarely more than that. Therefore, structures that are efficient in time and space for these cases are preferred. Structures that are efficient for a fairly large number of entries per bucket are not needed or desirable. If these cases happen often, the hashing function needs to be fixed.[citation needed]
Separate chaining with linked lists[edit]
Chained hash tables with linked lists are popular because they require only basic data structures with simple algorithms, and can use simple hash functions that are unsuitable for other methods.[citation needed]
The cost of a table operation is that of scanning the entries of the selected bucket for the desired key. If the distribution of keys is sufficiently uniform, the average cost of a lookup depends only on the average number of keys per bucket—that is, it is roughly proportional to the load factor.
For this reason, chained hash tables remain effective even when the number of table entries n is much higher than the number of slots. For example, a chained hash table with 1000 slots and 10,000 stored keys (load factor 10) is five to ten times slower than a 10,000-slot table (load factor 1); but still 1000 times faster than a plain sequential list.
For separate-chaining, the worst-case scenario is when all entries are inserted into the same bucket, in which case the hash table is ineffective and the cost is that of searching the bucket data structure. If the latter is a linear list, the lookup procedure may have to scan all its entries, so the worst-case cost is proportional to the number n of entries in the table.
The bucket chains are often searched sequentially using the order the entries were added to the bucket. If the load factor is large and some keys are more likely to come up than others, then rearranging the chain with a move-to-front heuristic may be effective. More sophisticated data structures, such as balanced search trees, are worth considering only if the load factor is large (about 10 or more), or if the hash distribution is likely to be very non-uniform, or if one must guarantee good performance even in a worst-case scenario. However, using a larger table and/or a better hash function may be even more effective in those cases.[citation needed]
Chained hash tables also inherit the disadvantages of linked lists. When storing small keys and values, the space overhead of the next pointer in each entry record can be significant. An additional disadvantage is that traversing a linked list has poor cache performance, making the processor cache ineffective.
Separate chaining with list head cells[edit]
Hash collision by separate chaining with head records in the bucket array.
Some chaining implementations store the first record of each chain in the slot array itself.[4] The number of pointer traversals is decreased by one for most cases. The purpose is to increase cache efficiency of hash table access.
The disadvantage is that an empty bucket takes the same space as a bucket with one entry. To save space, such hash tables often have about as many slots as stored entries, meaning that many slots have two or more entries.[citation needed]
Separate chaining with other structures[edit]
Instead of a list, one can use any other data structure that supports the required operations. For example, by using a self-balancing binary search tree, the theoretical worst-case time of common hash table operations (insertion, deletion, lookup) can be brought down to O(log n) rather than O(n). However, this introduces extra complexity into the implementation, and may cause even worse performance for smaller hash tables, where the time spent inserting into and balancing the tree is greater than the time needed to perform a linear search on all of the elements of a list.[3][11] A real world example of a hash table that uses a self-balancing binary search tree for buckets is the HashMap class in Java version 8.[12]
The variant called array hash table uses a dynamic array to store all the entries that hash to the same slot.[13][14][15] Each newly inserted entry gets appended to the end of the dynamic array that is assigned to the slot. The dynamic array is resized in an exact-fit manner, meaning it is grown only by as many bytes as needed. Alternative techniques such as growing the array by block sizes or pages were found to improve insertion performance, but at a cost in space. This variation makes more efficient use of CPU caching and the translation lookaside buffer (TLB), because slot entries are stored in sequential memory positions. It also dispenses with the next pointers that are required by linked lists, which saves space. Despite frequent array resizing, space overheads incurred by the operating system such as memory fragmentation were found to be small.[citation needed]
An elaboration on this approach is the so-called dynamic perfect hashing,[16] where a bucket that contains k entries is organized as a perfect hash table with k2 slots. While it uses more memory (n2 slots for n entries, in the worst case and n × k slots in the average case), this variant has guaranteed constant worst-case lookup time, and low amortized time for insertion. It is also possible to use a fusion tree for each bucket, achieving constant time for all operations with high probability.[17]
Open addressing[edit]
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".
In another strategy, called open addressing, all entry records are stored in the bucket array itself. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found. When searching for an entry, the buckets are scanned in the same sequence, until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table.[18] The name "open addressing" refers to the fact that the location ("address") of the item is not determined by its hash value. (This method is also called closed hashing; it should not be confused with "open hashing" or "closed addressing" that usually mean separate chaining.)
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 starting value given by the original hash computation
Double hashing, in which the interval between probes is computed by a second hash function
A drawback of all these open addressing schemes is that the number of stored entries cannot exceed the number of slots in the bucket array. In fact, even with good hash functions, their performance dramatically degrades when the load factor grows beyond 0.7 or so. For many applications, these restrictions mandate the use of dynamic resizing, with its attendant costs.[citation needed]
Open addressing schemes also put more stringent requirements on the hash function: besides distributing the keys more uniformly over the buckets, the function must also minimize the clustering of hash values that are consecutive in the probe order. Using separate chaining, the only concern is that too many objects map to the same hash value; whether they are adjacent or nearby is completely irrelevant.[citation needed]
Open addressing only saves memory if the entries are small (less than four times the size of a pointer) and the load factor is not too small. If the load factor is close to zero (that is, there are far more buckets than stored entries), open addressing is wasteful even if each entry is just two words.
This graph compares the average number of cache misses required to look up elements in tables with chaining and linear probing. As the table passes the 80%-full mark, linear probing's performance drastically degrades.
Open addressing avoids the time overhead of allocating each new entry record, and can be implemented even in the absence of a memory allocator. It also avoids the extra indirection required to access the first entry of each bucket (that is, usually the only one). It also has better locality of reference, particularly with linear probing. With small record sizes, these factors can yield better performance than chaining, particularly for lookups. Hash tables with open addressing are also easier to serialize, because they do not use pointers.[citation needed]
On the other hand, normal open addressing is a poor choice for large elements, because these elements fill entire CPU cache lines (negating the cache advantage), and a large amount of space is wasted on large empty table slots. If the open addressing table only stores references to elements (external storage), it uses space comparable to chaining even for large records but loses its speed advantage.[citation needed]
Generally speaking, open addressing is better used for hash tables with small records that can be stored within the table (internal storage) and fit in a cache line. They are particularly suitable for elements of one word or less. If the table is expected to have a high load factor, the records are large, or the data is variable-sized, chained hash tables often perform as well or better.[citation needed]
Ultimately, used sensibly, any kind of hash table algorithm is usually fast enough; and the percentage of a calculation spent in hash table code is low. Memory usage is rarely considered excessive. Therefore, in most cases the differences between these algorithms are marginal, and other considerations typically come into play.[citation needed]
Coalesced hashing[edit]
A hybrid of chaining and open addressing, coalesced hashing links together chains of nodes within the table itself.[18] Like open addressing, it achieves space usage and (somewhat diminished) cache advantages over chaining. Like chaining, it does not exhibit clustering effects; in fact, the table can be efficiently filled to a high density. Unlike chaining, it cannot have more elements than table slots.
Cuckoo hashing[edit]
Another alternative open-addressing solution is cuckoo hashing, which ensures constant lookup time in the worst case, and constant amortized time for insertions and deletions. It uses two or more hash functions, which means any key/value pair could be in two or more locations. For lookup, the first hash function is used; if the key/value is not found, then the second hash function is used, and so on. If a collision happens during insertion, then the key is re-hashed with the second hash function to map it to another bucket. If all hash functions are used and there is still a collision, then the key it collided with is removed to make space for the new key, and the old key is re-hashed with one of the other hash functions, which maps it to another bucket. If that location also results in a collision, then the process repeats until there is no collision or the process traverses all the buckets, at which point the table is resized. By combining multiple hash functions with multiple cells per bucket, very high space utilization can be achieved.[citation needed]
Hopscotch hashing[edit]
Another alternative open-addressing solution is hopscotch hashing,[19] which combines the approaches of cuckoo hashing and linear probing, yet seems in general to avoid their limitations. In particular it works well even when the load factor grows beyond 0.9. The algorithm is well suited for implementing a resizable concurrent hash table.
The hopscotch hashing algorithm works by defining a neighborhood of buckets near the original hashed bucket, where a given entry is always found. Thus, search is limited to the number of entries in this neighborhood, which is logarithmic in the worst case, constant on average, and with proper alignment of the neighborhood typically requires one cache miss. When inserting an entry, one first attempts to add it to a bucket in the neighborhood. However, if all buckets in this neighborhood are occupied, the algorithm traverses buckets in sequence until an open slot (an unoccupied bucket) is found (as in linear probing). At that point, since the empty bucket is outside the neighborhood, items are repeatedly displaced in a sequence of hops. (This is similar to cuckoo hashing, but with the difference that in this case the empty slot is being moved into the neighborhood, instead of items being moved out with the hope of eventually finding an empty slot.) Each hop brings the open slot closer to the original neighborhood, without invalidating the neighborhood property of any of the buckets along the way. In the end, the open slot has been moved into the neighborhood, and the entry being inserted can be added to it.[citation needed]
Robin Hood hashing[edit]
One interesting variation on double-hashing collision resolution is Robin Hood hashing.[20][21] The idea is that a new key may displace a key already inserted, if its probe count is larger than that of the key at the current position. The net effect of this is that it reduces worst case search times in the table. This is similar to ordered hash tables[22] except that the criterion for bumping a key does not depend on a direct relationship between the keys. Since both the worst case and the variation in the number of probes is reduced dramatically, an interesting variation is to probe the table starting at the expected successful probe value and then expand from that position in both directions.[23] External Robin Hood hashing is an extension of this algorithm where the table is stored in an external file and each table position corresponds to a fixed-sized page or bucket with B records.[24]
2-choice hashing[edit]
2-choice hashing employs two different hash functions, h1(x) and h2(x), for the hash table. Both hash functions are used to compute two table locations. When an object is inserted in the table, it is placed in the table location that contains fewer objects (with the default being the h1(x) table location if there is equality in bucket size). 2-choice hashing employs the principle of the power of two choices.[25]
Dynamic resizing[edit]
When an insert is made such that the number of entries in a hash table exceeds the product of the load factor and the current capacity then the hash table will need to be rehashed.[10] Rehashing includes increasing the size of the underlying data structure[10] and mapping existing items to new bucket locations. In some implementations, if the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.[10]
To limit the proportion of memory wasted due to empty buckets, some implementations also shrink the size of the table—followed by a rehash—when items are deleted. From the point of space–time tradeoffs, this operation is similar to the deallocation in dynamic arrays.
Resizing by copying all entries[edit]
A common approach is to automatically trigger a complete resizing when the load factor exceeds some threshold rmax. Then a new larger table is allocated, each entry is removed from the old table, and inserted into the new table. When all entries have been removed from the old table then the old table is returned to the free storage pool. Symmetrically, when the load factor falls below a second threshold rmin, all entries are moved to a new smaller table.
For hash tables that shrink and grow frequently, the resizing downward can be skipped entirely. In this case, the table size is proportional to the maximum number of entries that ever were in the hash table at one time, rather than the current number. The disadvantage is that memory usage will be higher, and thus cache behavior may be worse. For best control, a "shrink-to-fit" operation can be provided that does this only on request.
If the table size increases or decreases by a fixed percentage at each expansion, the total cost of these resizings, amortized over all insert and delete operations, is still a constant, independent of the number of entries n and of the number m of operations performed.
For example, consider a table that was created with the minimum possible size and is doubled each time the load ratio exceeds some threshold. If m elements are inserted into that table, the total number of extra re-insertions that occur in all dynamic resizings of the table is at most m − 1. In other words, dynamic resizing roughly doubles the cost of each insert or delete operation.
Alternatives to all-at-once rehashing[edit]
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.
Disk-based hash tables almost always use some alternative to all-at-once rehashing, since the cost of rebuilding the entire table on disk would be too high.
Incremental resizing[edit]
One alternative to enlarging the table all at once is to perform the rehashing gradually:
During the resize, allocate the new hash table, but keep the old table unchanged.
In each lookup or delete operation, check both tables.
Perform insertion operations only in the new table.
At each insertion also move r elements from the old table to the new table.
When all elements are removed from the old table, deallocate it.
To ensure that the old table is completely copied over before the new table itself needs to be enlarged, it is necessary to increase the size of the table by a factor of at least (r + 1)/r during resizing.
Monotonic keys[edit]
If it is known that key values will always increase (or decrease) monotonically, then a variation of consistent hashing can be achieved by keeping a list of the single most recent key value at each hash table resize operation. Upon lookup, keys that fall in the ranges defined by these list entries are directed to the appropriate hash function—and indeed hash table—both of which can be different for each range. Since it is common to grow the overall number of entries by doubling, there will only be O(log(N)) ranges to check, and binary search time for the redirection would be O(log(log(N))). As with consistent hashing, this approach guarantees that any key's hash, once issued, will never change, even when the hash table is later grown.
Linear hashing[edit]
Linear hashing[26] is a hash table algorithm that permits incremental hash table expansion. It is implemented using a single hash table, but with two possible lookup functions.
Hashing for distributed hash tables[edit]
Another way to decrease the cost of table resizing is to choose a hash function in such a way that the hashes of most values do not change when the table is resized. Such hash functions are prevalent in disk-based and distributed hash tables, where rehashing is prohibitively costly. The problem of designing a hash such that most values do not change when the table is resized is known as the distributed hash table problem. The four most popular approaches are rendezvous hashing, consistent hashing, the content addressable network algorithm, and Kademlia distance.
Performance analysis[edit]
In the simplest model, the hash function is completely unspecified and the table does not resize. With an ideal hash function, a table of size k {\displaystyle k} with open addressing has no collisions and holds up to k {\displaystyle k} elements with a single comparison for successful lookup, while a table of size k {\displaystyle k} with chaining and n {\displaystyle n} keys has the minimum m a x ( 0 , n − k ) {\displaystyle max(0,n-k)} collisions and Θ ( 1 + n k ) {\displaystyle \Theta (1+{\frac {n}{k}})} comparisons for lookup. With the worst possible hash function, every insertion causes a collision, and hash tables degenerate to linear search, with Θ ( n ) {\displaystyle \Theta (n)} amortized comparisons per insertion and up to n {\displaystyle n} comparisons for a successful lookup.
Adding rehashing to this model is straightforward. As in a dynamic array, geometric resizing by a factor of b {\displaystyle b} implies that only n b i {\displaystyle {\frac {n}{b^{i}}}} keys are inserted i {\displaystyle i} or more times, so that the total number of insertions is bounded above by b n b − 1 {\displaystyle {\frac {bn}{b-1}}} , which is Θ ( n ) {\displaystyle \Theta (n)} . By using rehashing to maintain n < k {\displaystyle n<k} , tables using both chaining and open addressing can have unlimited elements and perform successful lookup in a single comparison for the best choice of hash function.
In more realistic models, the hash function is a random variable over a probability distribution of hash functions, and performance is computed on average over the choice of hash function. When this distribution is uniform, the assumption is called "simple uniform hashing" and it can be shown that hashing with chaining requires Θ ( 1 + n k ) {\displaystyle \Theta (1+{\frac {n}{k}})} comparisons on average for an unsuccessful lookup, and hashing with open addressing requires Θ ( 1 1 − n / k ) {\displaystyle \Theta \left({\frac {1}{1-n/k}}\right)} .[27] Both these bounds are constant, if we maintain ' n k < c {\displaystyle {\frac {n}{k}}<c} using table resizing, where c {\displaystyle c} is a fixed constant less than 1.
Features[edit]
Advantages[edit]
The main advantage of hash tables over other table data structures is speed. This advantage is more apparent when the number of entries is large. Hash tables are particularly efficient when the maximum number of entries can be predicted in advance, so that the bucket array can be allocated once with the optimum size and never resized.
If the set of key-value pairs is fixed and known ahead of time (so insertions and deletions are not allowed), one may reduce the average lookup cost by a careful choice of the hash function, bucket table size, and internal data structures. In particular, one may be able to devise a hash function that is collision-free, or even perfect. In this case the keys need not be stored in the table.
Drawbacks[edit]
Although operations on a hash table take constant time on average, the cost of a good hash function can be significantly higher than the inner loop of the lookup algorithm for a sequential list or search tree. Thus hash tables are not effective when the number of entries is very small. (However, in some cases the high cost of computing the hash function can be mitigated by saving the hash value together with the key.)
For certain string processing applications, such as spell-checking, hash tables may be less efficient than tries, finite automata, or Judy arrays. Also, if there are not too many possible keys to store—that is, if each key can be represented by a small enough number of bits—then, instead of a hash table, one may use the key directly as the index into an array of values. Note that there are no collisions in this case.
The entries stored in a hash table can be enumerated efficiently (at constant cost per entry), but only in some pseudo-random order. Therefore, there is no efficient way to locate an entry whose key is nearest to a given key. Listing all n entries in some specific order generally requires a separate sorting step, whose cost is proportional to log(n) per entry. In comparison, ordered search trees have lookup and insertion cost proportional to log(n), but allow finding the nearest key at about the same cost, and ordered enumeration of all entries at constant cost per entry.
If the keys are not stored (because the hash function is collision-free), there may be no easy way to enumerate the keys that are present in the table at any given moment.
Although the average cost per operation is constant and fairly small, the cost of a single operation may be quite high. In particular, if the hash table uses dynamic resizing, an insertion or deletion operation may occasionally take time proportional to the number of entries. This may be a serious drawback in real-time or interactive applications.
Hash tables in general exhibit poor locality of reference—that is, the data to be accessed is distributed seemingly at random in memory. Because hash tables cause access patterns that jump around, this can trigger microprocessor cache misses that cause long delays. Compact data structures such as arrays searched with linear search may be faster, if the table is relatively small and keys are compact. The optimal performance point varies from system to system.
Hash tables become quite inefficient when there are many collisions. While extremely uneven hash distributions are extremely unlikely to arise by chance, a malicious adversary with knowledge of the hash function may be able to supply information to a hash that creates worst-case behavior by causing excessive collisions, resulting in very poor performance, e.g., a denial of service attack.[28][29][30] In critical applications, a data structure with better worst-case guarantees can be used; however, universal hashing—a randomized algorithm that prevents the attacker from predicting which inputs cause worst-case behavior—may be preferable.[31] The hash function used by the hash table in the Linux routing table cache was changed with Linux version 2.4.2 as a countermeasure against such attacks.[32]
Uses[edit]
This section does not cite any sources. Please help improve this section by adding citations to reliable sources. Unsourced material may be challenged and removed. (July 2013) (Learn how and when to remove this template message)
Associative arrays[edit]
Main article: Associative array
Hash tables are commonly used to implement many types of in-memory tables. They are used to implement associative arrays (arrays whose indices are arbitrary strings or other complicated objects), especially in interpreted programming languages like Perl, Ruby, Python, and PHP.
When storing a new item into a multimap and a hash collision occurs, the multimap unconditionally stores both items.
When storing a new item into a typical associative array and a hash collision occurs, but the actual keys themselves are different, the associative array likewise stores both items. However, if the key of the new item exactly matches the key of an old item, the associative array typically erases the old item and overwrites it with the new item, so every item in the table has a unique key.
Database indexing[edit]
Hash tables may also be used as disk-based data structures and database indices (such as in dbm) although B-trees are more popular in these applications. In multi-node database systems, hash tables are commonly used to distribute rows amongst nodes, reducing network traffic for hash joins.
Caches[edit]
Main article: Cache (computing)
Hash tables can be used to implement caches, auxiliary data tables that are used to speed up the access to data that is primarily stored in slower media. In this application, hash collisions can be handled by discarding one of the two colliding entries—usually erasing the old item that is currently stored in the table and overwriting it with the new item, so every item in the table has a unique hash value.
Sets[edit]
Besides recovering the entry that has a given key, many hash table implementations can also tell whether such an entry exists or not.
Those structures can therefore be used to implement a set data structure, which merely records whether a given key belongs to a specified set of keys. In this case, the structure can be simplified by eliminating all parts that have to do with the entry values. Hashing can be used to implement both static and dynamic sets.
Object representation[edit]
Several dynamic languages, such as Perl, Python, JavaScript, Lua, and Ruby, use hash tables to implement objects. In this representation, the keys are the names of the members and methods of the object, and the values are pointers to the corresponding member or method.
Unique data representation[edit]
Main article: String interning
Hash tables can be used by some programs to avoid creating multiple character strings with the same contents. For that purpose, all strings in use by the program are stored in a single string pool implemented as a hash table, which is checked whenever a new string has to be created. This technique was introduced in Lisp interpreters under the name hash consing, and can be used with many other kinds of data (expression trees in a symbolic algebra system, records in a database, files in a file system, binary decision diagrams, etc.).
Transposition table[edit]
Main article: Transposition table
Implementations[edit]
In programming languages[edit]
Many programming languages provide hash table functionality, either as built-in associative arrays or as standard library modules. In C++11, for example, the unordered_map class provides hash tables for keys and values of arbitrary type.
The Java programming language (including the variant which is used on Android) includes the HashSet, HashMap, LinkedHashSet, and LinkedHashMap generic collections.[33]
In PHP 5 and 7, the Zend 2 engine and the Zend 3 engine (respectively) use one of the hash functions from Daniel J. Bernstein to generate the hash values used in managing the mappings of data pointers stored in a hash table. In the PHP source code, it is labelled as DJBX33A (Daniel J. Bernstein, Times 33 with Addition).
Python's built-in hash table implementation, in the form of the dict type, as well as Perl's hash type (%) are used internally to implement namespaces and therefore need to pay more attention to security, i.e., collision attacks. Python sets also use hashes internally, for fast lookup (though they store only keys, not values).[34]
In the .NET Framework, support for hash tables is provided via the non-generic Hashtable and generic Dictionary classes, which store key-value pairs, and the generic HashSet class, which stores only values.
In Rust's standard library, the generic HashMap and HashSet structs use linear probing with Robin Hood bucket stealing.
ANSI Smalltalk defines the classes Set / IdentitySet and Dictionary / IdentityDictionary. All Smalltalk implementations provide additional (not yet standardized) versions of WeakSet, WeakKeyDictionary and WeakValueDictionary.
History[edit]
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.[35] Gene Amdahl, Elaine M. McGraw, Nathaniel Rochester, and Arthur Samuel implemented a program using hashing at about the same time. Open addressing with linear probing (relatively prime stepping) is credited to Amdahl, but Ershov (in Russia) had the same idea.[35]
See also[edit]
Rabin–Karp string search algorithm
Stable hashing
Consistent hashing
Extendible hashing
Lazy deletion
Pearson hashing
PhotoDNA
Search data structure
Related data structures[edit]
There are several data structures that use hash functions but cannot be considered special cases of hash tables:
Bloom filter, memory efficient data-structure designed for constant-time approximate lookups; uses hash function(s) and can be seen as an approximate hash table.
Distributed hash table (DHT), a resilient dynamic table spread over several nodes of a network.
Hash array mapped trie, a trie structure, similar to the array mapped trie, but where each key is hashed first.
References[edit]
Jump up ^ 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.
Jump up ^ 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
^ Jump up to: a b c Knuth, Donald (1998). 'The Art of Computer Programming'. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513–558. ISBN 0-201-89685-0.
^ Jump up to: a b 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.
Jump up ^ "JDK HashMap Hashcode implementation". Archived from the original on May 21, 2017.
Jump up ^ "python/cpython". GitHub. Retrieved 2018-09-19.
Jump up ^ Pearson, Karl (1900). "On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling". Philosophical Magazine. Series 5. 50 (302). pp. 157–175. doi:10.1080/14786440009463897.
Jump up ^ Plackett, Robin (1983). "Karl Pearson and the Chi-Squared Test". International Statistical Review (International Statistical Institute (ISI)). 51 (1). pp. 59–72. doi:10.2307/1402731.
^ Jump up to: a b Wang, Thomas (March 1997). "Prime Double Hash Table". Archived from the original on 1999-09-03. Retrieved 2015-05-10.
^ Jump up to: a b c d Javadoc for HashMap in Java 10 https://docs.oracle.com/javase/10/docs/api/java/util/HashMap.html
Jump up ^ Probst, Mark (April 30, 2010). "Linear vs Binary Search". Archived from the original on November 20, 2016. Retrieved November 20, 2016.
Jump up ^ "How does a HashMap work in JAVA". coding-geek.com. Archived from the original on November 19, 2016.
Jump up ^ 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). 3772/2005. pp. 91–102. doi:10.1007/11575832_11. ISBN 978-3-540-29740-6.
Jump up ^ Askitis, Nikolas; Sinha, Ranjan (2010). "Engineering scalable, cache and space efficient tries for strings". The VLDB Journal. 17 (5): 633–660. doi:10.1007/s00778-010-0183-9. ISSN 1066-8888.
Jump up ^ Askitis, Nikolas (2009). Fast and Compact Hash Tables for Integer Keys (PDF). Proceedings of the 32nd Australasian Computer Science Conference (ACSC 2009). 91. pp. 113–122. ISBN 978-1-920682-72-9. Archived (PDF) from the original on February 16, 2011.
Jump up ^ 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. CS1 maint: Archived copy as title (link)
Jump up ^ 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. .
^ Jump up to: a b Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C. Prentice Hall. pp. 456–461, p. 472. ISBN 0-13-199746-7.
Jump up ^ Herlihy, Maurice; Shavit, Nir; Tzafrir, Moran (2008). "Hopscotch Hashing". DISC '08: Proceedings of the 22nd international symposium on Distributed Computing. Berlin, Heidelberg: Springer-Verlag. pp. 350–364. CiteSeerX 10.1.1.296.8742.
Jump up ^ Celis, Pedro (1986). Robin Hood hashing (PDF) (Technical report). Computer Science Department, University of Waterloo. CS-86-14. Archived (PDF) from the original on July 17, 2014.
Jump up ^ Goossaert, Emmanuel (2013). "Robin Hood hashing". Archived from the original on March 21, 2014.
Jump up ^ Amble, Ole; Knuth, Don (1974). "Ordered hash tables". Computer Journal. 17 (2): 135. doi:10.1093/comjnl/17.2.135.
Jump up ^ Viola, Alfredo (October 2005). "Exact distribution of individual displacements in linear probing hashing". Transactions on Algorithms (TALG). ACM. 1 (2, ): 214–242. doi:10.1145/1103963.1103965.
Jump up ^ Celis, Pedro (March 1988). External Robin Hood Hashing (Technical report). Computer Science Department, Indiana University. TR246.
Jump up ^ "Archived copy" (PDF). Archived (PDF) from the original on March 25, 2015. Retrieved April 10, 2015. CS1 maint: Archived copy as title (link)
Jump up ^ Litwin, Witold (1980). "Linear hashing: A new tool for file and table addressing". Proc. 6th Conference on Very Large Databases. pp. 212–223.
Jump up ^ Doug Dunham. CS 4521 Lecture Notes Archived July 22, 2009, at the Wayback Machine.. University of Minnesota Duluth. Theorems 11.2, 11.6. Last modified April 21, 2009.
Jump up ^ Alexander Klink and Julian Wälde's Efficient Denial of Service Attacks on Web Application Platforms Archived September 16, 2016, at the Wayback Machine., December 28, 2011, 28th Chaos Communication Congress. Berlin, Germany.
Jump up ^ Mike Lennon "Hash Table Vulnerability Enables Wide-Scale DDoS Attacks" Archived September 19, 2016, at the Wayback Machine.. 2011.
Jump up ^ "Hardening Perl's Hash Function". November 6, 2013. Archived from the original on September 16, 2016.
Jump up ^ Crosby and Wallach. Denial of Service via Algorithmic Complexity Attacks Archived March 4, 2016, at the Wayback Machine.. quote: "modern universal hashing techniques can yield performance comparable to commonplace hash functions while being provably secure against these attacks." "Universal hash functions ... are ... a solution suitable for adversarial environments. ... in production systems."
Jump up ^ Bar-Yosef, Noa; Wool, Avishai (2007). Remote algorithmic complexity attacks against randomized hash tables Proc. International Conference on Security and Cryptography (SECRYPT) (PDF). p. 124. Archived (PDF) from the original on September 16, 2014.
Jump up ^ "Lesson: Implementations (The Java™ Tutorials > Collections)". docs.oracle.com. Archived from the original on January 18, 2017. Retrieved April 27, 2018.
Jump up ^ "Python: List vs Dict for look up table". stackoverflow.com. Archived from the original on December 2, 2017. Retrieved April 27, 2018.
^ Jump up to: a b Mehta, Dinesh P.; Sahni, Sartaj. Handbook of Datastructures and Applications. p. 9-15. ISBN 1-58488-435-5.
Further reading[edit]
Tamassia, Roberto; Goodrich, Michael T. (2006). "Chapter Nine: Maps and Dictionaries". Data structures and algorithms in Java : [updated for Java 5.0] (4th ed.). Hoboken, NJ: Wiley. pp. 369–418. ISBN 0-471-73884-0.
McKenzie, B. J.; Harries, R.; Bell, T. (Feb 1990). "Selecting a hashing algorithm". Software Practice & Experience. 20 (2): 209–224. doi:10.1002/spe.4380200207.
External links[edit]
Wikimedia Commons has media related to Hash tables.
Wikibooks has a book on the topic of: Data Structures/Hash Tables
A Hash Function for Hash Table Lookup by Bob Jenkins.
Hash Tables by SparkNotes—explanation using C
Hash functions by Paul Hsieh
Design of Compact and Efficient Hash Tables for Java
NIST entry on hash tables
Lecture on Hash Tables
Open Data Structures – Chapter 5 – Hash Tables
MIT's Introduction to Algorithms: Hashing 1 MIT OCW lecture Video
MIT's Introduction to Algorithms: Hashing 2 MIT OCW lecture Video
hide
v
t
e
Data structures
Types
Collection
Container
Abstract
Associative array
Multimap
List
Stack
Queue
Double-ended queue
Priority queue
Double-ended priority queue
Set
Multiset
Disjoint-set
Arrays
Bit array
Circular buffer
Dynamic array
Hash table
Hashed array tree
Sparse matrix
Linked
Association list
Linked list
Skip list
Unrolled linked list
XOR linked list
Trees
B-tree
Binary search tree
AA tree
AVL tree
Red–black tree
Self-balancing tree
Splay tree
Heap
Binary heap
Binomial heap
Fibonacci heap
R-tree
R* tree
R+ tree
Hilbert R-tree
Trie
Hash tree
Graphs
Binary decision diagram
Directed acyclic graph
Directed acyclic word graph
List of data structures
Retrieved from "https://en.wikipedia.org/w/index.php?title=Hash_table&oldid=866368727"
Categories:
Hashing
Search algorithms
Arrays
1953 in computer science
Hidden categories:
Webarchive template wayback links
CS1 maint: Archived copy as title
Use mdy dates from January 2013
All articles with unsourced statements
Articles with unsourced statements from October 2016
Articles with unsourced statements from July 2014
Articles with unsourced statements from March 2016
Articles with unsourced statements from March 2012
Articles needing additional references from July 2013
All articles needing additional references
Articles with example C code
Navigation menu
Personal tools
Not logged in
Talk
Contributions
Create account
Log in
Namespaces
Article
Talk
Variants
Views
Read
Edit
View history
More
Search
Navigation
Main page
Contents
Featured content
Current events
Random article
Donate to Wikipedia
Wikipedia store
Interaction
Help
About Wikipedia
Community portal
Recent changes
Contact page
Tools
What links here
Related changes
Upload file
Special pages
Permanent link
Page information
Wikidata item
Cite this page
Print/export
Create a book
Download as PDF
Printable version
In other projects
Wikimedia Commons
Languages
العربية
Български
Bosanski
Català
Čeština
Dansk
Deutsch
Eesti
Ελληνικά
Español
Esperanto
فارسی
Français
한국어
Hrvatski
Italiano
עברית
Latviešu
Lietuvių
Magyar
മലയാളം
Nederlands
日本語
Norsk
Norsk nynorsk
Polski
Português
Русский
Simple English
Slovenčina
Српски / srpski
Suomi
Svenska
Tagalog
ไทย
Türkçe
Українська
Tiếng Việt
中文
30 more
Edit links
This page was last edited on 29 October 2018, at 22:45 (UTC).
Text is available under the Creative Commons Attribution-ShareAlike License; additional terms may apply. By using this site, you agree to the Terms of Use and Privacy Policy. Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a non-profit organization.
Privacy policy
About Wikipedia
Disclaimers
Contact Wikipedia
Developers
Cookie statement
Mobile view
Enable previews

values: mw-page-base noprint

values: mw-head-base noprint

values: firstHeading firstHeading en

values: siteSub noprint

attrs: class href

values: mw-jump-link #mw-head

values: mw-jump-link #p-search

values:
/wiki/Hash_tree_(disambiguation)
mw-redirect mw-disambig
Hash tree (disambiguation)

values:
note
hatnote navigation-not-searchable

value: i

value: p

values:
/wiki/Instruction_(computer_science)
mw-redirect
Instruction (computer science)

values:
/wiki/Table_(computing)
mw-redirect
Table (computing)

values: checkbox button toctogglecheckbox toctogglecheckbox display:none

values: This claim needs references to reliable sources. (October 2016)

values:
noprint Inline-Template Template-Fact
white-space:nowrap;

values:
/wiki/Uniform_distribution_(discrete)
mw-redirect
Uniform distribution (discrete)

values: This claim needs references to reliable sources. (July 2014)

values:
/wiki/Denial_of_service_attack
mw-redirect
Denial of service attack

values:
/wiki/Universal_hash_function
mw-redirect
Universal hash function

values:
/wiki/Constant_time
mw-redirect
Constant time

values: {\displaystyle {\text{load factor}}={\frac {n}{k}},}

values: vertical-align: -2.005ex; width:16.707ex; height:4.843ex;

values: Edit section: Separate chaining with linked lists

values: This claim needs references to reliable sources. (March 2016)

values: Edit section: Separate chaining with list head cells

values: Edit section: Separate chaining with other structures

values: This claim needs references to reliable sources. (March 2012)

values: Concurrent hash table (page does not exist)

values: Edit section: Resizing by copying all entries

values:
/wiki/Dynamic_memory_allocation
mw-redirect
Dynamic memory allocation

values: Edit section: Alternatives to all-at-once rehashing

values:
/wiki/Real-time_system
mw-redirect
Real-time system

values: Edit section: Hashing for distributed hash tables

values: vertical-align: -0.338ex; width:1.211ex; height:2.176ex;

values: vertical-align: -0.338ex; width:1.395ex; height:1.676ex;

values: vertical-align: -0.838ex; width:14.052ex; height:2.843ex;

values: {\displaystyle \Theta (1+{\frac {n}{k}})}

values: vertical-align: -2.005ex; width:9.851ex; height:4.843ex;

values: vertical-align: -0.838ex; width:5.012ex; height:2.843ex;

values: vertical-align: -0.338ex; width:0.998ex; height:2.176ex;

values: vertical-align: -2.005ex; width:2.633ex; height:4.843ex;

values: vertical-align: -0.338ex; width:0.802ex; height:2.176ex;

values: vertical-align: -2.171ex; width:5.837ex; height:5.676ex;

values: vertical-align: -0.338ex; width:5.704ex; height:2.176ex;

values: vertical-align: -2.671ex; width:14.224ex; height:6.343ex;

values: vertical-align: -2.005ex; width:6.336ex; height:4.843ex;

values: vertical-align: -0.338ex; width:1.007ex; height:1.676ex;

values:
/wiki/Finite_automata
mw-redirect
Finite automata

values:
/wiki/Black_hat_hacking
mw-redirect
Black hat hacking

values: Help:Introduction to referencing with Wiki Markup/1

values: plainlinks metadata ambox ambox-content ambox-Unreferenced

values:
/wiki/String_(computing)
mw-redirect
String (computing)

values:
/wiki/Index_(database)
mw-redirect
Index (database)

values:
/wiki/Set_data_structure
mw-redirect
Set data structure

values: Edit section: Unique data representation

values:
/wiki/Expression_tree
mw-redirect
Expression tree

values:
/wiki/Unordered_map_(C%2B%2B)
mw-redirect
Unordered map (C++)

values:
/wiki/Smalltalk_(programming_language)
mw-redirect
Smalltalk (programming language)

values: Nathaniel Rochester (computer scientist)

values:
/wiki/Stable_hashing
mw-redirect
Stable hashing

values:
/wiki/Ronald_L._Rivest
mw-redirect
Ronald L. Rivest

values:
nofollow
external text
//doi.org/10.2307%2F1402731

values:
nofollow
external text
//doi.org/10.1007%2F11575832_11

values:
nofollow
external text
//www.worldcat.org/issn/1066-8888

values: Category:CS1 maint: Archived copy as title

values:
nofollow
external text
//doi.org/10.1093%2Fcomjnl%2F17.2.135

values:
nofollow
external text
//doi.org/10.1002%2Fspe.4380200207

values: Deterministic acyclic finite state automaton

values: nowraplinks hlist collapsible autocollapse navbox-inner mw-collapsible mw-made-collapsible

values: Category:Webarchive template wayback links

values: Category:Use mdy dates from January 2013

values: Category:All articles with unsourced statements

values: Category:Articles with unsourced statements from October 2016

values: Category:Articles with unsourced statements from July 2014

values: Category:Articles with unsourced statements from March 2016

values: Category:Articles with unsourced statements from March 2012

values: Category:Articles needing additional references from July 2013

values: Category:All articles needing additional references

values: Discussion about edits from this IP address [ctrl-alt-n]

values: A list of edits made from this IP address [ctrl-alt-y]

values: You are encouraged to create an account and log in; however, it is not mandatory

values: You're encouraged to log in; however, it's not mandatory. [ctrl-alt-o]

values:
/wiki/Hash_table
View the content page [ctrl-alt-c]
c

values: Discussion about the content page [ctrl-alt-t]

values: p-namespaces navigation vectorTabs p-namespaces-label

values:
p-variants
navigation
vectorMenu emptyPortlet
p-variants-label

values: Past revisions of this page [ctrl-alt-h]

values: p-views navigation vectorTabs p-views-label

values:
p-cactions
navigation
vectorMenu emptyPortlet
p-cactions-label

values:
mw-wiki-logo
/wiki/Main_Page
Visit the main page

values:
/wiki/Main_Page
Visit the main page [ctrl-alt-z]
z

values: Featured content – the best of Wikipedia

values: Find background information on current events

values:
/wiki/Special:Random
Load a random article [ctrl-alt-x]
x

values: portal navigation p-navigation p-navigation-label

values: Guidance on how to use and edit Wikipedia

values: About the project, what you can do, where to find things

values: A list of recent changes in the wiki [ctrl-alt-r]

values: portal navigation p-interaction p-interaction-label

values: List of all English Wikipedia pages containing links to this page [ctrl-alt-j]

values: Recent changes in pages linked from this page [ctrl-alt-k]

values:
/wiki/Wikipedia:File_Upload_Wizard
Upload files [ctrl-alt-u]
u

values: A list of all special pages [ctrl-alt-q]

values: Permanent link to this revision of the page

values: Link to connected data repository item [ctrl-alt-g]

values: Printable version of this page [ctrl-alt-p]

values: portal navigation p-wikibase-otherprojects p-wikibase-otherprojects-label

values: جدول هاش – Arabic

values: Хеш-таблица – Bulgarian

values:
interlanguage-link interwiki-bg
display: none;

values:
interlanguage-link interwiki-bs
display: none;

values:
interlanguage-link interwiki-ca
display: none;

values:
interlanguage-link interwiki-cs
display: none;

values:
https://da.wikipedia.org/wiki/Hashtabel
Hashtabel – Danish
da
da
interlanguage-link-target

values:
interlanguage-link interwiki-da
display: none;

values:
interlanguage-link interwiki-et
display: none;

values: Πίνακας κατακερματισμού – Greek

values:
interlanguage-link interwiki-el
display: none;

values:
interlanguage-link interwiki-eo
display: none;

values: جدول درهم‌سازی – Persian

values:
interlanguage-link interwiki-fa
display: none;

values: 해시 테이블 – Korean

values:
interlanguage-link interwiki-hr
display: none;

values:
interlanguage-link interwiki-it
display: none;

values: טבלת גיבוב – Hebrew

values:
interlanguage-link interwiki-he
display: none;

values:
interlanguage-link interwiki-lv
display: none;

values:
interlanguage-link interwiki-lt
display: none;

values:
interlanguage-link interwiki-hu
display: none;

values: ഹാഷ് ടേബിൾ – Malayalam

values:
interlanguage-link interwiki-ml
display: none;

values:
https://nl.wikipedia.org/wiki/Hashtabel
Hashtabel – Dutch
nl
nl
interlanguage-link-target

values:
interlanguage-link interwiki-nl
display: none;

values: ハッシュテーブル – Japanese

values:
interlanguage-link interwiki-no
display: none;

values:
interlanguage-link interwiki-nn
display: none;

values:
interlanguage-link interwiki-pl
display: none;

values: Хеш-таблица – Russian

values:
interlanguage-link interwiki-simple
display: none;

values:
interlanguage-link interwiki-sk
display: none;

values: Хеш табела – Serbian

values:
interlanguage-link interwiki-sr
display: none;

values:
interlanguage-link interwiki-fi
display: none;

values:
interlanguage-link interwiki-sv
display: none;

values:
interlanguage-link interwiki-tl
display: none;

values: ตารางแฮช – Thai

values:
interlanguage-link interwiki-th
display: none;

values:
interlanguage-link interwiki-tr
display: none;

values: Геш-таблиця – Ukrainian

values:
interlanguage-link interwiki-uk
display: none;

values:
interlanguage-link interwiki-vi
display: none;

values: All languages (initial selection from common choices by you and others)

values:
suggestions
display: none; font-size: 13px;

values: mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Hash_table rootpage-Hash_table skin-vector action-view