HashMaps Unlocked 🔓: A Beginner's Adventure Through Key-Value Land!
Part 6 of data structures series.
Welcome, brave adventurer! Today, we embark on a quest into the mystical realm of computer science, where we meet a quirky and powerful creature: the HashMap.
Along the way, we’ll unlock treasures like coding your own HashMap, discovering its magical strengths (and weaknesses), and finishing with a fun interactive quiz. Get your armor (code editor) ready!
Chapter 1: What on Earth is a HashMap? 🤔
Imagine you have a giant magical filing cabinet 🗄️ where each drawer holds information. Instead of shuffling through every drawer to find the one you need (like a noob would), you have a magical spell (a hash function) that zips you straight to the right drawer.
In simple terms:
A HashMap is a collection of key-value pairs, where each key points to a value. The magic (hash function) maps the keys to indices (drawers) in a way that we can find the value associated with a key really fast—like really fast.
🛠 Example in Real Life
Key: Your name
Value: Your phone number
HashMap: A phone book 📒
With a HashMap, when someone says your name, the hash function looks up your number almost instantly! ~O(1)
Chapter2: HashMap Lingo 🧙♂️
HashMaps come with a set of key terms that describe how they work and their operations. Here's a breakdown of the lingo you should know when dealing with HashMaps:
Key 🔑
The identifier used to access a value in a HashMap. Each key is unique within the HashMap.Example: In
{"name": "Frodo"},"name"is the key.
Value 💰
The data or object that is associated with a key. A HashMap stores these values and retrieves them using the corresponding key.Example: In
{"name": "Frodo"},"Frodo"is the value.
Put (or sometimes Set) 📝
The operation that adds or updates a key-value pair in the HashMap. If the key already exists, it updates the value.Example:
map.put("name", "Frodo")adds or updates the entry for the key"name".
Get (or sometimes Retrieve) 🧐
The operation that fetches the value associated with a key. If the key doesn’t exist, it usually returnsnullorundefined.Example:
map.get("name")would return"Frodo"if the key exists.
Remove (or sometimes Delete) 🗑️
The operation that deletes a key-value pair from the HashMap.Example:
map.remove("name")removes the key"name"and its associated value from the HashMap.
ContainsKey 🔍
A method that checks if a specific key exists in the HashMap. If it does, it returnstrue; otherwise,false.Example:
map.containsKey("age")checks if the key"age"is in the HashMap.
Hash Function 🧙♂️
The magical algorithm that takes a key and computes an index (or hash code) for the HashMap. This index tells the HashMap where to store or find the value. The quality of this function affects the performance of the HashMap.Example: A string like
"name"might be hashed to the index5.
Bucket 🗃️
HashMaps are often implemented as an array of buckets. Each bucket stores key-value pairs that hash to the same index. If two keys produce the same hash (a collision), they are placed in the same bucket. Buckets handle collisions through techniques like linked lists or trees.Example: A bucket at index
5might contain both{"name": "Frodo"}and{"title": "Hobbit"}if both hashed to the same index.
Collision 💥
When two keys are hashed to the same index, this is called a collision. A good hash function minimizes collisions, but they still happen sometimes. Different methods (like chaining or open addressing) are used to resolve them.Example: Both
"name"and"title"end up in bucket5.
PS: There are more terms beyond the 9 mentioned here, but to keep this article beginner-friendly, we'll stop here for now. Maybe I’ll dive deeper into them in a future article. 🤷♂️
Chapter 3: Let’s Build a HashMap from Scratch! 🛠️
JavaScript gives us the magical {} object, which already acts a lot like a HashMap! But where's the fun in using built-in tools? Let’s create our very own HashMap structure!
🧙♂️ Magic Code Time:
class HashMap {
constructor() {
this.map = {}; // Using a JS object for storage
}
// Hash function to generate a unique key (index) from a given key
_hash(key) {
let hash = 0;
const stringKey = String(key); // Ensure key is treated as a string
for (let i = 0; i < stringKey.length; i++) {
// Generate a simple hash, modded by a prime number
hash = (hash + stringKey.charCodeAt(i) * i) % 101;
}
return hash;
}
// The put method stores a key-value pair
put(key, value) {
const hashedKey = this._hash(key); // Generate the "bucket" index
if (!this.map[hashedKey]) {
this.map[hashedKey] = []; // Initialize a list to handle collisions
}
// Check if key already exists in the bucket and update it if necessary
for (let i = 0; i < this.map[hashedKey].length; i++) {
if (this.map[hashedKey][i][0] === key) {
this.map[hashedKey][i][1] = value; // Update value if key exists
return;
}
}
// If key is not found, add the new key-value pair
this.map[hashedKey].push([key, value]);
}
// The get method retrieves a value by key
get(key) {
const hashedKey = this._hash(key); // Generate the bucket index
const bucket = this.map[hashedKey];
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
return bucket[i][1]; // Return value if key matches
}
}
}
return null; // Return null if key not found
}
// The remove method deletes a key-value pair
remove(key) {
const hashedKey = this._hash(key); // Generate the bucket index
const bucket = this.map[hashedKey];
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
bucket.splice(i, 1); // Remove key-value pair if found
return;
}
}
}
}
// Check if a key exists
containsKey(key) {
const hashedKey = this._hash(key); // Generate the bucket index
const bucket = this.map[hashedKey];
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
if (bucket[i][0] === key) {
return true; // Return true if key exists
}
}
}
return false; // Return false if key is not found
}
// Get all keys in the HashMap
keys() {
const keysArray = [];
for (let hashedKey in this.map) {
if (this.map.hasOwnProperty(hashedKey)) {
for (let i = 0; i < this.map[hashedKey].length; i++) {
// Collect all original keys
keysArray.push(this.map[hashedKey][i][0]);
}
}
}
return keysArray;
}
}
// Let's test our custom HashMap!
const myHashMap = new HashMap();
myHashMap.put('name', 'Gandalf');
myHashMap.put('age', 2019);
console.log(myHashMap.get('name')); // Gandalf
console.log(myHashMap.containsKey('age')); // true
myHashMap.remove('age');
console.log(myHashMap.get('age')); // null
console.log(myHashMap.keys()); // ['name']In this code, we’ve built our own simplified HashMap using JavaScript's {} object as the underlying storage. We added methods for hashing, putting, getting, and removing key-value pairs. 🧑💻
Chapter 4: When to Call Upon the HashMap? 🤓
Need for Speed: When you need to retrieve values lightning-fast using keys.
Phonebooks: Perfect for situations where each item (value) needs a unique label (key), like storing user info by their username.
Avoiding Duplication: It ensures that keys are unique, so no two keys can be the same.
Chapter 5: The Magical Pros and Cons ✨
Pros (The Strengths):
Fast Retrieval (O(1)): HashMaps give us constant time access to values when you know the key. That's wizard-level speed, folks!
Flexible Keys: You can use strings, numbers, and even more complex types as keys (depending on the language, though JS uses strings internally).
No Duplicates: HashMaps don’t allow duplicate keys. If you try, it’ll just replace the old value with the new one.
Cons (The Weaknesses):
Collisions (Two Keys, One Drawer): Sometimes, two keys get hashed into the same index. This is called a collision and can slow things down.
Memory Hungry: HashMaps use extra space to maintain their structure, which may not be ideal when memory is tight.
Unordered: It doesn't maintain the order of insertion. If you need things in order, consider using something else.
Chapter 6: Under the Hood - Time & Space Complexity 🕰️
Time Complexity:
Best Case (O(1)): With no collisions, finding or inserting a key-value pair takes constant time.
Worst Case (O(n)): In the case of many collisions (if all keys hash to the same index), finding or inserting can degrade to linear time—this is rare though, thanks to good hash functions.
Space Complexity:
O(n): HashMaps require space proportional to the number of key-value pairs.
Chapter 7: Fun HashMap Quiz! 🎮
Are you ready to test your knowledge, adventurer? Let’s play a quick quiz!
1. Which method retrieves a value in a HashMap?
A)
fetch(key)B)
grab(key)C)
get(key)D)
call(key)
2. What’s a “collision” in a HashMap?
A) When two values are the same.
B) When two keys get hashed to the same index.
C) When the keys are deleted.
D) When a key magically vanishes.
3. What’s the time complexity of retrieving an element in the best case?
A) O(n)
B) O(1)
C) O(log n)
D) O(n^2)
4. True or False: A HashMap guarantees the order of elements.
A) True
B) False
5. What does the put method do in our custom HashMap?
A) Removes a key-value pair.
B) Adds or updates a key-value pair.
C) Sorts the keys alphabetically.
D) Returns all keys in the HashMap.
👇Watch out Solutions here ! 👇
The Wise Wizard's Solutions 🧙♂️
Q1: C)
get(key)Q2: B) A collision occurs when two keys get hashed to the same index.
Q3: B) O(1) is the ideal time complexity for retrieving a value.
Q4: B) False! HashMaps are unordered.
Q5: B) The
putmethod adds or updates a key-value pair.
Last Chapter: The Journey’s End 😭
Congratulations, adventurer! You’ve successfully navigated the wilds of HashMaps. 🏆 You now know how they work, when to use them, and even how to build one from scratch. As you venture further into the coding lands, may your keys always be unique, your hash functions strong, and your collisions rare!
See you on the next quest! 🧙♂️
In upcoming articles, we’ll uncover more data structures (next is the Tree Data structure), so buckle up and stay tuned—this adventure’s just getting started! 🎢🎉
🔔 Don't forget to subscribe to my blog and YouTube channel to stay updated with all the latest content!