JavaScript 哈希表(散列表)应用

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

查找的效率与比较次数密切相关。基于比较的程序，运算效率是比较低的。比如平时可以通过indexOf查找一个数据。但这是一个基于比较的一个实现。如果是淘宝那样有上亿个商品，那么用indeOf 来查数据就会性能非常差。

对一个在哈希表中的数据的访问过程是迅速有效的，通过散列函数，哈希表中的元素的key经常是唯一的，数据元素将被更快地定位。

最近学习了散列表（哈希表），参考这篇文章https://blog.csdn.net/zouchunlaigo1988/article/details/7163920。，换成了JavaScript语言实现。

问题描述

针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度不超过R，完成相应的建表和查表程序。

基本要求

假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个，取平均查找长度的上限为2。哈希函数用除留余数法构造，用伪随机探测再散列发处理冲突。

const Name_NO = 30;
const HASH_LENGTH = 50;
const M = 50;class Name {
constructor() {
this.py = '';
this.key = 0;
}
}class Hash {
constructor() {
//名字的拼音
//拼音对应的整数
//查找的长度
this.py = '';
this.key = 0;
this.si = 0;
}
}
const NameList = [];
for (let i = 0; i < Name_NO; i++) {
let studuent = new Name();
NameList.push(studuent);
}/** 算法设计*/
/**1 姓名结构体数组初始化 */
//名字以拼音形成字符串，将字符串的各个字符对应的ASCII码相加，所得的整数作为哈希表的关键字
const InitNameList = () => {
let f = '';
let r, s0, i;
NameList[0].py = "chenliang";//陈亮
NameList[1].py = "chenyuanhao";//陈元浩
NameList[2].py = "chengwenliang";//程文亮
NameList[3].py = "dinglei";//丁磊
NameList[4].py = "fenghanzao";//冯汉枣
NameList[5].py = "fuzongkai";//付宗楷
NameList[6].py = "hujingbin";//胡劲斌
NameList[7].py = "huangjianwu";//黄建武
NameList[8].py = "lailaifa";//赖来发
NameList[9].py = "lijiahao";//李嘉豪
NameList[10].py = "liangxiaocong";//梁晓聪
NameList[11].py = "linchunhua";//林春华
NameList[12].py = "liujianhui";//刘建辉
NameList[13].py = "luzhijian";//卢志健
NameList[14].py = "luonan";//罗楠
NameList[15].py = "quegaoxiang";//阙高翔
NameList[16].py = "sugan";//苏淦
NameList[17].py = "suzhiqiang";//苏志强
NameList[18].py = "taojiayang";//陶嘉阳
NameList[19].py = "wujiawen";//吴嘉文
NameList[20].py = "xiaozhuomin";//肖卓明
NameList[21].py = "xujinfeng"; //许金峰
NameList[22].py = "yanghaichun";//杨海春
NameList[23].py = "yeweixiong";//叶维雄
NameList[24].py = "zengwei";//曾玮
NameList[25].py = "zhengyongbin";//郑雍斌
NameList[26].py = "zhongminghua";//钟明华
NameList[27].py = "chenliyan";//陈利燕
NameList[28].py = "liuxiaohui";//刘晓慧
NameList[29].py = "panjinmei";//潘金梅 for (let i = 0; i < Name_NO; i++) {
s0 = 0;
f = NameList[i].py;
for (r = 0; r < f.length; r++) {
let str = f.slice(r, r + 1)
let intNum = str.charCodeAt();
s0 = (intNum) + s0;
}
NameList[i].key = s0;
}
}/**2 建立哈希表 */
//用除留余数法建哈希函数，用伪随机探测再散列法处理冲突
const HashList = [];
for (let i = 0; i < HASH_LENGTH; i++) {
let item = new Hash();
HashList.push(item);
}
const CreateHashList = () => {
let i;
for (i = 0; i < HASH_LENGTH; i++) {
HashList[i].py = '';
HashList[i].key = 0;
HashList[i].si = 0; } for (let j = 0; j < Name_NO; j++) {
let sum = 0;
let adr = (NameList[j].key) % M;
let d = adr;
if (HashList[adr].si == 0) {
HashList[adr].key = NameList[j].key;
HashList[adr].py = NameList[j].py;
HashList[adr].si = 1;
} else {
//冲突，车采用伪随机探测再散列法处理冲突
do {
d = (d + NameList[j].key % 10 + 1) % M
sum = sum + 1;
} while (HashList[d].key != 0);
HashList[d].key = NameList[j].key;
HashList[d].py = NameList[j].py;
HashList[d].si=sum+1; }
}
}
//3.查找
const FindList = (name) => {
let s0 = 0, r, sum = 1, adr, d;
for (r = 0; r < name.length; r++) {
let str = name.slice(r, r + 1)
let intNum = str.charCodeAt();
s0 = (intNum) + s0;
}
adr = s0 % M;//使用哈希函数
d = adr;
//strcmp
if (HashList[adr].key === s0 && (HashList[adr].py == name)) {
console.log(`姓名%${HashList[d].py},关键字${s0},查找长度1`)
} else if (HashList[adr].key == 0) {
console.log("无此记录")
} else {
let g = 0;
do {
d = (d + s0 % 10 + 1) % M; //伪随机探测在散列法处理冲突
sum = sum + 1;
if (HashList[d].key === 0) {
console.log("无此记录");
g = 1;
}
if (HashList[d].key === s0) {
console.log(`姓名:${HashList[d].py},关键字:${s0},查找长度:${sum}`)
}
} while (g == 0)
}
}//显示哈希表
const Display = () => {
let i;
let total = 0;
console.log("\n地址\t关键字\t\t搜索长度\tH(key)\t 姓名\n"); //显示的格式
for (i = 0; i < 50; i++) {
console.log(i,HashList[i].key,HashList[i].si,HashList[i].key % 30,HashList[i].py);
}
for (let i = 0; i < HASH_LENGTH; i++) {
total += HashList[i].si;
}
console.log(`平均查找长度：${total/Name_NO}`)
}//运行主函数
const main = () => {
InitNameList();
CreateHashList();
Display();
//查找唯一key值的数据
FindList('zhengyongbin');
//查找key值冲突的数据
FindList('panjinmei');}
main();

输出结果

另外再附上一个es6实现的HashTable类

class HashTable {
//初始化
constructor() {
this.obj = {};
this.count = 0;
}
//返回值
take(key) {
if (this.contains(key)) {
return this.obj[key]
}
}
//增加值
add(key, value) {
if (this.obj.hasOwnProperty(key)) {
return false;
} else {
this.obj[key] = value;
this.count++;
return true;
}
}
//清空
clear() {
this.obj = {}
}
//检测
contains(key) {
return this.obj.hasOwnProperty(key);
}
//移除hashtable中对象的值
remove(key) {
this.count--;
delete this.obj[key];
}
}