[CMU15445] 07 - Hash Tables

哈希表在数据库中也是经常被用到的数据结构，可以用哈希表来构建索引，组织底层文件，以及通过在内存中建立临时的哈希表结构来辅助完成操作

对于一个哈希表，会预先分配一定数量的bucket，每个bucket可以存放n条记录，当一个<key,value>要插入表中时，会将key放入hash函数，将结果mod bucket的数量，就可以得到该kv对存放的位置，如果一个bucket已经满了，常见的一种做法是通过链表的形式在后面添加溢出桶

image-20221203123719593

HashFunction的选择

hashfunction要满足以下两个特点

• random：哈希函数需要让每个bucket中分配相同数量的记录，例如将人的收入按范围分成十个bucket(0-9999, 10000-19999 .... 90000-99999)，这个hash函数是uniform的，因为每个分段都有相同的key的数量，但是不是random的，因为工资在4w-6w的人会比工资在0-3w的人多的多，这样会导致某个bucket里面有过多的记录
• uniform：哈希函数需要为每个bucket都分配相同的key的数量，例如如果一个hashtable有26个bucket，按照key首字母的值来将它分配到某个bucket，那么这个hash函数就不是uniform的，因为以B开头的单词会比以X开头的单词多得多

如何处理溢出

主要有两种方法：

• open addressing：在某个bucket满后，不去添加额外的溢出桶，而是在其他的空桶中寻找一个位置插入，通常的做法是使用下一个bucket，这在数据库中不常用，因为对于删除操作非常不友好，但是在编译原理中生成符号表时会使用，因为符号表基本只有插入和查找操作
• close addressing：在某个bucket满后，添加一个额外的溢出桶来存放，在查找时还需要查找这些溢出桶，如果溢出桶的数量过多就会导致性能下降，此时需要将哈希表扩容并对所有的record进行rehash

Static Hashing

static hasing是指slot的数量是预先分配好的，不会动态增长，当哈希表中记录的数量达到一定阈值时，就会将slot的数量翻倍，对所有的值进行rehash

Linear Probe Hashing

linear probe hashing通过线性的为一条记录寻找下一个可用的位置来解决冲突，它将整个hash table看成一个环，在查找时，会首先将key经过hash函数找到对应的位置，如果两个key不一样就会线性的寻找下一个位置，插入和查找类似

image.png

对于删除来说，不能直接删除，否则会影响后续的查找和插入，需要在原来的位置上使用一个tomestone的标记，来表明这个地方原来有记录，但是被删除了

image.png

ROBIN HOOD hashing

对于上面的linear probe hash，可能一个key已经偏离了它hash出来的位置很多，此时如果要线性查找，效率会很低，Robin hood hasing 便是对这个问题的一个改进，他会使得每个key都离原来的hash的位置差不多的距离，它的核心思想就和他的名字一样，劫富济贫。

它为每个记录保存一个值dis，表示它离hash出来的位置的距离，dis越小说明越富有，反之越穷，假设插入一个keyA，dis=0当发送碰撞的时候，会比较碰撞的位置的值，如果disB > disA，则A继续往下搜索，如果disB < disA,则A会抢了B的位置，让B往下去找别的位置，长远来看这样会让每个key都有平均且较小的dis，也就避免了一个key离原来的位置非常远的情况

image.png

CUCKOO Hashing

对于上面的两种方法来说，查找在最坏的情况下都会变成O(n)，而cuckoo hashing对于查找和删除来说都是O(1)的

对于每一个key，都会使用相同的hash函数，但是不同的seed来做hash，如下图，这个条记录可以存储在这两个地方的任何一个位置

image.png

当有一个B插入时，它也会做两次hash，发现一个位置被A占了，它就占另一个

image.png

image.png

当C被插入时，发现自己的两个位置都被占了

image.png

C选择把B的位置抢掉，让B重新去找个位置

image-20221203142637534

B发现自己的位置都被占了，又把A的位置抢了

image-20221203142734254

导致A重新找了个位置

image-20221203142749091

由上面可以看去，虽然对于删除和查找来说都是O(1)，但是对于插入来说，可以会不断触发这种调整导致效率下降

Dynamic Hashing

Dynamic Hashing可以按需扩容，而不需要整个重新申请空间，并且将所有的key rehash

Chained Hashing

将每个hash slot对应到一个bucket，对于映射到同一个slot上面的key，存放在对应的bucket中，当bucket满后添加溢出桶，感觉就是最普通的hash table的实现

image-20221203143711820

Extendible Hashing

extendible hashing通过将桶分裂和聚合来处理数据的增长和减少，对于一个hash table会给表中的每一项分配一个例如32bit标识符(可以表示2³²个bucket)，但是开始不会全部用到，也就不需要预先分配这么多空间，hashtable有一个prefix来指明当前整个hash table需要用到多少个bit来表示

image-20221203144214676

例如下图所示，当前hash table需要用两个bit来考虑一条记录存放到哪里，第一位0开头的都去1号bucket，10的去2号bucket，11的去3号bucket

image-20221203144647696

随着插入，2号bucket满了，就会将这个bucket一分为二，并且把它们的prefix加一，原来2号bucket都是10开头的元素，在一分为二后，100开头的去2号，101开头的去3号(原来的3号存放11开头的我们叫做4号),并且去更新hash table的prefix，hash table的prefix是所有bucket prefix的最大值

image-20221203144822512

把2号分裂后，就会得到如下所示

image-20221203145141665

因为在分裂2号时，其他的bucket仍然可以正常工作，所以对于不映射到2号bucket的查询，hash表仍可以正常工作