亲宝软件园·资讯

展开

 JavaScript 散列表

杨成功  人气:0

前言:

上一篇我们介绍了什么是散列表,并且用通俗的语言解析了散列表的存储结构,最后动手实现了一个散列表,相信大家对散列表已经不陌生了。

如果还不清楚散列表,请先阅读上一篇文章:JavaScript 数据结构之散列表的创建(1)

上篇末尾我们遗留了一个问题,就是将字符串转化为散列值后可能出现重复。当以散列值(hash 值)为 key 存储数据时,就会有覆盖已有数据的风险。本篇我们看如何处理散列值冲突的问题,并实现更完美的散列表。

一、处理散列值冲突

有时候一些键会有相同的散列值。比如 aab 和 baa,从字符串的角度来说它们是不同的值,但是按照我们的散列函数逻辑,将每个字母的 Unicode 码累加得出的散列值,一定是一样的。

我们知道在 JavaScript 对象当中,如果赋值时指定的 key 已存在,那么就会覆盖原有的值,

比如这个例子:

var json = { 18: '雷欧' }
json[18] = '欧布'
console.log(json) // { 18: '欧布' }

为了避免上述代码中出现的风险,我们需要想办法处理,如何使 key != key,则 hash != hash

目前可靠的方法有两个,分别是:分离链接 和 线性探查

1.分离链接

分离链接法是指在散列表存储数据时,value 部分用 链表 来代替之前的 键值对。键值对只能存储一个,而链表可以存储多个键值对。如果遇到相同的散列值,则在已有的链表中添加一个键值对即可。

我们需要重写三个方法:put、get 和 remove。我们看如何实现:

class HashTableSeparateChaining {
  constructor() {
    this.table = {}
  }
}

2.put 方法

首先还是基本的类结构,然后看 put 方法:

put(key, value) {
  if(key !== null && value !== null) {
    let pos = this.hashCode(key)
    if(!this.table[pos]) {
      this.table[pos] = new LinkedList()
    }
    this.table[pos].push(new ValuePair(key, value))
    return true;
  }
  return false;
}

LinkedList 类是标准的链表类,在链表篇讲过如何实现,这里直接使用

对比上篇的散列表 put 方法,你会发现差别不大,变化的部分如下:

// 变化前
this.table[pos] = new ValuePair(key, value)
// 变化后
if(!this.table[pos]) {
  this.table[pos] = new LinkedList()
}
this.table[pos].push(new ValuePair(key, value))

优化后的逻辑是,在存储数据时,将键值对存在一个链表里。如果有相同的 hash 值,则向已有的链表中添加一个键值对,这样就避免了覆盖。

不过这种方式也有弊端,每添加一个键值对就要创建一个链表,会增加额外的内存空间。

3.get 方法

get 方法:

get(key) { 
  let linkedList = this.table[this.hashCode(key)]
  if(linkedList && !linkedList.isEmpty()) {
    let current = linkedList.getItemAt(0);
    while(current) {
      if(current.value.key == key) {
        return current.value.value
      }
      current = current.next
    }
  }
  return undefined; 
}

新的 get 方法明显比之前的复杂了许多。主要逻辑是根据 key 找到一个链表,然后再遍历链表找到与参数 key 相匹配的键值对,最后返回找到的值。

while 循环中使用 return 可以直接中止当前函数

加载全部内容

相关教程
猜你喜欢
用户评论