Almost every backend codebase leans on a hash table somewhere. In Java it is HashMap, in Python it is dict, in JavaScript it is Map or a plain object, in C# it is Dictionary. Most developers use them daily without thinking about what happens inside. That is fine until a lookup that should take microseconds starts taking milliseconds, or a cache quietly eats several gigabytes. Understanding the mechanics makes those problems much easier to spot.

The basic trick: turn a key into an address

An array is fast because you can jump straight to position 42 without looking at positions 0 to 41. A hash table borrows that speed for keys that are not numbers. It runs the key through a hash function, which produces an integer, and then reduces that integer to a position in an internal array. Those positions are usually called buckets.

So when you write map.put("EMP1023", record), the map computes a hash of the string, picks a bucket from it, and stores the entry there. When you later call map.get("EMP1023"), it repeats the same calculation, lands on the same bucket, and returns what it finds. No scanning of the whole collection is needed. That is where the “constant time on average” description comes from.

Collisions are normal, not a bug

There are far more possible keys than buckets, so two different keys will sometimes land in the same bucket. This is a collision, and every real hash table expects it. The question is only how it copes.

Java’s HashMap keeps a small linked list in each bucket. On a lookup it goes to the bucket and then walks that short list, comparing keys with equals() until it finds a match. Since Java 8 there is a refinement: if one bucket’s list grows beyond eight entries (and the table has at least 64 buckets), that list is converted into a balanced tree, so a badly crowded bucket costs a logarithmic search instead of a linear one. Python’s dict takes a different route called open addressing, where a colliding key simply probes for another free slot in the same array. Different designs, same goal: keep the number of comparisons small.

Why hashCode and equals must agree

The bucket is chosen by the hash; the final match is confirmed by equality. If two objects are equal but produce different hash codes, they will be sent to different buckets, and the map will happily store what you think is the same key twice. The usual way this bites a team is a custom class used as a key, such as an EmployeeId with a department and a number, where someone overrides equals() and forgets hashCode(). Everything compiles, tests with one or two records pass, and then production starts showing duplicate entries and missed lookups.

A related trap is mutating a key after inserting it. If a field that feeds the hash changes, the entry now sits in a bucket that no longer matches its hash. The map cannot find it, and it cannot remove it either. Immutable keys (strings, records, value objects with final fields) avoid this entirely.

Load factor and resizing

As the table fills up, collisions become more frequent. To keep buckets short, the table grows. Java’s default load factor is 0.75, which means that once the number of entries exceeds three quarters of the bucket count, the map roughly doubles its array and moves every entry to its new position. This is called rehashing.

Rehashing is expensive at the moment it happens, but it happens rarely, so the average cost of an insert stays low. If you already know you are about to load two lakh records, passing an initial capacity to the constructor avoids a long series of intermediate resizes. It is a small change that shows up clearly in profiling during bulk loads.

When the “instant” lookup is not instant

  • Poor hash functions. If a custom hashCode() returns the same value for many objects (an extreme example is returning a constant), every entry ends up in one bucket and the map degrades into a list.
  • Deliberate collisions. Attackers have historically sent web requests with many parameter names crafted to collide, forcing servers to do heavy work per request. Language runtimes added randomised hashing and tree buckets partly for this reason.
  • Concurrent writes. A plain HashMap is not safe to modify from several threads. Use ConcurrentHashMap, which splits locking so readers rarely block, rather than wrapping everything in one big lock.
  • Memory overhead. Each entry carries the key, the value, the cached hash and pointers. For millions of small entries, that overhead can exceed the data itself. Primitive-specialised collections or a sorted array with binary search can be far leaner.

Ordering is not part of the deal

A hash table makes no promise about iteration order in general. Java offers LinkedHashMap when you need insertion order (handy for simple LRU caches) and TreeMap when you need keys sorted. Python’s dict has preserved insertion order since version 3.7 as a language guarantee, which is why code that relies on it works there but would be fragile if ported to a language without that guarantee.

A quick way to reason about it

When you reach for a hash table, three questions cover most of what matters: Is my key’s hash well spread and consistent with equality? Will the key stay unchanged while it is in the map? Do I need order, thread safety or very low memory, which might point to a different structure? If you can answer those, you understand hash tables better than most of the code that uses them.

Written by the RP Strativa Team. Behaviour described for Java refers to OpenJDK 8 and later.

Leave a Reply

Trending