Advanced Hash Tables

Learning Objectives Explain what a hash collision is and why it occurs. Implement separate chaining to resolve hash collisions. Implement open addressing (linear probing) to resolve hash collisions. Compare and contrast the trade-offs between separate chaining and open addressing. Calculate the load factor of a hash table and explain its impact on performance. Describe the concept of rehashing and when it is necessary. Ever wonder how a social media app can find your friend's profile out of a billion users in a split second? 🤔 The magic behind it is a super-efficient data structure called a hash table! In this tutorial, we'll dive deeper into hash tables, a powerful tool for storing and retrieving data almost instantly. We'll explore what happens when two it...

TermDefinitionExample Hash CollisionWhen two different keys produce the exact same hash value, meaning they are mapped to the same index in the hash table's underlying array.If our hash function is `key % 10`, both the key `17` and the key `27` would produce the hash value `7` (17 % 10 = 7 and 27 % 10 = 7), causing a collision at index 7. Separate ChainingA collision resolution technique where each index in the hash table's array points to a linked list (or another data structure) of all the key-value pairs that hashed to that index.If keys `17` and `27` both hash to index 7, we would create a linked list at index 7. The list would contain the node for `17` followed by the node for `27`. Open AddressingA collision resolution technique where all key-value pairs are stored directl...

Load Factor Formula α = n / m Use this to calculate the load factor (α), where 'n' is the number of elements currently in the hash table and 'm' is the size (capacity) of the hash table's array. A high load factor (e.g., > 0.75) signals that collisions will become frequent, slowing down operations. Separate Chaining Insertion Algorithm 1. Compute hash(key) to get index. 2. Go to the linked list at that index. 3. Traverse the list to see if the key already exists. If so, update its value. 4. If the key does not exist, add a new node with the key-value pair to the end (or beginning) of the list. This is the standard procedure for adding or updating an element in a hash table that uses separate chaining. It ensures all items hashing to the same spot...