Hashing Chaining
Introduction
- Hashing Chaining is a method of Open Hashing to avoid collisions (when two elements hash to the same index).
- Uses a linked list at each index to handle collisions.
Hash Table Setup
- Hash table size: m = 10.
- Hash function: x modulo 10.
- Each index points to a linked list, essentially making the hash table an array of pointers to linked lists.
- Can handle any number of elements without limit due to chaining.
Insertion
- Insert elements using the hash function to determine the index:
- 2: 2 modulo 10 = 2
- 11: 11 modulo 10 = 1
- 12: 12 modulo 10 = 2
- 25: 25 modulo 10 = 5
- 9: 9 modulo 10 = 9
- 8: 8 modulo 10 = 8
- 29: 29 modulo 10 = 9
- 122: 122 modulo 10 = 2
- 1: 1 modulo 10 = 1
- 10: 10 modulo 10 = 0
- Insert values in the corresponding linked list at each index.
- Maintain order in the linked list based on values.
Searching Elements
- Search in the linked lists at the calculated index:
- Ex: 122: Start at index 2, traverse list to find 122 using 3 comparisons.
- Ex: 5: Start at index 5, find immediately with 1 comparison.
- Ex: 30: Start at index 0, not found; stop.
Analysis
- Loading Factor (λ/α): Defined as n/m.
- Complexity of a successful search: O(1 + λ/α).
- Complexity of an unsuccessful search: O(1 + λ/α).
- Uniform distribution of the loading factor is crucial for optimal performance.
Average Case Analysis
- Success: Average comparisons = (1 + λ)/2.
- Unsuccess: Average comparisons = 1 + λ.
Deletion
- Similar to searching:
- Find the element using the hash function and linked list traversal.
- Remove the element, adjust pointers as needed.
Key Points
- Programmer responsibility: Ensure the hash function provides uniform distribution.
- Adequate understanding of data to choose the best hash function.
- Uniform distribution makes the hash table efficient.
- Hashing chaining is simple but requires careful handling of linked lists and hash function.
Summary
- Insert: Use hash function and append to linked list.
- Search: Traverse linked list at hashed index.
- Delete: Locate element in linked list and remove.
- Analyze: Understand loading factor and uniform distribution for efficiency.
See you in the next video!