数据结构与算法 javascript描述-散列表(下)

372 阅读6分钟

线性探测法

上篇讲了通过分离链接法来解决散列表冲突问题。今天我们学习一个新的方法来解决该问题。

核心思想是,如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入。那如何重新探测新的位置呢?

当我们往散列表中插入数据时,如果某个数据经过散列函数散列之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止。

黄色的色块表示空闲位置,橙色的色块表示已经存储了数据。

从图中可以看出,散列表的大小为 10,在元素 x 插入散列表之前,已经 6 个元素插入到散列表中。x 经过 Hash 算法之后,被散列到位置下标为 7 的位置,但是这个位置已经有数据了,所以就产生了冲突。于是我们就顺序地往后一个一个找,看有没有空闲的位置,遍历到尾部都没有找到空闲的位置,于是我们再从表头开始找,直到找到空闲位置 2,于是将其插入到这个位置。

在散列表中查找元素的过程有点儿类似插入过程。我们通过散列函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素。如果相等,则说明就是我们要找的元素;否则就顺序往后依次查找。如果遍历到数组中的空闲位置,还没有找到,就说明要查找的元素并没有在散列表中。

代码实现


/**
 * @description 在字典中我们是用键值对来存储数据
 */

const assert = require("assert");

// 散列函数
const loseloseHashCode = (key = "") => {
  let hashCode = 0;
  for (let i = 0; i < key.length; i++) {
    hashCode += key.charCodeAt(i);
  }
  return hashCode % 37;
};

class patchValue {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
}

class HashTableLine {
  constructor() {
    this.table = [];
  }

  put(key, value) {
    const position = loseloseHashCode(key);
    if (this.table[position] !== undefined) {
      let curIndex = position + 1
      while (this.table[curIndex] !== undefined) {
        curIndex++
      }
      this.table[curIndex] = new patchValue(key, value)
    } else {
      this.table[position] = new patchValue(key, value)
    }
  }

  remove(key) {
    const position = loseloseHashCode(key);
    if (this.table[position] && this.table[position].key === key) {
      this.table[position] = undefined;
      return true;
    }
    let curIndex = position + 1;
    while (this.table[curIndex].key !== key) {
      curIndex++;
    }
    this.table[curIndex] = undefined
    return true;
  }

  get(key) {
    const position = loseloseHashCode(key);
    if (this.table[position] && this.table[position].key === key) {
      return this.table[position].value;
    }
    let curIndex = position + 1
    while (this.table[curIndex].key !== key) {
      curIndex++
    }
    return this.table[curIndex].value
  }

  getItems() {
    return this.table;
  }
}

// test case

const hashTable = new HashTableLine();
hashTable.put("Donnie", "Donnie@qq.com");
hashTable.put("Ana", "Ana@qq.com");
console.log(hashTable.getItems());
hashTable.remove("Donnie");
hashTable.remove("Ana");
console.log(hashTable.getItems());
hashTable.put("Donnie", "Donnie@qq.com");
console.log(hashTable.getItems());

线性探测法 VS 分离链接法

首先不管采用哪种探测方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率,一般情况下,我们会尽可能保证散列表中有一定比例的空闲槽位。我们用装载因子(load factor)来表示空位的多少。


散列表的装载因子=填入表中的元素个数/散列表的长度

装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。 散列函数设计的好坏决定了散列冲突的概率,也就决定散列表的性能。

散列表的查询效率并不能笼统地说成是 O(1)。它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好,或者装载因子过高,都可能导致散列冲突发生的概率升高,查询效率下降。

如何选择冲突解决方法?

线性探测法

线性探测法不像链表法,需要拉很多链表。散列表中的数据都存储在数组中,可以有效地利用 CPU 缓存加快查询速度。而且,这种方法实现的散列表,序列化起来比较简单。链表法包含指针,序列化起来就没那么容易。你可不要小看序列化,很多场合都会用到的。

用线性探测法解决冲突的散列表,删除数据的时候比较麻烦,需要特殊标记已经删除掉的数据。而且,在线性探测法中,所有的数据都存储在一个数组中,比起链表法来说,冲突的代价更高。所以,使用线性探测法解决冲突的散列表,装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。

当数据量比较小、装载因子小的时候,适合采用线性探测法。

分离链接法

链表法比起线性探测法,对大装载因子的容忍度更高。线性探测法只能适用装载因子小于 1 的情况。接近 1 时,就可能会有大量的散列冲突,导致大量的探测、再散列等,性能会下降很多。但是对于链表法来说,只要散列函数的值随机均匀,即便装载因子变成 10,也就是链表的长度变长了而已,虽然查找效率有所下降,但是比起顺序查找还是快很多。

链表因为要存储指针,所以对于比较小的对象的存储,是比较消耗内存的,还有可能会让内存的消耗翻倍。而且,因为链表中的结点是零散分布在内存中的,不是连续的,所以对 CPU 缓存是不友好的,这方面对于执行效率也有一定的影响。当然,如果我们存储的是大对象,也就是说要存储的对象的大小远远大于一个指针的大小(4 个字节或者 8 个字节),那链表中指针的内存消耗在大对象面前就可以忽略了。

实际上,我们对链表法稍加改造,可以实现一个更加高效的散列表。那就是,我们将链表法中的链表改造为其他高效的动态数据结构,比如跳表、红黑树。这样,即便出现散列冲突,极端情况下,所有的数据都散列到同一个桶内,那最终退化成的散列表的查找时间也只不过是 O(logn)。这样也就有效避免了前面讲到的散列碰撞攻击。

基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表,而且,比起线性探测法,它更加灵活,支持更多的优化策略,比如用红黑树代替链表。

如何设计一个散列函数

  • 散列函数的设计不能太复杂

过于复杂的散列函数,势必会消耗很多计算时间,也就间接的影响到散列表的性能。

  • 散列函数生成的值要尽可能随机并且均匀分布

详细的介绍后续可以单独学习。

参考资料

数据结构与算法之美

感兴趣的可以关注下公众号