![Cover image for Data Structures in JavaScript [Hash Tables]](https://media2.dev.to/dynamic/image/width=1000,height=420,fit=cover,gravity=auto,format=auto/https%3A%2F%2Fdev-to-uploads.s3.amazonaws.com%2Fuploads%2Farticles%2Ff4iqdp8ln8ys2uefrll2.png)
- What is a Hash Tables?
- Why Hash Tables?
- How Hash Tables Work?
- What is a Hash Function?
- Hash Tables with Big O Notation
- Implementing Hash Tables
What is a Hash Tables?
Hash Tables, Hashes, Maps, Unordered Maps or Objects, There are many names to call This Data Structure.
In JavaScript, Objects are a type of a Hash Table
Hash Tables don't maintain order, like Arrays.
Why Hash Tables?
Imagine that we want to store the number of active Users in a particular app.
Doing this in Arrays is not the cleanest way.
So we need Hash Tables or Objects to do so
const users = {
activeUsers: 1000,
};
How Hash Tables Work?
In Hash Tables we use keys and values.
keys instead of indexes to find the data in memory.
To make this happen we need a Hash Function.
First, We pass the key to the Hash Function
Then, the Hash Function will generate a hashed output to store the data in the memory.
What is a Hash Function?
A function that coverts inputs of any length into a fixed size string using a mathematical equation.
The output of a hash function has to be unique.
And the same input should always produce the same hashed output.
And there are many types of Hash Functions such as MD2, CRC23, SHA-1, ... and more.
You can try it here
Example of a simple Hash Function
function hashFunction(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = hash + key.charCodeAt(i);
}
return hash;
}
// Giving it the string "Hello"
console.log(hashFunction("Hello")); // 500
console.log(hashFunction("Hello")); // 500
console.log(hashFunction("Hello")); // 500
// Giving it the string "hello"
console.log(hashFunction("hello")); // 532
console.log(hashFunction("hello")); // 532
console.log(hashFunction("hello")); // 532
Hash Tables with Big O Notation
- Access => O(1) || O(n).
- Insert => O(1).
- Delete => O(1).
Later in the article we will know why Accessing might be O(n).
Example
const user = {
firstName: "Youssef",
lastName: "Zidan",
};
// Access // O(1)
console.log(user.firstName); // "Youssef"
// Insert // O(1)
user.job = "Web Developer";
console.log(user.job); // "Web Developer"
// Delete O(1)
delete user.lastName;
console.log(user.lastName); // undefined
Implementing Hash Tables
In order to really understand Big O with Hash Tables, we are going to Implement one.
class HashTable {
constructor(size) {
this.data = new Array(size);
}
// hash function
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * i) % this.data.length;
}
return hash;
}
// O(1)
set(key, value) {
let address = this._hash(key);
if (!this.data[address]) {
this.data[address] = []; // O(1)
this.data[address].push([key, value]); // O(1)
} else {
this.data[address].push([key, value]); // O(1)
}
}
// O(1) || O(n)
get(key) {
let address = this._hash(key); // O(1)
let current = this.data[address]; // O(1)
if (current) {
for (let i = 0; i < current.length; i++) {
// O(n)
// O(1) if current.length === 1
// or the ele is found in the first index
if (current[i][0] === key) {
return current[i][1];
}
}
} else {
// O(1)
return undefined;
}
}
keys() {
if (!this.data.length) {
return undefined;
}
const keys = [];
for (let i = 0; i < this.data.length; i++) {
if (this.data[i]) {
if (this.data[i].length === 1) {
keys.push(this.data[i][0][0]);
}
if (this.data[i].length > 1) {
for (let j = 0; j < this.data[i].length; j++) {
keys.push(this.data[i][j][0]);
}
}
}
}
return keys;
}
}
Breaking Down
hash function
_hash(key) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * i) % this.data.length;
}
return hash;
}
Using this specific algorithm to determine that the created element will not exceed the length of the Hash Table.
set
set(key, value) {
let address = this._hash(key);
if (!this.data[address]) {
this.data[address] = []; // O(1)
this.data[address].push([key, value]); // O(1)
} else {
this.data[address].push([key, value]); // O(1)
}
}
- Getting the address using the hash function.
- If the generated address doesn't exist in
this.dataobject, Create an empty array of this address. - Push the key and the value passed inside another array to the created empty array.
- If there is no data in this particular address just push an array contains the key and value.
get
get(key) {
let address = this._hash(key); // O(1)
let current = this.data[address]; // O(1)
if (current) {
for (let i = 0; i < current.length; i++) {
// O(n) or
// O(1) if current.length === 1
// or the ele is found in the first index
if (current[i][0] === key) {
return current[i][1];
}
}
} else {
// O(1)
return undefined;
}
}
- Getting the address using the hash function.
- Getting the current value of the generated address.
- Checking if there is a value in this current position.
- Looping through the current array.
- Check for they key
current[i][0]if it's equal the passed key and return the valuecurrent[i][1]. - Return undefined if there is no current address found.
keys
keys() {
if (!this.data.length) {
return undefined;
}
const keys = [];
for (let i = 0; i < this.data.length; i++) {
if (this.data[i]) {
if (this.data[i].length === 1) {
keys.push(this.data[i][0][0]);
}
if (this.data[i].length > 1) {
for (let j = 0; j < this.data[i].length; j++) {
keys.push(this.data[i][j][0]);
}
}
}
}
return keys;
}
- Checking for the length of the Hash Table and return
undefinedif there is no data. - Creating an empty keys array.
- Checking if the current element has a value.
- Checking if the length of this array element is 1 O(1) so we will push the key which will be
this.data[i][0][0] - If the length is greater than 1 O(n), then this position has more than one array so we also loop through it and return the keys inside
this.data[i][j][0].
Example
const ht = new HashTable(10);
ht.set("a", 1);
ht.set("b", 2);
ht.set("c", 3);
ht.set("d", 4);
ht.set("e", 5);
ht.set("f", 6);
ht.set("g", 7);
ht.set("h", 8);
ht.set("i", 9);
ht.set("j", 10);
console.log(ht); /* 0: Array[10]
0: Array[2]
0: "a"
1: 1
1: Array[2]
2: Array[2]
3: Array[2]
4: Array[2]
5: Array[2]
6: Array[2]
7: Array[2]
8: Array[2]
9: Array[2]
1: undefined
2: undefined
3: undefined
4: undefined
5: undefined
6: undefined
7: undefined
8: undefined
9: undefined
*/
console.log(ht.get("g")); // 7
console.log(ht.keys()); // ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"]
Top comments (0)