A bucketed hash table implementation with pure JavaScript and arrays

hash-table.js

class BucketNode {
  _previous = null;
  _next = null;

  constructor (key, value) {
    this.key = key;
    this.value = value;
  }
}

class HashTableBucket {
  _head = null;
  _tail = null;

  set (key, value) {
    const bucketNode = new BucketNode(...arguments);

    if (!this._head) {
      this._head = bucketNode;
      this._tail = bucketNode;
    } else {
      let current = this._head;

      while (current) {
        if (current.key === key) {
          current.value = value;
          return;
        }

        current = current._next;
      }

      bucketNode._previous = this._tail;
      this._tail._next = bucketNode;
      this._tail = bucketNode;
    }
  }

  get (key) {
    let current = this._head;

    while (current) {
      if (current.key === key) {
        return current.value;
      }

      current = current._next;
    }
  }

  remove (key) {
    let current = this._head;

    while (current) {
      if (current.key === key) {
        if (current === this._head) {
          this._head = current._next;
        }

        if (current === this._tail) {
          this._tail._previous._next = null;
        }

        if (current._previous && current._next) {
          current._previous._next = current._next;
          current._next._previous = current._previous;
        }

        return;
      }

      current = current._next;
    }
  }
}

class HashTable {
  constructor (size = 100) {
    this.size = size;
    this.values = [];
    this._length = 0;
  }

  get length () {
    return this._length;
  }

  computeHash (key) {
    return String(key) % this.size;
  }

  set (key, value) {
    const hash = this.computeHash(key);

    if (!this.values[hash]) {
      this.values[hash] = new HashTableBucket();
    }

    this.values[hash].set(...arguments);

    this._length++;
  }

  remove (key) {
    const hash = this.computeHash(key);
    const list = this.values[hash];

    if (!list) {
      return;
    }

    list.remove(key);
    this._length--;
  }

  get (key) {
    const hash = this.computeHash(key);
    const list = this.values[hash];

    return list && list.get(key);
  }
}

const hashTable = new HashTable();
hashTable.set('foo', 'bar');
hashTable.set('bim', 'bam');

console.assert(hashTable.length === 2, 'computes length');
console.assert(hashTable.get('foo') === 'bar', 'retrieves data');
console.assert(hashTable.get('bim') === 'bam', 'retrieves data');
console.assert(hashTable.get('blorp') === undefined, 'does not find data that was not stored');

hashTable.remove('foo');
console.assert(hashTable.length === 1, 'computes updated length');
console.assert(hashTable.get('foo') === undefined, 'data was removed');
console.assert(hashTable.get('bim') === 'bam', 'retrieves data');

hashTable.remove('bim');
console.assert(hashTable.get('bim') === undefined, 'data was removed');
console.assert(hashTable.length === 0, 'computes updated length');

hashTable.set('animal', 'cow');
hashTable.set('animal', 'horse');
console.assert(hashTable.get('animal') === 'horse', 'data is overwritten');

const hashTable2 = new HashTable();
hashTable2.set('foo', 'bar');
hashTable2.set('bim', 'bam');
hashTable2.set('baz', 'qux');

hashTable2.remove('bim');
console.assert(hashTable2.get('bim') === undefined, 'data was removed from middle');

This is mostly an academic exercise for me. You probably wouldn't want to use this for anything of significance.

Suggested testcase:

const hashTable2 = new HashTable();
hashTable2.set('foo', 'bar');
hashTable2.set('bim', 'bam');
hashTable2.set('baz', 'qux');

hashTable2.remove('bim');
console.assert(hashTable2.get('bim') === undefined, 'data was removed from middle');

@dancrumb Thank you! I just added the test case and potential fix for the bug it revealed. It might need a bit more tweaking, but the tests at least pass now! 🙂