散列表也被称为哈希表, 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 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
- }
- // 更改 put
- 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() 复制代码
可以看到所有元素都被显示出来了
至此, 算是完成了散列表
来源: https://juejin.im/post/5b8915a96fb9a019df7f7b58