A.1.2: Hash Tables
Learning Objectives
Understand pros and cons of using hash tables
Understand how a hash table stores and retrieves values
Understand how to use hash tables to solve algorithm problems that require calculating frequencies of elements in a collection
Introduction
A "hash table" is a data structure that stores keyvalue pairs with constant time (O(1)
) lookup and insertion. It is also the computer science concept behind JavaScript objects. Every popular programming language has their own implementation of the hash table, such as Python Dictionaries and Java HashMaps.
We will use JS objects in a new way to solve algorithm problems. So far we have used JS objects primarily to store compound data such as playing cards, where it made sense to group card attributes such as name, rank and suit in a single data structure. We will now also use objects as frequency tallies.
Pros and cons of hash tables
Pros  Cons 



Generally the speed benefits of using a hash table outweigh the impact of additional space required, and when there is algorithmic benefit to using a hash table we should use it.
How does a hash table work?
Hash tables achieve O(1)
lookup and insertion by "hashing" keys (typically strings) into array indexes with a constanttime "hash function", such that given a key it knows exactly where to retrieve or insert the relevant data and can access that data in constant time. Hash table implementations typically maintain a larger array size than number of keyvalue pairs to minimise "collisions" (multiple keys hashing to the same index) and maintain O(1)
lookup and insertion.
Common use case: frequency tally
Example 1: Determine most popular candidate
Given 1000 votes, determine who is the winner
Example 2: Determine lowstock items
Given a number of fruits in stock, determine which fruits are lowstock and need replenishment
Exercises
After attempting each problem, find solutions in the Leaderboard tab (HackerRank, may be on left side of page) or Solution or Discuss tabs (LeetCode) on that problem's page. If you get stuck for more than 15 minutes, review and understand the solutions and move on. Come back and reattempt the problem after a few days.
PreClass
Two Strings (HackerRank)
Valid Anagram (LeetCode)
Part 1
NRepeated Element in Size 2N Array (LeetCode)
Sum of Unique Elements (LeetCode)
Unique Number of Occurrences (LeetCode)
Part 2
Ransom Note (HackerRank)
Maximum Number of Balloons (LeetCode)
Uncommon Words from Two Sentences (LeetCode)
Part 3
Find Words That Can Be Formed By Characters (LeetCode)
Intersection of Two Arrays II (LeetCode)
Find Common Characters (LeetCode)
More Comfortable
How Many Numbers are Smaller than the Current Number (LeetCode)
Hint: Sort, track num smaller numbers for each number in hash table, use hash table to generate results array
Sherlock and Anagrams (HackerRank)
Hint: Sliding window?
Longest Substring Without Repeating Characters (LeetCode)
Hint: Sliding window?
Permutation in String (LeetCode)
Hint: Fixedsize window with hash table of letter frequencies?
Last updated