散列表（或哈希表，HashMap）是一种最优时间复杂度可以达到O(1)的数据结构，其原理是根据指定键的hash值来确定它在表中的大致位置，之后再去寻找。在介绍这个数据结构如何实现之前，先让我们看看散列函数的相关知识。
散列函数所谓散列函数，只要知道以下这两个性质即可：
同一个数值进行散列，得到的结果必然相同；
当散列结果相同时，不一定是同一个数值。
借助散列函数，我们可以很方便地判断这两个数值是否不同，但却无法判断它们是否相同，会发生散列冲突。所以这就是为什么哈希表只是在理想状态下可以达到O(1)。
散列表这个数据结构的核心就是如何解决散列冲突。有两种最简单的方法，它们是分离链接法和开放地址法，下面来介绍这两种方式。
我们假设一个整数的散列值是它本身，由于表中没有那么多空，所以要把这个值与表长取模，即value % tableSize。
分离链接法：把发生冲突的值放到同一个坑的后面，用链表连接起来，如下：
Java的经典HashMap当数据量小时就用的这个方法。
开放地址法：把发生冲突的值放在表的下一个坑里，如果下一个坑也有元素那就再继续找，如下：
Python内部实现哈希表好像就用的这个方法，我就不亲自去扒源码看了。
但是，当表里的数据过多时，分离链接法的效率会变低，开放地址法会无法探测到下一个新的位置。那么此时就需要重新调整表的大小，即rehash再散列。
除此之外，我们这里演示的表长都是5，设想一下，如果传入的数据都是10、15、25这样的，那么这个表的效率就会变低。一个解决方式是，让表长为素数，就可以使得分布较为均匀了。
实现这里以开放地址法为例，实现一个以字符串为key的散列表。
素数由于表长需要是一个素数，这里就也需要写出相关代码：判断是否为素数的isPrime，和获取指定值的下一个素数nextPrime：
代码语言：javascript
复制
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生成了一个数组，这里只需要知道这样写是深拷贝，关于这个函数的详细用法请前往。
此外，我们用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存在与否判断当前的坑是否有元素，如下：
代码语言：javascript
复制
_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即可：
代码语言：javascript
复制
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方法：
代码语言：javascript
复制
get length() { return this.elements.reduce((n, el) => { return n + !el.empty }, 0) }
测试已经实现了一个基本的散列表！但是，为了写测试用例，我们还得下点功夫。首先是生成随机字符串的函数：
代码语言：javascript
复制
function randStr() { return Math.random().toString(36).slice(-8) }
然后我们用它生成指定长度的一组key，用来插入到我们的表中：
代码语言：javascript
复制
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环境里跑了几次，都没有什么问题，读者也可以到文章开头的源码链接去自己试一下。
参考数据结构与算法分析
