hash散列中需要确定key和value的唯一确定关系。
hash散列便于快速的插入删除和修改，不便于查找最大值等其他操作
以下为字符和数字的hash散列：
function HashTable () {
this.table = new Array(137);
this.value = new Array();
this.simpleHash = simpleHash;
this.betterHash = betterHash;
this.display = display;
this.put = put;
this.get = get;
this.buildChains = buildChains; // 开链法解决碰撞
}
function simpleHash (data) {
var total = 0;
for(var i =0; i<data.length; i++){
total= total + data.charCodeAt(i);
}
return total % this.table.length;
}
function betterHash (data) {
var total = 0;
const h = 37; // 挑选合适的质数
data = data.toString();
for(var i=0;i<data.length; i++){
total = total*h + data.charCodeAt(i);
}
total = total % this.table.length;
if(total<0) {
return total+=this.table.length-1;
}
return parseInt(total);
}
function put (key, value) {
var pos = this.betterHash(key);
if(this.table[pos] === undefined){
this.table[pos] = key;
this.value[pos] = value;
}else{
while(this.table[pos]!==undefined){
pos++
}
this.table[pos] = key;
this.value[pos] = value;
}
}
function get(key) {
var hash = -1;
hash = this.betterHash(key);
if (hash > -1) {
for (var i = hash; this.table[hash] != undefined; i++) {
if (this.table[hash] == key) {
return this.value[hash];
}
}
}
return undefined;
}
function display () {
var _this = this;
this.value.forEach(function(item, index){
if (item!==undefined) {
console.log(_this.table[index] + ": " + item);
}
})
}
function buildChains () {
this.table.forEach(function (item, index) {
item = new Array();
})
}
hash的使用方法：
function buildChains () {
this.table.forEach(function (item, index) {
item = new Array();
})
}
var someNames = ["David", "Jennifer", "Donnie", "Raymond","Cynthia", "Mike", "Clayton", "Danny", "Jonathan", "Donnie"];
var hs = new HashTable();
someNames.forEach(function(item, index){
hs.put(item, item + "Val")
})
hs.display();
console.log(hs.get("David"))