JavaScript 实现 HashTable 算法

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

Answer 1

四、KMP（Knuth-Morris-Pratt ） 算法

KMP 是著名的字符串匹配算法，效率高但比较难理解（一看就懂的请勿代入

Answer 2

动态规划优秀文章：动态规划套路详解

1. 核心观点

动态规划并不难，通常是通过流程 递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法 一步步铺垫而来，动态规划的核心是化递归（自顶向下）为循环迭代（自底向上）。

如上面流程所示，在动态规划中，得到暴力解（即如何穷举所有可能性，也即得到“状态转移方程”）是最困难的一步。为什么说困难，一是因为很多穷举需要递归实现，二是因为有的问题本身的解空间复杂，不容易穷举完整。

2. 凑零钱Demo演示

假设有 k 种不同币值硬币，总金额为 n 时最少需要几枚硬币可以凑出这个金额？无法凑出则给 -1。
比如说，k = 3，面值分别为 1，2，5，总金额 n = 11，那么最少需要 3 枚硬币，即 11 = 5 + 5 + 1 。

假设 n 总是可以被凑出来的，那么这个问题其实非常简单，我们只需要先从最大币值的硬币开始凑就可以了。然而这个假设并不总是成立，所以事实上我们需要穷举所有可能性——典型的可以采用动态规划方法来解决的问题。

下面我们按流程来解题：

1）暴力解（即状态转移方程）：

f(0) = 0;
f(n) = 1 + min{f(n - Ci)}  ( i 属于 [1, k], Ci 即对应的硬币币值)

其中，n 即总金额， i 为 1~k，即不同币值硬币个数，Ci 为对应硬币币值。

如上，可以理解为原问题的解可以通过子问题的最优解来得到，即 f(11) 是可以分解为：

• 硬币 1 元 和 f(10) 的最小硬币数
• 硬币 2 元 和 f(9) 的最小硬币数
• 硬币 5 元 和 f(6) 的最小硬币数

3种情形的最优解即为最终解，而f(10) / f(9) / f(6) 可以继续递归分解。

好了，给这个暴力解一个程序表达：

// 暴力递归
function assembleCoin(coins, amount) {
    if (amount === 0) {
        return 0;
    }

    let ans = Number.MAX_SAFE_INTEGER;
    for(let c of coins.values()) {
        // 剩余金额
        let value = amount - c;
        // 币值大于总金额，说明是无效的
        if (value < 0) continue;
        // 计算剩余金额可能的最少组合次数
        const sub = assembleCoin(coins, value);
        // 次数小于0，说明无效
        if (sub < 0) continue;

        // 该次组合有效，更新最少次数
        ans = Math.min(ans, 1 + sub);
    }

    return ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
}

2）带备忘录的递归

暴力解有太多的重复子问题（比如多个 f(5) 的求解）,如果重复子问题的求解结果被缓存了，那同一个子问题就只用计算一次了：

// 带备忘录的递归
function assembleCoinWithMemo(coins, amount) {
    const memo = {};
    return coinHelper(memo, coins, amount);
}

function coinHelper(memo, coins, amount) {
    if (amount === 0) {
        return 0;
    }

    if (memo[amount] !== undefined) {
        return memo[amount];
    }

    let ans = Number.MAX_SAFE_INTEGER;
    for (let c of coins.values()) {
        // 剩余金额
        let value = amount - c;
        // 币值大于总金额，说明是无效的
        if (value < 0) continue;
        // 计算剩余金额可能的最少组合次数
        const sub = coinHelper(memo, coins, value);
        // 次数-1，说明无效
        if (sub === -1) continue;

        // 该次组合有效，取最少次数
        ans = Math.min(ans, 1 + sub);
    }
    memo[amount] = ans === Number.MAX_SAFE_INTEGER ? -1 : ans;
    return memo[amount];
}

3）动态规划：递归 --> 循环

动态规划其实和上面的备忘录法已经相当接近了，把备忘录换成 DP 表，从而自底向上求解替代自顶向下，就是动态规划：

// 动态规划
function assembleCoinDP(coins, amount) {
    // dp 表最多包含 amount + 1 种情况（包括0）
    const dp = Array(amount + 1).fill(amount + 1);
    // 最简单（自底向上的底）的情况：
    dp[0] = 0;
    // 从 1 开始填充 dp 表的过程即自底向上逐渐求解的过程
    for(let i = 1; i < dp.length; i++) {
        // 内层 for 循环求所有子问题 + 1（种硬币） 的最小值
        // 比如 i = 1，我们即求解：1元+dp[0]，2元+dp[-1]，5元+dp[-4] 等3种情况，
        // 其中后两种被 continue 直接过滤了，所以 dp[1] 很容易得到为 1；
        // 随着 i 增大，我们最终总可以得到所有的 d[i]，且必然 d[x]（x < i）是已经计算
        // 有结果的（保持 amount + 1的最大值即代表amount 为该值时无可用的硬币排布，返回 -1）
        for (let c of coins.values()) {
            if (i - c < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - c]);
        }
    }
    return dp[amount] === amount + 1 ? -1 : dp[amount];
}

时间复杂度

最后顺便给一组实际测试时不同方式的用时：

// 1,2,5     -----------   13
4
normal: 2.667ms
4
memo: 0.166ms
4
dp: 0.171ms

// 1,2,5     -----------   27
6
normal: 35.627ms
6
memo: 0.185ms
6
dp: 0.183ms

// 1,2,5     -----------   39
9
normal: 18192.081ms
9
memo: 0.191ms
9
dp: 0.206ms

可以看到，相比带备忘录的递归和动态规划，暴力递归的用时太可怕了：

• 暴力递归时间复杂度：O(k*n^k)
• 备忘录：O(kn)
• 动态规划：O(kn)

如上，希望通过例子可以对动态规划更容易理解一些。

Answer 3

三、动态规划

背包问题

首先我们从背包问题开始。

一个背包可以装4kg的物品，现有物品音响（3000元|4kg）笔记本电脑（2000元|3kg）、吉他（1500元|1kg），那么我们怎么拿可以使物品价值最高？

1、 最简单的方法：罗列所有组合，选取符合条件的最高的那个。

物品是1个的时候，我们可以拿或不拿，即2种选择；物品3个的时候，我们有8种选择；物品n种时，我们有 2^n 种选择——时间复杂度 O(2^n)!

2、动态规划

动态规划的核心在于合并两个子问题的解来得到更大问题的解。

那么它的难度就在于怎么把大问题分解成子问题。

在这里的例子里，装入背包的物品价值取决于物品类型和背包容量两个因素，以这两个因素为维度，利用网格来得到问题的解（本质上是当容量更小、物品更少时更容易得到解）。

• 当只有一个物品时，随容量增加，很轻松可以得到容量对应的最大价值（这里作为第一行开始）。
• 当增加物品时（即下一行），那么每个格子的值将由上一行对应格子的值和当前物品价值来决定：
  • 增加物品，价值只可能增长，所以最小值是上一行对应格子的值；
  • 如果当前格子的容量可以放下当前物品，那么可能的最大值是当前物品的价值 + 上一行对应剩余容量格子的值。

Answer 4

二、KNN （k-nearest neighbors，K最近邻算法）

从一个很简单的例子来理解KNN。

假设我们有一堆橙子和一堆柚子，通常情况下，柚子比橙子更大，更红；现在有一个水果，我们怎么判断它是橙子还是柚子？肯定是比较它的大小和颜色，与橙子/柚子哪个更接近。怎么判断接近？我们可以把之前的橙子/柚子画到二维点图上，X轴为颜色，Y轴为大小，然后来看看离这个水果最近的3个点，结果这3个点里，有2个是橙子，那么我们大概率可以确定，这个水果就是橙子。

这里运用到的就是 KNN 算法：给定一个（训练）数据集，对新的输入实例，在训练数据集中找到与该实例最邻近的K个实例，这K个实例的多数属于某个类，就把该输入实例分类到这个类中。

KNN 算法是一种基本分类和回归方法，是机器学习中最简单的算法之一。

由于给定的数据集都带有label（即是橙子还是柚子），并且新输入的实例也会明确确定label，所以KNN属于监督学习。

下面讲一些KNN算法的注意点：

K 的选取

• K 不能过小，过小就容易被噪声干扰。极端情况，K 取 1，只要新实例最近的一个是噪点，那么新实例的分类就会出错。
• K 不能过大。过大时，表示邻域过大，这个范围内有很多非同类的数据也在起作用（训练实例和输入实例距离大，不相似），容易分类错误。极端情况，K 取全部数据，那么新实例永远归入数量占多的类别。
• 所以 K 不能过大过小，一般取一个较小的数值，并采取交叉验证法来选取最优的K值。

距离计算

• 一般采用欧氏距离（Euclidean Distance）。欧氏距离可以量测任意方向的线段，计算方法是
• 不采用曼哈顿距离（Manhattan Distance）。曼哈顿距离就像曼哈顿的街道一样，只有水平和垂直的线段，无法计算多维度，计算方法是
• 实际中经常使用余弦相似度（计算角度而非距离）。

特征归一化

假设我们通过两个维度（身高和脚长）来判断性别，很显然，计算距离时，结果会偏向于身高。

所以很容易理解，我们需要对特征归一化。即取每个维度的最大值减去最小值，然后该维度计算时首先除以这个值来进行归一化。