A hash table maps keys to table positions with a hash function so that a key can be found in almost constant time. This tool shows in a table where collisions occur and where each key is stored as the keys are inserted in order. Switch the collision-resolution method to see how the search effort changes.
Favorites and recently used calculators are stored only in this browser (localStorage).
Result
Load factor (number of keys ÷ table size)
–
Keys that collided
–
Average probes to store
–
Search–
How each key was stored
Comparison of collision-resolution methods
The number of probes is the number of positions examined until a key is stored (or found). For chaining, it counts the key's position in the list at its slot. With quadratic probing, depending on the table size and load factor, an empty position may not be found even though one exists.
See it as a graph
Other inputs stay at their current values while the chosen input varies from 1/4 to 4 times its current value. The red dot is the current value.
Hash tables and collisions
A hash table is a data structure that computes a table position from a key with a hash function and places the data at that position. If the keys are spread well, a key can be found in almost constant time regardless of how many keys there are. However, different keys can map to the same position; this is called a collision. Inserting 10, 17, 24 and 3 into a table of size 7 with h(k) = k mod 7 maps all four to position 3, so they collide. Collisions cannot be avoided, so how they are resolved determines performance.
Chaining and open addressing
Chaining links the keys that map to the same position in a linked list. The table never overflows and deletion is easy, but following the list takes extra search time and accesses scattered memory locations. Open addressing, on a collision, looks for another empty position in the table and stores the key there; depending on how it steps, there are linear probing (by 1 at a time), quadratic probing (by 1, 4, 9 …) and double hashing (by a step determined by each key). It cannot store more keys than the table size, and deletion requires a “deleted” marker.
Load factor and number of probes
The number of keys divided by the table size is called the load factor. The higher the load factor, the more collisions occur, and with open addressing in particular the number of probes rises sharply. Linear probing tends to form runs of consecutive occupied positions (clusters), and a key that hits a cluster makes it even longer, which is called clustering. Quadratic probing and double hashing reduce these clusters by stepping differently. Compare the average number of probes in the examples “Linear probing forming a cluster” and “Spreading keys with quadratic probing and double hashing”. Real hash tables enlarge the table and reinsert the keys (rehashing) when the load factor exceeds roughly 0.5 to 0.75.
Choosing a hash function
A good hash function spreads the keys evenly over the whole table. With k mod m, choosing a prime m makes the positions less biased even when the keys have a pattern (all even, all multiples of 10, and so on). Simply adding up the character codes of a string makes keys that are just rearrangements of the same letters, such as cat, act and tac in the example, always collide, so in practice each character is weighted before adding, among other techniques. Hash tables are used in many places, such as dictionaries (associative arrays) in programming languages, hash indexes in databases, and cache lookups.
ABeing able to work out the original key from its hash value
BDifferent keys producing the same hash value (storage position)
CThe same key producing a different hash value each time the program runs
Show answer and explanation
Answer: B. Different keys producing the same hash value (storage position)
A hash table computes a storage position from the key with a hash function, allowing search, insertion and deletion in O(1) on average. Because there are far more possible keys than table slots, different keys landing on the same position (a collision) cannot be avoided. Collisions are therefore handled by methods such as chaining, which links the elements at the same position into a list, or open addressing, which looks for another free position. The same key must always produce the same hash value or lookups would fail, and whether the key can be recovered from the hash value is a property that matters for cryptographic use, not collisions.
All four keys leave a remainder of 3 when divided by 7, so each one first tries position 3. Key 10 goes into position 3; 17 finds position 3 taken and goes into position 4; 24 finds positions 3 and 4 taken and goes into position 5. Key 3 finds positions 3, 4 and 5 taken and is stored at position 6. As this shows, linear probing makes occupied positions bunch together (clustering), so keys that arrive later need more probes.
AChaining can store elements even when the load factor exceeds 1, but open addressing cannot store more elements than the table size, and its number of probes rises sharply as the load factor approaches 1
BOpen addressing has no collisions, so a search always takes one probe regardless of the load factor
CWith chaining, the search cost stays the same however high the load factor becomes
Show answer and explanation
Answer: A. Chaining can store elements even when the load factor exceeds 1, but open addressing cannot store more elements than the table size, and its number of probes rises sharply as the load factor approaches 1
Chaining links elements at the same position into lists, so it can store more elements than the table size, but the average list length grows in proportion to the load factor and so does the search cost. Open addressing stores everything inside the table, so it can hold at most as many elements as the table size, and the number of probes to find a free slot rises sharply as the load factor approaches 1. With either method, it is usual to enlarge the table and reinsert all elements (rehash) once the load factor exceeds a chosen limit, such as about 0.5 to 0.75. Collisions also occur in open addressing; it handles them by looking for a free position.
AAfter a collision, the next position checked is the neighboring element, which is often in the same cache line or the next one, so fewer memory accesses are needed
BOpen addressing has no collisions at all
CChaining must compute the hash function two or more times
Show answer and explanation
Answer: A. After a collision, the next position checked is the neighboring element, which is often in the same cache line or the next one, so fewer memory accesses are needed
On modern CPUs, reading main memory after a cache miss takes far longer than computations such as comparisons. Linear probing checks the neighboring position after a collision, so most probes stay within the same cache line, and prefetching also helps. With chaining, the next element of a list is often somewhere else in memory, so each pointer followed is likely to cause a cache miss. Even with the same big-O complexity, the real speed can differ greatly depending on how memory is accessed. However, linear probing slows down sharply at high load factors as occupied positions cluster, so the load factor is kept fairly low.
FAQ
Which is faster, chaining or open addressing?
While the load factor is low, open addressing (especially linear probing) is often faster, because it examines consecutive positions in the table and so makes good use of the cache. As the load factor rises, the number of probes in open addressing increases sharply, so chaining is more stable.
Why choose a prime number for the table size?
Because with k mod m, if the keys and m share a common divisor, the positions used become biased. For example, with m = 10 and only even keys, only the even positions are used. If m is prime, such bias is less likely. For quadratic probing, it is also known that if m is prime and the load factor is 0.5 or less, an empty position is always found.
What is the time complexity of searching a hash table?
If the keys are spread well, it is O(1) on average (constant regardless of the number of items). In the worst case, however, where all keys collide at the same position, it becomes O(n).
How does this come up in exams?
IT certification exams such as Japan's Fundamental Information Technology Engineer Examination often give a hash function and a collision-resolution method and ask where a certain key is stored when the keys are inserted in order. Choose an example and compare the “Positions probed” in the table with your own answer.