Hash Table: Why Resize at Three-Quarters Full?

A hash table stores data by turning a key into a location. Instead of examining every stored item, it computes a hash value, converts that value into a bucket or slot index, and checks the resulting position. When the table distributes keys effectively and does not become too full, lookup, insertion, and deletion are expected to take constant time.

The central process is:

key -> hash value -> initial bucket or slot -> collision resolution

A collision occurs when two keys want the same location. Collisions are normal: a finite table has fewer positions than the potentially unlimited set of keys. A practical hash table therefore combines three ideas:

1. Compute an initial position from the key.
2. Resolve collisions through chaining or probing.
3. Resize and rehash entries before the table becomes too crowded.

The familiar resize threshold near three-quarters full is a performance policy. It is not a mathematical law that every implementation must use, but it provides useful space for future entries and helps keep collision-resolution work short.

1. From a key to a bucket​

Suppose a table has $m$ buckets. A hash function accepts a key $k$ and produces an integer hash value, written as $h(k)$. The table then reduces that value to the available index range. A common reduction is the remainder operation:

For example, if a table has $8$ buckets and a key produces hash value $42$, its initial bucket is:

The key initially belongs in bucket $2$.

The hash value does not need to be unique. In fact, it usually cannot be unique because many different keys must share a finite collection of buckets. Even different hash values can produce the same bucket after the remainder operation.

Consider a table with $5$ buckets and these already-computed hash values:

key       hash value       hash value modulo 5
red       11                1
blue      7                 2
green     16                1
yellow    9                 4

The resulting table is conceptually:

bucket 0: empty
bucket 1: red, green
bucket 2: blue
bucket 3: empty
bucket 4: yellow

The keys red and green both map to bucket $1$. That is a collision, not a failed hash computation. The collision strategy determines how both entries can be stored and later found.

A useful hash function spreads ordinary inputs across the available positions. If too many keys repeatedly map to one bucket, that bucket becomes long or crowded while other positions remain unused. Lookup then has to inspect many candidates, and the expected advantage of hashing starts to disappear.

2. Hash maps and hash sets​

A hash map stores associations between keys and values. A key might identify a word, a user, a category, or a prefix sum; its associated value might be a count, result, index, or collection. To retrieve a value, the map hashes the key and searches the entries associated with the resulting position.

A hash set stores keys for membership tests. It answers questions such as whether an item has already appeared. A set does not expose a separate value for each key, although its implementation still needs to store keys and internal bookkeeping information.

The usual workflow for either structure is:

1. Compute the key's hash value.
2. Reduce the hash to an initial bucket or slot.
3. Search the collision structure associated with that position.
4. Compare actual keys, not only hash values.
5. Return the value, report membership, insert a new entry, or remove an existing entry.

The key comparison in step four is essential. Unequal keys can have the same hash value, so a matching hash is only a candidate match. The table must verify equality before returning a result.

3. Why average operations are $O(1)$​

If keys are distributed reasonably evenly and the table maintains a suitable load factor, a lookup examines only a small expected number of entries. Computing a hash and selecting an index are treated as constant-time operations for the usual fixed-size key model. Searching a short chain or probe sequence is also expected to take constant time.

Under these ordinary average-case assumptions:

The word average, or expected, matters. A poor distribution can send many keys to the same bucket. An adversarial or unfortunate input can create a long chain or a long sequence of occupied probe slots. If $n$ keys effectively share one collision structure, a lookup can take $O(n)$ time. Thus, hashing provides expected constant-time operations, not an unconditional guarantee for every input.

The average-time claim depends mainly on two conditions:

• the hash function distributes keys effectively;
• the table is not allowed to become excessively full.

Resizing addresses the second condition. Collision resolution addresses the first condition and the unavoidable collisions that remain even with a good hash function.

4. Load factor​

The load factor measures how much data the table holds relative to its capacity. If $n$ is the number of stored entries and $m$ is the number of buckets or slots, then:

For a table with $8$ slots and $6$ entries:

The table is $75\%$ full, or three-quarters full.

Load factor is more than a storage statistic. It affects how likely a new key is to find its initial position occupied and how far it may need to search. As $\alpha$ increases, collisions and probe sequences generally become longer.

A table can define a maximum load factor. When an insertion would make the load factor exceed that threshold, the implementation allocates a larger table and rehashes the existing entries. A threshold near $0.75$ is common as a practical compromise, but the exact value depends on the collision strategy and implementation policy.

Chaining can technically support a load factor greater than $1$, because a bucket can contain several entries. Open addressing cannot store more entries than it has slots and normally resizes well before reaching $1$. For both designs, a lower load factor usually means shorter searches at the cost of more unused memory.

5. Chaining​

With chaining, each bucket refers to a collection of entries rather than holding only one entry. The collection may be represented by a linked structure, a dynamic array, or another container. Using the earlier example, the table could look like this:

bucket 0: empty
bucket 1: (red, value-red) -> (green, value-green)
bucket 2: (blue, value-blue)
bucket 3: empty
bucket 4: (yellow, value-yellow)

To find green, the table computes bucket $1$ and scans the entries stored there. It compares each key until it finds green or reaches the end of the chain.

To insert another key that maps to bucket $1$, the table adds that entry to the bucket's collection. To delete an entry, it removes the matching item from the collection. Deletion is relatively direct because removing one entry does not invalidate a search path through other buckets.

For chaining, the load factor can exceed $1$. For example, a table with $4$ buckets and $10$ entries has:

This is possible because several entries can share a bucket. However, if keys are evenly distributed, the average chain becomes longer as $\alpha$ increases. A lookup must perform more key comparisons, so expected constant-time behavior becomes less attractive as the table fills.

Chaining also needs rehashing after a resize. If the capacity changes from $m$ to $2m$, the new bucket calculation becomes:

An entry that was in one old bucket may belong in a different new bucket. The table must visit the existing entries and place them according to the new capacity.

6. Open addressing​

Open addressing stores entries directly in the table's slots. There is no separate chain attached to a bucket. If the initial slot is occupied, the table follows a probe sequence to inspect alternative slots.

A general probe formula is:

Here, $i$ is the probe number, $m$ is the table capacity, and $p(k,i)$ determines the offset from the initial position. The initial attempt uses $i=0$. Later attempts use $i=1$, $i=2$, and so on.

Open addressing needs empty slots. An unsuccessful search uses an empty position as evidence that the key is not present, provided the search has followed the same probe sequence used during insertion. As the table becomes full, finding an empty slot requires more probes. This is why open-addressed tables usually resize before they reach capacity.

Two important probing methods are linear probing and double hashing.

7. Linear probing​

Linear probing examines consecutive slots. If the initial slot is occupied, the algorithm checks the next slot, then the next, wrapping around at the end of the table.

For a table with $7$ slots and an initial position of $5$, the sequence is:

5, 6, 0, 1, 2, 3, 4

The wraparound follows modular arithmetic. If the current slot is $6$, the next slot is:

Linear-probing example​

Assume a table with $7$ slots and three keys whose initial positions are:

key       initial position
A         2
B         2
C         3

Insert A first. Slot $2$ is empty, so A occupies it. Insert B. Its initial slot $2$ is occupied, so the table checks slot $3$ and places B there. Insert C. Its initial slot $3$ is occupied by B; the table checks slot $4$ and places C there.

The result is:

slot 0: empty
slot 1: empty
slot 2: A
slot 3: B
slot 4: C
slot 5: empty
slot 6: empty

This creates a consecutive occupied region. Linear probing tends to produce primary clustering: once a cluster exists, collisions into any part of that region may require scanning through it. The method is simple and stores entries directly in the table, but probe lengths become increasingly sensitive to the load factor.

Deletion and tombstones​

Deletion requires special care in an open-addressed table. Suppose A occupies slot $2$ and B was displaced from slot $2$ to slot $3$. If slot $2$ is simply cleared, a later search for B may stop at slot $2 and incorrectly conclude that B is absent.

Implementations commonly use a special deleted marker, often called a tombstone. A tombstone says that the slot is not currently occupied but that a search must continue through it. New insertions may eventually reuse the position, while lookups continue past it.

Too many tombstones can lengthen probe sequences even when the table does not contain many live entries. An implementation may periodically rebuild or resize the table to remove them. This is another reason that capacity management affects more than the number of live entries.

8. Double hashing​

Double hashing uses a second hash-derived value to determine the probe step. A common formula is:

The first hash, $h_1(k)$, supplies the initial position. The second hash, $h_2(k)$, supplies the step size. For a table of size $7$, suppose:

The first several positions are:

The sequence begins:

2, 5, 1, 4, ...

Unlike linear probing, which always advances by one, double hashing gives different keys different step patterns when their second hash values differ. This can reduce the shared clusters created by consecutive probing.

The second hash must be chosen carefully. If the step size and table capacity interact badly, a probe sequence may visit only part of the table and fail to reach available positions. The exact requirements depend on the capacity policy, but the practical principle is simple: the second hash should produce useful, sufficiently varied steps.

Double hashing requires an additional hash calculation and more careful design than linear probing. In return, it can distribute probe paths more broadly.

9. Why resize near three-quarters full?​

The threshold $\alpha=0.75$ means that only one-quarter of the table's slots remain empty. For an open-addressed table, those empty slots must serve all future insertions and unsuccessful searches. They also need to be distributed usefully across the table rather than concentrated in a few isolated places.

As the load factor rises:

• more keys initially select occupied slots;
• probe sequences become longer;
• linear-probing clusters become larger;
• unsuccessful searches inspect more positions;
• insertions require more attempts;
• tombstones have a greater effect on search paths;
• the table has less room to absorb new entries.

A threshold near three-quarters creates a safety margin. The table grows before it becomes completely full and before probe sequences become excessively long. Resizing earlier uses more memory but tends to give faster operations. Resizing later uses capacity more aggressively but accepts more collision-resolution work.

The threshold is not universal. Chaining may tolerate a different value because it can store multiple entries in one bucket. Open addressing is especially sensitive to high load factors because every entry must occupy a physical slot. The important principle is to grow before crowding causes the expected short search path to become long.

10. Doubling and rehashing​

A common growth policy is to double the capacity. Suppose a table has $8$ slots and reaches six entries:

The next insertion may trigger growth to $16$ slots. After moving the existing entries, the load factor is:

If the insertion is completed after the resize, the new table contains seven entries:

The entries cannot simply remain in their old bucket positions because the capacity appears in the bucket calculation. For a key with hash value $14$:

That key moves from index $6$ to index $14$. For another key, the old and new indexes may happen to be the same. Every entry must nevertheless be reconsidered under the new capacity.

A resize generally performs these steps:

1. Allocate a larger table.
2. Visit every existing entry.
3. Recompute its bucket or initial slot with the new capacity.
4. Insert it using the chosen collision strategy.
5. Replace the old table.

One resize costs $O(n)$ because as many as $n$ existing entries may need to move. However, geometric growth such as doubling avoids resizing on every insertion. Over a long sequence of operations, the total movement work is spread across many insertions, giving amortized insertion time of $O(1)$ under the usual assumptions.

Amortized $O(1)$ does not mean that every insertion is individually constant time. An insertion that triggers rehashing can take $O(n)$ time. The amortized statement means that the total cost of many insertions, including occasional growth, is proportional to the number of inserted entries when capacity grows geometrically.

11. A complete resize example​

Consider an eight-slot table with a maximum load factor of $0.75$. After six entries have been stored:

Suppose the next insertion triggers a resize. The new capacity is $16$, and the six existing keys plus the new key must be placed again. Each new position is calculated using the new capacity:

For a key with hash value $19$:

This key happens to retain index $3$. For a key with hash value $14$:

This key moves. Other entries can move as well, and collisions must be resolved again in the new table.

The final table has more available positions and a lower load factor. That lower load factor is the reason future operations can again use short expected chains or probe sequences.

12. Hashing compared with sorting​

Hashing and sorting address different needs. A hash table is designed for exact-key access: given a key, find its value or determine whether it exists. With a good distribution, lookup is expected to be $O(1)$.

Sorting arranges a collection according to an order. Comparison-based sorting commonly costs:

After sorting, binary search can find an item in $O(\log n)$ time. The sorted order also supports range queries, ordered output, and comparisons between neighboring values.

Hashing is often the better choice when:

• only exact membership or exact key lookup is needed;
• key order is irrelevant;
• expected constant-time updates are valuable;
• additional table capacity is acceptable.

Sorting is often better when:

• the result must be ordered;
• range queries are important;
• neighboring values matter;
• ordered traversal is required;
• the data arrives as a batch and can be processed after sorting.

A hash table's performance depends on hashing, collision resolution, and load-factor management. Sorting does not depend on distributing keys among buckets. Conversely, sorting does not normally provide expected constant-time arbitrary updates in a changing collection.

13. Hashing compared with balanced trees​

A balanced search tree keeps keys in sorted order. Lookup, insertion, and deletion are typically $O(\log n)$ in the worst case. This is slower than the expected $O(1)$ operations of a well-maintained hash table, but a balanced tree naturally supports order-related operations.

A balanced tree can efficiently support tasks such as:

• finding the smallest or largest key;
• finding a predecessor or successor;
• iterating through keys in sorted order;
• finding keys in an interval.

A hash table is optimized for exact-key access rather than ordering. Finding the minimum key or all keys in a range generally requires additional work.

Space behavior also differs. A hash table allocates bucket or slot capacity and may intentionally leave unused space to maintain a low load factor. A balanced tree allocates nodes and pointers and maintains structural links. The appropriate structure depends on whether the main requirement is fast expected exact lookup or ordered operations with worst-case logarithmic bounds.

14. Frequency counting with a hash map​

Frequency counting maps each item to the number of times it has appeared. For every input item, the algorithm looks up its key, increments its count if present, or creates a count of one.

For example:

apple, pear, apple, orange, pear, apple

produces:

apple  -> 3
pear   -> 2
orange -> 1

If there are $n$ input items and each map operation is expected to take $O(1)$ time, the complete count takes expected $O(n)$ time. If $u$ distinct items occur, the map uses $O(u)$ additional space.

A balanced tree can also count frequencies, but each update typically costs $O(\log u)$. Hashing is attractive when sorted output is unnecessary. If counts must later be printed in key order, a tree or a separate sorting step may be more appropriate.

15. Deduplication with a hash set​

A hash set records which items have already appeared. For each incoming item, test membership. If the item is absent, add it and retain it. If it is present, skip it as a duplicate.

For $n$ input items and $u$ distinct items, expected total time is $O(n)$ and additional space can reach $O(u)$. The set is useful for removing repeated values, preventing repeated work, and checking whether an event or identifier has already been seen.

The set's central operation is membership. It does not need to associate a meaningful application value with each key, unlike a map.

16. Two-sum style lookups​

In a two-sum style problem, the input contains numbers and a target $T$. For a current number $x$, the required partner is:

A set or map records numbers already seen. For each new number, compute its partner and check whether that partner is present. If it is, a matching pair has been found.

The algebra is:

With expected constant-time membership checks, a one-pass approach takes expected $O(n)$ time and $O(n)$ additional space in the worst case. A sorting-based method can sort the values and use two pointers, typically taking $O(n\log n)$ time for sorting. The choice depends on whether expected lookup speed, ordering, memory, or input mutation matters more.

The hash table's job is to remember enough earlier information to answer the complement question without scanning every previous number.

17. Grouping values​

Grouping maps a group key to a collection of items. The group key may be a category, a normalized representation, or another computed identifier. For each item, compute its group key, locate the corresponding map entry, and append the item to that group's collection.

The result might look like this:

fruit     -> [apple, pear]
vegetable -> [carrot, spinach]

If there are $n$ items and group-key computation is treated as constant time, the map operations contribute expected $O(n)$ total time, excluding the cost of producing and storing the grouped output itself. Hashing is especially convenient when groups appear dynamically and their keys are not known in advance.

18. Caching​

A cache maps a request key to a previously computed result. On a request, the program hashes the key and checks the map. A hit returns the stored result. A miss performs the underlying computation and inserts the new result.

Expected fast lookup is valuable because checking the cache should be cheaper than repeating the work it is intended to avoid. A cache may also need a capacity limit and an eviction policy, but the key-to-value lookup is the hash-map part of the design.

The load-factor principle still applies. A cache table that becomes too full can make frequent checks more expensive. Maintaining spare capacity helps keep the lookup path short, while a separate cache policy determines which stored results should be removed when the cache's logical limit is reached.

19. Prefix-sum maps​

A prefix-sum map stores a previously observed prefix sum, often together with an index or a frequency. Let $P_i$ be the running sum through position $i$. If a subarray ending at position $i$ should have sum $T$, a preceding prefix sum $P_j$ must satisfy:

Rearranging gives:

During a scan, the algorithm computes the needed earlier prefix sum and checks the map. A lookup replaces a search through all earlier positions with an expected constant-time query.

The stored value depends on the problem. A map may store the earliest index for each prefix sum when seeking a longest qualifying subarray, or it may store a frequency when counting how many subarrays satisfy a sum condition. In both cases, the map remembers earlier states under keys that can be queried directly.

20. Correctness details​

Hashing is fast only when its correctness rules are respected.

First, equal keys must have compatible hash behavior. If two keys compare equal, the table must be able to find them consistently. Second, unequal keys may share a hash, so the implementation must compare actual keys after reaching a candidate entry. Third, resizing must move every entry according to the new capacity. Keeping an entry at its old bucket can make it unreachable by a later lookup.

For open addressing, lookup and insertion must use compatible probe sequences. An entry inserted using one sequence must be searched using the same sequence. Deletion must preserve enough information for later searches, usually with a tombstone or a rebuilding step.

For chaining, deletion can remove an item from its bucket collection without disturbing other buckets. Resizing still requires entries to be assigned according to the new bucket count.

These details explain why a hash table is more than an array plus a remainder operation. The index calculation, equality checks, collision policy, deletion behavior, and resize policy must work together.

21. Choosing a collision strategy​

Chaining is conceptually straightforward and makes deletion relatively simple. It can tolerate load factors above one because a bucket can contain several entries. Its trade-offs include extra collection storage and the indirection involved in following a bucket's chain.

Linear probing stores entries directly in the table and can use contiguous storage efficiently. It is simple, but primary clustering can increase probe lengths as the table fills. Deletion also requires tombstones or rebuilding.

Double hashing uses a second hash to create more varied probe sequences. It can reduce clustering compared with simple consecutive probing, but it requires another hash calculation and careful step-size design.

No collision strategy eliminates the need for capacity management. Chaining suffers from long chains when its load factor becomes high. Open addressing suffers from long probe sequences and must preserve empty positions. Keeping the table below an appropriate threshold is part of the algorithm, not an optional optimization.

22. Practical takeaways​

A hash table combines a fast key-to-position calculation with a collision strategy and a growth policy. Its basic model is:

Chaining follows a collection attached to the initial bucket. Open addressing searches other slots. Linear probing checks consecutive positions. Double hashing uses a second hash to choose the step pattern.

The load factor is:

As $\alpha$ grows, collisions and search paths generally grow. Resizing near three-quarters full is a practical compromise: it leaves enough capacity to keep searches short without allocating a new table after every few insertions. Doubling causes an individual resize to cost $O(n)$, but geometric growth makes insertion $O(1)$ amortized under the usual assumptions.

Use a hash map for expected fast exact-key lookup, frequency counting, grouping, caching, two-sum complements, and prefix-sum state. Use a hash set when membership and deduplication are the main goals. Prefer sorting or a balanced tree when order, range queries, ordered traversal, or worst-case logarithmic guarantees matter more than expected constant-time exact lookup.

The guiding principle is simple: compute a slot quickly, resolve collisions correctly, and resize before crowding turns short expected searches into long ones.