数据结构与算法的JavaScript描述——散列（HashTable）

数据结构与算法的JavaScript描述——散列（HashTable）

说明：以下部分均为《数据结构与算法的JavaScript描述》学习内容及笔记。
* 在散列表上插入、删除和取用数据都非常快，但是对于查找却效率低下，比如查找一组数组中的最大值和最小值。
* 对数组大小常见的限制是：数组长度应该是一个质数(如果键是随机的整数，则散列函数应该更均匀地分布)：除留余数法。

1、构造HashTable类

function HashTable(){
    this.table=new Array(137);
    this.simpleHash=simpleHash;
    this.showDistro=showDistro;//显示数据
    this.put=put;//加入数据
    this.get=get;
}

1.1 散列函数

1.1.1 散列函数 (将字符串（键）中的每个字符的ASCII码值) 容易碰撞

function simpleHash(data){
    var total=0;
    for(var i=0;i<data.length;i++){
        total+=data.charCodeAt(i);
    }
    return total % this.table.length;
}

1.1.2 散列函数 (霍纳算法)

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

1.2 put 加入数据

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

1.3 showDistro 显示数据

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

1.3 get 查找

function get(){
    return this.table[this.betterHash(key)];
}

2、碰撞处理

2.1 开链法

function buildChains(){
    for(var i=0;i<this.table.length;++i){
        this.table[i]=new Array();
    }
}
function showDistro(){
    var n=0;
    for(var i=0;i<this.table.length;++i){
        if(this.table[i][0]!=undefined){
            print(i+":"+this.table[i];
        }
    }
}
function put(key, value){
    var pos=this.betterHash(key);
    var index=0;
    while(this.table[pos][index]!=undefined){
        ++index;
    }
    this.table[pos][index]=data;
}
function get（key){
    var index=0;
    var pos=this.betterHash(key);
    while(this.table[pos][index]&&this.table[pos][index]!=key){
        index++;
    }
    this.table[pos][index]?this.table[pos][index]:undefined;
}

2.2 线性探查法

function HashTable(){
    this.table=new Array(137);
    this.simpleHash=simpleHash;
    this.showDistro=showDistro;//显示数据
    this.put=put;//加入数据
    this.get=get;
    this.value=[];
}

function put(key, value){
    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.table[pos]=value;
    }
}

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