什么是动态哈希
动态哈希，顾名思义，是与静态哈希对应的。
数据库文件系统中的哈希，需要两个要素：bucket和哈希函数。bucket是用来存储数据的，而哈希函数则可以将查询的key映射成它在bucket里的地址。静态哈希的哈希函数，同样的key值永远映射出唯一的地址值。这里就有一个很明显的问题，如果出现了哈希碰撞，bucket就会溢出。当然，这个问题是可以解决的。
两种方式：
-
链表
将拥有相同地址的值以链表串联起来
链表方式处理溢出 -
线性探测（开放定址法）
如果说哈希函数计算出的地址有冲突，那么就存到bucket里下一个空白的位置。
线性探测
静态哈希最大的缺点就是不能根据数据库数据大小增长或缩减。动态哈希能解决这个问题，动态哈希可以根据需求增减bucket，所以也叫extendable hashing。
动态哈希
动态哈希比起静态哈希，首先，哈希函数能产生的哈希值量很大，但是哈希值只会取一部分（前缀或后缀）来使用；其次，会记录每个record到底使用了哈希值的多少位（前缀或后缀）。当有冲突发生的时候，会拆分bucket，同时增加此bucket里所有的record使用哈希值的位数来解决冲突。
用例子说话：
下面是用一个哈希函数产生的key和哈希值的对应关系。
我们现在使用2位后缀的哈希值，假设一个bucket能存两条记录，那么现在的hash table的状态就是这样
现在要插入key = 9的值，hash值是10001，需要放入bucket 1，但是bucket 1已经满了，这时就需要拆分bucket 1。
我们把bucket 1所存的record使用的哈希值位数增大为3，可以看到，其他的bucket的状态并没有改变。这样，后缀同为001的5和9存到bucket 1中，而后缀为101的6则存到了bucket 5。
Postgres dynamic hash table
pg的动态哈希表既可以支持单个backend使用又可以支持在共享内存中跨backend使用。使用动态哈希表时，需要调用者来管理锁的问题。如果单个LWLock会造成性能瓶颈的话，pg也支持分片上锁，可以用多个锁分别锁住哈希表的各个部分，称为partitioned模式，需要在hash表创建的时候传入HASH_PARTITION这个flag。
几个相关函数
hash_create
创建新的动态hash表。对于跨backend使用的hash table，本地只需要存一个header，剩下的部分都在共享内存中。
ShmemInitHash
创建共享内存的hash table的函数。
注意⚠️ 在共享内存中，hash table的大小是不能动态增加的，需要调用hash_select_dirsize一次性把最大size分配好。
insert/remove/find
所有的hash表操作都是通过hash_search/hash_search_with_hash_value这个函数进行操作的。通过action这个参数来指定本次调用的操作。
首先，任何操作都会根据传入的key先找到bucket的地址。
- insert(HASH_ENTER) 如果key已经存在于哈希表中返回bucket的地址，由调用者将数据写入。否则，在表中创建这个key。
- remove(HASH_REMOVE) 将bucket插入freelist
- find(HASH_FIND) 直接返回地址
update
hash_update_hash_key函数
具体操作就是先删除bucket，再创建一个新的key，把旧的数据拷贝过去。但是和先调用remove再调用insert这种方式的不同之处，在于bucket不需要进入freelist，直接复用内存。
seq scan相关函数
hash_seq_init/hash_seq_search/hash_seq_term
是对哈希表进行seq scan的函数。
pg对于正在进行的所有hash tables的seq scan都有记录，而且seq scan的数量不能超过MAX_SEQ_SCANS的设定值（100）。
expand_table
增加新的bucket，或者说split bucket。
有以下几个条件：
- 如果是partitioned mode的表，那么不能split
- 如果目前表是frozen状态，不能split
- 如果正在有seq scan操作发生在这张表上，不能split
具体split的操作方法和上文提到的类似。
hash function
除了调用者可以传递进来hash function之外，pg还提供几个默认的hash function，例如uint32_hash和tag_hash以及string_hash。其中tag_hash是为固定大小key值的函数。虽然uint32/int32这种值也可以用tag_hash，但是pg仍然创建了uint32_hash，比tag_hash更快。
compare函数
调用者可以传入match函数用于hash值的比较，否则就用pg默认的函数。如果是string_hash，就用string_compare，否则就用默认的memcmp直接比较内存。
