Hash Tables

# Python dict internally hash table वापरतो
student_grades = {}

# Insert — O(1)
student_grades["Avadhoot"] = 95
student_grades["Rahul"] = 87
student_grades["Priya"] = 92

# Lookup — O(1)
print(student_grades["Avadhoot"])  # 95

# Check existence — O(1)
print("Rahul" in student_grades)   # True

# Delete — O(1)
del student_grades["Rahul"]

# Iterate
for name, grade in student_grades.items():
    print(f"{name}: {grade}")

# Problem: array मध्ये दोन numbers शोधा जे target ला add होतात
def two_sum(nums, target):
    seen = {}   # value → index

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

    return []

# Without hash: O(n²) nested loops
# With hash: O(n) single pass!
print(two_sum([2, 7, 11, 15], 9))  # [0, 1] → 2+7=9

# Problem: most frequent element शोधा
from collections import Counter

def most_frequent(arr):
    count = Counter(arr)  # {element: frequency}
    return count.most_common(1)[0][0]

print(most_frequent([1, 3, 2, 1, 4, 1, 3]))  # 1

# Counter — built-in hash table for counting
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
freq = Counter(words)
print(freq)  # Counter({'apple': 3, 'banana': 2, 'cherry': 1})