6:42
L-6.3: Chaining in Hashing | What is chaining in hashing with examples
Gate Smashers
Overview
This video explains the concept of chaining in hashing, a method for resolving collisions. It details how chaining works using a linked list structure at each hash table slot. The explanation covers the process of inserting elements, the advantages like easy deletion, and disadvantages such as potential for long search times in the worst case and the use of extra space. The video also defines the load factor and its calculation.
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- Chaining, also known as open hashing, is a collision resolution technique in hash tables.
- Collisions occur when the hash function maps multiple keys to the same slot in the hash table.
- Chaining resolves collisions by storing colliding elements in a linked list associated with that slot.
Understanding chaining is crucial because it's a fundamental method for handling data conflicts in hash tables, ensuring that all data can be stored and retrieved efficiently.
Using a hash function K mod 5 with keys 42, 19, 10, and 12: 42 maps to slot 2, 19 to slot 4, 10 to slot 0. When 12 (12 mod 5 = 2) also maps to slot 2, it's added to a linked list at that slot, with 12 preceding 42.
- Each slot in the hash table can potentially hold the head of a linked list.
- When a key hashes to a slot, a new node is created for that key, similar to linked list node creation.
- This node contains the data and a pointer to the next node in the chain.
- For new insertions into a slot that already has elements, the new node is typically added at the beginning of the linked list for efficiency.
This chapter explains the mechanics of chaining, illustrating how data is organized and linked, which is essential for understanding its performance characteristics.
When 12 hashes to slot 2 (where 42 already exists), a new node for 12 is created. Its pointer is set to point to the existing node (42), and the slot's pointer is updated to point to the new node (12), effectively inserting 12 at the head of the linked list.
- Advantage: Deletion is relatively easy, similar to deleting from a linked list, by updating pointers.
- Advantage: Insertion is generally efficient, often taking constant time if new nodes are added at the beginning of the list.
- Disadvantage: Searching can be time-consuming in the worst case, potentially taking O(n) time if all keys hash to the same slot, forming a long linked list.
- Disadvantage: Chaining uses extra memory to store pointers for the linked lists, in addition to the space for the keys themselves.
Weighing the pros and cons helps in deciding when chaining is an appropriate hashing strategy, balancing ease of implementation with potential performance bottlenecks.
Deleting 12 from the chain at slot 2 involves updating the pointer of the node before 12 (if any) to point to the node after 12, and then freeing the node containing 12. In the example, if 12 is at the head, the slot's pointer would be updated to point to 42.
- The worst-case scenario for chaining occurs when all keys hash to the same slot, resulting in a single, long linked list.
- In this worst case, both searching and deletion operations degrade to O(n) time complexity, where n is the number of elements.
- The load factor (alpha) is defined as the ratio of the total number of elements (keys) to the total number of slots in the hash table.
- A high load factor can indicate a greater likelihood of long chains and poorer performance.
Understanding the worst-case performance and the load factor is critical for predicting and managing the efficiency of a hash table that uses chaining.
If keys like 2, 12, 32, 42, 52, 62 all hash to slot 2 (using K mod 5), a long chain forms at that single slot, making searches and deletions inefficient.
Key takeaways
- Chaining resolves hash collisions by using linked lists at each hash table index.
- Insertion in chaining is typically fast, especially when adding new elements to the front of a linked list.
- Deletion is also a strong point of chaining, mirroring linked list deletion.
- The primary drawback of chaining is the potential for O(n) time complexity for search and deletion in the worst-case scenario.
- Chaining requires additional memory for pointers, making it less space-efficient than some other methods.
- The load factor (number of elements / number of slots) is a key metric for assessing the performance of a hash table using chaining.
Key terms
ChainingOpen HashingCollisionHash FunctionHash TableLinked ListNodePointerLoad FactorTime Complexity
Test your understanding
- How does chaining fundamentally differ from other collision resolution techniques like linear probing?
- Explain the process of inserting a key into a hash table that uses chaining, especially when a collision occurs.
- What makes deletion an advantageous operation in a hash table employing chaining?
- Describe the worst-case scenario for searching in a hash table that uses chaining and why it occurs.
- How is the load factor calculated, and what does it signify regarding the performance of chaining?