[WIP] Hash Table

 🚧 WORK IN PROGRESS
Description
A hash table is a data structure that stores data in the form of key-value pairs. This means that inside a hash table each key is mapped to a value. For example, names of your friends can be used as unique identifiers (keys) of their numbers (values) inside a phone book (hash table).
1
phoneBook.set('John Doe', '111-222-333');
2
​
3
phoneBook.set('Alberto Anderson', '111-333-444');
Copied!
// image
A hash table is an array of slots/buckets. “A hash table stores its data using a computed index, the result of which is always an integer. The computation of this index is called a hash function and it uses the value you want to store to derive the key”
Base Operations
Operation
Description
set(key, value)
add an element to a hash table based on key and value.
get(key)
get a value by its key.
delete(key)
delete value by its key.
When to use
Hash tables are one of the most common data structures just because they are fast. However, everything depends on the hashing algorithm, it can make a hash table slow. 
And because you are in an interview 🙂
Time Complexity
Operation
Average Complexity
Worst Complexity
Insertion
O(1)
O(n)
Deletion
O(1)
O(n)
Search
O(1)
O(n)
Code
1
import { LinkedList } from '../LinkedList/LinkedList';
2
​
3
export class HashTable<T> {
4
  // Allowed buckets number. The bigger the bucket number the fewer collisions we will get.
5
  private static readonly defaultBucketsNumber = 30;
6
  // hash table that will store buckets with linked list.
7
  private readonly buckets: LinkedList<{ key: string; value: T }>[];
8
​
9
  constructor(bucketsNumber = HashTable.defaultBucketsNumber) {
10
    // Create hash table of certain size and fill each bucket with empty linked list.
11
    this.buckets = Array(bucketsNumber)
12
      .fill(null)
13
      .map(() => new LinkedList());
14
  }
15
​
16
  /** Add or Update the value by its key */
17
  public set(key: string, value: T) {
18
    const bucketLinkedList = this.getBucketLinkedList(key);
19
    const node = bucketLinkedList.find((item) => Object.is(item.key, key));
20
​
21
    if (!node) {
22
      bucketLinkedList.append({ key, value }); // Add new node
23
    } else {
24
      node.value.value = value; // Update value of already existing node
25
    }
26
  }
27
​
28
  /** Get the value by its key */
29
  public get(key: string): T | null {
30
    const bucketLinkedList = this.getBucketLinkedList(key);
31
    const node = bucketLinkedList.find((item) => Object.is(item.key, key));
32
​
33
    return node?.value.value || null;
34
  }
35
​
36
  /** Delete the value by its key */
37
  public delete(key: string): T | null {
38
    const bucketLinkedList = this.getBucketLinkedList(key);
39
    const node = bucketLinkedList.find((item) => Object.is(item.key, key));
40
    const deletedNode = bucketLinkedList.delete(node?.value);
41
​
42
    return deletedNode?.value.value || null;
43
  }
44
​
45
  /** Returns bucket linked list based on key */
46
  private getBucketLinkedList(key: string): LinkedList<{ key: string; value: T }> {
47
    const keyHash = this.hash(key);
48
    return this.buckets[keyHash];
49
  }
50
​
51
  /** Converts key string to hash number */
52
  private hash(key: string): number {
53
    // Simple hash function that calculates sum of all characters codes inside the key
54
    // You may want to use better hashing function to reduce the number of collisions
55
    const hashCode = Array.from(key).reduce(
56
      (hashAcc, keySymbol) => hashAcc + keySymbol.charCodeAt(0),
57
      0
58
    );
59
​
60
    // Reduce hash code number to fit inside available buckets number
61
    // Example: 37 % 30 = 3; 79 % 30 = 19
62
    return hashCode % this.buckets.length;
63
  }
64
}
Copied!
Links:
​Linked List record.
Code on Github.
Solve problems using Stack on LeetCode.
​Big-O Cheat Sheet.

Queue

Trees

Last modified 1yr ago

Copy link

Contents