06 Hash Tables
研究access methods，需要支持数据库执行引擎，怎么去文件页找到文件
- 一个就是哈希表，一个是树
java中的支持多线程并发读写的哈希表ConcurrentHashMap：
（Java ConcurrentHashMap：线程安全的哈希表实现_java 安全的map-****博客）：Java ConcurrentHashMap是线程安全的哈希表，采用分段锁、CAS操作和红黑树提高并发性能。从Java 8开始，内部实现进行优化，减少锁使用，适合高并发读写场景，如缓存系统、并发计数器和状态管理。
hash tables
一列是k，一列是v。但是不同于map，map不可重复键，hash可重复
hash特点：
- 空间复杂度：O(n)，线性增长
- 时间复杂度是：一般来说平均是O(1)常数，直接命中，最差的情况时间复杂度是O(n)，全冲突。
static hash table
假设有一个数组可以存下所有kv，一百个槽，一百个位置，取余取模就是一个最简单的hash函数
设计哈希表的时候需要面对的两个问题：
-
Design Decision #1：Hash Function：具体的哈希函数是怎么样的？
- 怎么设计将很大key范围的map放到一个key范围较小的哈希表中
- 哈希表本身也存在速度和哈希碰撞的问题，速度快的哈希函数会经常碰撞，速度慢的哈希函数不容易碰撞
-
Design Decision #2：Hashing Scheme：哈希函数的结构
- 怎么去解决哈希冲突
- trade-off between allocating a large hash table vs. additional instructions to find/insert keys【在直接使用一个大哈希表还是直接使用更多的指令集之间做抉择】：使用大的哈希表，空间换时间，占用更多的空间，来减少哈希冲突（一定程度）加快插入和查找的速度；使用小的哈希表但是使用更加密集的指令数量，虽然节省了内存，但是平凡的哈希冲突降低了性能，延长了插入和查找的时间，所以是在使用哈希函数的次数和内存空间之间做抉择
研究三个主要问题：
-
哈希函数
???? 对于任何输入的键，都应该返回该键的整数表示
???? 不要使用加密用的哈希函数，比如比特币的sha256、sha513、sha3啥的，这类哈希函数是无法反译的：
-
哈希的过程是会丢失信息的，在编译的过程中，随着哈希计算得到一个结果，我们不知道这个结果对应原来的数，但是可以通过反译进行反推猜测大概的结果。
-
但是加密的哈希函数不是这样的，它是如果我计算了，得到结果，永远不可能通过结果去推测原来的数，但是我可以通过给出一个相同的数进行计算还能得到一模一样不能反推的结果
公钥和私钥的算法就是用了sha256，这种算法是完全公开的，这种加密哈希函数就是你正着算能算出一个数，反着算就没办法算出以前他这个数可能是一个什么值
???? 需要一个哈希函数，它又快又不容易碰撞
???? 常用的哈希函数列表
- CRC-64：底层的通信和校验比较多，MD5也是如此
- MurmurHash
- Google CityHash
- Facebook XXHash
- Google FarmHash
-
-
静态的哈希数据结构
???? 开放地址哈希（开放定址法）：哈希冲突就放到下一个位置，放到最近的一个可以存放的位置；删除的时候也要向下找，但是连续的碰撞中如果删除一个，可能会导致后面的数据找不到了
- Approach #1：Tombstone(墓碑)：删除的时候在哪里立个墓碑，当找到墓碑这个位置的时候就知道，本来这个地方有个墓碑，但是由于删除还是修改操作消失了，你要找的值可能需要继续下推寻找
- Approach #2：Movement(整理)：删除或者修改之后，进行整理，这样的化就能在（例如都向上移动一格）这样就能在正确的位置找到了（要看具体的问题）可能数据结构是一个环形链表，使用环形链表的时候可能将第一个位置的数据上推到最后的位置，所以特殊问题需要特殊注意一下
在map中可能不存在重复的键，但是在数据库和哈希表中存在重复键的解决方法：
- Choice #1：Separate Linked List：在哈希中存储链表
- Choice #2：Redundant Keys：将键和值拼在一块作为键，这样就能保证不同（有点像cpp函数重写）
???? Robin Hood Hashing：基础结构还是开放定址哈希，除了键值之外还包含一个标志，表示它被推了几格，当出现哈希冲突的时候，会进行平均移动距离，使移动的距离相对来说更短一些（例如移动3格到一个移动1格的元素下面那么就会将这个一格的元素下推一格变成移动2格，然后移动3格的元素只需要移动两格就可以了）当哈希发生了冲突，Robin Hood Hashing通过重新排列冲突元素以便最长的键可以放置到合适的位置，从而减少平均查找时间
???? Cuckoo Hashing(杜鹃鸟哈希)：cuckoo 多个hash，占据，然后善后，以此类推，会有最大的抢占次数，达到次数之后表明哈希满了（需要深入了解）杜鹃鸟哈希存在的问题：数量有限；
引用：巨人肩膀：CMU15-445笔记-索引篇 - 知乎理解
CKCKOO HASH：为了减少冲突，还可以将多个hash函数和hash表组合起来。假设有两个hash函数hash1、hash2，和两个hash表t1、t2，其插入的流程如下：
- 插入A，首先计算key1 = hash1(A)，若table1中key1位置为空，直接插入；否则
- 计算key2 = hash2(A)，若table2的key2位置为空，直接插入；否则
- 置换A和table2的key2中的元素B，此时问题便变成了插入B
- key1’ = hash1(B)。查看table1的key1‘位置是否为空，如果为空插入。否则置换
如上步骤最后就像乒乓球一样，在table1 table2中来回置换。这种方法的问题就是最后可能造成死循环。
-
动态的哈希数据结构
在开设这个静态哈希表的时候我们需要知道未来最多存了多少数据，如果估计不了未来的最多数据，那么未来扩展会比较麻烦。没有办法根据我们的需求设置一个静态的哈希，所以使用一个动态的哈希结构
???? Chained Hashing：（拉链式、链条式）方法就是在哈希的时候设置hash slot哈希槽，在插入数的时候经过哈希槽，然后哈希槽存储一个指针，指向对应的哈希桶（这个桶存储了很多对数据，存储的数据结构可能是数组/向量vector，可能是链表），然后如果出现了碰撞就接着往这个桶中的下一个位置放，放满了之后就再这个放满的桶之后接一个指针，在第二个桶接着存放；在java中hashmap是使用array+list/RBTree，使用数组存放位置，后面的桶只存放一个元素，作为一个纯链表，当这个数据过大到一定程度的时候就变为红黑树的数据结构（大于8转化？）
???? Extendible Hashing：（可扩展哈希）类似于IP地址的划分方式0、10、11，分为局部深度local和全局深度global，这两个深度确定扩展，如图如果选用全局深度为2，那么全局就有00、01、10、11四个桶，在填充桶的时候全局深度会赋值给局部深度，用于记录局部深度填充数据时候的全局深度，当某一个桶满了，就会进行桶分裂，在当前的桶不能存放下四个元素的时候分裂为两个桶，同时deep+1，存放这四个元素的桶和全局深度一起加到了3，全局深度下对应二进制为000、001、010、011、100、101、110、111八个，这时候只需要将需要分裂的桶 重新整理就好了，其余的桶保持原来的深度不变，本地深度就是用来干这个的，因为没有整理本地深度确定了前面集为相同即可
???? Linear Hashing：（线性哈希）渐进式哈希，在一个（key%N）的哈希中，有一个分家指针；当产生哈希冲突并且对应哈希冲突的桶无法容下新元素的时候，将当前元素前面的所有元素分家，前面所有对应key都加一个桶，加的桶使用新的哈希函数（key%2N）进行第二次存储，分家指针后面的元素保留使用原来的（key%N）哈希函数（慢速增加槽，减少单点延时）
巨人肩膀：这样会提高性能，因为假如没有分家指针这个东西单纯的用两个哈希函数，那么你每个单点查询可能都会去找两次，而用了分家指针你就能很快的辨别出哪部分是需要再分家的