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.
Go example and implementation choices
Reading a missing map[int]int entry returns zero, so counts[value]++ correctly handles the first occurrence. This convenience would be insufficient if zero itself needed to distinguish presence, as it does in some memoization tasks. The output slice is allocated to the exact input length and filled by index. Neither map iteration order nor append growth controls result ordering.
Worked example
func FrequencyCounts(values []int) []int {
counts := make(map[int]int)
for _, value := range values { counts[value]++ }
output := make([]int, len(values))
for index, value := range values { output[index] = counts[value] }
return output
}
Continue in Go
Open Hash Tables for the complete course explanation. The course keeps your saved programming-language choice. Use this standalone page to inspect the Go 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 Go interview preparation guide connects these language choices with further practice and the cross-language operation reference.