Sep 25, 2022
CMU 15-445: 3. Hash Table
3. Hash Table
[CMU-15-445 Lecture 6 Hash Tables - 知乎 (zhihu.com)
3.1. Hash Function
3.2. Hash Scheme
3.2.1. static hash scheme
3.2.1.1. 线性
3.2.1.2. Robin Hood Hashing
- 不清晰，需要学习一下
3.2.1.3. Cuckoo Hashing
- 多个 hash 表，对应不同的 hash function
上述谈论的 3 种方案都是静态哈希，这就意味着哈希表的大小是固定的，我们必须提前知道我们想要保存的 key 的大概数量，这样才能知道如何分配空间使得其足够容纳并能最小化哈希碰撞。但是现实没有那么理想，一旦超过容量，就要扩容。扩容并非是直接 append 一段内存，一般来说得重建整个哈希表并迁移。当我们谈到分布式数据库时我们还会谈到一致性哈希算法，这个算法无需调整大小（令人期待的算法）。但是对于单机数据库中的哈希表，我们还是得重新构建，这也是动态的哈希所要解决的问题。
3.2.2. dynamic hash scheme
3.2.2.1. Chained Hashing
3.2.2.2. Extendible Hashing
- 妙，但不好理解。多看看
3.2.2.3. Linear Hashing
3.2.3. 布隆过滤器
- 这篇文章写的很好