哈希表

技巧💡

哈希表可以快速的查询我们想要的元素。 比如HashMap、hashtable等实现。在很多地方，都有使用到。比如pagetable或者page directory时，其实他们就是一个hashtable，我们通过传入一个page id就能找到对应的frame，或者传入一个page id就能找到磁盘中对应的位置。

哈希函数 §

• 哈希结果，尽可能减少占用存储。 任意的key映射到一个较小范围的interger
• 减少哈希碰撞，即减少不同的key，生成相同的hash结果
• 速度要快，这里涉及到 是否需要加密。一般情况下，都是不需要进行加密的

完美哈希函数💡

即任意key映射，都不会产生相同的哈希结果。很明显这个是不可能的会有这种结果的。

目前各 DBMS 主要在用的 Hash Functions 包括：

• MurmurHash (2008)
• Google CityHash (2011)
• Facebook XXhash(2012) 一般来说，足够好用.比MurmurHash更快。 clickhouse 内置
• Google FarmHash (2014)
• CLHash (2016)
• MD5,速度太慢，并且不安全，可通过彩虹表破解

XXhash是上面这些hash函数中速度最快且碰撞率最低的函数

哈希冲突解决方案 §

静态哈希方案(需要预判最终数据量大小) §

线性探测法 §

技巧💡

threadlocal中，就是使用线性探测法。当前位置冲突了，直接找下一个位置。

A、B都经过hash函数计算后放入到了空的位置，但是C经过计算后发现被A占领了，没办法，C选择占用A下面的位置。

1. 添加时，冲突怎么解决？
   1. 找到下一个位置
2. 如何删除？
   1. 墓碑法解决：C被删除后，会在原位置上添加一个墓碑标记，防止查找D的时候，找到一个空的位置，误以为D不存在。
   2. 数据移动法解决：移动后我们就能通过hash函数顺利的找到元素了。

罗宾汉Hash法(劫富济贫，) §

Robin Hood Hashing 是 Linear Probe Hashing 的变种，为了防止 Linear Probe Hashing 出现连续区域导致频繁的探查操作。
让每个key尽可能靠近原来的位置

即每次比较的时候，同时需要比较每个 key 距离其原本位置的距离（越近越富余，越远越贫穷），如果遇到一个已经被占用的位置（slot），如果它比自己富余，则可以直接替代它的位置，然后把它顺延到新的位置。

动态哈希方案(按需扩容) §

链式地址法(#### Chained Hashing) §

Chained Hashing 是 动态哈希表 的小案例级别的实现，每个 key 对应一个链表，每个节点是一个 bucket，装满了就再往后挂一个 bucket。需要写操作时，需要请求 latch。

缺点: 最坏情况下，Hash Table 可能降级成链表，使得操作的时间复杂度降格为 O(n)。java的HashMap超过一定的数量，就会转换成红黑树。

Extendible Hashing（扩展哈希表） §

基本思路是一边扩容，一边重置哈希表。
Ps：感觉这样的算法很像计算机网络中的IP地址子网掩码，有点像划分子网的感觉。全局计数器就像子网划分掩码，决定了多少位是网络位，多少位是主机位。

扩容:
增加了全局计数器的位数，这样原来的值都需要进行重新rehash.

Linear Hashing（线性散列） §

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