Unit 9: Dictionaries, Hashing, and Sets
Looking a value up by key instead of by position, the hash function underneath, and what happens when two keys collide.
6 topics · 19 questions
Each topic is a path, not a menu: work down it in order and every question builds on the one above. Click any of them to watch the answer draw itself.
Dictionaries and Key-Value Lookup
- How it worksHow does a dictionary jump straight to a key's value instead of scanning every entry like a list would?
- Worked exampleTrace ages = {'Ana': 17, 'Ben': 19} then ages['Ben'] and ages.get('Cal', 0).
- Common mistakeWhy isn't looking something up in a dictionary the same speed as searching through a list?
Your turn1 of 2
A dictionary holds 69645 key-value pairs. Looking up a key takes roughly constant time regardless of size, while searching a list of the same n items checks all of them in the worst case. How many comparisons would the list-based search need in its worst case?Hash Functions: Turning a Key into an Index
- How it worksHow does a hash function take a key, produce a number, then reduce it to a valid slot with a modulo?
- Worked exampleTrace hashing the keys cat and dog into a table of 5 slots using hash(key) % 5.
- Common mistakeWhy doesn't a good hash function need to produce a different number for every possible key?
Your turn1 of 2
A hash function produces a raw hash value that equals 33 full table sizes of 15 plus a remainder of 2 (where 0 ≤ r < n). What raw hash value is this, computed as q times n plus r?Resolving Collisions with Chaining
- How it worksHow does chaining store every key that lands in one slot as a small linked list hanging off that slot?
- Worked exampleTrace inserting cat, dog, and rat into a 3-slot chained table where cat and rat both hash to slot 1.
- Going furtherWhat happens to a lookup's speed once one slot's chain grows to hold twenty keys?
Your turn1 of 2
A chained hash table has 36 slots, and one slot's chain has grown to hold 33 keys due to repeated collisions. In the worst case, how many keys might a lookup in that slot need to check?Resolving Collisions with Open Addressing
- How it worksHow does linear probing walk forward one slot at a time until it finds an empty spot for a colliding key?
- Worked exampleTrace inserting 12, 22, and 7 into a 5-slot table with open addressing where 12 and 22 both hash to slot 2.
- Common mistakeWhy doesn't deleting a key from an open-addressed table just leave that slot marked empty right away?
- Ties togetherHow does open addressing's probing compare with chaining's linked lists on the exact same collision?
Your turn1 of 2
Linear probing walks forward one slot at a time until it finds an empty spot. A key hashes to slot 7, and the next 7 slots in a row are already occupied before an empty one is found. At which slot index does the key finally get placed?Resizing and Rehashing a Hash Table
- How it worksHow does growing a hash table force every existing key to be re-hashed into a bigger array of slots?
- Worked exampleTrace a 4-slot table doubling to 8 slots and re-hashing the keys 3, 6, and 11 into their new positions.
- Common mistakeWhy isn't a hash table lookup always O(1) once you count in the occasional resize?
Your turn1 of 2
A hash table with 698 slots doubles its size once it grows too full, becoming n times 2 slots. If the table currently holds 649 keys, all of which must be re-hashed into the new, larger table, how many total keys get re-hashed during this resize?Sets and Set Operations
- How it worksHow does a set use the exact same hashing trick as a dictionary but store just the keys, no values?
- Worked exampleTrace {1, 2, 3} union {2, 3, 4}, then the same two sets intersected, then the first minus the second.
- Going furtherWhat happens to membership testing speed once a list of a million items becomes a set instead?
Your turn1 of 2
Two sets, one with 73 elements and one with 68 elements, share 8 elements in common. How many distinct elements does their union contain?