07.散列表.md

7. 散列

散列算法的作用是尽可能快地在数据结构中找到一个值。在之前的章节中，你已经知道如果 要在数据结构中获得一个值(使用get方法)，需要遍历整个数据结构来找到它。如果使用散列函数，就知道值的具体位置，因此能够快速检索到该值。散列函数的作用是给定一个键值，然后返回值在表中的地址。

• 散列后的数据可以快速插入取用
• 在散列表上插入、删除和取用数据非常快，但是查找数据却效率低下，比如查找一组数据中的最大值和最小值
• JavaScript散列表基于数组设计，理想情况散列函数会将每一个键值映射为唯一的数组索引，数组长度有限制，更现实的策略是将键均匀分布

散列关键概念

• �数组长度是预先设定的，可以随时增加，所有元素根据和该元素对应的键，保存数组特定位置
• 即使使用高效的散列函数，仍然存在两个键值相同的情况，这种现象成为碰撞
• 对数组的长度应该是一个质数，所有的策略都基于碰撞
• 开链法：两个键相同保存位置一样。开辟第二数组，也称第二个数组为链
• 线性探测法属于开放寻址散列，查找散列位置如果当前位置没有继续寻找下一个位置。存储数据较大较适合。数组大小 >= 1.5* 数据（开链法），数组大小 >=2* 数据（线性探测法

// 线性探测法

function HashTable(){
  this.table = new Array(137);
  this.simpleHash = simpleHash;
  this.put = put;
  this.get = get;
  this.showDistro = showDistro;
  this.betterHash = betterHash;
  this.buildChians = buildChians;
}
function buildChians(){
  for(var i=0;i<this.table.length;i++){
    this.table[i] = new Array();
  }
}

//除留余数法
function simpleHash(data){
  var total = 0;
  for(var i=0;i<data.length;i++){
    total+=data.charCodeAt(i);
  }
  return total%this.table.length;
}
function betterHash(data){
  var H = 31;
  var total = 0;
  for(var i=0;i<data.length;i++){
    total += H * total + data.charCodeAt(i);
  }
  if(total<0){
    total += this.table.length-1;
  }
  return total%this.table.length;
}
function put(data){
  var pos = this.simpleHash(data);
  if(this.table[pos] == undefined){
    this.table[pos] = data;
  }else{
    while(this.table[pos]!=undefined){
      pos++;
    }
    this.table[pos] = data;
  }
}
function get(key){
  var hash = this.simpleHash(key);
  console.info(hash);
  for(var i=0;i<this.table.length;i++){
    if(this.table[i] == key){
      return i;
    }
  }
  return undefined;
}
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 remove(data){
  this.table[this.simpleHash[data]] = undefined;
}
var hTable = new HashTable();
hTable.put("china");
hTable.put("japan");
hTable.put("america");
hTable.put("nicha");
console.log(hTable.get('nicha'));
hTable.showDistro();