Skip to content
AITroveRead. Build. Understand.
Reading list
Make this comfortable

Hash maps: keyed lookup with collision and load costs

Last updated: 4 Oct 20269 min read
tutorial
IntermediateBy AITrove Editorial

A hash map assigns a key to a bucket using a hash function, then resolves collisions among keys sharing a bucket. Lookups, insertions, and deletion are expected O(1) under ordinary hashing and controlled load; worst-case work can be O(n). Correctness requires equal keys to have equal hash values and keys not to change their hash-relevant state while stored. A map's key is an identity choice, not just a performance choice: using only a shipment number without tenant scope can join two different customers' records. Python dictionaries handle collisions and resizing internally, but application key design remains the caller's responsibility.

Operational case

Two depots both issue shipment number S-47. A global index keyed only by S-47 would overwrite one status with the other. The application uses a tuple of depot ID and shipment ID, so North/S-47 and South/S-47 remain distinct. The map returns a status quickly for a verified key, but it does not enforce tenant permissions by itself; the request layer must decide which depot key the caller may query. If the status object is mutable, returning it directly can also expose shared state that another request changes.

Working Python program

python
shipment_status = {
    ("north", "S-47"): "held",
    ("south", "S-47"): "queued",
}
print(shipment_status[("north", "S-47")])
print(len(shipment_status))

Output

Output
held
2

Time, space, and tradeoff

The example uses O(n) space for n keyed records and expected O(1) lookup. Resizing occasionally copies table entries, making a single insertion more expensive than the average. If every operation must have a strict worst-case bound, this ordinary hash-map contract may be insufficient. Use immutable tuple keys, test duplicate identifiers across scopes, and avoid relying on iteration order as a substitute for a sorting requirement.

Common Mistakes

  • Do not describe hash-map operations as guaranteed worst-case O(1).
  • Do not omit tenant scope from a key that must be unique across tenants.
  • Do not mutate a stored key's equality-relevant state.

Connected lessons

Open-addressed hash tables: tombstones and rebuilds continues this operation with mutation checks.

Inverted indexes: intersect sorted incident postings adds a related indexing contract.

LFU caches: evict by frequency, then recency adds a related lifecycle choice.

HyperLogLog: estimate unique IDs with fixed registers adds a bounded stream contract.

Blocked Bloom filters: localize probes and watch skew extends the membership design choices.

Spatial hash grids: move points between occupied cells adds another spatial query contract.

Bitmap hash tries: copy paths for immutable alert maps adds a keyed lookup comparison.

Extendible hashing: split buckets through a shared directory adds a keyed lookup comparison.

Linear hashing: split one bucket at a time as a table grows adds a distinct structure contract to compare.

data structures
hash-tables
Storage details