js:数据结构笔记7--哈希表
2024-10-07 01:15:18
哈希表(散列表):通过哈希函数将键值映射为一个字典;
哈希函数:依赖键值的数据类型来构建一个哈希函数;
一个基本的哈希表:(按字符串计算键值)
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倍及以上,使用线性探测法。
最新文章
- 凭吊一下ASP.NET 5,然后跨平台,越跨越开心
- ZOJ Problem Set - 1402 Magnificent Meatballs
- PowerDesigner工具箱(palette)如何打开
- makefile_2
- Git 分布式版本管理
- 洛谷 P2024 食物链 POJ 1182 Label:并查集Turbo
- 【转】最实用的IT类网站及工具大集合
- javascript 最常用的技巧整理
- C# 求斐波那契数列的前10个数字 :1 1 2 3 5 8 13 21 34 55
- .net mvc 发布部署到机器上
- HDU1754(线段树)
- Android的Drawable
- java-finalize
- 大爱jQuery,10美女模特有用jQuery/CSS3插入(集成点免费下载)
- 【原创】poj ----- 2376 Cleaning Shifts 解题报告
- 深入理解立即执行函数(function(){})();
- CodeBlocks中我遇到的无法调试问题及解决方案
- sql语句实例练习
- C++——Vector
- 【redis 学习系列】API的理解与使用(二)