A data structure that computes a storage position from a key with a hash function, allowing search, insertion and deletion in O(1) on average. Collisions, where different keys map to the same position, are handled by chaining or open addressing.
Japanese name: ハッシュテーブル
Hash table appears in 5 practice questions across 2 topics, including Data Structures and Algorithms, Probability, Statistics and Queueing.
A hash table converts a key into an integer with a hash function and uses, for example, its remainder when divided by the table size as the storage position. There are far more possible keys than positions, so collisions, where different keys map to the same position, cannot be avoided. Chaining links the elements at the same position, for example in a linked list. Open addressing looks for another free position within the table, using methods such as linear probing, which checks the neighboring positions in turn, or double hashing, which uses a second hash function to choose the step.
The number of stored elements divided by the table size is called the load factor. With chaining, the average list length is proportional to the load factor; with open addressing, the number of probes to find a free slot rises sharply as the load factor approaches 1. When the load factor exceeds a chosen limit, the table is therefore enlarged, typically to about twice its size, and all elements are reinserted (rehashing). A rehash takes O(n), but because the intervals between enlargements keep doubling, the cost per insertion stays at amortized O(1).
The O(1) average assumes the hash function spreads keys evenly over the table. A poor hash function, or input crafted to cause collisions (a hash flooding attack), can slow it down to O(n) in the worst case, so web servers and similar software use hash functions mixed with a random seed. A hash table also does not keep its elements in order, so binary search trees or B-trees are better for range searches and ordered listing. Real speed also depends on cache behavior: schemes that check neighboring slots, such as linear probing, are often faster than chaining, which follows pointers.
Answer: B. 0.45
There are 10C2 = 45 pairs of keys, and each pair lands in the same bucket with probability 1/100. By the linearity of expectation (the expected value of a sum is the sum of the expected values), the expected number of pairs in the same bucket is 45 × 1/100 = 0.45. Linearity of expectation holds even when the pairs are not independent, so the probabilities of the pairs can simply be added.
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.
A hash function computes a value in a fixed range from a key, and a hash table is a data structure that uses it to compute storage positions. Hash functions for hash tables emphasize speed and even distribution and usually do not need one-wayness like cryptographic hash functions.
They are used wherever values must be looked up quickly by key, such as dictionaries (associative arrays) and sets in programming languages, symbol tables in compilers, hash joins and hash indexes in databases, and cache management.
A hash table computes a storage position from the key with a hash function, allowing search, insertion and deletion in O(1) on average.
Which is the correct description of a collision in a hash t…As an Amazon Associate I earn from qualifying purchases.
Hash function Expected value Modulo operation Linked list Cache line Prefetching Pointer Binary heap Binary search Binary search tree