Hash Table

Hash Table is a data structure that provides efficient key-value pair storage, retrieval, and deletion operations. It uses a hashing function to convert keys into indices of an array, allowing for constant-time access to elements on average.

Python's built-in dict class is an example of a Hash Table. However, we will create our own simplified version of a Hash Table in Python for better understanding.

Here's an example implementation of a Hash Table:

class HashTable:
    def __init__(self):
        self.size = 1000  # initial size of the hash table
        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 table
        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 table
        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 table
        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_table = HashTable()
hash_table.put("apple", 5)
hash_table.put("banana", 10)
print(hash_table.get("apple"))  # Output: 5
print(hash_table.get("banana"))  # Output: 10
hash_table.remove("apple")
print(hash_table.get("apple"))  # Output: None

In this implementation, we define a HashTable 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 table. 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 table. 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 table. 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 Table 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 Table:

def two_sum(nums, target):
    hash_table = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in hash_table:
            return [hash_table[complement], i]
        hash_table[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 table. If it does, we return the indices of the current element and the complement. If not, we add the current element to the hash table 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 table.