散列：实现散列表的数据后可以快速地实现插入或者删除。但是对于实现查找操作则效率非常的低。
散列表的底层是数组实现的，长度是预先设定，可以随时根据需求增加。所有的元素根据和该元素对应的键，保存在特定的位置。使用散列表存储数据时，通过一个散列函数将键值映射为一个数字，数字的范围是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<data.length;i++) { ???????????????????total += data.charCodeAt(i);//方法可返回指定位置的字符的Unicode 编码。这个返回值是0-65535之间的整数。相加得到散列值。 ???????????????} ???????????????//console.log(total+"======"); ???????????????return total%this.table.length;//除留余数法返回一个数值 ???????????} ???????????function put(data) { ???????????????var _pos = this.simpleHash(data);//的到数组的索引 ???????????????//var _pos = this.betterHash(data);//的到数组的索引 ???????????????this.table[_pos] = data;//根据返回的值作为键值存储数据。 ???????????} ???????????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]); ???????????????????????//document.write(i+": "+this.table[i]+"<br>"); ???????????????????} ???????????????} ???????????} ???????????var hash = new HashTable(); ???????????var book = ["JavaScript","jQuery","php","java","go","html5","AI"]; ???????????for(var i =0;i < book.length;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 < str.length;i++) { ???????????????????total += h*total+str.charCodeAt(i); ???????????????} ???????????????total = total % this.table.length; ???????????????if(total < 0) { ???????????????????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 < book2.length;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 < arr.length;i++) { ???????????????????var num = ""; ???????????????????for(var j = 0;j < 9;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 < students.length;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 < students.length;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 < 3;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 < arrName.length;i++) { ???????????????hTable.put(arrName[i]); ???????????} ???????????hTable.showDistro1(); ???js--数据结构之散列
原文地址：http://www.cnblogs.com/intelwisd/p/7738180.html