Photo belongs to Ján Jakub Naništa in Unsplash
Last week, we began exploring Hash Tables, a crucial data structure for software engineers. Today we’ll continue our review by adding usability features to our custom Hash Table class.
Join me as we dive deeper into the magic of hash tables in this second installment.
Starting from where we left
Let’s make a quick recap of what we covered in our previous session: We began by constructing a custom hash table class that utilizes two generic types - one specifically for the key and another designated for the value. Subsequently, we established a table object designed to function as a container for our various buckets. Following this, we carefully defined a hash function implementing the well-known DJB2 algorithm to efficiently process our keys. This foundation provides us with the essential infrastructure to insert new buckets into our table structure and assign them a properly hashed key, ensuring optimal performance and data organization. These fundamental components form the backbone of our hash table implementation, allowing us to build more sophisticated features on top of this solid base. This leaves our class in the following state:
export class HashTable<K, V> {
private table: Array<Array<[K, V]>>;
constructor(private size: number) {
this.table = new Array(size).fill(null).map(() => []);
}
private hash(key: K): number {
let hash = 5381;
const strKey = String(key);
for (let i = 0; i < strKey.length; i++) {
const char = strKey.charCodeAt(i);
hash = (hash * 33) + char;
}
return Math.abs(hash) % this.size;
}
}
Adding New Data
Let’s define our set function which will insert or update a new key-value pair in our table. It will receive two generic parameters: one of type K for the key and another of type V for the value. Since it won't return anything, the return type is void.
set(key: K, value: V): void {}
First, in the function body, we need to get the index by hashing the key. Once we have the index, we'll retrieve the corresponding bucket from our table. If no bucket exists at that index, our table initialization will have already created an empty array there.
const index = this.hash(key);
const bucket = this.table[index];
Inside the bucket, we need to find the key. Remember the apartments analogy from the previous post? We have the building and the floor, now we need to locate the specific apartment number.
const existing = bucket.find(([k]) => k === key);
If the apartment already has an occupant (data), we need to update it; if not, we will assign the value.
if (existing) {
existing[1] = value;
} else {
bucket.push([key, value])
}
Retrieving Data by Key
Next, let’s create our get method. This method accepts a key parameter of type K and returns a value of type V, giving us the following method signature:
get(key: K): V | undefined {}
Notice the return type declaration includes both V and undefined. This is because the requested key might not exist in our hash table.
Similar to our set method, we first need to find the index and the bucket for the given key. Then we check if the key exists in that bucket. This two-step process is crucial, we first locate the index using our hash function, then search for the specific key within that bucket.
Using our apartment analogy: we first identify the building, then the floor, and finally check if the specific apartment exists on that floor.
const index = this.hash(key);
const bucket = this.table[index];
const entry = bucket.find(([k]) => k === key);
Finally, if the key exists in the bucket, we return the associated value; otherwise, we return undefined. We can achieve this using a ternary operator.
return entry ? entry[1] : undefined;
Checking for Key Existence in Our Hash Table
Now let’s implement our has method, which checks whether a key exists in our hash table. This method operates similarly to the get method, but with one key difference. Let me walk you through it.
Here’s the method signature:
has(key: K): boolean {}
Similar to the get method, this will accept a key parameter of type K, but will return a boolean value that indicates whether the key exists in our hash table. Let's follow the same approach as our previous methods by first obtaining the index and the bucket for the key.
const index = this.hash(key);
const bucket = this.table[index];
Here’s where things get interesting. After obtaining the bucket, we need to check if any entry in it contains our key. This is a perfect use case for the JavaScript some method, which tests whether at least one element in an array passes a given condition.
return bucket.some(([k]) => k === key);
Eliminating Data by Key from our Hash Table
Finally, let’s implement our remove method. This method takes a key parameter of type K and returns a boolean indicating whether the key was successfully removed from the table.
remove(key: K): boolean {}
Next, as you would expect, we’ll retrieve the index and the bucket using the same logic as our previous methods. Once we have the bucket, we need to find the position of the entry with our key so we can remove it from the array. To accomplish this, we'll use the findIndex method to locate the entry and the splice method to remove it.
After finding the index for the key in the bucket (continuing our apartments analogy), we need to check if the entry exists. The findIndex method returns -1 if no match is found or the actual index position if the entry exists.
Let’s add a condition to check before removing the key.
if (entryIndex !== -1)
If it’s not equal to -1, it means the key was found, so we can splice our array and return true because our value was successfully removed from the table; otherwise, we simply return false.
if (entryIndex !== -1) {
bucket.splice(entryIndex, 1);
return true;
}
return false;
Optimizing Our Implementation: A DRY Approach
At this point, you might notice we’re repeating ourselves in each method, and a pragmatic programmer never repeats themselves. Let's create a private getBucket method to eliminate this redundancy, since retrieving the bucket is the first step in every operation we perform.
private getBucket(key: K): Array<[K, V]> {
const index = this.hash(key);
return this.table[index];
}
This is a private method because it’s only for internal use within our class. It receives the key as a parameter and returns the corresponding bucket from our table.
And there you have it — a complete implementation of a simple Hash Table in TypeScript.
Complete Hash Table Implementation with TypeScript
export class HashTable<K, V> {
private table: Array<Array<[K, V]>>;
constructor(private size: number) {
this.table = new Array(size).fill(null).map(() => []);
}
private hash(key: K): number {
let hash = 5381;
const strKey = String(key);
for (let i = 0; i < strKey.length; i++) {
const char = strKey.charCodeAt(i);
hash = (hash * 33) + char;
}
return Math.abs(hash) % this.size;
}
private getBucket(key: K): Array<[K, V]> {
const index = this.hash(key);
return this.table[index];
}
set(key: K, value: V): void {
const bucket = this.getBucket(key);
const existing = bucket.find(([k]) => k === key);
if (existing) {
existing[1] = value;
} else {
bucket.push([key, value])
}
}
get(key: K): V | undefined {
const bucket = this.getBucket(key);
const entry = bucket.find(([k]) => k === key);
return entry ? entry[1] : undefined;
}
has(key: K): boolean {
const bucket = this.getBucket(key);
return bucket.some(([k]) => k === key);
}
remove(key: K): boolean {
const bucket = this.getBucket(key);
const entryIndex = bucket.findIndex(([k]) => k === key);
if (entryIndex !== -1) {
bucket.splice(entryIndex, 1);
return true;
}
return false;
}
}
Final Thoughts
As you can see, Data Structures and Algorithms aren't rocket science once you grasp the core concepts. Creating your own implementations helps you understand why and how they work in practical applications.
Keep practicing — the only way to master something is through consistent practice and patience. As usual, you can review this and other Data Structures in my Github repository: https://github.com/RubenOAlvarado/data-structures.
See you next week!
