Introduction
Hash sets and hash maps are among the most frequently used data structures in real-world programming and technical interviews. A hash set stores a collection of unique elements with no associated values (like Python's set), while a hash map (or dictionary) stores key-value pairs (like Python's dict). Both leverage hashing internally to provide average O(1) membership checks, insertions, and deletions, which makes them ideal building blocks for solving a huge range of practical problems efficiently.
Cricket analogy: A hash set is like a list of players who've scored a century this season with no extra info attached, while a hash map is like a table pairing each player's name to their exact century count, both let you check or update a player's status almost instantly, unlike scanning a full scorecard archive.
How It Works
Because hash sets and hash maps offer near-instant lookups, they are commonly used to trade memory for speed: instead of repeatedly scanning a list (O(n) per check), you insert elements into a hash-based structure once and then check membership or retrieve associated data in O(1) average time. This pattern underlies solutions for deduplication, frequency counting, caching, grouping, and fast existence checks such as detecting duplicates or finding complements in array problems (e.g., the classic 'two sum' problem).
Cricket analogy: Instead of re-scanning the entire wagon-wheel chart to check if a shot type has been played before, you log each shot type into a set once and then check instantly, the same pattern used to spot if a bowler has already conceded a boundary this over, trading a bit of memory for near-instant checks.
Explanation
Common applications include: (1) Deduplication - inserting items into a set automatically removes duplicates. (2) Frequency counting - using a map from item to count to tally occurrences, useful for problems like finding the most common word or checking anagrams. (3) Caching/memoization - storing previously computed results keyed by input so expensive computations aren't repeated. (4) Fast existence checks - checking 'have I seen this before?' in O(1) instead of scanning a list, as in the two-sum problem or detecting cycles. (5) Grouping - mapping a computed key (like a sorted string) to a list of items that share that key, as in grouping anagrams. (6) Set operations - union, intersection, and difference between two hash sets are fast ways to compare collections.
Cricket analogy: (1) A set removes duplicate player names from a scorer's list automatically; (2) a map tallies how many times each bowler has been hit for six; (3) caching stores a previously computed net run rate so it isn't recalculated; (4) checking "has this batting pair partnered before" is instant like a two-sum check; (5) grouping players by team name into lists; (6) comparing two squads' player sets for union, intersection, or difference.
Example
# 1. Deduplication using a set
nums = [1, 2, 2, 3, 3, 3, 4]
unique_nums = set(nums)
print(unique_nums) # {1, 2, 3, 4}
# 2. Frequency counting using a dict
def word_frequencies(words):
freq = {}
for w in words:
freq[w] = freq.get(w, 0) + 1
return freq
print(word_frequencies(["a", "b", "a", "c", "b", "a"]))
# {'a': 3, 'b': 2, 'c': 1}
# 3. Two Sum: find indices of two numbers that add to a target, using a hash map
def two_sum(nums, target):
seen = {} # value -> index
for i, n in enumerate(nums):
complement = target - n
if complement in seen:
return [seen[complement], i]
seen[n] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]
# 4. Detecting duplicates in O(n) using a set
def has_duplicate(nums):
seen = set()
for n in nums:
if n in seen:
return True
seen.add(n)
return False
print(has_duplicate([1, 2, 3, 2])) # True
# 5. Grouping anagrams using a hash map keyed by sorted letters
def group_anagrams(words):
groups = {}
for w in words:
key = "".join(sorted(w))
groups.setdefault(key, []).append(w)
return list(groups.values())
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))Complexity
Most hash set and hash map based solutions achieve overall O(n) time complexity for problems that would otherwise take O(n^2) with nested loops or O(n log n) with sorting-based approaches, because each membership check, insertion, or lookup costs average O(1). The tradeoff is O(n) additional space to store the set or map. For example, two-sum with a hash map runs in O(n) time and O(n) space, compared to the O(n^2) time, O(1) space brute-force approach with nested loops.
Cricket analogy: Instead of comparing every pair of overs to find two that sum to a target total (O(n^2) brute force), you hash each over's score and check for its complement in O(n) total time, trading extra scoreboard memory for speed, the same tradeoff behind fast two-sum-style stat lookups.
Key Takeaways
- Hash sets store unique elements; hash maps store key-value pairs, both with average O(1) operations.
- Common uses: deduplication, frequency counting, caching/memoization, fast existence checks, and grouping.
- The 'two sum' pattern trades O(n) extra space for reducing time complexity from O(n^2) to O(n).
- Set operations (union, intersection, difference) are efficient ways to compare collections.
- Hash-based structures are a go-to tool for optimizing brute-force nested-loop solutions in interviews.
Practice what you learned
1. What is the main structural difference between a hash set and a hash map?
2. In the classic 'two sum' problem, what is the benefit of using a hash map over a brute-force nested loop?
3. Which of the following is a typical use case for a hash set?
4. How can a hash map be used to group anagrams together?
5. What is a practical benefit of using a hash map for memoization/caching?
Was this page helpful?