图解PostgreSQL Dynamic Chained Hash Tables
PostgreSQL提供了一簇Dynamic Chained Hash Tables的接口，具体接口定义在src/backend/utils/hash/dynahash.c，采用了Linear Hashing的方式处理冲突，具有良哈的处理性能和简单的逻辑设计。提供了hash_create，hash_destroy，hash_search等一系列函数，相比较Linux的hsearch/hcreate/hdestroy，这里的Hash Table可以无限制地增长超过其原始大小。
Dynamic Chained Hash Tables，由HTAHCTL，HTAB，HASHHDR，HASHDIR，HASHSEGMENT，HASHBUCKET，HASHELEMENT，6种结构构成。
HTAB结构存储在本地，是由于此结构存在函数指针，函数指针指向进程私有的函数栈。
分析Hash Table算法时，主要是分析Hash Table的结构，Hash Table的生成、查找、删除、销毁以及哈希冲突的处理。
Hash Table的结构
HASHCTL : 生成Hash Table的参数的数据结构，在建立Hash Table时设置不同属性，储存在栈上，执行完函数后即被释放。可以分为Hash Table属性和函数指针：
num_partitions，分区数量，主要是指的是锁分区的数量。如果Hash Table较大，且存在并发操作，使用一把锁来处理Hash Table的增、查、删、改将严重影响性能，通过分区来减少锁粒度，提高性能，数量必须是2的幂，当前默认使用的是NUM_BUFFER_PARTITIONS ；
ssize，每个segment中的bucket数量；
dsize，segment的数量；max_dsize，dsize的最大值，也就是segment数量的最大值；
keysize，key的长度；entrysize；value的长度，一般设置HASH_ELEM的flag后，entry是包含key和value两部分，因此entrysize是包含key和value两部分的size；
hash，计算key的hash value的函数指针；match，比较key的函数指针；keycopy，key复制使用的函数指针；alloc，内存分配的函数指针；
hcxt，用来分配Hash Table内存区域；
hctl，指向共享内存的HASHHDR的指针；
HTAB : 存储Hash Table元数据的结构体，储存在本地Memory Context中，Hash Table销毁时释放。可以分为Hash Table属性和函数指针：
htcl，指向HASHHDR结构体；
dir，指向Segment数组的首地址，一般是放在HASHHDR结构体后面申请；
hash，match，keycopy，alloc，同HASHCTL，根据flags，由HASHCTL复制而来；
hcxt，同HASHCTL，根据flags，由HASHCTL复制而来；
tabname，Hash Table的名称，能够在日志信息显示精确的信息；
isshared，是否在共享内存中；
isfixed，是否不允许动态改变大小；
frozen，是否不允许插入数据，在共享内存中是不会为true的；
keysize，同HASHCTL，由HASHCTL复制而来；
ssize，同HASHCTL，由HASHCTL复制而来；
sshift，sszie的指数，由HASHHDR复制而来；
HASHHDR : 存储了所有可变属性的结构体（也包含固定值的属性），在本地模式中，存储在本地Memory Context中，Hash Table销毁时释放，在功能上和HTAB没有任何区别；在共享模式中，存储在Shared Memory中，在实例退出时释放，部分可变属性此时无法被修改。可以分为可变属性和不可变属性：
freelist，Hash Table建立时将指向所有的元素。如果Hash Table是分区的，那么freelist同样将分为NUM_FREELISTS个freelist，且每个freelist都有自己的mutex，用来提高并发效率；
dsize，同HASHCTL，由HASHCTL复制而来；
nsegs，已分配的segment数量，小于等于dsize；
max_bucket，使用过的bucket ID的最大值；
high_mask将掩码转换为对整个表的模运算;
low_mask，将掩码转换为对表的下半部分的模运算;
keysize，entrysize，num_partitions，max_dsize，ssize，同HASHCTL，由HASHCTL复制而来；
sshift，sszie的指数（Hash Table中有大量的MOD运算，为了能够高效的计算，所有数字必须是2的幂，这样可以通过&和|运算）；
nelem_alloc，当发生扩充时，一次性申请的元素数量；
HASHDIR，HASHSEGMENT的指针，Dir是Segment数组的首地址；
HASHSEGMENT，HASHBUCKET的指针，Segment是Bucket数组的首地址；
HASHBUCKET，HASHELEMENT的指针，由Bucket指向Element；
HASHELEMENT，由指针link和hash value构成，后面紧跟着实际的Entry：
link，指向同一个Bucket的元素；
hash value，hash函数指针计算的key的value；
Hash Table的生成
Hash Table的生成就是对上面的结构体进行分配内存。根据内存存在的位置，可以分为共享内存和本地内存两种模式。
在本地模式中，上述结构体都将存储在本地Memory Context分配的内存种；而共享模式时，HTAB结构将会存储在本地Memory Context分配的内存，其他都将会存储到Shared Memory中。HTAHCTL储存在栈上，执行完生存函数后即被释放。
共享内存模式
由shmem分配器，在Shared Memory中划分一部分内存给Hash Table。共享Hash Table一般是先由hash_estimate_size估算出在共享内存中所占的大小，在这里已经预先将所有内存都计算好，并在申请共享内存时全部申请出来。在共享内存模式下Dynamic主要是指的可以在建立初始化时只初始化一部分Element，等待需要的时候再去初始化剩余的部分。
由ShmemInitHash初始化，调用ShmemInitHash前，会首先设置HASHCTL属性，以此建立符合需求的Hash Table；
首先由ShmemInitStruct对HASHDIR和DIR进行初始化；
然后使用hash_create，在本地由DynaHashAlloc申请一块内存，对HTAB初始化，将HTAB中的hctl指向HASHHDR，然后根据flags设置变量，例如分配alloc函数指针为ShmemAllocNoError（共享内存的分配函数）；
由init_htab对Segment也就是Bucket数组进行初始化，并计算后续每次再分配的Element数量；
根据hash_create传入的nelem参数，由element_alloc初始化Element；
由element_alloc初始化nelem个Element；
由HASHHDR的freelist指向Element；
每个Element会通过指针link指向下一个Element；
当Hash Table插入的数量超过已分配的Element数量时，将会继续分配Element或者报错；
本地内存模式
通过hash_create，根据HASHCTL设置的属性，开始建立Hash Table；
首先由DynaHashAlloc申请一块内存存储HTAB，并开始初始化，然后根据flags设置变量；
DynaHashAlloc申请一块内存存储HASHHDR，进行初始化；
HTAB的hctl指向HASHHDR；
由init_htab对通过DynaHashAlloc申请DIR也就是Segment数组，同时申请Segment也就是Bucket数组进行初始化，并计算后续每次再分配的Element数量；
根据hash_create传入的nelem参数，由element_alloc初始化Element；
DynaHashAlloc分配一块内存给Element，并对所有Element进行初始化；
由HASHHDR的freelist指向Element；
每个Element会通过指针link指向下一个Element；
当Hash Table插入的数量超过已分配的Element数量时，通过expand_table，realloc DIR也就是Segment数组，同时继续申请内存并初始化Segment也就是Bucket数组；
然后会根据init_htab计算的再分配的Element数量申请并分配新的Element；
Hash Table的插入、查找、删除
Hash Table的插入、查找、删除操作是由函数hash_search_with_hash_value操作的，会根据HASHACTION执行相应的操作。
在执行上面操作时，都会通过calc_bucket根据hash_value查找对应bucket。calc_bucket是根据当前bucket数量，和high_mask或low_mask计算得到的bucket位置的；
static inline uint32
calc_bucket(HASHHDR *hctl, uint32 hash_val)
{
uint32 bucket;
bucket = hash_val & hctl->high_mask;
if (bucket > hctl->max_bucket)
bucket = bucket & hctl->low_mask;
return bucket;
}
查找操作
当calc_bucket找到的bucket指向的所有Element的key和插入元素的key相同时，即返回Element；当bucket为NULL或者在此bucket指向的所有Element的key和插入元素的key不同时，则返回NULL；
删除操作
当calc_bucket找到的bucket指向的所有Element的key和插入元素的key相同时，进入删除操作，将元素放入到freelist中，并返回Element；当无法找到时，返回NULL；
插入和冲突处理操作
当calc_bucket找到的bucket为NULL或者在此bucket指向的所有Element的key和插入元素的key不同时，才会进行插入。当不同的key得到的hash value在同一个bucket上时，会将数据写入到Element，并由上一个Element的link指向当前插入的Element。Element分为两部分，一部分是是指向下一个Element的指针link和hash_values以及在按照HASHCTL设置的entrysize申请的内存区域：
插入扩容操作
共享内存模式
共享内存模式下的Hash Table，由于DIR Segment数组和Segment Bucket数组已经分配好了，是无法改变大小的，因此只会在Shared Memory找到空闲位置，初始化新的Element，并由freelist指向。
本地内存模式
本地内存模式下的Hash Table是可以扩充DIR Segment数组和Segment Bucket数组的，同时也可以扩充Element的。其中Segment数组是通过realloc分配的，因此原来的区域会被释放，在新的区域重新申请足够的内存来存放新的Segment数组；而Bucket数组是为新增的数组申请，由Segment数组指向新的数组即可，不需要重分配。因此这里的Segment数组指向的地址是不连续的。
Bucket分裂操作
当Bucket足够时，插入操作是正常进行的，但是随着Hash Table的扩容，Bucket超过原来的2倍时，high_mask和low_mask都会随之改变。由于查找过程是通过hash value对mask取模运算的，所以当其改变后，需要进行Bucket分裂。
if ((uint32) new_bucket > hctl->high_mask)
{
hctl->low_mask = hctl->high_mask;
hctl->high_mask = (uint32) new_bucket | hctl->low_mask;
}
Hash Table的销毁
调用函数hash_destroy对Hash Table进行销毁，只有在Local Memory模式下才会调用此函数销毁Hash Table。
