JavaScript 哈希函数 哈希表的简单实现

Question

这一章节内容主要是 HashTable，中文即哈希表，散列表等等。HashTable 是编程中日常使用，不可或缺的一个数据结构，本章节最终会代码实现一个简单哈希表，来解释哈希表相关的重要概念。

对前端同学而言，哈希表是个每天用但说起来可能陌生的概念。说每天用，是因为在 JavaScript 中，对象（{}）的底层实现即哈希表，我们也经常用对象来做缓存等各种用法，利用其查找时间复杂度为 O(1) 的特性。

1. 为什么需要 hash table （元素查找的时间复杂度）

对若干个元素（key-value对），如果我们想通过 key 来找到对应的 value，通常情况下，我们需要遍历所有元素，一一比较 key，来找到对应的 value。这个时间复杂度是 O(n) 。

然后我们假设这些元素是有序的，那么通过二分查找，时间复杂度可以降到 O(log n) 。

那么有没有更好的方法呢？这就是 hash table 出现的原因，它可以达到 O(1) 的时间复杂度。

2. 什么是 hash table？

哈希表是一种用于存储键值对（key-value pairs）的数据结构，它可以实现key到value的映射，一般情况下查找的时间复杂度是O(1) 。

• 哈希表的核心是哈希函数（hash function），它可以接收 key 作为参数（一般是字符串），然后返回一个数字（通常作为 index 去找到对应的 bucket，bucket 里存储了一个或多个 value）。
• 哈希函数应该尽可能均匀的把不同的 key 映射到不同的 bucket（即产出不同的 index）。最差情况下，如果所有的 key 都得到相同的 index，那么哈希表就退化成一个链表了（取决于 bucket 的实现）。
• bucket 指什么？理想情况下，如果每个 key 都得到一个唯一的 index，那么这时候一个bucket对应一个元素，我们通过哈希函数可以一步取到 value；但通常这是不可能的，即 key -- > index 的映射肯定会有冲突的，所以一个 bucket 可能会有多个元素。

3. 哈希表的简单实现

/**
 * 哈希函数，接收字符串返回数字
 * https: //github.com/darkskyapp/string-hash
 * 
 * @param str 字符串
 * @returns number，32位整数，0～4294967295
 */
function hash(str) {
    var hash = 5381,
        i = str.length;

    while (i) {
        hash = (hash * 33) ^ str.charCodeAt(--i);
    }

    /* JavaScript does bitwise operations (like XOR, above) on 32-bit signed
     * integers. Since we want the results to be always positive, convert the
     * signed int to an unsigned by doing an unsigned bitshift. */
    return hash >>> 0;
}

class HashTable {
    static hash(key) {
        return hash(key)
    }
    constructor() {
        this.buckets = [];
    }
    set(key, value) {
        const index = HashTable.hash(key);
        let bucket = this.buckets[index];
        // 直接使用数组来处理哈希函数冲突的问题 
        if (!bucket) {
            this.buckets[index] = bucket = [];
        }
        if (!bucket.some(el => el.key === key)) {
            bucket.push({ key, value });
        }
    }
    get(key) {
        const index = HashTable.hash(key);
        const bucket = this.buckets[index];
        if (!bucket) return;

        let result;
        bucket.some(el => {
            if (el.key === key) {
                result = el.value;
                return true;
            }
            return false;
        });
        return result;
    }
}

以上是一个简单的哈希表实现，还有很多细节没有考虑，比如：

• 填装因子（填装因子 = 哈希表的元素数量 / 哈希表的位置总数）。根据经验，一旦填装因子大于 0.7，我们就需要调整哈希表的长度。
• buckets 数组这里没有规定长度，如果考虑 buckets 的长度，那么我们就要对哈希函数返回的值进行取余操作。

参考：

• implementing-a-hash-table-in-javascript
• Hash table