講座＃07：哈希表

1. 数据结构#

DBMS 主要包括以下几种数据

内部元数据：记录有关数据库和系统的信息
核心数据存储：记录元组的信息
临时数据结构
表索引

主要考虑以下两个问题

数据组织
数据的可靠性

2. 哈希表#

哈希表

哈希表目标

哈希函数

将值转化为一个较小的键
在速度和碰撞率之间进行权衡。

哈希方案

如何处理碰撞的情况
需要在哈希表大小与额外信息维护之间权衡

3. 哈希函数#

不管输入的键是什么，输出一个特别的数字的函数。

哈希函数

哈希函数基准

4. 静态哈希方案#

4.1 线性探针哈希#

线性探针

我们解决哈希冲突的方法是，如果我们的哈希函数返回的位置已经被占用了，那么则一直向下取一个位置，直到找到表中空的值。

在删除操作中，可能会出现一种情形，有的值并不是哈希函数产生的直接值，而是通过一直取下一个位置得到的值。

在这种情形下，我们所采取的方法有。

将受到偏移影响的值往回调整。通过重新哈希的方式进行调整。效率比较低下。
将那些删除了的值标记为已删除。这些值可以在新的值需要使用的时候重新利用。不过需要周期性的垃圾回收。

存储相同的值

非唯一键

存储相同的键但有不同的值的值的时候，我们可以有两种办法解决。

对于每个键，它们的值开辟出一个单独的空间
所有的键都用哈希函数散列在一个存储空间中。

4.2 Robin Hood 哈希#

这是线性探针算法的一个升级版，旨在解决分布不均的问题。在上面的算法中，可能存在一些键，经过哈希计算后可能会聚集在一块导致哈希算法劣化。 Robin Hood 哈希解决冲突的方式会将部分富有的键分配给贫穷的键。

这种避免哈希碰撞的方法是，给每个值都记录一个偏移值，表中的每个值在向下搜索的时候，需要和表中的值进行对比。如果当前偏移值比表中值的偏移值大，那么则将当前值和表中值进行替换。直到找到空位结束。

void Robin_hood_Hashing(int key) {
     int val = hash(key);
     int offset = 0;
     for (int i = val ; ; i ++ , offset ++ ) {
          if(hash_table->is_empty(i)){ 
               hash_table->insert(i , val , offset);
               break;
          }

          if(hash_table->get_offset(i) < offset) {
               auto [n_val , n_offset] = hash_table->get_data(i);
               hash_table->insert(i , val , offset);
               val = n_val , offset = n_offset;
          }
          if(i == MAXSIZE) i = 0;
     }
}