Hash Tables and Dictionaries

A dictionary associates a value with a key, allowing retrieval by that key rather than by an arbitrary position. A word-frequency dictionary can map a normalised word to its count. Replacing a value for an existing key differs from adding another distinct key.

A hash table computes a storage location from the key. The hash function must give a consistent result for the same key under the table’s rules; equal keys must be treated consistently. A hash is not necessarily unique, and dictionary behaviour is not defined by the physical slot numbers.

For a simple table of length m, h(k)=k mod m maps integer keys into valid indices. If two different keys map to the same occupied slot, a collision occurs. An open-addressing policy such as linear probing checks successive positions, wrapping around the table.

Lookup must follow the same probe sequence and compare the actual keys, not simply accept the first occupied slot. Deletion may require a special marker so that a later displaced key remains discoverable. A table must also detect full storage or resize rather than probe forever.

A dictionary-based frequency count reads each word, applies the intended normalisation and updates the corresponding value. Case handling and punctuation rules affect what counts as the same key. An absent-key rule supplies the initial zero without confusing it with an existing count.

Hash tables commonly offer expected constant-time access under suitable assumptions, but many collisions or an unsuitable load factor can degrade performance. Rehashing into a new table can restore a useful distribution. “Average efficient” is not the same as “every lookup is guaranteed one comparison”.

counts = {}
for word in "red blue red green blue red".split():
    counts[word] = counts.get(word, 0) + 1
print(counts)

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.