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.