数据库管理系统中的哈希表详解

数据库管理系统中的哈希表详解

引用

CSDN

1.

https://m.blog.csdn.net/qq_31179577/article/details/136924627

哈希表是数据库管理系统（DBMS）中一种重要的数据结构，它支持快速的查找操作，时间复杂度为O(1)。本文将详细介绍哈希表在DBMS中的应用，包括数据结构、设计考虑、静态哈希表、哈希函数、静态哈希方案、动态哈希方案等多个方面。

1. 数据结构

DBMS内部使用多种数据结构来实现不同的功能：

• 内部元数据：例如页目录（Page Dictionary）或页表（Page Table），使用哈希结构，将页ID映射到磁盘中页的位置或缓冲区中的位置。
• 核心数据存储：例如索引组织的表，其中实际的元组存储在B+树的叶节点中。
• 临时数据结构：用于执行查询时生成临时数据集合，以更有效地执行查询，例如在哈希连接中动态建立的哈希表。
• 表索引：用于快速定位表中的数据。

2. 设计考虑

在设计哈希表时需要考虑以下因素：

• 数据组织：如何在内存/页面中布局数据结构以及存储哪些信息以支持高效访问。
• 并发性：如何让多个线程同时访问数据结构而不引起问题。

3. 哈希表

哈希表是一种无序关联数组，使用哈希函数将键映射到值。其空间复杂度为O(n)，平均时间复杂度为O(1)，最坏情况下的时间复杂度为O(n)。

3.1 静态哈希表

静态哈希表假设元素数量提前已知并固定，使用一个巨大的数组存储元素。通过将元素键的哈希值与数组大小N取余，可以得到其在数组中的偏移量。实际中通常存储的是指向其他地址的指针，该指针所在的结构中存储着key和其对应的值。

不切实际的假设包括：

• 元素数量提前已知并固定
• 每个键都是唯一的
• 完美的哈希函数保证不会发生冲突

3.2 哈希函数

DBMS中常用的哈希函数包括：

• CRC-64 (1975)：用于网络中的错误检测。
• MurmurHash (2008)：设计为快速、通用的哈希函数，Redis也是用的它。
• Google CityHash (2011)：设计针对短密钥（<64字节）更快。
• Facebook XXHash (2012)：来自zstd压缩的创建者。
• Google FarmHash (2014)：CityHash的新版本具有更好的碰撞率。

3.3 静态哈希方案

3.3.1 线性探针哈希

线性探针哈希是一个巨大的表（可以看作是一个巨大的环形缓冲），通过线性搜索表中的下一个空闲槽来解决冲突。当表满时，需要崩溃或扩容。

示例：

1. 插入元素A时，计算哈希值并存储key和value。
   

2. 插入元素C时，与元素A的插槽冲突，需要向后扫描找到最近的空槽。
   

3. 删除元素C时，使用墓碑（Tombstone）标记，而不是直接删除，以避免扫描问题。
   

4. 处理不唯一键的方法：

• 单独的链表：将每个键的值存储在单独的存储区域中。
• 冗余键：将重复的键的条目一起存储在哈希表中。

优化点：

• 基于键的类型和大小的专用哈希表实现。
• 将元数据（如墓碑）信息存储到一个单独的数组中。
• 使用表版本+槽版本控制元数据快速使哈希表中的所有条目失效。

3.3.2 布谷鸟哈希

布谷鸟哈希使用多个哈希函数，在哈希表中查找多个位置来插入记录。插入时，检查多个位置并选择空的位置。如果所有位置都被占用，则驱逐其中一个元素并重新散列。

示例：

1. 插入元素A时，根据哈希函数计算两个候选槽位。
   

2. 选择一个位置插入元素A。
   

3. 插入元素B时，选择空槽进行插入。
   

4. 插入元素C时，如果所有位置都被占用，则驱逐元素B，然后重新散列。
   

5. 如果陷入无限循环，则需要将哈希数组扩容并进行rehash。

3.4 动态哈希方案

动态哈希表根据需要逐渐调整自身大小，不需要提前知道元素数量。

3.4.1 链式哈希

为哈希表中的每个槽维护一个存储桶的链表，通过将具有相同哈希键的所有元素放入同一个桶中来解决冲突。

示例：

1. 简单的插入元素A，B。
   

2. 当出现冲突时，通过链来解决。
   

3. 可以在bucket中放入一个Bloom过滤器来协助过滤。
   

Bloom过滤器是一个概率数据结构，用于回答集合成员关系查询。它可能会产生假阳性，但不会产生假阴性。

3.4.2 可扩展散列

链式哈希方法逐步分割存储桶，而不是让链表永远增长。多个槽位置可以指向同一个桶链。在拆分时重新洗牌存储桶条目并增加要检查的位数。

示例：

1. 初始化时全局ID = 2，控制全局Bucket数组的大小和哈希结果的有效位。
   

2. 当桶列表满了时，需要将全局ID从2增加到3，并拆分为两个本地ID = 3的桶列表。
   

3.4.3 线性哈希

哈希表维护一个指针，用于跟踪下一个要拆分的桶。当任何桶溢出时，在指针位置分裂桶。使用多个哈希来查找给定键所在的正确存储桶。

示例：

1. 初始化时桶列表长这样。

2. 查询元素时，需要哈希计算后找到对应的桶列表，在内部做扫描查询。

3. 插入元素时，如果桶列表满了，则需要进行溢出处理。
   

4. 进行溢出处理时，需要新增一个槽位，并对元素进行rehash。
   

5. 拆分指针会继续向下移动，直到到达所有溢出的桶。

6. 查询元素时，需要计算两次哈希，以找到正确的插槽。
   

7. 当拆分指针到达最后一个槽时，删除第一个哈希函数并将指针移回到开头。

8. 如果拆分指针下方的“最大”的桶为空，则哈希表可以将其删除，并沿相反方向移动拆分指针。

示例：

1. 删除元素20时，拆分指针位于插槽1处。
   

2. 通过计算找到元素20位于插槽4，删除后需要删除最大的插槽及其桶数组，并将拆分指针向上移动。

3.4 结论

哈希表是支持O(1)查找的快速数据结构，在整个DBMS内部都有使用。但是哈希表通常不是用于表的索引。