Hash Map

Python provides a built-in dict class that implements the Hash Map data structure. However, for the purpose of understanding, we'll implement our own simplified version of a Hash Map in Python.

Here's an example implementation of a Hash Map in Python:

class HashMap:
    def __init__(self):
        self.size = 1000  # initial size of the hash map
        self.buckets = [[] for _ in range(self.size)]  # list of buckets

    def _hash(self, key):
        # Compute the hash value for the given key
        return hash(key) % self.size

    def put(self, key, value):
        # Insert or update a key-value pair in the hash map
        hash_value = self._hash(key)
        bucket = self.buckets[hash_value]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Update the existing key-value pair
                return
        bucket.append((key, value))  # Insert a new key-value pair

    def get(self, key):
        # Retrieve the value associated with the given key from the hash map
        hash_value = self._hash(key)
        bucket = self.buckets[hash_value]
        for k, v in bucket:
            if k == key:
                return v  # Return the value if the key is found
        return None  # Return None if the key is not found

    def remove(self, key):
        # Remove a key-value pair from the hash map
        hash_value = self._hash(key)
        bucket = self.buckets[hash_value]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]  # Delete the key-value pair
                return

# Example usage:
hash_map = HashMap()
hash_map.put("apple", 5)
hash_map.put("banana", 10)
print(hash_map.get("apple"))  # Output: 5
print(hash_map.get("banana"))  # Output: 10
hash_map.remove("apple")
print(hash_map.get("apple"))  # Output: None

In this implementation, we define a HashMap class with methods for put(), get(), and remove(). The _hash() method computes the hash value for a given key using Python's built-in hash() function. We use the hash value to determine the bucket where the key-value pair will be stored.

The put() method inserts or updates a key-value pair in the hash map. It first computes the hash value for the key and retrieves the corresponding bucket. It then iterates over the key-value pairs in the bucket and checks if the key already exists. If it does, the method updates the value. If not, it appends a new key-value pair to the bucket.

The get() method retrieves the value associated with a given key from the hash map. It follows a similar process as the put() method, computing the hash value and retrieving the bucket. It then iterates over the key-value pairs in the bucket and returns the value if the key is found.

The remove() method removes a key-value pair from the hash map. It computes the hash value, retrieves the bucket, and iterates over the key-value pairs. If the key is found, it uses the del keyword to delete the key-value pair from the bucket.

Now, let's solve a problem from LeetCode using the Hash Map concept.

Problem: Two Sum Description: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to the target.

Here's the solution using a Hash Map:

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

# Example usage:
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target))  # Output: [0, 1]

In this solution, we iterate over the array nums using the enumerate() function to keep track of the indices. For each element num, we calculate the complement by subtracting it from the target. We then check if the complement exists in the hash map. If it does, we return the indices of the current element and the complement. If not, we add the current element to the hash map with its index.

The time complexity of this solution is O(n) since we iterate over the array once. The space complexity is also O(n) in the worst case if all elements are stored in the hash map.