跳转至

哈希表

基础

数组通过索引在 O(1)的时间复杂度内查找到对应元素,索引是一个非负整数。

哈希表通过 key 在 O(1)的时间复杂度内查找到这个 key 对应的 value。key 的类型可以是数字、字符串等多种类型。

哈希表的底层实现就是一个数组(我们不妨称之为 table)。它先把这个 key 通过一个哈希函数(我们不妨称之为 hash)转化成数组里面的索引,然后增删查改操作和数组基本相同:

// 哈希表伪码逻辑
class MyHashMap {

private:
    vector<void*> table;

public:
    // 增/改,复杂度 O(1)
    void put(auto key, auto value) {
        int index = hash(key);
        table[index] = value;
    }

    // 查,复杂度 O(1)
    auto get(auto key) {
        int index = hash(key);
        return table[index];
    }

    // 删,复杂度 O(1)
    void remove(auto key) {
        int index = hash(key);
        table[index] = nullptr;
    }

private:
    // 哈希函数,把 key 转化成 table 中的合法索引
    // 时间复杂度必须是 O(1),才能保证上述方法的复杂度都是 O(1)
    int hash(auto key) {
        // ...
    }
};

常见的哈希函数

字符串

int hashCode() {
    for (int i = 0; i < str.size(); i++) {
        h = 31 * h + str[i];
    }
}

int hash(K key) {
    int h = key.hashCode();
    // 保证非负数
    h = h & 0x7fffffff;
    // 映射到 table 数组的合法索引
    return h % table.length;
}

需要注意的几个点:

  • 哈希表key唯一,value不唯一(类比数组索引和元素值)
  • 哈希函数:把任意长度的输入(key)转化成固定长度的输出(索引)。哈希函数需要保证:

    • 哈希函数的复杂度为O(1)。如果你设计的这个哈希函数复杂度是 O(N),那么哈希表的增删查改性能就会退化成 O(N)
    • 输入相同的 key,输出也必须要相同。
  • 哈希冲突:如果两个不同的 key 通过哈希函数得到了相同的索引

    • 哈希冲突是一定会出现的。因为这个 hash 函数相当于是把一个无穷大的空间映射到了一个有限的索引空间,所以必然会有不同的 key 映射到同一个索引上。
    • 解决哈希冲突的方法

      • 拉链法(纵向):哈希表的底层数组并不直接存储 value 类型,而是存储一个链表,当有多个不同的 key 映射到了同一个索引上,这些 key -> value 对儿就存储在这个链表中,这样就能解决哈希冲突的问题。
      • 线性探查法(开放寻址法)(横向):一个 key 发现算出来的 index 值已经被别的 key 占了,那么它就去 index + 1 的位置看看,如果还是被占了,就继续往后找,直到找到一个空的位置为止
    • 那么为什么会频繁出现哈希冲突:

      1. 哈希函数设计的不好,导致 key 的哈希值分布不均匀,很多 key 映射到了同一个索引上。
      2. 哈希表里面已经装了太多的 key-value 对了,这种情况下即使哈希函数再完美,也没办法避免哈希冲突。

      对于第一个问题没什么好说的,开发编程语言标准库的大佬们已经帮你设计好了哈希函数,你只要调用就行了。

      对于第二个问题是我们可以控制的,即避免哈希表装太满,这就引出了「负载因子」的概念。

「负载因子」

负载因子是一个哈希表装满的程度的度量。一般来说,负载因子越大,说明哈希表里面存储的 key-value 对越多,哈希冲突的概率就越大,哈希表的操作性能就越差。

负载因子的计算公式也很简单,就是 size / table.length。其中 size 是哈希表里面的 key-value 对的数量,table.length 是哈希表底层数组的容量。

你不难发现,用拉链法实现的哈希表,负载因子可以无限大,因为链表可以无限延伸;用线性探查法实现的哈希表,负载因子不会超过 1。

像 Java 的 HashMap,允许我们创建哈希表时自定义负载因子,不设置的话默认是 0.75,这个值是经验值,一般保持默认就行了。

当哈希表内元素达到负载因子时,哈希表会扩容。和之前讲解 动态数组的实现 是类似的,就是把哈希表底层 table 数组的容量扩大,把数据搬移到新的大数组中。size 不变,table.length 增加,负载因子就减小了。

为什么不能依赖哈希表的遍历顺序

首先,由于 hash 函数要把你的 key 进行映射,所以 key 在底层 table 数组中的分布是随机的,不像数组/链表结构那样有个明确的元素顺序。

其次,刚才讲了哈希表达到负载因子时会怎样?会扩容对吧,也就是 table.length 会变化,且会搬移元素。

那么这个搬移数据的过程,是不是要用 hash 函数重新计算 key 的哈希值,然后放到新的 table 数组中?

而这个 hash 函数,它计算出的值依赖 table.length。也就是说,哈希表自动扩容后,同一个 key 的哈希值可能变化,即这个 key-value 对儿存储在 table 的索引也变了,所以遍历结果的顺序就和之前不一样了。

面试常考问题

1、为什么我们常说,哈希表的增删查改效率都是 O(1)?

因为哈希表底层就是操作一个数组,其主要的时间复杂度来自于哈希函数计算索引和哈希冲突。只要保证哈希函数的复杂度在 O(1)O(1),且合理解决哈希冲突的问题,那么增删查改的复杂度就都是 O(1)。

2、哈希表的遍历顺序为什么会变化?

因为哈希表在达到负载因子时会扩容,这个扩容过程会导致哈希表底层的数组容量变化,哈希函数计算出来的索引也会变化,所以哈希表的遍历顺序也会变化。

3、哈希表的增删查改效率一定是 O(1)吗?

不一定,正如前面分析的,只有哈希函数的复杂度是 O(1),且合理解决哈希冲突的问题,才能保证增删查改的复杂度是 O(1)。

哈希冲突好解决,都是有标准答案的。关键是哈希函数的计算复杂度。如果使用了错误的 key 类型,比如前面用 ArrayList 作为 key 的例子,那么哈希表的复杂度就会退化成 O(N)。

4、为啥一定要用不可变类型作为哈希表的 key?

因为哈希表的主要操作都依赖于哈希函数计算出来的索引,如果 key 的哈希值会变化,会导致键值对意外丢失,产生严重的 bug。