哈希表（散列表）：通过哈希函数将键值映射为一个字典;
哈希函数：依赖键值的数据类型来构建一个哈希函数；
一个基本的哈希表：（按字符串计算键值）
function HashTable() {
this.table = new Array(137);
this.simpleHash = simpleHash;
this.showDistro = showDistro;
this.put = put;
this.init = init;
}
function simpleHash(data) {
var total = 0;
for(var i = 0; i < data.length; ++i) {
total += data.charCodeAt(i);
}
return total % this.table.length;
}
function showDistro() {
var n = 0;
for(var i = 0; i < this.table.length; ++i) {
if(this.table[i] !== undefined) {
console.log(i + " : " + this.table[i]);
}
}
}
function put(data) {
var pos = this.simpleHash(data);
this.table[pos] = data;
}
function init(data) {
for(var i = 0; i < data.length; ++i) {
this.put(data[i]);
}
}
操作：demo:;
可能出现的问题：
- 碰撞;即在哈希函数计算的时候出现相同的哈希值；
- 解决：这要解决哈希函数的计算问题；如上面定义中哈希函数，是求余计算：这里首先确保数组大小为质数（求余）；大小应该在100以上（分布均匀）；
上例中使用霍纳算法：求和时每次乘以一个较小的质数；
function betterHash(string) {
var 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);
}
散列化整型键：
- 随机生成id+score的数字：
function getRandomInt(min,max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
function genStuData(arr) {
for(var i = 0; i < arr.length; ++i) {
var num = "";
for(var j = 0; j < 6; ++j) { //id : length - 6;
num += Math.floor(Math.random() * 10);
}
num += getRandomInt(50,100);
arr[i] = num;
}
}
- 操作：demo; 经测试betterHash不但对字符，对整数类型也是有更好的效果；
碰撞处理：
- 开链法：（利用二维数组）
修改：
function put(data) {
var pos = this.simpleHash(data);
this.table[pos].push(data);
}
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 builChains() {
for(var i = 0; i < this.table.length; ++i) {
this.table[i] = new Array();
}
}
操作：demo
- 线性探测法：发生碰撞时依次向下存储；
修改：
function put(data) {
var pos = this.simpleHash(data);
while(this.table[pos] !== undefined) {
++pos;
}
this.table[pos] = data;
}
一般而言：如果数组大小是要存储数据的2倍及以上，使用线性探测法。