SOURCE

//线性探测法隶属于一种 更一般化 的散列技术：开放寻址散列 。
//当发生碰撞时，线性探测法检查散列表中的下一个位置是否为空。
//如果为空， 就将数据存入该位置；
//如果不为空，则继续检查下一个位置，直到找到一个空的位置为止。
function HashTable() {
    this.table = new Array(137);
    this.simpleHash = simpleHash;
    this.betterHash = betterHash;
    this.showDistro = showDistro;
    this.put = put;
    this.get = get;
    this.buildChinas = buildChinas;
    //数组table和values并行工作，当将一个键值保存到数组 table 中时，
    //将数据存入数组 values 中相应的位置上。
    this.value = [];
}

function simpleHash(data) {//每个字符的ASCII码相加，得到散列值，有碰撞风险
    var total = 0;
    for (var i = 0; i < data.length; i++) {
        total += data.charCodeAt(i);
    }
    console.log('Hash value:' + data + '->' + total)
    return total % this.table.length;
}

function betterHash(string) {//霍纳算法 求和时乘一个质数
    const H = 37;
    var total = 0;
    for (var i = 0; i < string.length; i++) {
        total += H * total + string.charCodeAt(i);
    }
    total = total % this.table.length;
    if (total < 0) {
        total += this.table.length - 1;
    }
    return parseInt(total);
}

// function put(key, data) {
//     var pos = this.betterHash(key);
//     this.table[pos] = data;
// }

// function get(key) {
//     return this.table[this.betterHash[key]];
// }
//重写put() get()方法
function put(key, data){
    var pos = this.betterHash(key)
    if(this.table[pos]==undefined){
        this.table[pos] = key
        this.value[pos] = data
    }else{
        while(this.table[pos]!=undefined){
            pos++
        }
        this.table[pos] = key
        this.value[pos] = data
    }
}

function get(key){
    var hash = this.betterHash(key)
    for(var i=hash; this.table[hash]!=undefined; i++){
        if(this.table[hash] == key){
            return this.value[hash]
        }
    }
}


function showDistro() {
    var n = 0;
    for (var i = 0; i < this.table.length; i++) {
        if (this.table[i][0] != undefined) {
            console.log(i + ':' + this.table[i])
        }
    }
}

function buildChinas(){
    for(var i = 0; i < this.table.length; i++){
        this.table[i] = new Array();
    }
}