🚀 Welcome to the Beginner’s Guide to Hash Tables in Data Structures!

Hash Tables are one of the most powerful data structures in computer science, and they're used everywhere — from storing key-value pairs in a dictionary to implementing databases and caching mechanisms. If you're starting your programming journey or preparing for interviews, understanding hash tables is a must.

---

🔍 What is a Hash Table?

A hash table (or hash map) is a data structure that stores data in an associative manner. In simpler terms, it stores data in key-value pairs.

Imagine a real-life dictionary. You search for a word (key) to get its definition (value). A hash table works similarly.

---

⚙️ How Does It Work?

1. Hash Function: Converts the key into an index for storing in an array.

2. Array Storage: The value is stored at the computed index.

3. Collision Handling: If two keys hash to the same index, a strategy like chaining or open addressing is used to resolve the conflict.

# Python Example
my_dict = {}
my_dict["name"] = "Sayan"
print(my_dict["name"])  # Output: Sayan

🧠 Why Use Hash Tables?

• ⚡ Fast access – Average time complexity: O(1) for insert, delete, and search.

• 🧱 Efficient for large datasets

• 🧠 Widely supported in programming languages (e.g., dict in Python, Map in JavaScript)

---

🔥 Real-World Applications

• 🔍 Database indexing

• 🧠 Caching (e.g., LRU Cache)

• 📘 Symbol tables in compilers

• 🌐 Routing tables in networks

---

⚔️ Common Interview Questions

🛠️ Implement a HashMap from scratch

• Here’s a basic implementation of a HashMap using:

  • An array (list) of fixed size is used with chaining (using lists) to handle collisions.

    class MyHashMap:
        def __init__(self):
            self.size = 1000
            self.buckets = [[] for _ in range(self.size)]

        def _hash(self, key):
            return hash(key) % self.size

        def put(self, key, value):
            index = self._hash(key)
            for pair in self.buckets[index]:
                if pair[0] == key:
                    pair[1] = value
                    return
            self.buckets[index].append([key, value])

        def get(self, key):
            index = self._hash(key)
            for pair in self.buckets[index]:
                if pair[0] == key:
                    return pair[1]
            return -1

        def remove(self, key):
            index = self._hash(key)
            for i, pair in enumerate(self.buckets[index]):
                if pair[0] == key:
                    self.buckets[index].pop(i)
                    return

✅ Example Usage:

    pythonCopyEdithmap = MyHashMap()
    hmap.put("name", "Sayan")
    print(hmap.get("name"))  # Output: Sayan
    hmap.remove("name")
    print(hmap.get("name"))  # Output: -1

• 🧩 Find the first non-repeating character in a string using a hash table

Problem: Return the index of the first non-repeating character in a string. Return -1 if none exist.

pythonCopyEditdef first_unique_char(s):
    from collections import OrderedDict

    freq = OrderedDict()

    for char in s:
        freq[char] = freq.get(char, 0) + 1

    for index, char in enumerate(s):
        if freq[char] == 1:
            return index
    return -1

✅ Examples:

pythonCopyEditprint(first_unique_char("leetcode"))  # Output: 0
print(first_unique_char("aabb"))      # Output: -1

• 🧮 Two Sum problem (Leetcode #1)

  Problem: Given an array nums and a target value, return the indices of the two numbers that add up to the target.

    pythonCopyEditdef two_sum(nums, target):
        hashmap = {}
  
        for i, num in enumerate(nums):
            complement = target - num
            if complement in hashmap:
                return [hashmap[complement], i]
            hashmap[num] = i
  

  ✅ Example:

    pythonCopyEditprint(two_sum([2, 7, 11, 15], 9))  # Output: [0, 1]
  

  🧠 Tip: This uses a hash map to store the index of each number as you traverse the array, checking for the complement of the current number.

---

✅ Key Takeaways

• Hash Tables store data in key-value pairs.

• They're fast, efficient, and powerful.

• Mastering them helps in interviews and real-world software development.

---

🙌 Final Thoughts

If you're diving into data structures and algorithms, hash tables are a perfect place to start. Experiment with them in your favorite language, try implementing one yourself, and solve problems on platforms like LeetCode, GeeksforGeeks, and HackerRank.