The classic dictionary

dictionary.ts

import * as fs from "fs";
import * as assert from "assert";

type DictionaryEntry<K, V> = [key: K, value: V];

const DICT_INITIAL_SIZE = 8;
const DICT_MAX_LOAD_FACTOR = 0.75;

class Dictionary<V> implements Iterable<[string, V]> {
  private _entries = 0;
  loadFactor = 0;
  buckets: DictionaryEntry<string, V>[][] = Array(DICT_INITIAL_SIZE);

  get(key: string) {
    const i = this.hash(key) % this.buckets.length;
    const slots = this.buckets[i] || [];
    const [_, result] = slots.find(([_key, _]) => _key === key) || [key, null];
    return result;
  }

  put(key: string, value: V) {
    this.loadFactor = this.length / this.buckets.length;

    if (this.loadFactor >= DICT_MAX_LOAD_FACTOR) {
      this.buckets = this.rehash(this.buckets);
    }

    const i = this.hash(key) % this.buckets.length;
    const slots = this.buckets[i] || [];
    slots.push([key, value]);

    this.buckets[i] = slots;
    this._entries++;
  }

  remove(key: string) {
    const i = this.hash(key) % this.buckets.length;
    const slots = this.buckets[i] || [];
    this.buckets[i] = slots.filter(([_key]) => _key !== key);
    this._entries--;
  }

  [Symbol.iterator]() {
    return this.buckets.flat()[Symbol.iterator]();
  }
  
  get length() {
    return this._entries;
  }

  private rehash(buckets: DictionaryEntry<string, V>[][]) {
    const s = this.nextSize(buckets.length);
    const newBuckets = Array(s);

    for (const [key, value] of buckets.flat()) {
      const i = this.hash(key) % newBuckets.length;
      const slots = newBuckets[i] || [];
      slots.push([key, value]);
      newBuckets[i] = slots;
    }

    return newBuckets;
  }

  private nextSize(size: number) {
    return 2 * size;
  }

  private hash(key: string) {
    const bytes = [...Buffer.from(key)];
    let hash = 5381;

    for (const byte of bytes) {
      hash = (33 * hash + byte) >>> 0;
    }

    return hash;
  }
}

function randomPick(array: string[], amount: number) {
  const result: string[] = [];

  for (let i = 0; i < amount; i++) {
    const j = Math.floor(Math.random() * array.length);
    result.push(array[j]);
  }

  return result;
}

function main(fname: string) {
  const words = fs.readFileSync(fname).toString().split("\n").filter(Boolean);
  const dict = new Dictionary<string>();

  assert([...dict].length === 0);

  for (const word of words) {
    dict.put(word, word.toUpperCase());
  }

  assert.equal([...dict].length, words.length);
  assert.equal(dict.length, words.length);

  for (const word of randomPick(words, 50)) {
    const upperCased = dict.get(word);
    console.log(`Random pick: ${word}, Dictionary value: ${upperCased}`);
    assert.deepEqual(word.toUpperCase(), upperCased);
  }

  for (const [key, _] of dict) {
    dict.remove(key);
  }

  assert.equal([...dict].length, 0);
  assert.equal(dict.length, 0);
}

main("/usr/share/dict/words");