数据结构与算法-散列表

散列算法的作用是尽可能快地在数据结构中找到一个值。在之前的章节中,你已经知道如果 要在数据结构中获得一个值(使用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();  

作者:@lsxlsxxslxsl