# Hash Tables

本节开始之前，先看一下目前课程的进度状态：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZm-dCZw2aX5oghZvtx%2F-LZlixmK1o4A-8LSbzNf%2FScreen%20Shot%202019-02-28%20at%209.33.02%20AM.jpg?alt=media\&token=da63e291-f8ce-435a-b295-dc76db7b39ec)

为了支持 DBMS 更高效地从 pages 中读取数据，DBMS 的设计者需要灵活运用一些数据结构及算法，其中对于 DBMS 最重要的两个是：

* Hash Tables
* Trees

它们可能被用在 DBMS 的多个地方，包括：

* Internal Meta-data
* Core Data Storage
* Temporary Data Structures
* Table Indexes

在做相关的设计决定时，通常需要考虑两个因素：

* Data Organization：如何将这些数据结构合理地放入 memory/pages 中，以及为了支持更高效的访问，应当存储哪些信息
* Concurrency：如何支持数据的并发访问

## Hash Tables

Hash Table 是 associative array/dictionary ADT 的实现，它将键映射成对应的值。简介这里不再赘述，可参考[ MIT 6.006 Dictionary Problem & Implementation](https://zhenghe.gitbook.io/open-courses/mit-6.006/dictionary-problem-and-implementation)。

Hash Table 主要分为两部分：

* Hash Function：
  * How to map a large key space into a smaller domain
  * Trade-off between being fast vs. collision rate
* Hashing Scheme：
  * How to handle key collisions after hashing
  * Trade-off between allocating a large hash table vs. additional instructions to find/insert keys

### Hash Functions

由于 DBMS 内使用的 Hash Function  并不会暴露在外，因此没必要使用加密（cryptographic）哈希函数，我们希望它速度越快，collision rate 越低越好。目前各 DBMS 主要在用的 Hash Functions 包括：

* [MurmurHash (2008)](https://github.com/aappleby/smhasher)
* [Google CityHash (2011)](https://github.com/google/cityhash)
* [Google FarmHash (2014)](https://github.com/google/farmhash)
* [CLHash (2016)](https://github.com/lemire/clhash)

### Hashing Scheme

#### Linear Probe Hashing

Linear Probe Hashing 的主要原理在 MIT 6.006 中已经介绍，这里不赘述。

当 keys 可能出现重复，但 value 不同时，有两种做法：

1. Separate Linked List
2. Redundant Keys

如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZm-dCZw2aX5oghZvtx%2F-LZloXTbn2KUJdCZ5iDf%2FScreen%20Shot%202019-02-28%20at%209.57.22%20AM.jpg?alt=media\&token=c2f6ac8c-b0ae-489a-86ea-6e7387df9a7c)

通常为了减少 collision 和 comparisons，Hash Table 的大小应当是 table 中元素量的两倍以上。

#### Robin Hood Hashing

Robin Hood Hashing  是 Linear Probe Hashing 的变种，为了防止 Linear Probe Hashing 出现连续区域导致频繁的 probe 操作。基本思路是 “劫富济贫”，即每次比较的时候，同时需要比较每个 key 距离其原本位置的距离（越近越富余，越远越贫穷），如果遇到一个已经被占用的 slot，如果它比自己富余，则可以直接替代它的位置，然后把它顺延到新的位置。

#### Cuckoo Hashing

（略）

### 小结

以上介绍的 Hash Tables 要求使用者能够预判所存数据的总量，否则每次数量超过范围时都需要重建 Hash Table。它可能被应用在 Hash Join 的场景下，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZm-dCZw2aX5oghZvtx%2F-LZm-oH5M7QtWAd6rdjS%2FScreen%20Shot%202019-02-28%20at%2010.50.56%20AM.jpg?alt=media\&token=baa94ccd-cc5d-41c9-90d6-f9dc786d3461)

由于 A, B 表的大小都知道，我们就可以预判到 Hash Table 的大小。

## Dynamic Hash Tables

与 Static Hash Tables 需要预判最终数据量大小的情况不同，Dynamic Hash Tables 可以按需扩容缩容，本节主要介绍 Chained Hashing，Extendible Hashing 和 Linear Hashing。

### Chained Hashing

Chained Hashing 是 Dynamic Hash Tables 的 HelloWorld 实现，每个 key 对应一个链表，每个节点是一个 bucket，装满了就再往后挂一个 bucket。需要写操作时，需要请求 latch。

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZm-dCZw2aX5oghZvtx%2F-LZm1nxoABpPpsTAZUoj%2FScreen%20Shot%202019-02-28%20at%2010.59.44%20AM.jpg?alt=media\&token=8e479c62-7875-4117-bec5-96b1990e0c15)

这么做的好处就是简单，坏处就是最坏的情况下 Hash Table 可能降级成链表，使得操作的时间复杂度降格为 $$O(n)$$ 。

### Extendible Hashing

Extendible Hashing 的基本思路是一边扩容，一边 rehash，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZm-dCZw2aX5oghZvtx%2F-LZm3RAyswk-XP1ucR0t%2FScreen%20Shot%202019-02-28%20at%2011.06.50%20AM.jpg?alt=media\&token=516c091b-732f-408d-8846-13965cfb551a)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZm-dCZw2aX5oghZvtx%2F-LZm3dmy1q873AKttSwl%2FScreen%20Shot%202019-02-28%20at%2011.07.47%20AM.jpg?alt=media\&token=085ff0b4-2892-425b-8402-81805be6e720)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZm-dCZw2aX5oghZvtx%2F-LZm3tcLbF38x4TxrOTC%2FScreen%20Shot%202019-02-28%20at%2011.08.47%20AM.jpg?alt=media\&token=5e29616b-af2a-4f6d-9f3e-bf0b4261b4f3)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZm-dCZw2aX5oghZvtx%2F-LZm431TmIL6e5dRFRKs%2FScreen%20Shot%202019-02-28%20at%2011.09.34%20AM.jpg?alt=media\&token=49b3a2ad-dbb0-46bf-b7ca-0dc527499def)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-LZm-dCZw2aX5oghZvtx%2F-LZm49uT7iKIa7MNhOZ3%2FScreen%20Shot%202019-02-28%20at%2011.10.02%20AM.jpg?alt=media\&token=e3352e28-5e49-4fa5-ba6a-ac2fe2f6e359)

### Linear Hashing

基本思想：维护一个指针，指向下一个将被拆分的 bucket，每当任意一个 bucket 溢出（标准自定，如利用率到达阈值等）时，将指针指向的 bucket 拆分。

## 总结

Hash Tables 提供 $$O(1)$$ 的访问效率，因此它被大量地应用于 DBMS 的内部实现中。即便如此，它并不适合作为 table index 的数据结构，而 table index 的首选就是下节将介绍的 B+ Tree。

## 参考

[slides](https://15445.courses.cs.cmu.edu/fall2018/slides/06-hashtables.pdf), video