Hashmaps
A hashmap, also known as a hash table, is a data structure that implements an associative array abstract data type—a structure that can map keys to values. Hashmaps are designed to provide fast insertion, deletion, and lookup of key-value pairs. In Python, the built-in dict type is an implementation of a hashmap.
A hashmap stores data in an array-like structure, where each position in the array corresponds to a hash code derived from a key. The key is processed through a hash function, which computes an index in the array where the corresponding value is stored.
Key Components:
Key: An immutable object used to uniquely identify a value in the hashmap.
Value: The data associated with a key.
Hash Function: A function that takes a key and returns an integer (the hash code), which determines where the key-value pair is stored in the array.
How It Works:
Hashing the Key: The key is passed through a hash function to generate a hash code.
Index Calculation: The hash code is mapped to an index in the array (usually by taking the modulus with the array size).
Storing the Value: The value is stored at the computed index in the array.
Collision Handling: If two keys hash to the same index (a collision), a collision resolution strategy like chaining or open addressing is used.
Why Use Hashmaps?
Efficiency: Provide average-case constant time complexity O(1) for insertion, deletion, and lookup operations.
Associative Access: Allow retrieval of values based on keys rather than numerical indices.
Flexibility: Can handle a large number of entries and are dynamic in size.
Real-World Applications: Useful in scenarios like caching, indexing databases, counting frequencies, and more.
Hashmaps in Python
In Python, hashmaps are implemented using the built-in dict type.
Features of Python Dictionaries:
Keys: Must be hashable (immutable types like strings, numbers, or tuples of immutable elements).
Values: Can be of any data type.
Dynamic: Automatically resize themselves to maintain performance.
Order Preservation: As of Python 3.7, dictionaries maintain the insertion order of keys.
Example 1: Simple Key-Value Storage
# Creating a hashmap (dictionary)
student_ages = {}
# Inserting key-value pairs
student_ages['Alice'] = 25
student_ages['Bob'] = 22
student_ages['Charlie'] = 23
# Accessing values
print(student_ages['Alice']) # Output: 25
# Updating a value
student_ages['Bob'] = 23
# Deleting a key-value pair
del student_ages['Charlie']
# Iterating over keys and values
for name, age in student_ages.items():
print(f"{name} is {age} years old.")
Example 2: Counting Word Frequencies
sentence = "the quick brown fox jumps over the lazy dog the fox was quick"
words = sentence.split()
word_frequencies = {}
# Counting frequencies
for word in words:
word_frequencies[word] = word_frequencies.get(word, 0) + 1
# Displaying word counts
for word, count in word_frequencies.items():
print(f"'{word}': {count}")
Output:
'the': 3
'quick': 2
'brown': 1
'fox': 2
'jumps': 1
'over': 1
'lazy': 1
'dog': 1
'was': 1
Example 3: Caching Function Results (Memoization)
def fibonacci(n, cache={}):
if n in cache:
return cache[n]
if n <= 1:
return n
else:
result = fibonacci(n-1, cache) + fibonacci(n-2, cache)
cache[n] = result
return result
print(fibonacci(10)) # Output: 55
In this example, a hashmap is used to cache the results of the Fibonacci function to avoid redundant calculations.
How Hashmaps Handle Collisions
Collisions occur when two keys hash to the same index. Python dictionaries handle collisions using open addressing with probing:
Open Addressing: Instead of storing multiple items at the same index, the algorithm probes for the next available slot.
Probing Sequence: Python uses a combination of linear probing and randomization to find the next slot.
Internal Implementation Details (Advanced)
While you can effectively use dictionaries without knowing their internals, understanding them can be beneficial.
Dynamic Resizing: The dictionary resizes itself when it reaches a certain load factor to maintain performance.
Hash Function: Python uses a built-in hash function (
hash()) which can be overridden for custom objects by defining__hash__()and__eq__()methods.Key Requirements: Keys must be immutable and hashable to ensure that the hash code remains constant.
Practical Applications of Hashmaps
Database Indexing: Quickly retrieve records based on keys.
Caching: Store expensive computation results for faster retrieval.
Configuration Management: Store settings and configurations as key-value pairs.
Data Grouping: Group data based on certain attributes.
Symbol Tables: In compilers and interpreters to store variable and function names.
Hashmaps in Algorithm
Hashmaps are an essential tool in algorithm problem-solving due to their ability to provide constant-time complexity for insertion, deletion, and lookup operations. They can be utilized in a variety of ways to optimize algorithms and simplify complex problems.
1. Two Sum Problem
Problem Statement
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
Thought Process
Brute Force Approach: Use two nested loops to check all pairs—O(n²) time complexity.
Optimized Approach with Hashmap:
Iterate through the list.
For each element, check if
target - nums[i]exists in the hashmap.If it exists, return the indices.
Else, store the current number with its index in the hashmap.
Python Code
def two_sum(nums, target):
num_to_index = {}
for index, num in enumerate(nums):
complement = target - num
if complement in num_to_index:
return [num_to_index[complement], index]
num_to_index[num] = index
return []
# Example Usage
nums = [2, 7, 11, 15]
target = 9
print(two_sum(nums, target)) # Output: [0, 1]
Explanation
Iteration 1:
num = 2,complement = 77not innum_to_index, store2:0
Iteration 2:
num = 7,complement = 22innum_to_index, return[0, 1]
2. Anagram Grouping
Problem Statement
Given an array of strings, group the anagrams together.
Thought Process
Anagrams have the same characters when sorted.
Use a hashmap where the key is the sorted tuple of the word’s letters.
Group words with the same sorted key.
Python Code
from collections import defaultdict
def group_anagrams(strs):
anagram_map = defaultdict(list)
for word in strs:
key = tuple(sorted(word))
anagram_map[key].append(word)
return list(anagram_map.values())
# Example Usage
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(strs))
# Output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
Explanation
Key Generation:
For “eat”: key = (‘a’, ‘e’, ‘t’)
Grouping:
Words with the same key are grouped together.
3. Counting Frequencies
Problem Statement
Count the frequency of each element in an array.
Thought Process
Use a hashmap to store elements as keys and their counts as values.
Iterate through the array and update counts.
Python Code
def count_frequencies(arr):
freq_map = {}
for elem in arr:
freq_map[elem] = freq_map.get(elem, 0) + 1
return freq_map
# Example Usage
arr = [1, 2, 2, 3, 3, 3]
print(count_frequencies(arr))
# Output: {1: 1, 2: 2, 3: 3}
Explanation
Initialize an empty hashmap.
For each element, increment its count.
4. Subarray Sum Equals K
Problem Statement
Given an array of integers and an integer k, find the total number of continuous subarrays whose sum equals to k.
Thought Process
Use a hashmap to store the cumulative sum frequencies.
Initialize
count = 0,cumulative_sum = 0.For each element:
Update
cumulative_sum.If
cumulative_sum - kexists in the hashmap, incrementcountby the frequency.Update the hashmap with the current
cumulative_sum.
Python Code
def subarray_sum(nums, k):
count = 0
cumulative_sum = 0
sum_freq = {0: 1}
for num in nums:
cumulative_sum += num
if (cumulative_sum - k) in sum_freq:
count += sum_freq[cumulative_sum - k]
sum_freq[cumulative_sum] = sum_freq.get(cumulative_sum, 0) + 1
return count
# Example Usage
nums = [1, 1, 1]
k = 2
print(subarray_sum(nums, k)) # Output: 2
Explanation
Cumulative Sum:
At each step, the cumulative sum includes all elements up to the current index.
Hashmap Use:
Stores the number of times a particular cumulative sum has occurred.
Subarrays Found:
When
(cumulative_sum - k)has occurred before, it means the subarray sums tok.
5. Longest Consecutive Sequence
Problem Statement
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
Thought Process
Use a set (hashmap without values) for O(1) lookups.
Iterate through the array.
For each element, if it’s the start of a sequence (no
num - 1in set), count the length of the sequence.
Python Code
def longest_consecutive(nums):
num_set = set(nums)
max_length = 0
for num in num_set:
if num - 1 not in num_set:
current_num = num
length = 1
while current_num + 1 in num_set:
current_num += 1
length += 1
max_length = max(max_length, length)
return max_length
# Example Usage
nums = [100, 4, 200, 1, 3, 2]
print(longest_consecutive(nums)) # Output: 4
Explanation
Sequence Start:
Only start counting if
num - 1is not in the set.
Counting Sequence Length:
Increment
current_numandlengthwhilecurrent_num + 1exists.
6. Detecting Cycles in Linked Lists
Problem Statement
Given a linked list, determine if it has a cycle.
Thought Process
Use a hashmap to store visited nodes.
Traverse the list and check if the current node is already in the hashmap.
Alternatively, use Floyd’s Tortoise and Hare algorithm without extra space.
Python Code
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def has_cycle(head):
visited_nodes = set()
current = head
while current:
if current in visited_nodes:
return True
visited_nodes.add(current)
current = current.next
return False
# Example Usage
# Create a cycle manually for testing
node1 = ListNode(1)
node2 = ListNode(2)
node1.next = node2
node2.next = node1 # Creates a cycle
print(has_cycle(node1)) # Output: True
Explanation
Hashmap Use:
Stores references to nodes.
Cycle Detection:
If a node is revisited, a cycle exists.
7. LRU Cache Implementation
Problem Statement
Design and implement a data structure for Least Recently Used (LRU) cache.
Thought Process
Use a combination of a hashmap and a doubly-linked list.
The hashmap provides O(1) access to cache items.
The linked list maintains the order of usage.
Python Code
class DLinkedNode:
def __init__(self):
self.key = 0
self.value = 0
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.cache = {} # Hashmap to store key-node pairs
self.capacity = capacity
self.size = 0
# Dummy head and tail nodes
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
def _add_node(self, node):
"""Add node right after head."""
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
"""Remove an existing node from the list."""
prev_node = node.prev
next_node = node.next
prev_node.next = next_node
next_node.prev = prev_node
def _move_to_head(self, node):
"""Move certain node to the head."""
self._remove_node(node)
self._add_node(node)
def _pop_tail(self):
"""Pop the current tail."""
res = self.tail.prev
self._remove_node(res)
return res
def get(self, key):
node = self.cache.get(key, None)
if not node:
return -1
# Move accessed node to head
self._move_to_head(node)
return node.value
def put(self, key, value):
node = self.cache.get(key)
if not node:
new_node = DLinkedNode()
new_node.key = key
new_node.value = value
self.cache[key] = new_node
self._add_node(new_node)
self.size += 1
if self.size > self.capacity:
# Pop the tail
tail = self._pop_tail()
del self.cache[tail.key]
self.size -= 1
else:
# Update the value
node.value = value
self._move_to_head(node)
# Example Usage
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
print(cache.get(1)) # Returns 1
cache.put(3, 3) # Evicts key 2
print(cache.get(2)) # Returns -1 (not found)
Explanation
Hashmap Use:
Stores key-node pairs for O(1) access.
Doubly-Linked List:
Maintains the order of usage.
Recently used items are moved to the head.
8. Word Pattern Matching
Problem Statement
Given a pattern and a string s, find if s follows the same pattern.
Thought Process
Use two hashmaps to maintain bijection mapping between pattern characters and words.
Ensure that each character maps to one word and vice versa.
Python Code
def word_pattern(pattern, s):
words = s.split()
if len(pattern) != len(words):
return False
char_to_word = {}
word_to_char = {}
for c, w in zip(pattern, words):
if c in char_to_word:
if char_to_word[c] != w:
return False
else:
if w in word_to_char:
return False
char_to_word[c] = w
word_to_char[w] = c
return True
# Example Usage
pattern = "abba"
s = "dog cat cat dog"
print(word_pattern(pattern, s)) # Output: True
Explanation
Hashmaps Used:
char_to_word: pattern character to word mapping.word_to_char: word to pattern character mapping.
Validation:
If a mapping exists, it must be consistent.
9. Isomorphic Strings
Problem Statement
Determine if two strings are isomorphic.
Thought Process
Similar to word pattern matching.
Use two hashmaps to map characters from one string to the other.
Python Code
def is_isomorphic(s, t):
if len(s) != len(t):
return False
s_to_t = {}
t_to_s = {}
for c1, c2 in zip(s, t):
if c1 in s_to_t:
if s_to_t[c1] != c2:
return False
else:
if c2 in t_to_s:
return False
s_to_t[c1] = c2
t_to_s[c2] = c1
return True
# Example Usage
s = "egg"
t = "add"
print(is_isomorphic(s, t)) # Output: True
Explanation
Hashmaps Used:
s_to_t: mapping fromstot.t_to_s: mapping fromttos.
Consistency Check:
Ensure one-to-one mapping.
10. Memoization in Dynamic Programming
Problem Statement
Compute the nth Fibonacci number using memoization to optimize recursive calls.
Thought Process
Use a hashmap to cache computed Fibonacci numbers.
Avoid redundant calculations by checking the cache before computing.
Python Code
def fibonacci(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
memo[n] = n
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# Example Usage
print(fibonacci(10)) # Output: 55
Explanation
Hashmap Use:
memostores previously computed Fibonacci numbers.
Efficiency:
Reduces time complexity from exponential to linear.