源码

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

前往Github获取本文源码。

介绍

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

散列函数

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

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

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

散列表

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

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

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

    分离链接法

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

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

    开放地址法

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

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

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

实现

这里以开放地址法为例,实现一个以字符串为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的准确性。

散列表

总览如下,不包括私有函数:

class HashMap {
    elements = []

    constructor() {}

    set(key, val) {}

    delete(key) {}

    get(key) {}

    get length() {}
}

接下来我们逐个来看。

构造函数

代码如下:

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这个属性判断是否有元素,详细的方法会在下文描述。

散列函数

贴上代码:

_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
}

再散列

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

_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))
}

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

插入

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

_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存在与否判断当前的坑是否有元素,如下:

_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
}

那么我们的删除操作就简单了,找到位置后标记emptytrue即可:

delete(key) {
    const index = this._findIndexForKey(key)
    if (index === -1) {
        return false
    }
    this.elements[index].empty = true
    return true
}

查找

和删除的逻辑基本相通:

get(key) {
    const index = this._findIndexForKey(key)
    if (index === -1) {
        return undefined
    }
    return this.elements[index].val
}

获取长度

用一下Arrayreduce方法:

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

测试

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

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

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

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环境里跑了几次,都没有什么问题,读者也可以到文章开头的源码链接去自己试一下。

参考

数据结构与算法分析