15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Topic 7 of 12 in the free DSA Basics course · 6 lessons
Build a model of how hash-based collections store and find data.
The lesson covers direct addressing and hashing, keys that map to the same location, table behavior as it fills, and maps and sets for counting repeated values and checking whether a value has appeared before.
No prior lessons are required.
Be comfortable with array indices, basic arithmetic including remainder (mod), and operations such as insert, search, and delete.
Use the keys [12, 22, 5] with a table capacity of 10 and this hash function:
1h(k) = k mod 10The table has indices 0 through 9.
h(12) = 2, so 12 maps to index 2.h(22) = 2, so 22 also maps to index 2.h(5) = 5, so 5 maps to index 5.12 and 22 have different keys and the same table index. The hash function produced a valid index for both keys. The table needs a collision-handling rule so storing 22 does not overwrite 12.
With chaining, index 2 can hold a small sequence:
1index 2: 12 -> 22
2index 5: 5With open addressing, 12 might occupy index 2, and 22 would probe forward until it finds another empty slot, such as index 3.
The running example traces insertion, lookup, deletion, table fullness, and the map and set operations built on hashing.
Direct Addressing vs Hash Table compares two ways to use an array for keys. Hashing compresses a large or sparse key range, which makes collisions possible.
Hash Functions establishes deterministic key-to-index mapping. Distinguish a key, such as 22, from its computed index, such as 2, and check that every result fits inside the table's index range.
Collision Handling - Chaining introduces a strategy for keeping multiple keys at one index. Use a bucket or chain to insert, search for, and delete colliding keys without affecting neighboring keys.
Collision Handling - Open Addressing keeps every entry in the main array and searches for an available slot by probing. Chaining establishes why collisions must be preserved instead of overwritten.
Load Factor and Rehashing explains what happens as a table fills. More entries usually mean longer searches, and resizing requires recomputing indices.
Frequency Maps and Sets applies the earlier mechanics to collection tasks. A frequency map stores a count for each key; a set stores only whether a key is present.
A hash table begins with a deterministic hash function. Deterministic means that when you look up 22 later, the function computes the same starting index it used during insertion. Without that consistency, the table would not know where to search.
Direct addressing is the simpler alternative: if keys range from 0 to 9, use each key itself as an index. If possible keys are sparse or very large, an array covering every possible key wastes space. Hashing reduces that range to a smaller table, so different keys can share an index.
A shared index is a collision. Collision Handling - Chaining keeps colliding entries together in one bucket. Collision Handling - Open Addressing finds another slot in the array through a probe sequence. Both approaches preserve enough information for future search and deletion. An open-addressing table cannot always clear a deleted slot completely, because a later lookup may need to probe through that position to reach an entry farther along the sequence.
As entries are added, the load factor
1α = number of entries / table capacityincreases. A higher load factor means longer chains on average or more probing on average. Load Factor and Rehashing allocates a larger table and reinserts entries. Recomputing each hash is necessary because changing the capacity changes results such as k mod m; copying entries to their old indices would place them incorrectly.
Maps and sets use these lookup operations as building blocks. For a stream like [12, 22, 12, 5], a frequency map becomes:
112 -> 2
222 -> 1
35 -> 1A set for the same stream contains:
1{12, 22, 5}Use a map when the count matters. Use a set when you only need presence or absence.
In Direct Addressing vs Hash Table, decide how you would represent a small dense range such as scores 0 through 100, then compare it with a sparse range such as large user IDs.
Start with Hash Functions by calculating indices for several keys and identifying collisions. For the running example, verify that 12 and 22 both map to 2.
In Collision Handling - Chaining, insert 12, 22, and 5; search for both an existing key and a missing key; then delete one key from the chain at index 2.
In Collision Handling - Open Addressing, insert the same keys using linear probing. Trace where each key lands, then examine why a deleted marker is needed after removing a key.
In Load Factor and Rehashing, count entries and capacity to compute the load factor. Resize a table, reinsert its entries using the new capacity, and compare the new positions with the old ones.
Finish with Frequency Maps and Sets by processing a short list of repeated values. Build a frequency map when you need totals and a set when you only need to detect duplicates or test membership.