What is a Hash Table?
Time to read: 6 mins
A hash table is a very popular data structure used to store data. It uses a predictable pattern of associating a key with data; this is similar to how a JavaScript Object Literal stores data using a key: value pair format.
Here are some other interesting facts about Hash Tables:
- Hash tables are known as hash maps, associative arrays, and a few other names.
- A Hash table is a type of data structure, and data structures help us optimize the process of accessing and putting data.
- Most languages support Hash Tables, and in JavaScript, Hash Tables are likely used to implement Objects.
Accessing Data From A Hash Table
In order to locate data within a collection, Hash tables associate a key with an index, which provides the location of the actual data in an array.
How does it work?
The key we use to associate with our data is passed through what is known as a hash function, which looks up the proper index for where the data is stored; once the index is discovered, we can retrieve that piece of data. This is why most developers agree that hash tables have an O(1) lookup time.
However, sometimes two or more keys can get mapped to the same index; this is called a collision. To address this, we could add a sub array to our index instead; this might increase lookup time. In many cases, a linked list is used as a strategy to help manage performance, but it doesn't descrease lookup time because we'd have to iterate over the list to find the appropriate piece of data.
In summary, the performance of a Hash Table is highly dependent upon the hash function and in some cases, its size.
Here's an example of a very simple implementation of a Hash Table:
class HashTable {
constructor(size = 10) {
this.storageLimit = size;
this.storage = new Array(size);
}
_hash(string) {
let hash = 0;
for (let i = 0; i < string.length; i++) {
hash += string.charCodeAt(i);
}
console.log(hash);
return hash % this.storageLimit;
}
print() {
let items = this.storage.flat();
let result = items.reduce((hashTable, [key, value]) => {
hashTable[key] = value
return hashTable;
}, {});
console.log(result);
return result;
}
add(key, value) {
let index = this._hash(key);
if (this.storage[index] === undefined) {
this.storage[index] = [[key, value]];
} else {
let inserted = false;
for (let i = 0; i < this.storage[index].length; i++) {
if (this.storage[index][i][0] === key) {
this.storage[index][i][1] = value;
inserted = true;
}
}
if (inserted === false) {
this.storage[index].push([key, value]);
}
}
this.print();
}
remove(key) {
let index = this._hash(key);
if (this.storage[index].length === 1 && this.storage[index][0][0]) {
this.storage.splice(index, 1);
} else {
for (let i = 0; i < this.storage[index].length; i++) {
if (this.storage[index][i][0] === key) {
this.storage[index].splice(i, 1);
}
}
}
this.print();
}
lookup(key) {
let index = this._hash(key);
if (this.storage[index] === undefined) {
return undefined;
} else {
for (let i = 0; i < this.storage[index].length; i++) {
if (this.storage[index][i][0] === key) {
return this.storage[index][i];
}
}
}
}
}
const myNewHashTable = new HashTable(); // Passing in the length is optional
As we can see, this Hash Table is implemented using a JavaScript class. One thing to keep in mind and remind ourselves is that it's improbable we'd ever need to implement something like this in an actual JavaScript program as we'd likely use a JavaScript Object Literal instead.
However, for learning purposes, we'll use this example to get a feel for how Hash Tables work.
For the remaining part of this walkthrough, we'll go through the individual methods to explain what they each do.
constructor
constructor(size = 10) {
this.storageLimit = size;
this.storage = new Array(size);
}
This method gets called automatically upon instantiation of the class (see ES6 JavaScript class syntax); in this particular case, we have the option to pass in the max length we want for our hash table. The default, in this case, is 10. We'll use that value to set our storage and storageLength fields.
_hash
_hash(string) {
let hash = 0;
for (let i = 0; i < string.length; i++) {
hash += string.charCodeAt(i);
}
console.log(hash);
return hash % this.storageLimit;
}
This simple hash function implementation creates a sum of all the character codes from each character contained within a provided key used to map to a piece of data in our hash table; the assumption here is that we're using the string datatype for our keys.
In addition, the hash result is simply a sum of each char code contained with the key string. We are also returning the result of computing the hash modulo the storageLimit, or hash % this.storageLimit; this is how we calculate the index position of the bucket we'll store our key-value pair within the Hash Table.
print
print() {
let items = this.storage.flat();
let result = items.reduce((hashTable, [key, value]) => {
hashTable[key] = value
return hashTable;
}, {});
console.log(result);
return result;
}
I had a lot of fun putting this method together; basically, this function produces a human-readable view object using a JavaScript Object Literal.
It flattens the storage array removing the empty slots, and then maps over the result adding the corresponding key: value pairs to a locally initialized JavaScript Object literal. We'll finish the task by console logging and returning the result.
add
add(key, value) {
let index = this._hash(key);
if (this.storage[index] === undefined) {
this.storage[index] = [[key, value]];
} else {
let inserted = false;
for (let i = 0; i < this.storage[index].length; i++) {
if (this.storage[index][i][0] === key) {
this.storage[index][i][1] = value;
inserted = true;
}
}
if (inserted === false) {
this.storage[index].push([key, value]);
}
}
this.print();
}
This method allows us to add a piece of data to our Hash Table.
First, we start by finding an index to put our new piece of data; we do this by generating a hash using our hash function. Then our next step is to see if anything currently exists at that location within our storage array. If it doesn't exist, we'll insert it there inside another list we'll use as a bucket in case of a collision.
However, if a bucket exists, we'll check to see if there's a matching key in that bucket by searching each item in the bucket; this will likely increase our lookup time to O(n), assuming the worst case. If we find a matching key, we'll update its value with the new value provided. However, we'll push our new key: value pair into that bucket if we don't have a matching key.
remove
remove(key) {
let index = this._hash(key);
if (this.storage[index].length === 1 && this.storage[index][0][0] === key) {
this.storage.splice(index, 1);
} else {
for (let i = 0; i < this.storage[index].length; i++) {
if (this.storage[index][i][0] === key) {
this.storage[index].splice(i, 1);
}
}
}
this.print();
}
This method allows us to delete a piece of data from our Hash Table using just the key name.
So, naturally, this method accepts the key name as an argument and uses that key to find the index position in our storage array by invoking our hash function. Once we've achieved that step, we'll first check the bucket within our storage array to see if there's only one item in that bucket. If there's only one item, we'll remove the item and the entire bucket.
However, if there are multiple items, we'll need to iterate the bucket at the current index until we find a match and remove the matched key from the bucket while leaving the others intact.
Lookup
lookup(key) {
let index = this._hash(key);
if (this.storage[index] === undefined) {
return undefined;
} else {
for (let i = 0; i < this.storage[index].length; i++) {
if (this.storage[index][i][0] === key) {
return this.storage[index][i];
}
}
}
}
This method performs a look-up of a piece of data using a key. First, we find the item's index by invoking our hash function, which will return our index.
Next, once we have our index, we'll check to see if that index exists within the Hash Table. If it doesn't exist, in other words, if it's undefined, we'll return the value of undefined.
Otherwise, we'll search the bucket located at the corresponding index and return the item whose key we've matched.
Conclusion
That concludes the walkthrough of my explanation/implementation of a Hash Table using a JavaScript Class. Keep in mind that in a real-world scenario, we'd probably use a JavaScript Object Literal (assuming we're using JavaScript).
Also, when it comes to writing a hash function, there are likely better ways to do it versus how I've done it in this example. Besides the hash function being super crucial regarding performance, there are other considerations we'd need to factor in, such as choosing the proper length for our hash table and so forth.
I hope you've enjoyed this walkthrough and have found it valuable for your understanding of them.