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;
}

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]];
// }

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();
    }
}
//新的put()方法将键值散列 散列后的值对应数组的一个位置 若该位置上数组第一位已有数据 put()会搜索下一个位置 直到找到位置并储存
function put(key, data){
    var pos = this.betterHash(key)
    var index = 0
    if(this.table[pos][index]==undefined){		//此时 this.table[pos] 对应一个数组结构
        //该方法使用链中两个连续的单元格，第一个用来保存键值，第二个用来保存数据。
        this.table[pos][index] = key
        this.table[pos][index+1] = data
    }else{
        //循环
        while(this.table[pos][index]!=undefined){
            ++index
        }
        this.table[pos][index] = key
        this.table[pos][index+1] = data
    }
}


//新的 get() 方法先对键值散列 根据散列后的值找到散列表中相应的位置 然后搜索该位置上的链 直到找到键值 如果找到 就将紧跟在键值后面的数据返回 如果没找到 就返回 undefined
function get(key){
    var pos = this.betterHash(key)
    var index = 0
    if(this.table[pos][index]==key){
        return this.this.table[pos][index+1]
    }else{
        while(this.table[pos][index]!=key){
            index += 2
        }
        return this.table[pos][index+1]
    }
    return undefined			//散列表里没有此项
}



var hTable = new HashTable();
hTable.buildChinas();
var someNames = ['David','Jennifer','Donnie','Raymond','Cynthia','Mike','Clayton',
'Danny','Jonathan'];
for(var i = 0; i < someNames.length; i++){
    hTable.put(someNames[i]);
}
hTable.showDistro();