https://15445.courses.cs.cmu.edu/fall2018/slides/06-hashtables.pdf

DBMS对系统内部的许多不同部分使用各种数据结构：
•内部元数据：跟踪有关数据库和系统状态的信息。
•核心数据存储：可用作数据库中元组的基本存储。
•临时数据结构：DBMS可以在处理查询时动态构建数据结构以加速执行（例如，用于连接的哈希表）。
•表索引：辅助数据结构，以便更容易找到特定元组。
设计决策：
1.数据组织：我们如何布局内存以及在数据结构中存储哪些信息。
2.并发：如何在不引起问题的情况下启用多个线程来访问数据结构。

Hash 表 设计理念

哈希表实现了将键映射到值的关联数组抽象数据类型。
哈希表实现由两部分组成：

•散列函数：如何将大密钥空间映射到较小的空间里。我们需要考虑如何在快速与冲突率之间的权衡。

•散列方案：如何在散列后处理关键冲突。 需要考虑需要分配大型哈希表以减少冲突与执行其他指令以查找/插入密钥之间的权衡。

考虑一个简单的静态哈希表实现：
•为每个元素分配一个带有一个插槽的巨型阵列。 通过元素数修改键以查找数组中的偏移量。
•有问题的假设：
你提前了解了元素的数量
2.每个密钥都是唯一的
3.完美散列函数（如果key1！= key2则hash（key1）！= hash（key2））

经典的hash算法比较

首先又一些hash函数，我们会想到，如md5,crc,sha。但是我们不需要这些加密哈希函数，因为我们不需要从哈希中获取密钥。 我们只关心速度和碰撞率。
下面是几种hash函数的吞吐率。

image.png

静态hash结构

1 开放寻址法

哈希冲突解决策略：开放寻址法（Open Addressing）

通常采用的冲突解决策略为开放寻址法（Open Addressing），将所有的元素都存放在哈希表内的数组中，不使用额外的数据结构。

开放寻址法的最简单的一种实现就是线性探查（Linear Probing），步骤如下：

1. 当插入新的元素时，使用哈希函数在哈希表中定位元素位置；
2. 检查哈希表中该位置是否已经存在元素。如果该位置内容为空，则插入并返回，否则转向步骤 3。
3. 如果该位置为 i，则检查 i+1 是否为空，如果已被占用，则检查 i+2，依此类推，直到找到一个内容为空的位置。

线性探查（Linear Probing）方式虽然简单，但并不是解决冲突的最好的策略，因为它会导致同类哈希的聚集（Primary Clustering）。这导致搜索哈希表时，冲突依然存在。如果我们要访问 Edward 的信息，因为 Edward 的社保号 111-00-1235 哈希为 1235，然而我们在 1235 位置找到的是 Bob，所以再搜索 1236，找到的却是 Danny，以此类推直到找到 Edward。

2. 罗宾汉哈希

罗宾汉哈希可以显著降低探查长度的方差。我们来看一下它是怎么做的：

对每个哈希表中的元素，记录插入时的探查长度
当插入一个新元素时，对于探查过程中的元素，如果它的探查长度小于当前插入元素的探查长度，那么交换这两个元素 (以及探测长度)，然后继续探查
也就是说，事实上大家的探查长度更加平均了，所以期望最长探查长度也会显著的下降。这也是罗宾汉 (英国传说中的侠盗) 哈希名字的来源，劫富济贫。虽然大部分元素的探查长度都更趋近于平均值，不是一次就能查到，但是由于这部分开销较 CPU 加载 cache line 开销可以忽略不计，所以整体上仍有显著的提高。

如果没有冲突，数值是0，如果冲突1次数值为1.

image.png

image.png

当冲突的次数超过当前的次数了，就先把这个坑占了，如图e 占了 d。
就要把当前的d再计1次冲突。

image.png

image.png

3. cuckoo hash

使用具有不同散列函数的多个散列表。
→在插入时，检查每个表并选择任何有空闲插槽的表。
→如果没有表有空闲插槽，则从其中一个中删除该元素，然后重新散列它以找到新位置。
查找和删除始终为O（1），因为每个哈希表只检查一个位置。

移动键时，确保我们不会陷入无限循环。
如果我们找到一个循环，那么我们可以用新的散列函数重建整个散列表。
→使用两个哈希函数，我们（可能）不需要重建表，直到它满50％。
→使用三个哈希函数，我们（可能）不需要重建表，直到它满约90％。

image.png

image.png

动态hash结构

1. Chained Hash

•为哈希表中的每个槽维护一个桶的链表。
•通过将具有相同散列键的元素放入同一个存储桶中来解决冲突。
•如果存储桶已满，请添加另一个存储桶列表。 哈希表可以无限增长，因为您不断添加新桶。
•要处理并发性，您只需要在每个存储桶上设置一个latch

image.png

•非唯一键的方法

1.单独的链表：将值存储在单独的存储区域中
2.存储在存储桶中：将重复的密钥存储在相同的存储桶中（把value 和key 存在一起）

image.png

2. extensible hash

http://www.cosc.brocku.ca/~efoxwell/2P03/slides/Week12Slides.pdf
实现见project 1

3. linear hash

线性哈希是一种动态扩展哈希表的方法。

线性哈希的数学原理:

假定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

线性哈希的具体实现:

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

image.png

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

1：为了使哈希表能进行动态的分裂，我们从桶0开始设定一个分裂点。

2：一个桶的容量为listSize = 5，当桶的容量超出后就从分裂点开始进行分裂。

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进行新哈希函数运算后，将产生如下的哈希表

image.png

5:虽然进行了分裂，但桶3并不是分裂点，所以桶3会将多出的key，放于溢出页.,一直等到桶3进行分裂。

6:进行分裂后，将分裂点向后移动一位。

一次完整的分裂结束。

key的读取:

采用h0对key进行计算。

如果算出的桶号小于了分裂点，表示桶已经进行的分裂，我们采用h1进行hash运算，算出key所对应的真正的桶号。再从真正的桶里取出value

如果算出的桶号大于了分裂点，那么表示此桶还没进行分裂，直接从当前桶进行读取value。

说明:

1:如果下一次key插入0、1、2、4桶，是不会触发分裂。（没有超出桶的容量）如果是插入桶3，用户在实现时可以自己设定，可以一旦插入就触发，也可以等溢出页达到listSize再触发新的分裂。

2:现在0桶被分裂了，新数据的插入怎么才能保证没分裂的桶能正常工作，已经分裂的桶能将部分插入到新分裂的桶呢?

只要分裂点小于桶的总数，我们依然采用h0函数进行哈希计算。

如果哈希结果小于分裂号，那么表示这个key所插入的桶已经进行了分割，那么我就采用h1再次进行哈希，而h1的哈希结果就这个key所该插入的桶号。

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

这也是为什么虽然是桶3的容量不足，但分裂的桶是分裂点所指向的桶。如果直接在桶3进行分裂，那么当新的key插入的时候就不能正常的判断哪些桶已经进行了分裂。

3:如果使用分割点，就具备了无限扩展的能力。当分割点移动到最后一个桶(桶3)。再出现分裂。那么分割点就会回到桶0，到这个时候，h0作废，h1替代h0, h2(key % 12)替代h1。那么又可以开始动态分割。那个整个初始化状态就发生了变化。就好像没有发生过分裂。那么上面的规则就可以循环使用。

3:线性哈希的论文中是按上面的规则来进行分裂的。其实我们可以安装自己的实际情况来进行改动。

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

可以考虑了以下方案：

1：为所有桶增加一个标志位。初始化的时候对所有桶的标志位清空。

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

   Linehash 实现代码如下:

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LineHash {
    
    public int pageSize;  //桶的容量

    public int overPoint = 0; //分裂点

    public int listSize = 4; //哈希表的初始大小

    public int initlistSize = 4; //哈希大小的记录值
     
    public int workRound = 1;  //分裂轮数
    
    public List> hash = null; //模拟哈希表

    public LineHash(int pageSIze) {
        this.pageSize = pageSIze;
        hash = new ArrayList>(4);
        for (int i = 0; i < listSize; i++) {
            hash.add(new HashMap()); //向哈希表中初始化桶
        }
    }
    //查询函数
    public String getKeyValue(int key){
        int index = hashFun(key, workRound); //根据分裂轮数调用不同的哈希函数
        if(index < overPoint){              //当前桶产生了分裂
            index = hashFun(key, workRound + 1); //采用新的哈希函数进行计算
        }
        return hash.get(index).get(key);
    }
    //添加函数
    public void addKeyValue(int key, String value) { 
        int index = hashFun(key, workRound);   
        if(index < overPoint){
            index = hashFun(key, workRound + 1);
        }
        Map map = hash.get(index);
        if (map.size() < pageSize) {   //判断当前桶是否满了
            map.put(key, value);
        } else {
            map.put(key, value);  
            splitHash();              //满了就进行分裂
        }
    }

    public int hashFun(int key, int f1) {
        return key % (4 * f1);
    }

    public void splitHash() {
        Map OldMap = hash.get(overPoint);   //旧桶
        Map NewMap = new HashMap(); //分裂产生的新桶

        Integer[] keyList = OldMap.keySet().toArray(new Integer[0]);
        for (int i = 0; i < keyList.length; i++) {  //准备移动一半的数据到新桶
            int key = keyList[i].intValue();
            int index = hashFun(key, workRound + 1);
            if (index >= listSize) {
                String value = OldMap.get(key);
                OldMap.remove(key);
                NewMap.put(key, value);
            }
        }
        hash.add(NewMap);  //将新桶放入哈希表
        listSize++;  //哈希表长度增加
        overPoint++;  //分裂点移动
        if(overPoint >= initlistSize){  //分裂点移动了一轮就更换新的哈希函数
            workRound++;
            initlistSize = initlistSize * 2;
            overPoint = 0;
        }
    }
}