martincartledge.github.io

This is the third post in my series Data Structures and Algorithms using JavaScript. Last week, I discussed The Array Data Structure. This week I am going to talk about another popular data structure, the Hash Table. Much like in my previous post, I will cover the Big O of common Hash Table actions (insert, lookup, delete, search). We will also create our own Hash Table data structure! Let’s get to it.

What is a Hash Table?

A defintion of a hash Table

• some notes about hash tables
• some notes about hash tables
• some notes about hash tables

Common Hash Table Actions

Insert O(1)

A definition of Insert

Lookup O(1)

A definition of Lookup

Delete O(1)

A definition of Delete

Search O(1)

A definition of Search

Hash Collision

A definition of Hash Collision

Let’s Create a Hash Table Data Structure

class HashTable {
  constructor(size){
    this.data = new Array(size);
  }

  _hash(key) {
    let hash = 0;
    for (let i =0; i < key.length; i++){
        hash = (hash + key.charCodeAt(i) * i) % this.data.length
    }
    return hash;
  }

  get(key) {
    let address = this._hash(key);
    const currentBucket = this.data[address];
    if (currentBucket) {
      for(let i = 0; i < currentBucket.length; i++) {
        if (currentBucket[i][0] === key) {
          return currentBucket[i][1]
        }
      }
    } 
		// O(n)
    return undefined
  }

  set(key, value) {
    let address = this._hash(key)
    if (!this.data[address]) {
      this.data[address] = [];
    }
    this.data[address].push([key, value]);
		// O(1)
    return this.data
  }
}

const myHashTable = new HashTable(50);
myHashTable.set('grapes', 10000)
// myHashTable.get('grapes')
// myHashTable.set('apples', 9)
// myHashTable.get('apples')