close_hash_table.js

//close hashing
//an array

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

Hash.prototype.getIndex = 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
}

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

Hash.prototype.resize = function(){
    console.log(this.size + ' exceeds capacity ' + this.capacity)
    this.len *= 2
    this.capacity *= 2
    
    var copy = this.arr
    this.arr = new Array(this.len)
    for(var i = 0; i < copy.length; i++){
      if(copy[i] !== undefined){
        this.put(copy[i].key, copy[i].value)
      }
    }
}

Hash.prototype.get = function(key) {
    var index = this.getIndex(key)
    var count = 0
    while (count < this.len) {
        if (this.arr[index] === undefined) break // not found
        else if (typeof this.arr[index] === 'object' && this.arr[index].key === key) {
            //found
            return this.arr[index].value
        } else {
          count++
          index++
          if(index === this.len) index = 0
        }
    }
}

Hash.prototype.delete = function(key) {
    var index = this.getIndex(key)
    var count = 0
    while (count < this.len) {
        if (this.arr[index] === undefined) break // not found
        else if (typeof this.arr[index] === 'object' && this.arr[index].key === key) {
            //delete
            this.arr[index] = 'deleted'
            this.size--
        } else {
          count++
          index++
          if(index === this.len) index = 0
        }
    }
}

Hash.prototype.put = function(key, value) {
    var index = this.getIndex(key)
    var count = 0
    while (count < this.len) {

        if (this.arr[index] === undefined || this.arr[index] === 'deleted') {
            //create
            this.arr[index] = {
                key: key,
                value: value
            }
            this.size++
            if(this.isOverLoad()){
              this.resize()
            }
            break
        } else if (this.arr[index].key === key) {
            //update
            this.arr[index].value = value
            break
        } else {
          count++
          index++
          if(index === this.len) index = 0
        }
    }
}

var test = new Hash(3, 3)
test.put('a', 'aa')
test.put('b', 'bb')
test.put('c', 'cc')
test.put('d', 'dd')
test.delete('b')
test.put('e', 'ee')
console.log(test.get('c'))
console.log(test.get('b'))
console.log(test.get('e'))