js:数据结构笔记7--哈希表

哈希表(散列表):通过哈希函数将键值映射为一个字典;

哈希函数:依赖键值的数据类型来构建一个哈希函数;

一个基本的哈希表:(按字符串计算键值)

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不但对字符,对整数类型也是有更好的效果;
    
    

碰撞处理:

  • 开链法:(利用二维数组)

js:数据结构笔记7--哈希表

修改:
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倍及以上,使用线性探测法。

上一篇:Java 集合系列16之 HashSet详细介绍(源码解析)和使用示例


下一篇:django的序列化