前言：

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

如果还不清楚散列表，请先阅读上一篇文章：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 可以直接中止当前函数

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！