Hash Map / Dictionary Complete Guide

type HashNode = { key: string; value: number; next: HashNode | null }

class SimpleHashMap {
  private buckets: Array<HashNode | null>
  private entryCount = 0

  constructor(private capacity = 16) {
    this.buckets = new Array<HashNode | null>(capacity).fill(null)
  }

  private hashKey(key: string): number {
    let hashValue = 2166136261
    for (let index = 0; index < key.length; index += 1) {
      hashValue ^= key.charCodeAt(index)
      hashValue = Math.imul(hashValue, 16777619)
    }
    return (hashValue >>> 0) % this.capacity
  }

  private resizeIfNeeded(): void {
    const loadFactor = this.entryCount / this.capacity
    if (loadFactor < 0.75) {
      return
    }

    const oldBuckets = this.buckets
    this.capacity *= 2
    this.buckets = new Array<HashNode | null>(this.capacity).fill(null)
    this.entryCount = 0

    for (const bucketHead of oldBuckets) {
      let currentNode = bucketHead
      while (currentNode) {
        this.set(currentNode.key, currentNode.value)
        currentNode = currentNode.next
      }
    }
  }

  set(key: string, value: number): void {
    this.resizeIfNeeded()
    const bucketIndex = this.hashKey(key)
    let currentNode = this.buckets[bucketIndex]

    while (currentNode) {
      if (currentNode.key === key) {
        currentNode.value = value
        return
      }
      currentNode = currentNode.next
    }

    this.buckets[bucketIndex] = { key, value, next: this.buckets[bucketIndex] }
    this.entryCount += 1
  }

  get(key: string): number | null {
    const bucketIndex = this.hashKey(key)
    let currentNode = this.buckets[bucketIndex]

    while (currentNode) {
      if (currentNode.key === key) {
        return currentNode.value
      }
      currentNode = currentNode.next
    }

    return null
  }
}

function firstDuplicateUsingCustomHashMap(values: number[]): number | null {
  const countsByValue = new SimpleHashMap()

  for (const value of values) {
    const key = String(value)
    const previousCount = countsByValue.get(key) ?? 0
    const nextCount = previousCount + 1
    countsByValue.set(key, nextCount)

    if (nextCount > 1) {
      return value
    }
  }

  return null
}