Introduction
A hashmap (also called a hash table) is one of the most fundamental data structures in computer science. It allows for fast lookups, insertions, and deletions in constant time O(1)O(1)O(1), making it an essential tool in many algorithms.
In this article, we’ll explore:
- What a hashmap is and how it works
- How hashmaps achieve O(1) lookup using an array and a hash function
- Why hashmaps are so efficient
- How they’re used in algorithms
- Real-world applications
- Implementation and best practices in TypeScript
Checkout out our Essential Technical Interview Algorithm Concepts article for more essential concepts.
What Is a Hashmap?
A hashmap is a key-value data structure that allows you to store and retrieve data efficiently. Instead of searching through an entire list to find a value, a hashmap uses a hash function to determine where to store or retrieve a value in constant time O(1)O(1)O(1) (on average).
Real-World Analogy
Think of a hashmap like a dictionary:
- The word is the key
- The definition is the value
- Instead of flipping through pages one by one, you jump straight to the word using an index (this is like the hash function).
How Does a Hashmap Work?
A hashmap achieves fast lookups using two core components:
- A Hash Function: Converts a key into an array index.
- An Array: Stores the key-value pairs at the computed index.
Step-by-Step Breakdown
- A key is passed to a hash function, which converts it into a numerical index.
- The value is stored in an array at that index.
- To retrieve the value, the key is hashed again, and the result is used to look up the value in the array.
🔥 Example: Simple Hash Function
function simpleHash(key: string, size: number): number {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i); // Convert each character to a number
}
return hash % size; // Ensure the index is within the array bounds
}
If we apply this to some keys:
console.log(simpleHash("apple", 10)); // Example output: 5
console.log(simpleHash("banana", 10)); // Example output: 6
console.log(simpleHash("grape", 10)); // Example output: 1
🔹 Notice how different keys get mapped to different indices!
How This Enables O(1) Lookup
Because the hash function instantly calculates an index, we can go directly to that index in the array—just like using an array index in regular programming.
🔹 Example: Using an Array for Fast Lookups
const hashmap = new Array(10); // Create an array with 10 slots
const key1 = "apple";
const index1 = simpleHash(key1, hashmap.length);
hashmap[index1] = 5; // Store value at computed index
console.log(hashmap[index1]); // Output: 5
⏩ No need to search through an entire list—just jump straight to the correct index!
This direct access makes the average time complexity for lookups O(1) instead of O(n) in a list.
Hashmaps in Algorithms
1. Counting Frequencies (e.g., word count in a text)
function wordFrequency(text: string): Record<string, number> {
const words = text.split(" ");
const frequency: Record<string, number> = {};
for (const word of words) {
frequency[word] = (frequency[word] || 0) + 1;
}
return frequency;
}
console.log(wordFrequency("apple banana apple orange apple banana"));
// Output: { apple: 3, banana: 2, orange: 1 }
🔹 Real-World Use Case: Word count in search engines or NLP applications.
2. Finding Duplicates in an Array
function hasDuplicates(arr: number[]): boolean {
const seen = new Set<number>();
for (const num of arr) {
if (seen.has(num)) return true;
seen.add(num);
}
return false;
}
console.log(hasDuplicates([1, 2, 3, 4, 5])); // false
console.log(hasDuplicates([1, 2, 3, 4, 1])); // true
🔹 Real-World Use Case: Checking for duplicate usernames or email addresses.
3. Memoization in Dynamic Programming
Memoization stores previously computed results to avoid redundant calculations, making recursive solutions much more efficient.
function fibonacci(n: number, memo: Record<number, number> = {}): number {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
console.log(fibonacci(10)); // Output: 55
🔹 Real-World Use Case: Optimizing expensive computations like caching API responses.
Handling Hash Collisions
Since a hashmap has a limited number of storage slots, different keys may produce the same index (a collision). There are two main ways to handle this:
- Chaining: Store multiple values at the same index using an array.
- Open Addressing: Find an alternative index when a collision occurs.
Example of chaining:
class HashTable {
private table: Record<number, [string, any][]> = {};
private hash(key: string): number {
return key.length % 10; // Simple hash function
}
set(key: string, value: any) {
const index = this.hash(key);
if (!this.table[index]) this.table[index] = [];
this.table[index].push([key, value]);
}
get(key: string): any {
const index = this.hash(key);
if (!this.table[index]) return undefined;
for (const [storedKey, storedValue] of this.table[index]) {
if (storedKey === key) return storedValue;
}
return undefined;
}
}
const ht = new HashTable();
ht.set("apple", 5);
ht.set("banana", 10);
console.log(ht.get("apple")); // 5
console.log(ht.get("banana")); // 10
Best Practices
- Use Built-in Hashmaps: In TypeScript, prefer using
Mapover plain objects for better performance and features. - Choose a Good Hash Function: A poorly designed hash function can lead to frequent collisions.
- Resize Hashmaps Dynamically: If too many collisions occur, increasing the table size helps.
Conclusion
Hashmaps are a powerful and efficient data structure used in many algorithms. Their ability to store key-value pairs with fast lookups makes them ideal for problems like counting frequencies, detecting duplicates, and optimizing recursive functions with memoization.
By combining a hash function with an array, they enable O(1) lookups, making them much faster than linear search-based data structures.
Next time you need quick access to data, think hashmaps! 🚀
Checkout out our Essential Technical Interview Algorithm Concepts article for more essential concepts.