hash_map_typescript.md

Hash Map implementation in Typescript

function DJB2Hash(key: string) {
  let hash = 5381; // magic start djb2 number

  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    // using (hash << 5 + hash) instead of hash * 33 because '<<' is operation is faster than '*' on computer cpu
    hash = hash & hash;
  }

  return hash;
}

class HashMap<T> {
  private table = Array<[string, T][]>(17);
  private numberOfItems = 0;
  private TABLE_LOAD_FACTOR = 0.8;

  private hashKeyToIdx(key: string, tableSize: number): number {
    const hash = DJB2Hash(key);

    return (hash >>> 0) % tableSize; // (hash >>> 0) handles edge cases where the returned hash is negative number as result of integer overflow
  }

  private resizeTable() {
    const newTable: typeof this.table = Array(this.table.length * 2);

    for (const slot of this.table) {
      if (slot != null) {
        for (const column of slot) {
          const [key, value] = column;

          const keyIdx = this.hashKeyToIdx(key, newTable.length);

          if (newTable[keyIdx] != null) {
            // collision re-occurred while re-adding, pushing key,value pair into next index of the slot
            newTable[keyIdx].push([key, value]);
          } else {
            newTable[keyIdx] = [[key, value]];
          }
        }
      }
    }

    this.table = newTable;
  }

  public get size(): number {
    return this.numberOfItems;
  }

  public setValue(key: string, value: T) {
    this.numberOfItems++;

    const loadFactor = this.numberOfItems / this.table.length;

    if (loadFactor > this.TABLE_LOAD_FACTOR) {
      this.resizeTable();
    }

    // hash key
    const keyIdx = this.hashKeyToIdx(key, this.table.length);

    // store value
    if (this.table[keyIdx] != null) {
       const slot = this.table[keyIdx];

      for (const column of slot) {
        const [columnKey, columnValue] = column;

        if (columnKey === key) {
          // if key already present in hashmap update value
          column[1] = value;
          return;
        }
      }
    
      // collision occurred pushing key,value pair into slot
      this.table[keyIdx].push([key, value]);
    } else {
      this.table[keyIdx] = [[key, value]];
    }
  }

  public getValue(key: string) {
    // retrieve value from hash
    const keyIdx = this.hashKeyToIdx(key, this.table.length);

    const slot = this.table[keyIdx];

    if (slot != null) {
      if (slot.length === 1) return slot[0][1]; // no collision occurred constant time look up O(1)
      // collision occurred linear time lookup O(n)
      for (const column of slot) {
        const columnKey = column[0];

        if (columnKey === key) {
          return column[1]; // return value
        }
      }
    }

    return undefined;
  }
}