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

栏目: JavaScript · 发布时间: 5年前

内容简介:散列后的数据 可以快速插入和取用在散列表上插入、删除和取用数据非常快,但是查找数据却效率低下

散列表(Hashtable)

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

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

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

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

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

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

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

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

碰撞解决方法

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

线性探测法 属于 开放寻址散列 ,查找散列位置如果当前位置没有继续寻找下一个位置。存储数据较大较适合。数组大小>=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个,原因是发生了碰撞

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

解决方法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
}
复制代码

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

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

解决方法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()复制代码

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

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

解决方法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()复制代码

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

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

至此,算是完成了散列表


以上所述就是小编给大家介绍的《js实现数据结构及算法之散列表(Hashtable)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

HotSpot实战

HotSpot实战

陈涛 / 人民邮电出版社 / 2014-3 / 69

《HotSpot实战》深入浅出地讲解了HotSpot虚拟机的工作原理,将隐藏在它内部的本质内容逐一呈现在读者面前,包括OpenJDK与HotSpot项目、编译和调试HotSpot的方法、HotSpot内核结构、Launcher、OOP-Klass对象表示系统、链接、运行时数据区、方法区、常量池和常量池Cache、Perf Data、Crash分析方法、转储分析方法、垃圾收集器的设计演进、CMS和G......一起来看看 《HotSpot实战》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

RGB CMYK 转换工具
RGB CMYK 转换工具

RGB CMYK 互转工具