Hash Tables

A hash table is a data structure that stores data in key-value pairs.

[key, value]

It works by passing a key (usually a string) through a hash function.
The hash function generates a number, called the hash index, which tells the table where to store that key–value pair.

Example:

key = "bar" 
hash("bar") => 4

The hash index is 4. This index points to a bucket, which is like a storage box where the value is placed.

Hash tables have O(1) time for inserting, deleting, and retrieving with a worst case scenario of O(n) time if many keys collide. In JavaScript, hash tables appear as:

• Objects {}
• Maps (new Map())

Hash Collisions

A collision happens when two different keys hash to the same index.

Example:

hash("cat") → 2
hash("tap") → 2

Both keys go into bucket 2 → collision!

Chaining

A common fix for collision is the chaining method. This is where multiple key–value pairs are stored in the same bucket using a list/array.

Bucket 2:
[
  ["cat", 5],
  ["tap", 9]
]

Both live in the same index, no overwriting.

Hash Table Implementation (Explained Step-by-Step)

Below is a simplified JavaScript implementation showing how hash tables work under the hood.

const hash = (key, bucketSize) => {
  let hash = 0;

  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }

  return hash % bucketSize;
};

function HashTable() {
  let table = [];
  let tableLimit = 10;

  // print
  this.printTable = function () {
    console.log(table);
  };
  // add
  this.set = function (key, value) {
    // get the index of the key
    const index = hash(key, tableLimit);
    // check if the item exists at the index
    if (!table[index]) {
      table[index] = [[key, value]];
    } else {
      // if it does, update the value
      let inserted = false;
      for (let i = 0; i < table[index].length; i++) {
        if (table[index][i][0] === key) {
          table[index][i][1] = value;
          inserted = true;
        }
      }

      if (!inserted) {
        table[index].push([key, value]);
      }
    }
  };

  // delete
  this.remove = function (key) {
    const index = hash(key, tableLimit);

    if (table[index].length === 1 && table[index][0][0] === key) {
      delete table[index];
    } else {
      for (let i = 0; i < table[index].length; i++) {
        if (table[index][i][0] === key) {
          delete table[index][i];
        }
      }
    }
  };

  // lookup
  this.get = function (key) {
    const index = hash(key, tableLimit);
    if (!table[index]) return undefined;

    for (let i = 0; i < table[index].length; i++) {
      if (table[index][i][0] === key) {
        return table[index][i][1];
      }
    }
  };
}

const myTable = new HashTable();
myTable.set("name", "Alice");
myTable.set("age", 30);
myTable.printTable();
myTable.set("name", "Jane");
myTable.printTable();

The Hash Function

const hash = (key, bucketSize) => {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash += key.charCodeAt(i);
  }
  return hash % bucketSize;
};

• Start with hash = 0.
• Loop through each character of the key.
• Convert each character → number (charCodeAt).
• Add all the numbers together.
• % bucketSize makes sure the number fits inside the table size.
• The result tells you which bucket to store the key-value pair in.

The Hash Table

function HashTable() {
  let table = [];
  let tableLimit = 10;
/*...some code here..*/
}

• table is the actual array holding buckets.
• tableLimit is how many buckets exist (size of the table).

The Print Function

this.printTable = function () {
  console.log(table);
};

This just shows the table in the console.

SET (insert or update)

this.set = function (key, value) {
  /*some code here*/
}

const index = hash(key, tableLimit); converts the key to a bucket index.

if (!table[index]) {
  table[index] = [[key, value]];
}

This checks if the bucket is empty. If it is, it creates the bucket and stores the key/value in a mini array, e.g. [ [key, value] ]. This is chaining. Each bucket stores a list of items.

else {
  let inserted = false;

  for (let i = 0; i < table[index].length; i++) {
    if (table[index][i][0] === key) {
      table[index][i][1] = value;
      inserted = true;
    }
  }

The bucket already has items (collision happened). So;

• Loop through every item in the bucket.
• If the key already exists, update the value.
• Set inserted = true so you know the key was found.

If key was not found, then add it:

if (!inserted) {
  table[index].push([key, value]);
}

Remove

this.remove = function (key) {
  const index = hash(key, tableLimit);

/*more code here*/
}

If the bucket has only one item, remove the whole bucket:

if (table[index].length === 1 && table[index][0][0] === key) {
  delete table[index];
}

If the bucket has only multiple items, loop through the items and delete only the matched one.

Get (lookup)

this.get = function (key) {
  const index = hash(key, tableLimit);
/*...more code here...*/
}

If the bucket doesn’t exist, the item is not in the table.

if (!table[index]) return undefined;

Search the bucket and check each item in the chain. If a match is found, return the match.

for (let i = 0; i < table[index].length; i++) {
  if (table[index][i][0] === key) {
    return table[index][i][1];
  }
}

Hash tables are used in many places,like storing user information, counting things, checking if something already exists, or quickly finding data by a key. They help programs run faster because they make lookups very quick. It may look complex at first, but once you understand the idea of hashing and buckets, everything becomes surprisingly simple.

Check out this easy mode hash table question on leetcode: Roman to Integer.