哈希

(Updated: )
(5 mins to read)

$O(1)$单点插入、删除、查询。在数据库里主要用在join和group by中。

静态哈希表

benchmark1

benchmark2

有些哈希表是不稳定的（flat_map），存储在其中的value的地址可能因为插入和删除而失效（因为发生了rehash）。稳定的方法通常需要通过间接寻址（node_map）。

node_map和flat_map的区别是flat_map将value直接存到数组中，因此在rehash时地址会改变，而node_map将value存在另一个保持不变的数组中，其优点是提供了稳定性，并且可以存储不可移动或不可复制的元素，并且也更适合大value对象（因为把大对象直接存到数组中会破坏cache），但也导致了额外开销。

关键点：哈希函数、冲突解决方法。

MurmurHash、Facebook XXHash

开放寻址

  • 线性探测：如果映射位置已经被占用，就检查紧接着的下一个位置，不断重复
  • 二次探测：如果被占用，则检查+1^2, -1^2, +2^2, -2^2…

删除的时候一种是所有元素都重hash，另一种是用tombstome标记。

布谷鸟哈希

布谷鸟在孵化时会将一些蛋/幼鸟推出巢外，布谷鸟哈希在插入新key时，可能把旧key移动到其它位置。

通用的讲：布谷鸟哈希使用n个哈希函数，然后将key插入到其中第一个空闲的哈希位置，如果都非空，就选择踢掉一个冲突的key，并重新插入这个冲突的key。

这里介绍使用两个哈希表$T_1$和$T_2$，以及两个哈希函数$h_1$和$h_2$的版本。

查找

查找$T_1[h_1(x)]$和$T_2[h_2(x)]$即可。

删除

同理。

插入

如果$T_1[h_1(x)]$为空，就插入；否则替换为$x$（踢掉旧值$x’$），并将原有的$x’$插入到$T_2$，不断重复至多MAX_LOOP次（这个过程中可能发生死循环）。超过固定阈值，就扩展两个哈希表，进行重哈希。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def insert(x):
    if lookup(x):
        return
    for _ in range(MAX_LOOP):
        if T1[h1(x)] is empty:
            T1[h1(x)] = x
            return
        swap(x, T1[h1(x)])
        if T2[h2(x)] is empty:
            T2[h2(x)] = x
            return
        swap(x, T2[h2(x)])
    rehash()
    insert(x)

如果将$T_1[h_1(x)]$和$T_2[h_2(x)]$看作一条边，就构成一张图。

其优点是最坏复杂度有保证，并且查找过程可以完全向量化，适用于大量单点查询的场景。

其缺点是缓存不友好。rocksdb的一个优化方案是在某个哈希映射冲突时，进一步尝试连续的若干位置（+1,+2,…），这被称作布谷鸟块，这样可以通过预取这个块来加速（85%的key都在第一个布谷鸟块中）。

布谷鸟过滤器

相比于布隆过滤器，能够支持删除操作。

std::unordered_map

使用拉链法实现，有多个桶，每个桶都是一个链表。max_load_factor是元素个数除以桶个数的上限（默认为1），当超过这个上限时，说明桶的个数过少了，就会将bucket_size扩大2倍，然后重新进行hash。

1
2
3
4
5
6
7
class unordered_map {
  private:
    list<pair<int,int>> *buckets;
    int bucket_size;
    int total_elements;
    float max_load_factor;
}

这种实现方式是很慢的，因为数据局部性很差，cache不友好。但因为C++标准规定在插入或删除元素时其他元素必须有效，因此选择了拉链法，但更现代的hashmap通常采用线性探测或其变种。

robin_hood::unordered_flat_map

robin hood是线性探测的变种。通过劫富济贫来优化每个元素的实际位置与其哈希位置的距离。在插入时，如果当前元素的距离已经比占用元素的距离大（占用元素更富有），那就取代这个占用元素，让占用元素继续找下一个空的位置。避免了线性探测中某些元素极度贫困的问题，需要连续多次探测。

slotmap

与常规的hashmap需要自己提供key和value不同，slotmap只在插入时只需要提供value，然后会自动返回一个唯一且永久有效的key。

优化

  • 通常会根据键值的类型、大小以及取值分布选择合适的哈希函数和解决冲突方式
  • 使用版本号实现快速的清空操作

动态哈希表

拉链法

拉链法可以算作一种动态哈希表的类型。因为线性探测中元素的个数只能固定在预设的N个，要扩大只能rehash，而拉链法中链表没有大小限制，但实际会通过负载因子来进行平衡。

可以套上布隆过滤器避免无用的查找。

可扩展哈希