Imagine you’re in a vast library with millions of books đ. How do you find the exact book you’re looking for without spending hours searching through every shelf? đ”ïžââïž The answer lies in the library’s catalog system – a powerful tool that allows you to locate any book in seconds âĄ. This is precisely the real-world analogy of a Hash Table, a fundamental data structure that enables lightning-fast data storage and retrieval đ.
Hi đ, welcome to this article on Hash Tables! In this article, we’ll be demystifying Hash Tables đ§©, exploring their inner workings and implementing them in JavaScript.
Before we move on, let’s take a look at what we’ll be covering in this article:
Table of Contents
Introduction
What is a Hash Table?
Common Terminologies Used in Hash Tables
How Hash Tables Work
Implementing a Hash Table in JavaScript
Creating the Hash Table
Adding Values to the Hash Table
Retrieving Values from the Hash Table
Removing Values from the Hash Table
Checking if a Value exists in the Hash Table
Conclusion
Introduction
The importance of Hash Tables in the world of programming cannot be overstated. They are the backbone of many real-world applications, from database indexing to caching systems, and from compilers to blockchain technology. Moreover, Hash Tables are a favorite topic in coding interviews, making them an essential skill for any aspiring software developer.
You might be wondering why we need a Hash Table in the first place. A Hash Table is a data structure designed to be fast to work with.
The reason Hash Tables are sometimes preferred instead of arrays or linked lists is because searching for, adding, and deleting data can be done really quickly, even for large amounts of data.
In a Linked List, finding a person “Esther” takes time because we would have to go from one node to the next, checking each node, until the node with “Esther” is found.
And finding “Esther” in an Array could be fast if we knew the index, but when we only know the name “Esther”, we need to compare each element (like with Linked Lists), and that takes time.
With a Hash Table however, finding “Esther” is done really fast because there is a way to go directly to where “Esther” is stored, using something called a hash function.
In this comprehensive article, we’ll demystify Hash Tables, explore their inner workings, implement them in JavaScript, and solve popular LeetCode problems. By the end of this journey, you’ll have a solid understanding of Hash Tables and be well-equipped to optimize your code and ace your next coding interview.
That being said, let’s dive into the world of Hash Tables!
What is a Hash Table?
A hash table is a data structure that allows you to store data in key-value pairs and quickly access it using a key. Think of it like a dictionary or a phone book, where you can look up information (value) by a name (key). A hash table is a data structure that stores values using keys. It uses a hash function to compute an index into an array in which an element will be stored.
Common Terminologies Used in Hash Tables
Term
Definition
Key
The identifier used to store or retrieve a value in the hash table.
Value
The actual data associated with the key.
Hash Function
A function that converts the key into a unique hash code used to store the value.
Bucket / Slot
A location in the hash table where a value is stored, indexed by the hash code.
Collision
When two different keys produce the same hash code and are assigned to the same bucket.
Chaining
A method for handling collisions by storing multiple values in a list within a bucket.
Rehashing
Resizing the hash table and recalculating hash codes to redistribute the keys.
Hash Code
The result of the hash function used as the index to store or retrieve values.
How Hash Tables Work
Implementing a Hash Table in JavaScript
Let’s roll up our sleeves and implement a simple Hash Table in JavaScript. We’ll go through this process step-by-step, explaining each part of the implementation.
When it comes to implementing a Hash Table, the first thing we need to do is to create a hash function. This hash function will take a key and return an index in the array where the value should be stored. To implement this, we’ll use a simple algorithm that involves multiplying by a prime number and taking the modulo with the array length.
A hash map uses a simple array (or a list of buckets) to store data. The data is accessed by using a key and the hash function maps that key to an index in the array.
Hash Map: We’ll represent the hash map as an array.
Hash Function: This will take a string key, convert it into a hash code (an index in the array), and return that index. The hash function needs to ensure that keys are mapped to valid indices within the array bounds.
Let’s start by creating our Hash Map class and the hash function:
Creating the Hash Table
class HashTable {
constructor(size) {
this.size = size; // size of the hash map (number of buckets)
this.buckets = new Array(size); // create an array of the given size (buckets)
}
// Hash function to generate an index based on the key
_hash(key) {
let hashValue = 0;
for (let i = 0; i < key.length; i++) {
hashValue += key.charCodeAt(i); // get the ASCII value () of each character and sum it
}
return hashValue % this.size; // ensure the index is within the bounds of the array
}
}
// Create a hash map of size 10 and test the hash function
let myHashTable = new HashTable(10);
console.log(myHashTable._hash(“Alice“)); // This will return the index for “Alice”
console.log(myHashTable._hash(“Bob“)); // This will return the index for “Bob”
Explanation:
We created a HashTable class with a size and an array of buckets (empty spots).
The hash function (_hash) takes a key, sums up the ASCII values of the characters, and modulo the result by the size of the array to ensure the result stays within the arrayâs bounds.
This function is private (indicated by _) because we don’t want it to be directly accessible outside the class.
ASCII, which stands for American Standard Code for Information Interchange, is a character encoding standard used to represent text in computers and other devices that use text. It is a 7-bit code, meaning it uses seven bits to represent a character, allowing for 128 possible characters (0-127). The ASCII table includes control characters (0-31 and 127), printable characters (32-126), and extended ASCII characters (128-255).
Now that we can generate an index from a key, the next step is to insert values into the hash table. We’ll create a function called set that:
Adding Values to the Hash Table
Now that we can generate an index from a key, the next step is to insert values into the hash map. We’ll create a function called set that:
Takes a key-value pair.
Uses the hash function to find the index (bucket) where the value should be stored.
Adds the key-value pair into that bucket.
We will use chaining (a list at each bucket) to handle potential collisions (when two keys map to the same bucket).
set(key, value) {
const index = this._hash(key); // Get the index for the key
// Initialize the bucket if it’s empty
if (!this.buckets[index]) {
this.buckets[index] = []; // Use an array to handle multiple values (chaining)
}
// Add the key-value pair to the bucket
this.buckets[index].push([key, value]);
console.log(`Set ${key}: ${value} at index ${index}`);
}
// Example of adding values
myHashMap.set(“Alice“, “555-1234“);
myHashMap.set(“Bob“, “555-5678“);
myHashTable.set(“Charlie“, “555-9999“);
Explanation:
The set method uses the hash function to find the correct index.
If the bucket at that index is empty, it initializes an empty list.
The key-value pair is then pushed into that bucket.
This implementation handles collisions by chainingâstoring multiple key-value pairs in a list if two keys map to the same bucket.
Retrieving Values from the Hash Table
Once we’ve inserted values, the next logical step is to retrieve values. We’ll create a function get that:
Takes a key.
Uses the hash function to find the index (bucket) where the value should be stored.
Searches the bucket for the key and returns the value if found.
get(key) {
const index = this._hash(key); // Get the index for the key
// Check if the bucket at that index exists
if (!this.buckets[index]) {
return null; // If the bucket is empty, return null (key not found)
}
// Search through the bucket for the key
for (let i = 0; i < this.buckets[index].length; i++) {
const pair = this.buckets[index][i];
if (pair[0] === key) {
return pair[1]; // Return the value if the key is found
}
}
return null; // Return null if the key is not found in the bucket
}
// Example of retrieving values
console.log(myHashMap.get(“Alice“)); // Should print “555-1234”
console.log(myHashMap.get(“Bob“)); // Should print “555-5678”
console.log(myHashMap.get(“Charlie“)); // Should print “555-9999”
console.log(myHashMap.get(“Dave“)); // Should print null (not found)
Explanation:
The get function finds the index for the key using the hash function.
If the bucket at that index is empty, it returns null because the key doesn’t exist.
If there are multiple entries in that bucket (due to collisions), the function searches through the list to find the correct key and returns its value.
Removing Values from the Hash Table
To complete the basic operations of a hash table, we’ll add a method to remove a key-value pair. This function will:
Take a key.
Use the hash function to find the bucket.
Remove the key-value pair if found.
// Remove values from the hash map
remove(key) {
const index = this._hash(key); // Get the index for the key
// Check if the bucket exists
if (!this.buckets[index]) {
return null; // If the bucket is empty, return null (key not found)
}
// Search through the bucket for the key
for (let i = 0; i < this.buckets[index].length; i++) {
const pair = this.buckets[index][i];
if (pair[0] === key) {
this.buckets[index].splice(i, 1); // Remove the key-value pair from the bucket
return pair[1]; // Return the removed value
}
}
return null; // Return null if the key is not found in the bucket
}
// Example of removing values
console.log(myHashMap.remove(“Alice“)); // Should print “555-1234”
console.log(myHashMap.get(“Alice“)); // Should now print null (not found)
Explanation:
The remove function searches for the key in the appropriate bucket and removes the key-value pair if found.
After removal, it returns the value that was removed.
If the key doesn’t exist, it returns null.
Checking if a Value exists in the Hash Table
The contains function will:
Loop through all the buckets in the hash map.
Check each key-value pair in the bucket.
Return true if the value is found, and false if it’s not.
contains(value) {
// Loop through all the buckets
for (let i = 0; i < this.size; i++) {
const bucket = this.buckets[i];
// If the bucket exists, search through its key-value pairs
if (bucket) {
for (let j = 0; j < bucket.length; j++) {
const pair = bucket[j];
if (pair[1] === value) { // Check if the value matches
return true; // Return true if the value is found
}
}
}
}
return false; // Return false if the value is not found in any bucket
}
// Example of checking for values
console.log(myHashMap.contains(“555-1234“)); // Should return false (because Alice was removed)
console.log(myHashMap.contains(“555-5678“)); // Should return true (Bob’s number)
console.log(myHashMap.contains(“555-9999“)); // Should return true (Charlie’s number)
console.log(myHashMap.contains(“555-8888“)); // Should return false (not found)
Explanation:
The contains function loops through each bucket in the hash map.
If the bucket exists (i.e., it contains some key-value pairs), it checks whether any value in that bucket matches the value we are looking for.
If it finds a match, it returns true; otherwise, after searching all buckets, it returns false.
Conclusion
Hash Tables are a powerful and versatile data structure that offer efficient data storage and retrieval. Through this guide, we’ve explored their inner workings, implemented them in JavaScript, and solved several LeetCode problems that leverage their strengths.
In our next article, we’ll be solving some LeetCode problems that use Hash Tables. Until then, happy coding!
Stay Updated and Connected
To ensure you don’t miss any part of this series and to connect with me for more in-depth discussions on Software Development (Web, Server, Mobile or Scraping / Automation), data structures and algorithms, and other exciting tech topics, follow me on:
Stay tuned and happy coding đšâđ»đ
