简单实现一个 HashTable

[hacker0limbo]

简单实现一个 hashtable

这个玩意有无数个别名: map/dict/object/hashTable

需求:

• 具有读写功能, 可以使用setItem(key, value)写入键值对(key-value), 当写入的是相同的键但不同的值时, 为更新, 当重复写入同样的键值对, 不做任何操作(即不会存在重复将一个键值对存两遍, 也不会存在同一个键对应多个不同的值)
• 具有读功能, 可以使用getItem(key)根据键名得到值, 当读取不存在的键名是, 抛出null

思路:
首先需要一个数组来存取所有的 key-value, 取名table

然后最简单的, 写一个函数hashStringToInt(s), 该函数接受字符串为参数, 返回的是经过hash过的数字. 对应到实现 hashTable, 将 key 传入到该函数, 得到的结果即为对应table的索引, 然后在对应索引下存入 value, 如下

// 三个 key-value 以及对应的 hash 值
key    hash    value
name   0       'a' 
age    2       '18'
height 3       169

// table 最后为
['a', undefined, '18', 169, ...]

但是这样做存在两个问题:

• 第一个问题, 初始化table的时候, 一般会固定一个值, 假设为100(有效的索引最多到 99), hashStringToInt(key)很有可能是超过 99 的. 这个时候可以对最后的结果取table.length的模, 即这样无论如何最后 hash 出来的结果都不会超过table.length(这里是 99)
• 第二个问题, 很有可能出现冲突(collide), 理想情况下所有的 key 根据 hash 后的结果均匀分布到各个 index 上, 实际情况可能会出现多个 key 同一个 value, 这时候需要改变存取方法

方法为, 将出现冲突的 index 的位置的元素, 改成一个数组, 该数组存取所有 hash 结果和该索引一样的 key-value, 形式也为一个数组, 如下

// 三个 key-value 以及对应的 hash 值
// 其中 name 和 gae hash 冲突, 均为 0
key    hash    value
name   0       'a' 
age    0       '18'
height 3       169

// table 最后为
[[['name', 'a'], ['age', '18']], undefined, undefined, [[['height', 169]]]]

到这里基本上没有什么问题了, 但是性能还是要考虑一下, 运气不好你甚至可能出现你想存的所有 key-value 对所对应的 hash 都是同一个...那么该 index 下就会存在 n(n 可以是 9999999...) 个 key-value 组合, 然后最坏情况就是你遍历 n 次, 然后找到了最后一个才是你想要的

所以比较好的情况还是能够比较均匀的将 key-value 分布到各个 index, 每个 index 下可能只存 1-3 个 key, value, 那么查找的时候最坏也就查 3 次找到, 相比 9999999 实在好很多

要实现这一功能, 其实很简单, 增加一个loadFactor系数, 为存取的 key-value 数量 / table length, 这里可以设定当loadFactor大于 0.8 的时候, 增加table的容量, 将容量扩大到下一个质数

同时最后还要注意一个问题, 当对同一个 key 进行写入的时候, 如果是不同的 value, 则更新 value, 如果还是同一个 value, 不做任何操作, 因此需要做一些判断

完整代码如下:

class HashTable {
  constructor() {
    this.table = new Array(3)
    this.numItems = 0
  }
  
  hashStringToInt(s, tableSize) {
    let hash = 17
    for (let i = 0; i < s.length; i++) {
      hash = (13 * hash * s.charCodeAt(i)) % tableSize
    }
    return hash
  }
  
  resize() {
    // 使用 Mersenne prime 得到下一个 prime, 肮脏实现
    const newTable = new Array(2 ** this.table.length - 1)
    // rehash all
    for (const e of this.table) {
      if (e) {
        // 存在该 index 下的元素是 undefined 的可能性...
        for (const [key, value] of e) {
          const index = this.hashStringToInt(key, newTable.length);
          if (newTable[index]) {
            newTable[index].push([key, value]);
          } else {
            newTable[index] = [[key, value]];
          }
        }
      }
    }
    this.table = newTable
  }

  getItem(key) {
    const index = this.hashStringToInt(key, this.table.length)
    if (!this.table[index]) {
      return null
    }
    return this.table[index].find(e => e[0] === key)[1]
  }

  setItem(key, value) {
    const loadFactor = this.numItems / this.table.length
    if (loadFactor > 0.8) {
      // resize
      this.resize()
    }
    const index = this.hashStringToInt(key, this.table.length)
    if (this.table[index]) {
      // 判断是否在设置同一个 key
      const item = this.table[index].find(e => e[0] === key)
      if (item) {
        // 相同即更新
        item[1] = value
      } else {
        // 否则添加新元素
        this.numItems++
        this.table[index].push([key, value])
      }
    } else {
      this.numItems++
      this.table[index] = [[key, value]]
    }
  }
}

const hashTable = new HashTable()
hashTable.setItem('A', 'a')
hashTable.setItem('B', 'b')
hashTable.setItem('A', 'a1')
hashTable.setItem('C', 'c')
hashTable.setItem('D', 'd')
console.log(hashTable.numItems) // 4
console.log(hashTable.table.length) // 7
console.log(hashTable.getItem('A')) // a1
console.log(hashTable.getItem('B')) // b
console.log(hashTable.getItem('C')) // c
console.log(hashTable.getItem('D')) // d

参考

• https://gist.github.com/benawad/7a71da878100eec3b0958fbd0882576c
• https://gist.github.com/alexhawkins/f6329420f40e5cafa0a4