Introduction
A hash map turns a key into a bucket number. The useful idea is simple: find the bucket first, then deal with any other keys that happened to land there too.
The mental model
A hash map stores a key and a value, but it does not search every key from the beginning each time. It first turns the key into a number, uses that number to choose a bucket, and then searches only the entries in that bucket.
The Hash-Map repository uses an array of buckets. Each bucket is a KeyedLinkedList, passed into the constructor as new HashMap(KeyedLinkedList). A list node stores a key, a value, and a nextNode reference. This approach is called separate chaining: one bucket can contain a chain of several entries instead of requiring every key to have its own array position.
The descriptions in this article are separated deliberately:
- Documented behaviour comes from the repository README and source files.
- Demonstrated behaviour comes from running the current source with small examples.
- Design reflection is my judgement about what the implementation makes easier to understand or what I would tighten next.
From a string key to a bucket
The repository accepts string keys. Its hash method starts at zero and processes each character using the multiplier 31. The remainder operation keeps the intermediate value within the current capacity:
hashCode = (31 * hashCode + key.charCodeAt(i)) % this.#capacity;
The returned number is already in the range 0 through capacity - 1, so it can be used as an index in the bucket array. Applying the remainder operation after each step is part of this implementation, not a requirement for every hash map. The important point is that the final bucket index must be valid for the current capacity.
For example, with the repository's initial capacity of 16, "ab" and "a" both produce bucket 1 under this calculation. Different strings can therefore select the same bucket. A collision does not mean either key is lost; it means the bucket's linked list must distinguish them by comparing their keys.
The lookup path is therefore:
- Check that the key is a string.
- Hash the key using the current capacity.
- Select that bucket.
- Traverse its keyed list and compare keys with strict equality.
set calls findNode(key) first. An existing node is updated in place; a missing key is appended to the bucket. get returns the matching value or null, while has returns a boolean. remove finds the node's index in the chain and removes that list node, returning true only when a key was present.
What a collision looks like
Suppose bucket 1 contains ("a", 10). Setting ("ab", 20) hashes to the same bucket at capacity 16. The second entry is appended to that bucket's chain:
bucket[1] -> ( a: 10 ) -> ( ab: 20 ) -> null
The chain is why key comparison matters. Looking up "ab" does not stop at the first node merely because the bucket matched; it follows nextNode until the key matches or the chain ends. If many keys collide, that chain becomes longer and the operation approaches a linear scan of the entries in that bucket.
The repository also exposes keys(), values(), and entries(). These methods scan every bucket from index zero upward and then walk each non-empty chain. Their output order is bucket traversal order, not insertion order promised by the project.
Growing the bucket array
The map starts with capacity 16 and a load-factor threshold of 0.75. The load factor is the number of stored entries divided by the number of buckets. length() counts nodes across all buckets, and currentLoad() divides that count by capacity. After inserting a new key, growHashMap() checks whether the threshold has been exceeded. If it has, the implementation doubles capacity, creates a fresh bucket array, and reinserts every entry through set.
Rehashing is necessary because the modulo depends on capacity. An entry that was in bucket 1 when the capacity was 16 may belong in a different bucket when the capacity is 32. Copying each entry to the same numeric index would preserve the old distribution rather than recompute the new one.
The source does not shrink the map after removals. clear() replaces the bucket array but leaves the current capacity unchanged. The README documents the resize threshold and operations; the source is the authority for these details.
A small reproducible run
The following example uses the repository classes and the current Node.js runtime. It intentionally chooses the colliding keys "a" and "ab" at the initial capacity:
const map = new HashMap(KeyedLinkedList);
map.set("a", 10);
map.set("ab", 20);
console.log(map.get("ab")); // 20
console.log(map.has("a")); // true
console.log(map.entries()); // contains ["a", 10] and ["ab", 20]
map.set("ab", 99); // updates, does not add a second "ab"
map.remove("a"); // true
That output demonstrates the collision strategy and update semantics. It does not prove a performance benchmark; no benchmark is included in the repository.
Complexity without saying “always O(1)”
Let n be the number of stored entries, m the number of buckets, and k the length of a string key. Hashing costs O(k) because the method visits each character. If entries are distributed across the buckets reasonably well, the chain being searched is usually short. However, if many keys collide, the chain can become long and the operation can approach a scan of all n entries.
| Operation | Current implementation | Typical assumption | Worst case |
|---|---|---|---|
hash(key) |
scans key characters | O(k) |
O(k) |
get, has |
hash then scan one chain | expected near O(k) |
O(k + n) |
set existing key |
hash then scan one chain | expected near O(k) |
O(k + n) |
set new key |
chain scan, append, load check | expected near O(k) |
O(k + n); resize adds rehashing |
remove |
chain scan then unlink | expected near O(k) |
O(k + n) |
length |
scans every chain | O(n + m) |
O(n + m) |
keys, values, entries |
scans every bucket and node | O(n + m) |
O(n + m) |
| resize | reinsert all entries | — | O(n · k) for key hashing plus traversal |
These are structural costs, not measured timings. The repository's separate-chaining design explains why a hash map can be fast in typical conditions without promising that every access takes constant time. The key length, number of entries, bucket capacity, and collision pattern all matter.
What this project clarified for me
The most useful connection to the earlier linked-list project is that the list is not competing with the map. It is the collision-resolution mechanism inside the map. The map narrows the search to a bucket; the keyed list handles the remaining local sequence.
Passing the linked-list class into the constructor also keeps the map coupled to a small interface rather than hard-coding one list implementation. That is a useful modularity lesson, although the current map still expects methods such as findNode, append, removeAt, size, and the head getter.
The implementation is a learning project, not a drop-in replacement for JavaScript's built-in Map. It accepts only string keys, exposes its own null-for-missing convention, and does not document iteration-order guarantees. Those are boundaries to keep visible when transferring the idea to application code.
Key takeaways
- A hash map computes a bucket index before it searches for a key.
- Distinct keys can collide; separate chaining stores them together in a keyed linked list.
- Updating an existing key changes its node instead of appending a duplicate.
- Resizing requires rehashing because the capacity is part of the bucket calculation.
- Expected near-constant access depends on a useful distribution and a controlled load factor; the worst case is still a chain traversal.