源码
前往Github获取本文源码。
介绍
散列表（或哈希表，HashMap）是一种最优时间复杂度可以达到O(1)的数据结构，其原理是根据指定键的hash值来确定它在表中的大致位置，之后再去寻找。在介绍这个数据结构如何实现之前，先让我们看看散列函数的相关知识。
散列函数
所谓散列函数，只要知道以下这两个性质即可：
- 同一个数值进行散列，得到的结果必然相同；
- 当散列结果相同时，不一定是同一个数值。
借助散列函数，我们可以很方便地判断这两个数值是否不同，但却无法判断它们是否相同，会发生散列冲突。所以这就是为什么哈希表只是在理想状态下可以达到O(1)。
散列表
这个数据结构的核心就是如何解决散列冲突。有两种最简单的方法，它们是分离链接法和开放地址法，下面来介绍这两种方式。
我们假设一个整数的散列值是它本身，由于表中没有那么多空，所以要把这个值与表长取模，即value % tableSize。
- 分离链接法：把发生冲突的值放到同一个坑的后面，用链表连接起来，如下：
Java的经典HashMap当数据量小时就用的这个方法。
- 开放地址法：把发生冲突的值放在表的下一个坑里，如果下一个坑也有元素那就再继续找，如下：
Python内部实现哈希表好像就用的这个方法，我就不亲自去扒源码看了。
但是，当表里的数据过多时，分离链接法的效率会变低，开放地址法会无法探测到下一个新的位置。那么此时就需要重新调整表的大小，即rehash再散列。
除此之外，我们这里演示的表长都是5，设想一下，如果传入的数据都是10、15、25这样的，那么这个表的效率就会变低。一个解决方式是，让表长为素数，就可以使得分布较为均匀了。
实现
这里以开放地址法为例，实现一个以字符串为key的散列表。
素数
由于表长需要是一个素数，这里就也需要写出相关代码：判断是否为素数的isPrime，和获取指定值的下一个素数nextPrime：
function isPrime(n) {
// 不考虑负数和 0, 1
if (n <= 1) {
return false
}
// 大于 2 的偶数都不是素数
if (n > 2 && n % 2 === 0) {
return false
}
// 从 3 遍历到 n 的平方根, 因为如果它有大于 sqrt(n) 的因数
// 那么必然另一个因数小于 sqrt(n)。
const max = Math.floor(Math.sqrt(n))
for (let i = 3; i <= max; i = 2) {
if (n % i === 0) {
return false
}
}
return true
}
function nextPrime(n) {
while (!isPrime(n)) {
n
}
return n
}
const primes = [
2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47,
53, 59, 61, 67, 71, 73, 79,
83, 89, 97,
]
for (let i = 1; i < 100; i ) {
console.assert(isPrime(i) === primes.includes(i), i)
}我们在代码下方就用100以内的素数，验证了isPrime的准确性。
散列表
总览如下，不包括私有函数：
代码语言：javascript复制class HashMap {
elements = []
constructor() {}
set(key, val) {}
delete(key) {}
get(key) {}
get length() {}
}接下来我们逐个来看。
构造函数
代码如下：
代码语言：javascript复制constructor() {
this._createElements(4)
}
_createElements(length) {
length = nextPrime(length)
this.elements = Array.from({ length }, () => ({ empty: true }))
}我们通过Array.from生成了一个数组，这里只需要知道这样写是深拷贝，关于这个函数的详细用法请前往MDN。
此外，我们用empty属性判断是否有元素。如果直接把元素赋值为undefined的话，就会出现下图的情况：
那么在查找41的时候，当找到原来的21的位置时，因为这个值现在是undefined，它到底是该继续向下找，还是该停止？就无从得知了。所以，我们需要用empty这个属性判断是否有元素，详细的方法会在下文描述。
散列函数
贴上代码：
代码语言：javascript复制_hash(key) {
let val = 0
// 这是从书里抄过来的计算方式，它能保证这个值分布较为均匀。
for (let i = 0; i < key.length; i ) {
val = 37 * val key.charCodeAt(i)
}
// 对表长取模，方便在表里查找。
val %= this.elements.length
// 防止值为负数
if (val < 0) {
val = this.elements.length
}
return val
}再散列
这还是一个内部的私有函数，但也比较重要，没了它就没法说插入的逻辑。代码如下：
代码语言：javascript复制_rehash() {
// 找出所有非空的元素。
const old = this.elements.filter(el => !el.empty)
// 重置 this.elements，让它的大小至少是两倍。
// 由于表长使用给定数字的下一个素数，所以实际上比两倍要多。
this._createElements(this.elements.length * 2)
// 把所有非空的再添加到这个表中，是用的 set 方法，下文要说。
old.forEach(el => this.set(el.key, el.val))
}好了，现在可以说插入方法了。
插入
其核心为寻找下一个空位，如果没有了， 那就执行一次再散列，之后插入：
代码语言：javascript复制_findIndexToInsert(key) {
let index = this._hash(key)
while (index < this.elements.length) {
const el = this.elements[index]
if (el.empty || el.key === key) {
return index
}
index
}
return -1
}
set(key, val) {
const index = this._findIndexToInsert(key)
// 没找到位置
if (index === -1) {
this._rehash()
// 在重置之后的表中再次执行插入，如果还是失败，
// 还会再进行一次再散列操作，直到插入成功。
this.set(key, val)
return
}
// 设置当前值，并且把 empty 置为 false
this.elements[index] = { empty: false, key, val }
}上文提到过empty这个属性了，这里不再描述。
删除
不同于插入时探测方法，我们如果要删除就不能继续用了，用下图说明原因：
因为上图中的21被标记成删除，那我们如果还是用_findIndexToInsert方法查找41，它会立即返回一个1，就是已经被删除的21的位置。
那我们可以考虑用key存在与否判断当前的坑是否有元素，如下：
_findIndexForKey(key) {
let index = this._hash(key)
while (index < this.elements.length) {
const el = this.elements[index]
// 如果 key 没有被设置过，说明查找到这里就该停止了。
// 开放地址法对于几个相同 hash 值的元素来说，它们应该是挨在一起的，
// 表现为连着几个元素的 key 都被设置过。
if (el.key === undefined) {
return -1
}
// 找到指定的元素的位置了
if (el.key === key) {
// 如果它是空的，就说明它已经被删除掉了。
// 这里返回 -1 表示没找到。
if (el.empty) {
return -1
}
// 如果它不是空的，那就说明找到了。
return index
}
index
}
// 遍历完整个数组，就返回 -1 表示没找到
return -1
}那么我们的删除操作就简单了，找到位置后标记empty为true即可：
delete(key) {
const index = this._findIndexForKey(key)
if (index === -1) {
return false
}
this.elements[index].empty = true
return true
}查找
和删除的逻辑基本相通：
代码语言：javascript复制get(key) {
const index = this._findIndexForKey(key)
if (index === -1) {
return undefined
}
return this.elements[index].val
}获取长度
用一下Array的reduce方法：
get length() {
return this.elements.reduce((n, el) => {
return n !el.empty
}, 0)
}测试
已经实现了一个基本的散列表！但是，为了写测试用例，我们还得下点功夫。首先是生成随机字符串的函数：
代码语言：javascript复制function randStr() {
return Math.random().toString(36).slice(-8)
}然后我们用它生成指定长度的一组key，用来插入到我们的表中：
function generateKeys(n) {
const result = new Set()
while (result.size < n) {
result.add(randStr())
}
return Array.from(result)
}这里用Set去重，之后把它转换成了Array。
之后再借助原有的映射类型辅助我们进行验证：
代码语言：javascript复制const totalKeys = generateKeys(200)
const removeKeys = totalKeys.slice(0, 100)
const remainKeys = totalKeys.slice(100, 201)
const jsMap = new Map()
const map = totalKeys.reduce((map, key) => {
const val = randStr()
map.set(key, val)
jsMap.set(key, val)
return map
}, new HashMap())
removeKeys.forEach(key => {
console.assert(map.delete(key), 'Failed to delete', key)
})
remainKeys.forEach(key => {
console.assert(map.get(key) === jsMap.get(key), 'Wrong value for', key)
})我在本地的NodeJS环境里跑了几次，都没有什么问题，读者也可以到文章开头的源码链接去自己试一下。
参考
数据结构与算法分析
