Lecture #07: Hash Tables

2023-11-19

CMU15-445

CMU15-445, 数据库

refer to Note

refer to Slides

refet to courses

cover

1. Data Structure
2. Hash Table
3. Hash Function
4. Static Hashing Schemes
5 Dynamic Hashing Schemes

1. Data Structure

DBMS 主要包括以下几种数据

Internal Meta-Data : 记录有关数据库和系统的信息
Core Data Storage : 记录 tuple 的信息
Temporary Data Structures
Table Indices

主要考虑以下两个问题

数据组织
数据的可靠性

2. Hash Table

hash_table

hash_table_target

Hash Function

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

Hashing Scheme

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

3. Hash Function

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

Hash_Function

Hash_Function bench_mark

4. Static Hashing Schemes

4.1 Linear Probe Hashing

线性探针

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

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

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

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

存储相同的值

NON-UNIQUE-KEY

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

对于每个 key 他们的 value 开辟出来一个单独的空间
所有的 key 都用哈希函数散列在一个存储空间中。

4.2 Robin Hood Hashing

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

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

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;
     }
}