Implementing a HashTable based on JS arrays... just for fun

hash-table.js

export default class HashTable {
  constructor(size) {
    this._data = new Array(size);
  }

  // Inserts `value` under `key`, forgetting any previous value stored under `key`.
  // Returns the HashTable.
  insert(key, value) {
    bucketFor(this._data, key, true).insert(key, value);
    return this;
  }
  
  // Returns the value stored under `key`, or `undefined` if nothing is stored there.
  get(key) {
    const bucket = bucketFor(this._data, key, false);
    return bucket === undefined ? undefined : bucket.get(key);
  }
  
  // Returns `true` iff there is a value (other than `undefined`) stored under `key`.
  has(key) {
    return this.get(key) !== undefined;
  }
  
  // Deletes the value stored under `key`. Idempotent.
  // Returns the HashTable.
  remove(key) {
    const bucket = bucketFor(this._data, key, false);
    if (bucket) { bucket.remove(key); }
    return this;
  }
};

function bucketFor(data, key, createIfEmpty) {
  const index = indexFor(data, key);
  let bucket = data[index];
  if (bucket === undefined && createIfEmpty) {
    bucket = data[index] = new Bucket();
  }
  return bucket;
}

class Bucket {
  constructor() {
    this._entries = [];
  }
  
  insert(key, value) {
    const existing = this._entries.find(matchingKey(key));
    if (existing) {
      existing[1] = value;
    } else {
      this._entries.push([ key, value ]); 
    }
  }
  
  get(key) {
    const existing = this._entries.find(matchingKey(key));
    return existing === undefined ? undefined : existing[1];
  }
  
  remove(key) {
    const existingIndex = this._entries.findIndex(matchingKey(key));
    if (existingIndex) {
      this._entries.splice(existingIndex, 1);
    }
  }
}

function matchingKey(target) {
  return function([ key, _ ]) { return key === target; };
}

const SOME_PRIME = 7;
const ANOTHER_PRIME = 31;

function indexFor(data, key) {
  key = '' + key;
  let hash = SOME_PRIME;
  for (let i = 0; i < key.length; ++i) {
    hash = hash * ANOTHER_PRIME + key.charCodeAt(i);
  }
  return hash % data.length;
}