Understanding Hash Maps

Introduction

• Importance of learning Hash Maps
  • Commonly used data structure in real-world applications like database indexing, caching, compilers.
  • Fundamental for software engineering and highly performant code.

Basics of Hash Maps

• A collection of key-value pairs.
• Operations: Insert, find, delete elements.
• Faster than other data structures like lists for most use cases.

Implementation

• Typically implemented on arrays where each element contains key and value.

Hash Function

• Assigns a slot for each key in an array.
• Produces a hash value to determine the slot.
• Handles large numbers by taking remainder when dividing by array size.

Handling Collisions

• Collision: Occurs when a slot is already taken by another key.
• Collision Resolution Techniques:
  • Closed Addressing (Chaining)
    • Store elements with the same hash in a bucket (linked list, array, or balanced tree).
    • Each slot in the array becomes a linked list.
  • Open Addressing
    • All elements stored in array slots directly.
    • Uses probing to find empty slots.

Chaining

• Using linked lists to handle collisions.
• Time Complexity:
  • Worst case: Proportional to length of list.
  • Average case: O(1) for search, insertion, deletion.
• Load Factor (α): n/m, where n is elements, m is slots.
  • High load factor suggests need for rehashing (creating a larger array).

Open Addressing

• No additional lists; array slots either contain elements or are empty.
• Load factor never exceeds 1.
• Probing: Sequence of slots checked for empty space.
  • Linear Probing: Next slot is checked sequentially.
  • Quadratic Probing: Better distribution than linear.
  • Double Hashing: Uses two hash functions for better distribution.

Deletion

• Mark as deleted instead of removing.
• Search continues until an empty slot is found.

Choosing Between Open and Closed Addressing

• Closed Addressing
  • Simpler to implement.
  • May waste memory due to storage of buckets.
• Open Addressing
  • Better memory usage.
  • Improved cache performance.
  • Use when keys and their frequency are known.

Good Hash Function

• Ensures equal likelihood for keys to hash to any slot.
• Should be fast to compute.

Conclusion

• Understanding Hash Maps is crucial for efficient coding.
• Subscribe for more tech and computer science content.
• Share with friends who may find it useful.