CMU 15-445 -- Hash Tables - 04

CMU 15-445 -- Hash Tables - 04

引言

本系列为 CMU 15-445 Fall 2022 Database Systems 数据库系统 [卡内基梅隆] 课程重点知识点摘录，附加个人拙见，同样借助CMU 15-445课程内容来完成MIT 6.830 lab内容。

本节开始之前，先看一下目前课程的进度状态：

在这里插入图片描述

为了支持 DBMS 更高效地从 pages 中读取数据，DBMS 的设计者需要灵活运用一些数据结构及算法，其中对于 DBMS 最重要的两个是：

• Hash Tables
• Trees

它们可能被用在 DBMS 的多个地方，包括：

• Internal Meta-data
• Core Data Storage
• Temporary Data Structures
• Table Indexes

在做相关的设计决定时，通常需要考虑两个因素：

• Data Organization：如何将这些数据结构合理地放入 memory/pages 中，以及为了支持更高效的访问，应当存储哪些信息
• Concurrency：如何支持数据的并发访问

Hash Tables

Hash Table 主要分为两部分：

• Hash Function：
  • How to map a large key space into a smaller domain
  • Trade-off between being fast vs. collision rate
• Hashing Scheme：
  • How to handle key collisions after hashing
  • Trade-off between allocating a large hash table vs. additional instructions to find/insert keys

Hash Functions

由于 DBMS 内使用的 Hash Function 并不会暴露在外，因此没必要使用加密（cryptographic）哈希函数，我们希望它速度越快，collision rate 越低越好。目前各 DBMS 主要在用的 Hash Functions 包括：

• MurmurHash (2008)
• Google CityHash (2011)
• Google FarmHash (2014)
• CLHash (2016)

Hashing Scheme

• Linear Probe Hashing (线性探测法) ：就是在发生冲突的时候，找到最近的下一个空闲位置，将 item 插入。

当 keys 可能出现重复，但 value 不同时，有两种做法：

• Separate Linked List（分离链表）：这种方法使用链表来处理哈希表中冲突的情况。当发生冲突时，即多个键被映射到同一个哈希桶（存储位置），它们将被存储在一个链表中。每个节点包含键和对应的值。通过遍历链表，可以在哈希表中找到具有相同键的不同值。这样，即使键相同，不同的值也可以被存储和访问。
• Redundant Keys（冗余键）：这种方法在哈希表中允许存储相同的键，但每个键都关联着不同的值。当发生冲突时，新的键值对可以被插入到相同的哈希桶中，作为已有键的一个冗余副本。通过遍历哈希桶中的冗余键，可以找到具有相同键的不同值。

如下图所示：

在这里插入图片描述

通常为了减少 collision 和 comparisons，Hash Table 的大小应当是 table 中元素量的两倍以上。

• Robin Hood Hashing: 是 Linear Probe Hashing 的变种，为了防止 Linear Probe Hashing 出现连续区域导致频繁的 probe 操作。基本思路是 “劫富济贫”，即每次比较的时候，同时需要比较每个 key 距离其原本位置的距离（越近越富余，越远越贫穷），如果遇到一个已经被占用的 slot，如果它比自己富余，则可以直接替代它的位置，然后把它顺延到新的位置。

在这里插入图片描述

这样做的好处是什么呢？最大的好处就是各个键值对离自己的理想位置的距离变得“均衡”了，或许对查询的平均时间复杂度有一定的优化，但是一定复杂化了插入操作的时间复杂度。

实际上，经过实验发现，这种方法的效率不如线性探测法，不过这种方法的思想还是很有价值的。

• Cuckoo Hashing (布谷鸟哈希)

本部分参考: 布谷鸟哈希（Cuckoo hash）

首先要理解布谷鸟的行为，这也是算法的核心:

• 布谷鸟妈妈从不筑巢，它将自己的鸟蛋生在其他鸟类的巢穴里，要别的鸟给它孵蛋
• 新出生的布谷鸟会本能地将巢穴里的其他蛋踢开（kick out ），推出鸟巢，以确保自己在鸟巢里可以独享宠爱

布谷鸟哈希有几种变种，先介绍一个哈希桶和两个哈希函数的版本：

insert逻辑：

1. 若值x已存在哈希表中，则直接返回
2. 若insert后哈希表空间会不够，则先进行扩容，再rehash，再继续3、4、5
3. 用哈希函数h1(x)计算出下标i1，当bucket[i1]为空时，说明鸟巢可用，插入x
4. 若bucket[i1]非空，用新值x将bucket[i1]上的老值x’踢开（kick out），对应小布谷鸟将老蛋踢出巢穴，老蛋当然也不能坐以待毙，继续kick out别的蛋，老值x’的下一个位置用哈希函数h2(x)寻找
5. 重复2，直到达到最大循环次数MaxLoop（插入失败）；或者所有被踢开的值都找到新位置（插入完成）

lookup逻辑：查找逻辑非常简单，去可能的两个巢穴里寻找，即去下标h1(x)和h2(x)寻找，若没有匹配上，则不存在（从这里可以发现查找是非常快的，且时间复杂度稳定是O(1)）

下图展示的是两个哈希函数，两个哈希桶的版本:

在这里插入图片描述

为了防止我们不会陷入一个无限循环中，一旦我们发现了一个死循环或者达到最大循环次数，我们就需要对现有的hash table进行扩容。

• 如果使用两个hash function，那么我们大概只需要当hash table达到50%容量左右时，才需要进行扩容重建
• 如果使用三个hash function，那么我们大概需要当hash table达到90%容量的左右时，才需要进行扩容重建

小结

以上介绍的 Hash Tables 要求使用者能够预判所存数据的总量，否则每次数量超过范围时都需要重建 Hash Table。它可能被应用在 Hash Join 的场景下，如下图所示：

在这里插入图片描述

由于 A, B 表的大小都知道，我们就可以预判到 Hash Table 的大小。

Dynamic Hash Tables

与 Static Hash Tables 需要预判最终数据量大小的情况不同，Dynamic Hash Tables 可以按需扩容缩容，本节主要介绍 Chained Hashing，Extendible Hashing 和 Linear Hashing。

Chained Hashing (链式哈希)

Chained Hashing 是 Dynamic Hash Tables 的 HelloWorld 实现，每个 key 对应一个链表，每个节点是一个 bucket，装满了就再往后挂一个 bucket。需要写操作时，需要请求 latch。

在这里插入图片描述

• 在查找元素时，根据元素的哈希键计算出对应的槽位，并遍历该槽位的链表桶，搜索具有相同哈希键的元素
• 对于插入和删除操作，也可以看作是查找操作的一般化。在插入元素时，需要进行查找并确定插入位置；在删除元素时，也需要查找并删除相应元素

这么做的好处就是简单，坏处就是最坏的情况下 Hash Table 可能降级成链表，使得操作的时间复杂度降格为 O(n)。

当然，如果桶中只有一个元素，那么可以将其视为链表，可以在链表长度到达指定阈值后，变成二叉查找树，提升查询效率。并且当负载因子达到指定阈值后，可以对哈希表进行扩容，此时如果不考虑性能，可以采用copy all策略，如果考虑性能，可以考虑渐进式扩容策略。

Extendible Hashing(可扩展哈希)

在Chained Hashing中，一种可行的方法是在链表变得过长时，将桶（bucket）进行分割，而不是让链表无限增长。这种方法可以避免链表过长导致的性能问题，并且需要进行分割时，只需要对特定的桶进行重新分配。

可扩展哈希方式包含一个slot数组和一系列的buckets，每个slot中保存对应bucket的指针。对于slot数组有一个全局bit位，记录在这个哈希表中需要多少位才能找到对应bucket，对于每一个bucket，有一个本地bit位，记录找到本地的bucket需要多少位。

extendible hash像一种结合hash与redix（前缀树）的技术的哈希方法

Extendible Hashing 的基本思路是一边扩容，一边 rehash，如下图所示：

在这里插入图片描述

可拓展哈希允许插入哈希值相同的记录。所以当插入4条哈希值一样的记录，一个桶就一定放不下（假设桶的容纳上限是3条）。这种情况被叫做overflow，而解决方法是用指针指向overflow bucket，也就是人为增加桶。这种方式看上去不美，也暴露了可拓展哈希的局限性，但一个方法在实际应用中确实无法确保永远的统一性，总是会需要“补丁”。实际应用中，可拓展哈希也不是最普遍的方法，更多则是B-Tree。

Linear Hashing(线性哈希)

本部分参考文章

线性哈希是可扩展哈希的改进，可扩展哈希有一个小的性能瓶颈，在bucket分裂且需要扩展slot array时，需要对整个slot array加锁直到bucket分裂完成。为了解决这个问题，提出了线性哈希方式。哈希表维护一个指针，指向下一个准备分裂的bucket，并且线性哈希采用多个哈希函数来寻找正确的bucket。

线性哈希的数学原理:

• 假定key = 5 、 9 、13

此时所有 key % 4 = 1

• 现在我们对8求余

5 % 8 = 5

9 % 8=1

13 % 8 = 5

由上面的规律可以得出

• (任意key) % n = M
• (任意key) %2n = M或 (任意key) %2n = M + n

线性哈希的具体实现如所示:

• 我们假设初始化的哈希表如下:

在这里插入图片描述

为了方便叙述，我们作出以下假定:

1. 为了使哈希表能进行动态的分裂，我们从桶0开始设定一个分裂点。
2. 一个桶的容量为listSize = 3，当桶的容量超出后就从分裂点开始进行分裂。
3. hash函数为 h0 = key %4 h1 = key % 8，h1会在分裂时使用。
4. 整个表初始化包含了4个桶，桶号为0-3，并已提前插入了部分的数据。

分裂过程如下:

现在插入key = 27

1. 进行哈希运算，h0 = 27 % 4 = 3
2. 将key = 27插入桶3，但发现桶3已经达到了桶的容量，所以触发哈希分裂
3. 由于现在分裂点处于0桶，所以我们对0桶进行分割。这里需要注意虽然这里是3桶满了，但我们并不会直接从3桶进行分割，而是从分割点进行分割。这里为什么这么做，在下面会进一步介绍。
4. 对分割点所指向的桶(桶0)所包含的key采用新的hash函数(h1)进行分割。

对所有key进行新哈希函数运算后，将产生如下的哈希表：

在这里插入图片描述

1. 虽然进行了分裂，但桶3并不是分裂点，所以桶3会将多出的key，放于溢出桶.,一直等到桶3进行分裂。
2. 进行分裂后，将分裂点向后移动一位。

在这里插入图片描述

1. 一次完整的分裂结束

key的读取:

1. 采用h0对key进行计算。
2. 如果算出的桶号小于了分裂点，表示桶已经进行的分裂，我们采用h1进行hash运算，算出key所对应的真正的桶号。再从真正的桶里取出value
3. 如果算出的桶号大于了分裂点，那么表示此桶还没进行分裂，直接从当前桶进行读取value。

说明

1. 如果下一次key插入0、1、2、4桶，是不会触发分裂（没有超出桶的容量）, 如果是插入桶3，用户在实现时可以自己设定，可以一旦插入就触发，也可以等溢出桶达到listSize再触发新的分裂。
2. 现在0桶被分裂了，新数据的插入怎么才能保证没分裂的桶能正常工作，已经分裂的桶能将哪部分插入到新分裂的桶呢?
   1. 只要分裂点小于桶的总数，我们依然采用h0函数进行哈希计算。
   2. 如果哈希结果小于分裂号，那么表示这个key所插入的桶已经进行了分割，那么我就采用h1再次进行哈希，而h1的哈希结果就这个key所该插入的桶号。

   

   在这里插入图片描述

   1. 如果哈希结果大于分裂号，那么表示这个key所插入的桶还没有进行分裂。直接插入。

   

   在这里插入图片描述

   1. 这也是为什么虽然是桶3的容量不足，但分裂的桶是分裂点所指向的桶。如果直接在桶3进行分裂，那么当新的key插入的时候就不能正常的判断哪些桶已经进行了分裂。
3. 如果使用分割点，就具备了无限扩展的能力。当分割点移动到最后一个桶(桶3)。再出现分裂。那么分割点就会回到桶0，到这个时候，h0作废，h1替代h0, h2(key % 12)替代h1。那么又可以开始动态分割。那个整个初始化状态就发生了变化。就好像没有发生过分裂。那么上面的规则就可以循环使用。
4. 线性哈希的论文中是按上面的规则来进行分裂的。其实我们可以安装自己的实际情况来进行改动。

假如我们现在希望去掉分割点，一旦哪个桶满了，马上对这个桶进行分割。

可以考虑了以下方案：

1. 为所有桶增加一个标志位。初始化的时候对所有桶的标志位清空。
2. 一旦某个桶满了，直接对这个桶进行分割，然后将设置标志位。当新的数据插入的时候，经过哈希计算（h0）发现这个桶已经分裂了，那么就采用新的哈希函数(h1)来计算分裂之后的桶号。在读取数据的时候处理类似。

采用此种方案实现的LinerHash简易代码如下所示:

/**
 * lineHash简单实现模型
 */
public class LineHash {
    /**
     * 单桶最多容纳元素个数
     */
    public final int bucketMaxSize;
    /**
     * 分裂点索引
     */
    public int overPoint = 0;
    /**
     * 每一轮的哈希桶数组初始大小
     */
    private int initSize;
    /**
     * 哈希桶数组
     */
    public Bucket[] buckets;

    public LineHash(int bucketMaxSize) {
        this.bucketMaxSize = bucketMaxSize;
        // 初始桶数组大小为4
        buckets = new Bucket[4];
        initSize = 4;
    }

    public String get(int key) {
        int index = calculateIndex(key);
        return buckets[index].get(key);
    }


    public void put(int key, String val) {
        int index = calculateIndex(key);
        Bucket bucket = buckets[index];
        // 判断当前桶是否满了
        if (bucket.size() < bucketMaxSize) {
            bucket.put(key, val);
        } else {
            //满了就进行分裂
            bucket.put(key, val);
            splitHash();
        }
    }

    private int calculateIndex(int key) {
        //根据分裂轮数调用不同的哈希函数
        int index = hashFun(key, 1);
        //当前桶产生了分裂
        if (index < overPoint) {
            //采用新的哈希函数进行计算
            index = hashFun(key, 2);
        }
        lazyInitIfNeed(index);
        return index;
    }

    private void lazyInitIfNeed(int index) {
        if (buckets[index] == null) {
            buckets[index] = new Bucket(bucketMaxSize);
        }
    }

    public int hashFun(int key, int round) {
        return key % (initSize * round);
    }

    public void splitHash() {
        // 待分裂的旧桶
        Bucket oldBucket = buckets[overPoint];
        //分裂产生的新桶
        Bucket newBucket = new Bucket(bucketMaxSize);

        // 对旧桶中的元素进行rehash
        Set<Integer> keySet = oldBucket.keySet();
        List<Integer> removeKeyList=new ArrayList<>(oldBucket.size()/2);
        keySet.forEach(key -> {
            int index = hashFun(key, 2);
            // 说明当前key需要被rehash到新桶中
            if (index >= buckets.length) {
                newBucket.put(key, oldBucket.get(key));
                removeKeyList.add(key);
            }
        });
        removeKeyList.forEach(oldBucket::remove);
        // 将新桶添加进哈希桶数组中
        addBucket(newBucket);
        // 分裂点前移
        overPoint++;
        // 分裂点移动了一轮就更换新的哈希函数
        if (overPoint >= initSize) {
            initSize = initSize * 2;
            overPoint = 0;
        }
    }

    private void addBucket(Bucket newBucket) {
        Bucket[] temp = new Bucket[buckets.length + 1];
        System.arraycopy(buckets, 0, temp, 0, buckets.length);
        temp[buckets.length] = newBucket;
        buckets = temp;
    }

    /**
     * 桶
     */
    private static class Bucket {
        private final Map<Integer, String> map;

        private Bucket(int bucketMaxSize) {
            this.map = new HashMap<>(bucketMaxSize);
        }

        public void put(Integer key, String val) {
            map.put(key, val);
        }

        public String get(Integer key) {
            return map.get(key);
        }

        public int size() {
            return map.size();
        }

        public Set<Integer> keySet() {
            return map.keySet();
        }

        public void remove(Integer key) {
            map.remove(key);
        }
    }
}

这段代码逻辑不完全正确，本人目前能力所限，对liner hash理解还不够透彻，如果有大佬有补充，可以在评论区留言。

总结

Hash Tables 提供 O(1) 的访问效率，因此它被大量地应用于 DBMS 的内部实现中。即便如此，它并不适合作为 table index 的数据结构，而 table index 的首选就是下节将介绍的 B+ Tree。

本节参考课程PDF