open_hash_table.js

function Node(key, val) {
    this.key = key
    this.val = val
    this.next = undefined
}

function Hash(len, capacity) {
    this.len = len
    this.arr = new Array(len)
    this.capacity = capacity
    this.loadFactor = 0.5
    this.size = 0
}

Hash.prototype.isOverLoad = function() {
    return this.size >= this.capacity * this.loadFactor
}

Hash.prototype.getNode = function(key){
  
  var out = {
    has: false,
    index: undefined,
    node: undefined
  }
  
  var index = this.generateIndex(key)
  if(this.arr[index] === undefined) return out
  
  out.index = index
  
  var node = this.arr[index]
  while(node !== undefined && node.key !== key){
    node = node.next
  }
  if(node === undefined) return out
  
  out.has = true
  out.node = node
  
  return out
}

Hash.prototype.generateIndex = function(key) {
    var sum = 0
    for (var i = 0; i < key.length; i++) {
        sum = sum * 33 + key.charCodeAt(i)
        sum = sum % this.len
    }
    return sum
}

//http://www.lintcode.com/en/problem/rehashing/
Hash.prototype.resize = function() {
    console.log(this.size + ' exceeds capacity ' + this.capacity)
    //1.double the size of the array 
    this.len *= 2
    this.capacity *= 2

    //2.rehashing
    var copy = this.arr
    this.arr = new Array(this.len)

    for (var i = 0; i < copy.length; i++) {
        if (copy[i] !== undefined) {
            var node = copy[i]
            while (node !== undefined) {
                this.put(node.key, node.val)
                node = node.next
            }
        }
    }
}

Hash.prototype.get = function(key) {
    var result = this.getNode(key)
    if(!result.has) return
    else return result.node.val
}


Hash.prototype.delete = function(key) {
   var result = this.getNode(key)
    if(!result.has) return
    else{

      var root = this.arr[result.index]
      var node = result.node
         
      //if node is head
      if(root.val === node.val){
        this.arr[result.index] = undefined
      }else{
        
        //find pre
        while(root.next.val !== result.node.val){
          root = root.next
        }
        root.next = node.next
      }

      this.size--
    }
}

Hash.prototype.put = function(key, value) {
  var result = this.getNode(key)
  if(result.has){
    result.node.val = value
  }else{
        
    if(this.isOverLoad()){
      this.resize();
      this.put(key, value)
      return
    }    
    
    if(!result.index){
      var index = this.generateIndex(key)
      this.arr[index] = new Node(key, value)
    }else{
      var tmp = this.arr[result.index]
      this.arr[result.index] = new Node(key, value)
      this.arr[result.index].next = tmp
    }   
    this.size++
  }
}

var test = new Hash(6, 6)

test.put('b', 'bb')
test.put('r', 'rr')

//console.log(test.arr)

test.put('z', 'zz')
// test.put('g', 'gg')
// test.put('s', 'ss')
test.put('h', 'hh')
// test.put('j', 'jj')
// test.put('f', 'ff')
// test.put('e', 'ee')
// test.put('w', 'ww')
// test.put('d', 'dd')
// test.put('y', 'yy')
// test.put('q', 'qq')

//console.log(test.arr)

console.log(test.get('r'))

//console.log(test.arr)

test.delete('h')

console.log(test.arr)

console.log(test.get('r'))
console.log(test.get('b'))
console.log(test.get('h'))


//2.implement a data structure with O(1) delete, O(1) insert, O(1) delete random