A hash table associates a key with a value. A hash function chooses a storage location, and the table resolves cases where different keys choose the same location. That makes it useful for frequency counts, membership checks, and finding a previously seen complement. The recording introduces the representation before the implementation lesson builds the operations.
Separate a key from its bucket
Suppose two different names hash to bucket 3. Storing only a value at that index would lose the ability to distinguish the names. A chained table stores key-value pairs in the bucket and compares keys when looking up a match. The hash narrows the search; it does not prove that two keys are equal.
Updating a key should replace that key's value without creating a duplicate entry. Removing one key must leave colliding neighbors intact. Missing keys also need a defined result. If a table permits storing an absent-looking value, use a membership operation when you need to distinguish that stored value from a missing entry.
Qualify the constant-time claim
Expected constant-time lookup assumes a suitable hash distribution and a controlled load factor. A bucket holding every entry degenerates into a linear search. Growing a table can keep chains short, but rehashing moves existing entries and makes that particular operation more expensive. Explain the expected or amortized model instead of promising an unconditional constant worst case.
String keys have a length too. Computing a hash may inspect their characters, and an equality check may compare multiple characters. Treating those costs as constant can be reasonable for bounded identifiers; name that assumption when comparing algorithms over arbitrary text.
Choose key semantics before writing the loop
In JavaScript, a Map supports object identity keys and avoids the inherited-property behavior of an ordinary object. A dictionary intended for arbitrary string keys should handle those keys deliberately. The right representation depends on the contract, including whether two separately created objects count as the same key.
Follow Implement a Hash Table to trace collisions and deletion. Then compare Target Two Sum, where the table remembers earlier indexes, with Catch the Hacker, where it accumulates counts. Both use a table, but they store different facts and maintain different invariants.
Trace frequency updates without losing input order
For [7, 3, 7, 7], the example builds a frequency map and then returns [3, 1, 3, 3]. Each result position reports the total count of the value at the same input position. It is not a list of unique keys or an iteration over the map's entries. The second pass over the original input makes that ordering explicit.
After processing the first three values, the map contains 7 → 2 and 3 → 1. Reading the final 7 must retrieve its existing count before storing 3. Creating a fresh count of one on every visit would turn every result into one and discard the work already done.
Distinguish expected performance from a guarantee
With expected constant-time map operations, the two passes take O(n) expected time. The map stores O(u) distinct keys, where u is the number of unique input values, and the returned list uses O(n) storage. Hashing, equality, collisions, and resizing belong to the implementation behind that expected bound.
Use an empty input, all-equal values, alternating values, zero, and negative keys as checks. A missing key and a stored zero are different states; this algorithm stores only positive counts, but your lookup logic should still make its default policy readable. The hash table implementation lesson makes collisions visible by storing multiple key/value pairs in a bucket.
TypeScript example and implementation choices
Map<number, number> records the key and count types. The non-null assertion in the output pass relies on a runtime invariant: the first pass inserted every input value. It does not insert or validate anything by itself. If those passes could observe a mutated input or an external map, that assertion would need a stronger design or an explicit missing-key branch.
Worked example
function frequencyCounts(values: readonly number[]): number[] {
const counts = new Map<number, number>();
for (const value of values) counts.set(value, (counts.get(value) ?? 0) + 1);
return values.map(value => counts.get(value)!);
}
Continue in TypeScript
Open Hash Tables for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the TypeScript example and run it in your own local environment. Follow the original course sequence when you want the surrounding lesson context and related exercises.
The TypeScript interview preparation guide connects these language choices with further practice and the cross-language operation reference.