JavaScript 实现哈希表（HashTable）

哈希表是根据键可以访问到值的一种数据结构

在JavaScript中, 原生的 Object 就是哈希表的一种

这里用JavaScript实现一个哈希表, 完成存储和取值的两个方法

其中, 会用一个数组来存储哈希表的数据

最基本的功能

一. 数据存储在哪里?

哈希表需要一个数组, 用来存储所有的数据, 并且, 这个数组的长度应该是一个质数, 我们这里暂时取为137

二. 如何存储

当给一个哈希表提供一个 key 和 value 时, 有一个函数对这个key做一次运算, 根据他生成一个 0 - 137 的数字(这个过程就叫做哈希 hash),以这个数字为下标, 将数组的对应位置设置成 value

三. 如何取值

当给哈希表一个key, 希望取出对应的value时, 可以对这个key用第二步一样的哈希方法, 算出一个位置, 取出数组上对应位置的 value

知道了这些, 代码就比较好写了

class HashTable {
  constructor() {
    this.table = new Array(137)
  }
  hash(string) {
    // 采用霍纳算法, 使得到的结果更分散
    const H = 37
    let total = 0
    for (let i = 0; i < string.length; i++) {
      total += H * total + string.charCodeAt(i)
    }
    total = total % this.table.length
    return parseInt(total)
  }
  put(key, data) {
    const index = this.hash(key)
    this.table[index] = data
  }
  get(key) {
    return this.table[this.hash(key)]
  }
}

但是, 对不同的字符串进行哈希运算, 可能会得到一样的结果, 比如, 字符串 "aa_" 和 "_X" 哈希的结果都是 136
那么, 在设置或取值的时候, 就有可能会发生重复, 这个问题就是 哈希冲突

如何应对哈希冲突

开链法

开链法的过程

1. 不变的是, 仍然要对 key 进行哈希运算, 找到这个位置
2. 之前的这个位置应该存储的直接是 value, 开链法会在这个位置新建一个数组, 将 key 和 value 依次放到这个数组上(如果数组上的第一项已经有值了, 那么一直向后找, 直到没有值为止)
3. 取值的时候, 需要先对key进行哈希, 然后找到这个位置上的数组, 再找到相同的key的位置, 下一个位置就是value了
   代码如下

class HashTable {
  constructor() {
    this.table = new Array(137)
    this.buildChains()
  }
  hash(string) {
    const H = 37
    let total = 0
    for (let i = 0; i < string.length; i++) {
      total += H * total + string.charCodeAt(i)
    }
    total = total % this.table.length
    return parseInt(total)
  }
  put(key, data) {
    const position = this.hash(key)
    let index = 0
    if (this.table[position][index] == undefined) {
      this.table[position][index] = key
      this.table[position][index + 1] = data
      return
    }
    if (this.table[position][index] == 'key') {
      this.table[position][index + 1] = data
      return
    }
    while (this.table[position][index] != undefined) {
      if (this.table[position][index] == key) {
        break
      }
      index += 1
    }
    this.table[position][index] = key
    this.table[position][index + 1] = data
  }
  buildChains() {
    for (var i = 0; i < this.table.length; i++) {
      this.table[i] = new Array()
    }
  }
  get(key) {
    var index = 0
    var position = this.hash(key)
    if (this.table[position][index] == key) {
      return this.table[position][index + 1]
    } else {
      while (this.table[position][index] && this.table[position][index] != key) {
        index += 2
      }
      return this.table[position][index + 1]
    }
  }
}

线性探测法

线性探测法的过程

1. 内部有两个数组, 一个专门放key(这里简称为数组A), 另一个数组专门放value(这里简称为数组B)
2. 存储时, 对key进行哈希, 如果数组A上的这个位置为空, 那么就把key放在这里, 把value放在数组B的相同位置; 如果不为空, 就去看看下一项, 直至找到为空的, 然后把key和value分别放进数组A和数组B
3. 取值时, 对 key 进行哈希, 找到数组A上对应的位置, 如果key相等, 就取数组B上的这一项为value; 如果不相等, 则看下一位的key是否相等, 直至找到为止

class HashTable {
  constructor() {
    this.table = new Array(137)
    this.values = []
  }
  hash(string) {
    const H = 37
    let total = 0
    for (let i = 0; i < string.length; i++) {
      total += H * total + string.charCodeAt(i)
    }
    total = total % this.table.length
    return parseInt(total)
  }
  put(key, data) {
    var position = this.hash(key)
    if (this.table[position] == undefined) {
      this.table[position] = key
      this.values[position] = data
    } else {
      while (this.table[position] != undefined) {
        if (this.table[position] == key) {
          this.values[position] = data
          return
        }
        // 防止超过数组的最后一位
        if (position >= this.table.length - 1) {
          position = 0
          continue
        } else {
          position++
        }
      }
      this.table[position] = key
      this.values[position] = data
    }
  }
  get(key) {
    let hash = this.hash(key)
    for (let i = 0; i < this.table.length; i ++) {
      if (i == hash) {
        if (key == this.table[hash]) {
          return this.values[hash]
        } else {
          // 防止超过数组的最后一位
          if (hash == this.table.length - 1) {
            hash = 0
          } else {
            hash += 1
          }
          if (key == this.table[hash]) {
            return this.values[hash]
          }
        }
      }
    }
  }
}