Hash Maps Lecture Notes

Introduction

• Topic: Hash Maps
  • Important for data structures, algorithms, and interview preparation.
  • Part of the complete data structures and algorithms bootcamp.

Importance of Hash Maps

• Used in various problems including:
  • Trees
  • Dynamic programming
  • Sorting
  • Heaps
• Allows for constant-time access to elements.

Overview of Hash Maps

• Structure: Key-Value Pairs
  • Example: "Kunal" : 88 marks.
• Each entry in a hash map consists of a key and its corresponding value.
• Hash maps allow access in constant time, unlike arrays (O(n)) and binary search trees (O(log n)).

How Hash Maps Work

1. Hash Code
   • A function that converts keys (strings, integers) into numeric hash codes.
   • Example: hash("Kunal") gives a hash code, let's say 3.
2. Storage
   • Hash maps use an array to store these key-value pairs at the index corresponding to the hash code.
3. Retrieving Values
   • Accessing a value is done by computing the hash code and directly accessing the index.

Real-World Uses of Hash Maps

• Compilers and interpreters (C, C++, Java, Python)
• Network routers (IP address routing)
• Virtual memory management
• Cryptography (hashing)
• String search (e.g., grep command)

Internal Mechanisms

• Hash Function: Transforms keys into integers for array indexing.
  • Issues:
    • Large hash codes need to be reduced (e.g., using modulo).
    • Collisions (multiple keys leading to the same index) need resolution.

Collision Resolution Techniques

1. Chaining
   • Each index points to a linked list of entries that fall under that index.
   • Pros: Can handle multiple items at the same index.
2. Open Addressing
   • All elements are stored in the main array.
   • Probing strategies include Linear Probing and Double Hashing.

Load Factor and Resizing

• Load factor ( alpha) = n / m (number of items / size of table).
• If the load factor exceeds a certain threshold (e.g., 0.75), the hash map resizes by doubling.
• This keeps the operations efficient (amortized O(1) time complexity).

Hash Functions

• Different hash functions include:
  • Division Method: h(k) = k % m
  • Multiplication Method: More complex mathematical functions.
  • Universal Hashing: Provides a probabilistic guarantee against collisions.

HashMap in Java

• Java's Map interface implementations include HashMap, LinkedHashMap, and TreeMap.
• HashMap is not synchronized, whereas Hashtable is synchronized and thread-safe.
• HashMap allows for one null key and multiple null values.

Implementation of Hash Maps

1. Basic Structure: Key-value pair storage.
2. Methods:
   • put(key, value): Adds an entry.
   • get(key): Retrieves the value for the given key.
   • remove(key): Deletes an entry.
   • containsKey(key): Checks if a key exists.
3. Custom Implementation:
   • Can be implemented using linked lists for collision handling.

Summary

• Hash maps are essential data structures for efficient data retrieval.
• Understanding their internal workings and implementation can significantly aid in coding interviews and practical applications.

Next Steps

• Upcoming videos will focus on coding questions and further concepts utilizing hash maps.