How to create a hash table in JavaScript

JavaScript, data structures, hash table

This is one way to create a hash table in JavaScript using an array and chaining for handling collisions. Improvements can be made by swapping out the buckets in storage for linked lists instead of arrays and optimizing the hash function.

HashTableTry in REPL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
// Assumptions:
// In JavaScript, hash tables only accept strings
// Other languages support different data types but we'll stick with strings
// To handle collisions, we'll use the concept of chaining.
// Temporarily, we will not use a linked list. Instead we'll use another array.
// A linked list is preferable as it'll allow for fast insert and removal.
function HashTable(a, b) {
  this._storage = [];
  this._limit = 8; // A limit on the size of our hash table.
  this._size = 0;  // we can't rely on this._storage's length property and need to keep track of how many entries are in the hash table.
}
HashTable.prototype.insert = function(key, value) {
  const index = hash(key, this._limit);
  const oldSize = this._size;
  
  if (!this._storage[index]) {
    this._storage[index] = [[key, value]];
    this._size++;
  } else {
    let hasKey = false;
    const bucket = this._storage[index];
    for (let i = 0; i < bucket.length; i++) {
      const [entryKey, entryValue] = bucket[i];
      if (entryKey === key) {
        hasKey = true;
        bucket[i][1] = value;
      }
    }
    
    if (!hasKey) {
      bucket.push([key, value]);
      this._size++;
    }
  }
  
  if (this._size !== oldSize && this._size > this._limit * 0.75) {
    this._resize(this._limit * 2);    
  }
};
HashTable.prototype.remove = function(key) {
  const index = hash(key, this._limit);
  const bucket = this._storage[index];
  let entryIndex = -1;
  
  
  if (!bucket) return false;
  
  for (let i = 0; i < bucket.length; i++) {
    const [entryKey, entryValue] = bucket[i];
    if (entryKey === key) {
      entryIndex = i;
    }
  }
  
  bucket.splice(entryIndex, 1);
  this._size--;
  if (this._size < 0.25 * this._limit) {
    this._resize(Math.floor(this._limit / 2));
  }
};
HashTable.prototype.retrieve = function(key) {
  const index = hash(key, this._limit);
  
  if (!this._storage[index]) return undefined;
  
  const bucket = this._storage[index];
  let result;
  
  bucket.forEach((entry) => {
    [entryKey, entryValue] = entry;
    if (entryKey === key) {
      result = entryValue; 
    }
  });
  
  return result;
  
};
HashTable.prototype._resize = function(newLimit) {
  const oldStorage = this._storage;
  
  newLimit = Math.max(newLimit, 8); // our min limit is 8.
  if (newLimit === this._limit) return;
  
  this._limit = newLimit;
  this._size = 0;
  this._storage = [];
  
  oldStorage.forEach(bucket => {
    if (!bucket) return;
    for (let i = 0; i < bucket.length; i++) {
      const [key, value] = bucket[i];
      this.insert(key, value);
    }
  });
};
function hash(string, max) {
  let ret, i;
  for(ret = 0, i = 0, len = string.length; i < len; i++) {
    ret = (31 * ret + string.charCodeAt(i)) << 0;
  }
  return ret % max; 
}

Tests can be found at REPL.it