Hash Tables JS

gistfile1.txt

// NOT DEBUGGED

class HashTable {
  constructor() {
    this._storage = [];
    this._count = 0;
    this._limit = 10;
  }

  insert(key, value) {
    const hashedKey = _hash(key, this._limit);
    let bucket = this._storage[hashedKey];

    if (!bucket) {
      bucket = [];
      this._storage[hashedKey] = bucket
    }

    let didOverwrite = false
    bucket.forEach( tuple => {
      if (tuple[0] === key) {
        tuple[1] === value
        didOverwrite = true;
      }
    })

    if (!didOverwrite) {
      const tuple = [key, value];
      bucket.push(tuple);
      this._count++;
    }

    // if we reach a specified upper threshold, we should resize
    if (this._count / this._size > 0.8) {
      this.resize(this._size * 3)
    }

  }

  retrieve(key) {
    const hashedKey = this._hash(key, this._limit);
    const bucket = this._storage[hashedKey];

    if (!bucket) {
      return null
    }

    bucket.forEach( tuple => {
      if (tuple[0] === key) {
        return tuple[1]
      }
    })
    
  }

  remove(key) {

  } 
  
  resize(newLimit) {
    const prevStorage = this._storage;
    this._count = 0;
    this._limit = newLimit;
    this._storage = [];

    prevStorage.forEach( bucket => {
      bucket.forEach( ({key, value}) => {
        this.insert(key, value)
      })
    })

  }

  _hash(key, limit) {
    let hash = 0;
    for (let i = 0; i < str.length; i++) {
      let letter = str[i];
      hash = (hash << 5) + letter.charCodeAt(0);
      hash = (hash & hash) % max;
    }
    return hash;
  }

}