Software Engineering
Personal Development
TIL - Today I Learned

WIP

# 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).

`phoneBook.set('John Doe', '111-222-333');​phoneBook.set('Alberto Anderson', '111-333-444');`

// 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

`import { LinkedList } from '../LinkedList/LinkedList';​export class HashTable<T> {  // Allowed buckets number. The bigger the bucket number the fewer collisions we will get.  private static readonly defaultBucketsNumber = 30;  // hash table that will store buckets with linked list.  private readonly buckets: LinkedList<{ key: string; value: T }>[];​  constructor(bucketsNumber = HashTable.defaultBucketsNumber) {    // Create hash table of certain size and fill each bucket with empty linked list.    this.buckets = Array(bucketsNumber)      .fill(null)      .map(() => new LinkedList());  }​  /** Add or Update the value by its key */  public set(key: string, value: T) {    const bucketLinkedList = this.getBucketLinkedList(key);    const node = bucketLinkedList.find((item) => Object.is(item.key, key));​    if (!node) {      bucketLinkedList.append({ key, value }); // Add new node    } else {      node.value.value = value; // Update value of already existing node    }  }​  /** Get the value by its key */  public get(key: string): T | null {    const bucketLinkedList = this.getBucketLinkedList(key);    const node = bucketLinkedList.find((item) => Object.is(item.key, key));​    return node?.value.value || null;  }​  /** Delete the value by its key */  public delete(key: string): T | null {    const bucketLinkedList = this.getBucketLinkedList(key);    const node = bucketLinkedList.find((item) => Object.is(item.key, key));    const deletedNode = bucketLinkedList.delete(node?.value);​    return deletedNode?.value.value || null;  }​  /** Returns bucket linked list based on key */  private getBucketLinkedList(key: string): LinkedList<{ key: string; value: T }> {    const keyHash = this.hash(key);    return this.buckets[keyHash];  }​  /** Converts key string to hash number */  private hash(key: string): number {    // Simple hash function that calculates sum of all characters codes inside the key    // You may want to use better hashing function to reduce the number of collisions    const hashCode = Array.from(key).reduce(      (hashAcc, keySymbol) => hashAcc + keySymbol.charCodeAt(0),      0    );​    // Reduce hash code number to fit inside available buckets number    // Example: 37 % 30 = 3; 79 % 30 = 19    return hashCode % this.buckets.length;  }}`