js--数据结构之散列
2021-05-18 10:28
标签：uil 存储 保存 build math ann 一个 哈希 操作 js--数据结构之散列 标签：uil 存储 保存 build math ann 一个 哈希 操作 原文地址：http://www.cnblogs.com/intelwisd/p/7738180.html散列：实现散列表的数据后可以快速地实现插入或者删除。但是对于实现查找操作则效率非常的低。
散列表的底层是数组实现的，长度是预先设定，可以随时根据需求增加。所有的元素根据和该元素对应的键，保存在特定的位置。使用散列表存储数据时，通过一个散列函数将键值映射为一个数字，数字的范围是0-散列表的长度。
碰撞（collision）:理想状态下散列函数会将每一个键值映射成一个唯一的数组索引。但是健的数量是无限的，数组的长度是有限的，一个更现实的目标是让散列函数尽量将键均匀地映射到数组中。即使使用一个高效的散列函数，仍然存在两个键映射成同一个值的可能。这就是所谓的碰撞。它产生时我们就要去解决。
散列表中的数组究竟设置多大？
常见设置：数组长度是一个质数。 function HashTable() {
this.table = new Array(137);
this.simpleHash = simpleHash;//哈希函数
this.betterHash = betterHash;//霍纳哈希函数
this.buildChains = buildChains;//开连法
this.showDistro = showDistro;//显示散列表中的数据
this.showDistro1 = showDistro1;//开连法显示散列表中的数据
this.put = put;//将数据存储到列表中
//this.newPut = newPut;//将数据存储到列表中
this.get = get;
}
//哈希函数：简单的除留余数法
function simpleHash(data) {
var total = 0;
for(var i = 0;i
");
}
}
}
var hash = new HashTable();
var book = ["JavaScript","jQuery","php","java","go","html5","AI"];
for(var i =0;i ) {
hash.put(book[i]);
}
//hash.showDistro();
console.log(book.length);1: AI
7: java
54: php
56: JavaScript
77: go
79: html5
92: jQuery上述会有问题：
1.数据呈现向两端分布。
2.有时会出现内容显示不全的问题，（散列函数处理时有了相同的散列值，就产生了碰撞）散列函数的设计：解决碰撞
确保散列表用来存储数据的数组其大小是一个质数（数学运算对质数取余数时余数重复率低）。数组的长度应该大于100，让其分布更加的均匀。
霍纳算法：
新的散列函数仍然先用计算字符串的ASCII码值，不过在求和时每次乘以一个质数。建议一个较小的，（31，37）； function betterHash(str) {
var h = 37;
var total = 0;
for(var i = 0;i ) {
total += h*total+str.charCodeAt(i);
}
total = total % this.table.length;
if(total ) {
total += this.table.length - 1;
}
return parseInt(total);
}
var hash2 = new HashTable();
var book2 = ["JavaScript","jQuery","php","java","go","html5","AI"];
for(var i = 0;i ) {
hash2.put(book2[i]);
}
散列化整型键：
上述两个例子都是对于字符串类型的键值进行操作，现在研究整型键的数据操作。
eg:学生的成绩查询，随机生成一个9位数的键（ID），用以识别学生身份和一门成绩。 //生成学生成绩：
function getRandomGrade(min,max) {
return Math.floor(Math.random()*(max-min+1))+min;
}
//生成ID:
function getStuID(arr) {
for(var i = 0;i ) {
var num = "";
for(var j = 0;j ) {
num +=Math.floor(Math.random()*10);
}
num += getRandomGrade(50,100);
arr[i] = num;
}
}
var stuNum = 10;
var students = new Array(stuNum);
getStuID(students);
for(var i = 0;i ) {
//console.log(students[i]);
console.log(students[i].substring(0,8)+" "+students[i].substring(9));
}
var hTab = new HashTable();
for(var i = 0;i ) {
hTab.put(students[i]);
}
hTab.showDistro();
//如果同样用第一种哈希函数解决会产生碰撞，用较好的哈希函数则不会产生碰撞。
//散列表的排序，取值：
// 要重新定义put(),get();
//带有键值的添加方法
function newPut(key,data) {
var _pos = this.betterHash(key);
this.table[_pos] = data;
}
//获取方法：
function get(key) {
return this.table[this.betterHash(key)];
}
//test: 输入三个人的姓名和电话号码进行查询，三个输入后输出quit进行查询
var numbers = new HashTable();
var name,number;
for(var i = 0;i ) {
//name = prompt("请输入姓名:");
//number = prompt("请输入电话:");
numbers.newPut(name,number);
}
name = "";
prompt("输入quit结束:");
while(name != "quit") {
name = prompt("里面的成员:");
if(name == "quit") {
break;
}
alert(name+"成员的电话是：" + numbers.get(name));
prompt("输入quit结束:");
}
碰撞处理：开链法和线性检测
开链法：将键同样存储到通过散列函数计算的索引位置上，但不可能将多份数据存储到一个数组单元中。在实现散列表的底层数组中的每一个元素又是一个新的数据结构，即使使用两个键三列后的值相同，依然被保存在同样的位置，但是他们在第二个数组的位置不一样。
实现方法：在创建存储散列的键值的数组时通过调用一个函数创建一个空数组，然后将该数组赋值给散列表中的每个数组。这样就创建了一个二维数组。 function buildChains() {
for(var i = 0;i this.table.length;i++) {
this.table[i] = new Array();
}
}
//相应的显示元素也要改变
function showDistro1() {
//var num = 0;
for(var i = 0;i this.table.length;i++) {
if(this.table[i][0] != undefined) {
console.log(i + ":" +this.table[i]);
}
}
}
//put
function put(key,data) {
var pos = this.simpleHash(key);
var index = 0;
if(this.table[pos][index] == undefined) {
this.table[pos][index] = data;
}else {
while(this.table[pos][index] != undefined) {
++index;
}
this.table[pos][index] = data;
}
}
//get
function get(key) {
var index = 0;
var pos = this.simpleHash(key);
if(this.table[pos][index] == key) {
return this.table[pos][index];
}else {
while(this.table[pos][index] != key) {
++index;
}
return this.table[pos][index];
}
return undefined;
}
//test:
var hTable = new HashTable();
hTable.buildChains();
var arrName = ["David","Jennifer","Donnie","Raymond","Cynthia","Mike","Clayton","Danny","Jonathan"];
for(var i = 0;i ) {
hTable.put(arrName[i]);
}
hTable.showDistro1();