Hash Tables
Description:
A data structure that stores unique keys to values, for example <number,string>. Each of this key value pairs are known as an Entry. The main concept of the Hash Table is that takes the keys of the Entry and using a Hashing function computes an Integer that it's used with the Table Capacity (length of the table) to calculate the index of it.
For example, let's say that we have this entries:
0
1
2
3
4
5
{ key: "apple", value: 4}
{ key: "banana", value: 2}
{ key: "grape", value: 3}
{ key: "watermelon", value: 1}
{ key: "orange", value: 5}The hash function is going to use each key, and generate a integer value out of each one of them. This could be calculated by multiple ways but, what is important here is that after that number is calculated it should be less than the capacity of the table, so it can be use as an index of it.
The way to do this is grabbing that number and mod it with the capacity of the table. For example: if we put the "apple" key in the hash function and we get the integer: 29656 and, the capacity of the table is 10, the way to calculate the index would be: 29656 % 10 = 6. This is the index of that key in our table.
Pros & Cons:
Using this data structure has some benefits, such as:
Get values: because all values are indexed by the hash finding elements it's really fast, specially if the capacity is big enough to prevent collisions. On the worst case scenario is O(capacity) but the best case scenario is O(1). This also could be improved using LinkedList for handling the collisions, that would make the time to be O(amount collision for that hash) which, depending on the capacitiy of the hash table, shoul be smaller.
It also has some cons, for example:
Collisions: the main con about hash tables are collisions. This is when two different keys have the same hash value, which means the same index. There are multiple ways to solve this problem, for example probing (the one implemented) or linked lists.
Chained Collision Handling: in one of the pros we mention that the time could be improved to O(amount collision for that hash) while using it. The con about this is that the logic could be a little bit more complex and the memory would increase to store the linked chain.
1. Hash Implementation:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
table: Array<Entry<K,V> | undefined>;
capacity: number;
constructor(capacity: number = 10) {
this.capacity = capacity;
this.table = new Array(capacity);
}
// This method is going to calculate the integer value that is going to be used as a index.
private hash(key: K): number {
// Transform the key into a string.
const keyString = String(key);
let hash = 0;
// Add up all the ascii codes of the chars of the string.
for(let i=0; i < keyString.length; i++) {
hash += keyString.charCodeAt(i);
}
// Get the index that we are going to use for this key.
// We use mod, to get the rest which will determine the inex.
hash = hash % this.capacity;
return hash;
};
2. Setting key values:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Set the key value pair into the table.
set(key: K, value: V) {
// Get the index on the table based on the hash function of the key.
const index = this.hash(key);
// Check for collisions.
if(this.table[index]) {
// Move through the table to find a empty spot.
for( let i = 0; i < this.capacity; i++) {
// We are going to iterate from the next position and go around the table
const nextIndex = (index+i) % this.capacity;
const entry = this.table[nextIndex];
// If we find an empty space, we store it.
if(!entry)
{
this.table[nextIndex] = { key, value };
return;
}
}
// The table is full
throw new Error("HashTable is full");
} else {
this.table[index] = { key, value };
}
}
3. Getting values:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
get(key: K): V | undefined {
// Get the index on the table based on the hash function of the key.
const index = this.hash(key);
// Check if the key is the same. It could be different if the table already had a entry there.
if(this.table[index]?.key === key)
return this.table[index].value;
// The key is different, it could be somewhere else on the table.
for(let i=0; i < this.capacity; i++) {
const nextIndex = (i+index) % this.capacity;
const entry = this.table[nextIndex];
// If the key is there, we return the value.
if(entry?.key === key)
return entry.value
}
// The key is not in the table.
return undefined;
}
4. Deleting:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
delete(key: K) {
// Get the index on the table based on the hash function of the key.
const index = this.hash(key);
// Check if the key is the same. It could be different if the table already had a entry there.
if(this.table[index]?.key === key)
this.table[index] = undefined;
else {
// The key is different, it could be somewhere else on the table.
for(let i=0; i < this.capacity; i++) {
const nextIndex = (i+index) % this.capacity;
const entry = this.table[nextIndex];
// If the key is there, we return the value.
if(entry?.key === key)
this.table[nextIndex] = undefined;
}
// The key is not in the table.
throw new Error("Key not present in the table");
}
}
5. All keys and all values:
Keys and Values:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
keys(): K[] {
let array = [];
for(let i=0; i < this.capacity; i++) {
const entry = this.table[i];
if(entry)
array.push(entry.key);
}
return array;
}
values(): V[] {
let array = [];
for(let i=0; i < this.capacity; i++) {
const entry = this.table[i];
if(entry)
array.push(entry.value);
}
return array;
}
Testing it
So, we are going to test in console to see if it is working. We are going to run the following:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const hashTable = new HashTable<string, number>(10);
console.log('** Add elements to the hash table.');
hashTable.set("apple", 4);
hashTable.set("banana", 2);
hashTable.set("grape", 3);
hashTable.set("watermelon", 1); // index of 6
hashTable.set("orange", 5); // index of 6 - so collision with watermelon
console.log('** Get values for apple.');
console.log('value: ', hashTable.get("apple"));
console.log('** Get values for banana.');
console.log('value: ', hashTable.get("banana"));
console.log('** Get all keys.');
console.log(hashTable.keys());
console.log('** Get all values.');
console.log(hashTable.values());
console.log('** Delete apple.');
hashTable.delete("apple");
console.log('** Try to get values for apple (previusly deleted).');
console.log('value: ', hashTable.get("apple"));
console.log('** Get all keys.');
console.log(hashTable.keys());
Console Output Example
You should see something like the following in the console:
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
** Add elements to the hash table.
** Get values for apple.
value: 4
** Get values for banana.
value: 2
** Get all keys.
(5) ['apple', 'watermelon', 'grape', 'orange', 'banana']
** Get all values.
(5) [4, 1, 3, 5, 2]
** Delete apple.
hashtable.ts:89 DELETING KEY --> apple
hashtable.ts:92 index for that key --> 0
hashtable.ts:93 element at that index: {key: 'apple', value: 4}
** Try to get values for apple (previusly deleted).
value: undefined
** Get all keys.
(4) ['watermelon', 'grape', 'orange', 'banana']
Final file
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
export type Entry<K,V> = {
key: K,
value: V,
}
export class HashTable<K,V> {
table: Array<Entry<K,V> | undefined>;
capacity: number;
constructor(capacity: number = 10) {
this.capacity = capacity;
this.table = new Array(capacity);
}
// This method is going to calculate the integer value that is going to be used as a index.
private hash(key: K): number {
// Transform the key into a string.
const keyString = String(key);
let hash = 0;
// Add up all the ascii codes of the chars of the string.
for(let i=0; i < keyString.length; i++) {
hash += keyString.charCodeAt(i);
}
// Get the index that we are going to use for this key.
// We use mod, to get the rest which will determine the inex.
hash = hash % this.capacity;
return hash;
};
// Set the key value pair into the table.
set(key: K, value: V) {
// Get the index on the table based on the hash function of the key.
const index = this.hash(key);
// Check for collisions.
if(this.table[index]) {
// Move through the table to find a empty spot.
for( let i = 0; i < this.capacity; i++) {
// We are going to iterate from the next position and go around the table
const nextIndex = (index+i) % this.capacity;
const entry = this.table[nextIndex];
// If we find an empty space, we store it.
if(!entry)
{
this.table[nextIndex] = { key, value };
return;
}
}
// The table is full
throw new Error("HashTable is full");
} else {
this.table[index] = { key, value };
}
}
get(key: K): V | undefined {
// Get the index on the table based on the hash function of the key.
const index = this.hash(key);
// Check if the key is the same. It could be different if the table already had a entry there.
if(this.table[index]?.key === key)
return this.table[index].value;
// The key is different, it could be somewhere else on the table.
for(let i=0; i < this.capacity; i++) {
const nextIndex = (i+index) % this.capacity;
const entry = this.table[nextIndex];
// If the key is there, we return the value.
if(entry?.key === key)
return entry.value
}
// The key is not in the table.
return undefined;
}
delete(key: K) {
// Get the index on the table based on the hash function of the key.
const index = this.hash(key);
// Check if the key is the same. It could be different if the table already had a entry there.
if(this.table[index]?.key === key)
this.table[index] = undefined;
else {
// The key is different, it could be somewhere else on the table.
for(let i=0; i < this.capacity; i++) {
const nextIndex = (i+index) % this.capacity;
const entry = this.table[nextIndex];
// If the key is there, we return the value.
if(entry?.key === key)
this.table[nextIndex] = undefined;
}
// The key is not in the table.
throw new Error("Key not present in the table");
}
}
keys(): K[] {
let array = [];
for(let i=0; i < this.capacity; i++) {
const entry = this.table[i];
if(entry)
array.push(entry.key);
}
return array;
}
values(): V[] {
let array = [];
for(let i=0; i < this.capacity; i++) {
const entry = this.table[i];
if(entry)
array.push(entry.value);
}
return array;
}
};