js实现数据结构及算法之散列表(Hashtable)

散列表(Hashtable)

散列表 也被称为 哈希表 ，Hash表是一种特殊的数据结构。

散列后的数据 可以快速插入和取用

在散列表上插入、删除和取用数据非常快，但是查找数据却效率低下

js散列表基于 数组 设计，理想情况散列函数会将每一个键值映射为唯一的数组索引，数组长度有限制，更现实的策略是将键均匀分布

数组长度是预先设定的，可以随时增加，所有元素根据和该元素对应的 键 ，保存数组特定的位置

即使使用高效的散列函数，依然存在两个键值相同的情况，这种现象称为 碰撞（collision）

数组的长度应该是一个质数，所有的策略都基于碰撞

碰撞解决方法

开链法 ：两个键相同保存位置一样，开辟第二数组，也称第二个数组为链，适合空间小，数据量大

线性探测法 属于 开放寻址散列 ，查找散列位置如果当前位置没有继续寻找下一个位置。存储数据较大较适合。数组大小>=1.5*数据（开链法），数组大小>=2*数据（线性探测法）

js实现

/**
  * 一个简单的散列表
  * @constructor
  */
 function HashTable() {
this.table = new Array(137);    // 定义数组长度
this.simpleHash = simpleHash;         // 简单的散列函数
this.betterHash = betterHash;         // 简单的散列函数
this.showDistro = showDistro;         // 显示元素
this.put = put;       // 插入元素
this.openPut = openPut;       // 开链法插入元素
this.linkPut = linkPut;       // 线性探测法插入元素
this.get = get;     // 获取元素
this.bulidTable = bulidTable //添加二维数组
}//简单的散列函数 除留余数法
 function simpleHash(data) {
   var total = 0
   for(var i = 0; i < data.length; i++){
     total += data.charCodeAt(i)
   }
   console.log(data + '->total' + total)
   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)
   }
   // console.log(data + '->total' + total)
   return total % this.table.length
 }
 //显示元素
 function showDistro() {
   for(var i = 0; i < this.table.length; i++) {
     if(this.table[i]  !== undefined) {
       console.log('键值是->' + i + '值是' + this.table[i])
     }
   }
 }
 //插入元素
 function put(data) {
  var pos = this.simpleHash(data)
   this.table[pos] = data
 }

 //获取元素
 function get(data) {
   return this.table[this.simpleHash(data)]
 }

 var ht = new HashTable()
 ht.put('abc')
 ht.put('china')
 ht.put('bbb')
 ht.put('ss')
 ht.put('nicah')
 ht.put('cba')
 ht.showDistro()复制代码

可以看到我们插入6个值，最后只显示3个，原因是发生了碰撞

解决方法1：改造hash函数

//改造后的散列函数
function betterHash(data) {
  var h = 31
  var total = 0
  for(var i = 0; i < data.length; i++){
    total += h*total + data.charCodeAt(i)
  }
  // console.log(data + '->total' + total)
  return total % this.table.length
}
function put(data) {
 var pos = this.betterHash(data) //使用betterHash
  this.table[pos] = data
}
复制代码

可以看到其他元素可以显示出来了，但是添加相同元素的时候，不显示

解决方法2：开链法

//添加二维数组
function bulidTable() {
  for(var i = 0; i<this.table.length; i++){
    this.table[i] = new Array()
  }
}//开链法插入元素
function openPut(data) {
  var pos = this.simpleHash(data)
  var index = 0
  if(this.table[pos][index] === undefined) {
    this.table[pos][index] = data
    index ++
  }else {
    while(this.table[pos][index] !== undefined) {
       ++index
    }
    this.table[pos][index] = data
  }
}
//显示元素更改
function showDistro() {
  for(var i = 0; i < this.table.length; i++) {
    if(this.table[i][0] !== undefined) {
      console.log('键值是->' + i + '值是' + this.table[i])
    }
  }
}
//插入元素更改为simpleHash
function put(data) {
 var pos = this.simpleHash(data)
  this.table[pos] = data
}var ht = new HashTable()
ht.bulidTable()
ht.openPut('abc')
ht.openPut('china')
ht.openPut('bbb')
ht.openPut('ss')
ht.openPut('nicah')
ht.openPut('cba')
ht.openPut('cba')
ht.showDistro()复制代码

可以看到所有元素都被显示出来了

解决方法3：线性探测法

//线性探测法
function linkPut(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 showDistro() {
  for(var i = 0; i < this.table.length; i++) {
    if(this.table[i]  !== undefined) {
      console.log('键值是->' + i + '值是' + this.table[i])
    }
  }
}
var ht = new HashTable()
// ht.bulidTable()
ht.linkPut('abc')
ht.linkPut('china')
ht.linkPut('bbb')
ht.linkPut('ss')
ht.linkPut('nicah')
ht.linkPut('cba')
ht.linkPut('cba')
ht.showDistro()复制代码

可以看到所有元素都被显示出来了

至此，算是完成了散列表