简单实现一个 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

hacker0limbo / my-blog

简单实现一个 HashTable #8

简单实现一个 hashtable

参考