Hash Tables Introduction

Operation | Big O
insert | O(1)
lookup | O(1)
delete | O(n)
search | O(n)

Examples of Hash Tables

• Map is a collection of keyed data items, just like an Object. But the main difference is that Map allows keys of any type.
• A Set is a special type collection – "set of values" (without keys), where each value may occur only once.
  Map and Set
• Objects in JavaScript are a type of Hash Table.

Implement A Hash Table

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

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

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

  get(key) {
    const address = this._hash(key);
    const currentBucket = this.data[address]
    return currentBucket 
      ? currentBucket.find(item => item[0] === key)[1] 
      : undefined
  }

  keys() {
    return this.data.filter(item => !!item).map(item => item[0][0]);
  }
}

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

Hash Tables VS Arrays