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!