Hashing Chaining

Jul 13, 2024

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!