源码

来自半年后的说明：我把代码转放到 gists 里了，当时代码风格受 Python 影响较大，这里就不再更改了，毕竟大家本地都有自己的格式化工具。

前往Github获取本文源码。

介绍

散列表（或哈希表，HashMap）是一种最优时间复杂度可以达到O(1)的数据结构，其原理是根据指定键的hash值来确定它在表中的大致位置，之后再去寻找。在介绍这个数据结构如何实现之前，先让我们看看散列函数的相关知识。

散列函数

所谓散列函数，只要知道以下这两个性质即可：

  1. 同一个数值进行散列，得到的结果必然相同；
  2. 当散列结果相同时，不一定是同一个数值。

借助散列函数，我们可以很方便地判断这两个数值是否不同，但却无法判断它们是否相同，会发生散列冲突。所以这就是为什么哈希表只是在理想状态下可以达到O(1)。

散列表

这个数据结构的核心就是如何解决散列冲突。有两种最简单的方法，它们是分离链接法和开放地址法，下面来介绍这两种方式。

我们假设一个整数的散列值是它本身，由于表中没有那么多空，所以要把这个值与表长取模，即value % tableSize。

  • 分离链接法：把发生冲突的值放到同一个坑的后面，用链表连接起来，如下：

    分离链接法

    Java的经典HashMap当数据量小时就用的这个方法。

  • 开放地址法：把发生冲突的值放在表的下一个坑里，如果下一个坑也有元素那就再继续找，如下：

    开放地址法

    Python内部实现哈希表好像就用的这个方法，我就不亲自去扒源码看了。

但是，当表里的数据过多时，分离链接法的效率会变低，开放地址法会无法探测到下一个新的位置。那么此时就需要重新调整表的大小，即rehash再散列。

除此之外，我们这里演示的表长都是5，设想一下，如果传入的数据都是10、15、25这样的，那么这个表的效率就会变低。一个解决方式是，让表长为素数，就可以使得分布较为均匀了。

实现

这里以开放地址法为例，实现一个以字符串为key的散列表。

素数

由于表长需要是一个素数，这里就也需要写出相关代码：判断是否为素数的isPrime，和获取指定值的下一个素数nextPrime：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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的准确性。

散列表

总览如下，不包括私有函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
class HashMap {
    elements = []

    constructor() {}

    set(key, val) {}

    delete(key) {}

    get(key) {}

    get length() {}
}

接下来我们逐个来看。

构造函数

代码如下：

1
2
3
4
5
6
7
8
constructor() {
    this._createElements(4)
}

_createElements(length) {
    length = nextPrime(length)
    this.elements = Array.from({ length }, () => ({ empty: true }))
}

我们通过Array.from生成了一个数组，这里只需要知道这样写是深拷贝，关于这个函数的详细用法请前往MDN。

此外，我们用empty属性判断是否有元素。如果直接把元素赋值为undefined的话，就会出现下图的情况：

21被删除了，直接用undefined覆盖掉

那么在查找41的时候，当找到原来的21的位置时，因为这个值现在是undefined，它到底是该继续向下找，还是该停止？就无从得知了。所以，我们需要用empty这个属性判断是否有元素，详细的方法会在下文描述。

散列函数

贴上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
_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
}

再散列

这还是一个内部的私有函数，但也比较重要，没了它就没法说插入的逻辑。代码如下：

1
2
3
4
5
6
7
8
9
_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))
}

好了，现在可以说插入方法了。

插入

其核心为寻找下一个空位，如果没有了， 那就执行一次再散列，之后插入：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
_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被标记为已经删除了

因为上图中的21被标记成删除，那我们如果还是用_findIndexToInsert方法查找41，它会立即返回一个1，就是已经被删除的21的位置。

那我们可以考虑用key存在与否判断当前的坑是否有元素，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
_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即可：

1
2
3
4
5
6
7
8
delete(key) {
    const index = this._findIndexForKey(key)
    if (index === -1) {
        return false
    }
    this.elements[index].empty = true
    return true
}

查找

和删除的逻辑基本相通：

1
2
3
4
5
6
7
get(key) {
    const index = this._findIndexForKey(key)
    if (index === -1) {
        return undefined
    }
    return this.elements[index].val
}

获取长度

用一下Array的reduce方法：

1
2
3
4
5
get length() {
    return this.elements.reduce((n, el) => {
        return n + !el.empty
    }, 0)
}

测试

已经实现了一个基本的散列表！但是，为了写测试用例，我们还得下点功夫。首先是生成随机字符串的函数：

1
2
3
function randStr() {
    return Math.random().toString(36).slice(-8)
}

然后我们用它生成指定长度的一组key，用来插入到我们的表中：

1
2
3
4
5
6
7
8
9
function generateKeys(n) {
    const result = new Set()

    while (result.size < n) {
        result.add(randStr())
    }

    return Array.from(result)
}

这里用Set去重，之后把它转换成了Array。

之后再借助原有的映射类型辅助我们进行验证：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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环境里跑了几次，都没有什么问题，读者也可以到文章开头的源码链接去自己试一下。

参考

数据结构与算法分析