A Hash table is a data structure with a highly efficient lookup, which store key values pairs. Each key is generated by a hash function based on the value being stored. Also, the hash table has to handle collisions that happens when the same key is generated for different values.
1 [1] 2 [2] = ["A"] // value A store in the key 2 3 [3] 4 [4] = ["B"]
Whenever we need to retrieve a value we use its key, so this operation will be done in a constant time, considering that a good hash function is being used and the values are uniformly distributed across the hash table, which means fewer collisions. Inserting a value into a hash table, is pretty straightforward, just generate the key, and use it to find the right position in the hash table.
A basic hash function
A hash function should be easy to compute because it will be used whenever is necessary to insert or search a value, also this function has to provide uniform distribution across the hash table in order to avoid clustering which would affect the hash table performance.
For this example, our hash table will store strings, so the hash function will sum the ASCII values of each character, then it will divide that sum by the size of the hash table and get the reminder using the modulo operator (%), the result will be the key.
1// hash function
2hash(value: string): number {
3 const sum = value
4 .split("")
5 .reduce((acc: number, char: string) => acc + char.charCodeAt(0), 0);
6
7 // force sum into the hash table size
8 return sum % this.size;
9}
How to handle collisions
Collisions happen when the same key is generated for different values, a common strategy to handle collisions is Separate chaining:, instead of storing the value directly in the hash table, we store it in a Linked List, and the generated key points to that Linked list. If there were too many collisions, searching a value would take a linear time complexity O(n) instead of O(1), this time can be reduced to O(log n) using another data structure like a Binary Search Tree.
1[1] 2[2] = ["A"] -> 3[3] 4[4] = ["B"] -> ["C"] -> ["D"] -> // collisions happened, so these 3 values are in the same linked list
Implementation
Here is an implementation of a Hash Table in TypeScript
1class HashTable {
2 private size: number;
3 private data: LinkedList<string>[] = [];
4
5 constructor(size: number) {
6 this.size = size;
7 }
8
9 hash(value: string): number {
10 const sum = value
11 .split("")
12 .reduce((acc: number, char: string) => acc + char.charCodeAt(0), 0);
13
14 // force sum into the hash table size
15 return sum % this.size;
16 }
17
18 insert(value: string): void {
19 const index = this.hash(value);
20
21 if (!this.data[index]) {
22 this.data[index] = new LinkedList<string>(
23 (a: string, b: string) => a === b
24 );
25 }
26
27 this.data[index].append(value);
28 }
29
30 search(value: string): string | null {
31 const index = this.hash(value);
32
33 if (this.data[index]) {
34 return this.data[index].search(value)!.data;
35 }
36
37 return null;
38 }
39}
40
41const hashTable = new HashTable(10);
42
43hashTable.insert("aabb");
44hashTable.insert("bbcc");
45hashTable.insert("abcd");
46
47console.log(hashTable.search("abcd"));
