Use a hash to choose candidate storage
A hash table implements a dictionary by transforming a key into a hash value and using that value to choose candidate storage locations. In a toy table with eight buckets, assigning integer keys by their remainder modulo eight maps key 10 to bucket two. A hash is not a unique substitute for a key: different keys can map to the same bucket. Lookup must therefore compare candidate keys for equality. The equality rule and the hash rule must agree about which keys count as the same key.
Follow a collision through the table
Insert key 18 into the same toy table and it also maps to bucket two. Separate chaining stores multiple entries associated with that bucket, while open addressing searches other positions according to a probing rule. The rule must be applied consistently during lookup and deletion. For example, simply clearing a slot in an open-addressed table can break a probe sequence and hide keys stored later along it. A tombstone or another correct deletion strategy preserves the information needed to continue searching beyond that position.
Qualify the constant-time claim
Load factor is the number of stored entries divided by the number of buckets. Increasing it tends to increase the number of candidates or probes examined. Expected constant-time lookup relies on assumptions such as suitable hash distribution and controlled load, rather than holding for every possible input. If many entries collect in one chain, a lookup can take linear time in the number of entries. Resizing and rehashing also requires relocating existing entries, so an individual resize usually performs linear work even when ordinary operations are fast.
Match the dictionary to the query
A hash table is a good fit for equality-based membership and key-to-value lookup. It does not inherently support retrieving the smallest key, scanning keys in sorted order, or efficiently reporting a key range. A balanced search tree can be a better choice for those queries. With untrusted input, consider whether an attacker can deliberately concentrate collisions and degrade performance. Cryptographic properties, ordinary hash distribution, equality semantics, deletion rules, and iteration order are separate design questions. State the guarantees of the particular implementation instead of extending the abstract expected bound to every situation.
Do not break a probe chain on deletion
In an eight-slot table with h(key)=key mod 8 and linear probing, inserting 10, 18 and 26 places them at positions two, three and four. If deleting 10 turns slot two into a never-used empty slot, a search for 26 can stop there incorrectly. A tombstone that allows the search to continue, or an appropriate repair of the following cluster, is needed. Tombstones also affect performance: a table can contain few live entries yet still have long probe sequences after many deletions. The live-entry count alone is not a complete measure of an open-addressed table’s state.
Distinguish resizing from amortized insertion
Growing the table changes bucket selection, so existing keys must be redistributed. When the table grows from eight to sixteen slots, keys 10 and 18 no longer share their old remainder-two destination: their new remainders are ten and two. One insertion that triggers a rebuild can therefore cost O(n). Amortized O(1) insertion is not a guarantee of constant latency for every operation. Applications with strict latency requirements may consider incremental rehashing or reserving capacity. The equality-and-hash contract must remain consistent before and after resizing: keys considered equal must produce equal hash values.