# Maps

# Terms

Load Factor - the amount of data points vs the amount of storage (data.len / storage.capacity)

Key - a value that is consistently hashable and is used to look up data

Value - data associated with a key

Collision - when two or more keys map to the same cell

type map = {key, value}[][]
hash(key) -> number

take that number % capacity to produce index of item

if there is more than one item stored there (from collisions), linear search at that index

# LRU Cache

Least recently used items get evicted

Under the hood it's a linked list supported by a hash map for lookup, if you lookup an item it gets moved to the front of the list.

Super handy because it has a fixed capacity.

type Node<T> = {
  value: T;
  next?: Node<T>;
  prev?: Node<T>;
};

class LRUCache<K, V> {
  private length: number;
  private lookup: Map<K, Node<V>>;
  private reverseLookup: Map<Node<V>, K>;
  private head?: Node<V>;
  private tail?: Node<V>;

  constructor(private capacity: number = 10) {
    this.length = 0;
    this.head = this.tail = undefined;
    this.lookup = new Map<K, Node<V>>();
    this.reverseLookup = new Map<Node<V>, K>();
  }

  update(key: K, value: V): void {
    let node = this.lookup.get(key);
    if (!node) {
      node = createNode(value);
      this.length++;
      this.prepend(node);
      this.trimCache();

      this.lookup.set(key, node);
      this.reverseLookup.set(node, key);
    } else {
      this.detach(node);
      this.prepend(node);
      node.value = value;
    }
  }

  get(key: K): V | undefined {
    const node = this.lookup.get(key);
    if (!node) return undefined;

    this.detach(node);
    this.prepend(node);

    return node.value;
  }

  private detach(node: Node<V>): void {
    if (node.prev) {
      node.prev.next = node.next;
    }

    if (node.next) {
      node.next.prev = node.prev;
    }

    if (this.head === node) {
      this.head = this.head.next;
    }

    if (this.tail === node) {
      this.tail = this.tail.prev;
    }

    node.next = undefined;
    node.prev = undefined;
  }

  private prepend(node: Node<V>): void {
    if (!this.head) {
      this.head = this.tail = node;
      return;
    }

    node.next = this.head;
    this.head.prev = node;
  }

  private trimCache(): void {
    if (this.length <= this.capacity) {
      return;
    }

    const tail = this.tail!;
    this.detach(this.tail);

    const key = this.reverseLookup.get(tail) as K;
    this.lookup.delete(key);
    this.reverseLookup.delete(tail);
    this.length--;
  }
}

function createNode<T>(value: T): Node<T> {
  return { value };
}