Map keys to values in average O(1) time using hash functions.
A hash table maps keys to array slots via a hash function; collisions are resolved by chaining or open addressing. Average O(1) insert, lookup and delete; load factor triggers resizing. Good hash functions distribute keys uniformly. Python dicts and Java HashMaps use them.
A word-frequency counter uses a dictionary from word to count.
Hash tables give very fast lookup by key, which is why they are used in caches, symbol tables and indexes.
Map keys to values in average O(1) time using hash functions.
Hash tables give very fast lookup by key, which is why they are used in caches, symbol tables and indexes.
This is a collision, handled by chaining or open addressing, and too many collisions slow the table down.
Worst-case collisions can make lookups slow, and resizing the table takes time, so the O(1) bound is an average over typical inputs.
Typical applications include counting word frequencies in a document, storing user settings by name in an application and checking if a device ID has already been seen in a stream.
Study "Linked lists" first (topic 20 of 104 in Software & Computing). It covers the groundwork this topic builds on.
Collision resolution. Load factor ~0.7. Hash flooding attacks.
A word-frequency counter uses a dictionary from word to count.
The next topic is "Trees", which builds directly on this one.
It is classed as Beginner in Software & Computing (topic 21 of 104). It is an entry-level topic. It relies only on basic school mathematics and the ideas introduced earlier in this discipline.
Want to practise? Open the interactive course for quick checks, quizzes, simulations and progress tracking.