1. 为什么需要动态hash

@H_403_3@ 平常的hash，大多是下面这样一副面孔:

@H_403_3@ 图1 一个静态hash结构

@H_403_3@ 这种Hash维护着一些桶，就是图上左边的部分，每一个桶中装着hash值相同的数据。

@H_403_3@这些具有相同hash值的数据形成一个链表。这种hash的一个最主要缺点就是桶的数目是一定的，不易扩展，随着插入数据增多，查找效率会急剧下降。

@H_403_3@

@H_403_3@ 动态hash就是用来解决这个问题的,postgresql实现的动态hash保证填充因子不超过一个预定值的情况下动态地增长hash表的容量。同时每一次扩容所作的改动不大，空间利用率也比较地高。

@H_403_3@

2.动态hash的结构

@H_403_3@ Postgresql与动态hash相关的代码分布在dynahash.c和hashfn.c这两个文件之中hashfn.c

@H_403_3@主要是一些Hash Function，而dynahash.c才是动态hash的主要实现。

@H_403_3@

@H_403_3@ 与普通hash表相比，动态hash多了一个新的行政单位: 目录。 如下图:

@H_403_3@ 图2 postgresql 动态hash结构

@H_403_3@dir是一个大小可变的数组，初始长度可以在创建时指定，以后每一次扩展其长度都会X2。dir中的每一项都指向一个长度固定的Segment,这些Segment的长度都相同且必须是2的整数次幂，Segment数组中的元素是Bucket(桶) ，每一个桶中存放着一个链表，动态hash将所有具有相同hash值的元素都放在同一个桶中。

@H_403_3@ 现在来看一下pg中 这些基本概念的定义:@H_403_3@

@H_403_3@ 这些定义都可以和上图相对应，不再多说。

@H_403_3@

@H_403_3@3. 给定hash value，如何找到与其对应的Bucket

@H_403_3@ 先看一下实现吧:

@H_403_3@

@H_403_3@ hctl->max_bucket 指的是bucket总数减1，对于图2来说，这个值为15

@H_403_3@ hctl->low_mask 是<= (hctl->max_bucket + 1)的最大的2^K减1， 对于图2来说，这个值是16 - 1 = 15 (0000 1111)

@H_403_3@ hctl->high_mask 是2^(K + 1)减1,对于图2来说，这个值是32 - 1 = 31 (0x0001 1111)

@H_403_3@ 这几个变量要注意的是，hctl->max_bucket在hash表创建好以后，会变化，一般情况下每次增加一个，如果hctl->max_bucket变成了2的整数次幂，就需要更新hctl->low_mask和hctl->high_mask。更新代码如下:

@H_403_3@

@H_403_3@我们回头继续看那个calc_bucket函数,因为理解这个函数是理解动态扩展的关键。从上面关于max_bucket,low_mask和high_mask的介绍，可以得出下面的结论:

@H_403_3@ hctl->high_mask >= hctl->max_bucket >= hctl->low_mask

@H_403_3@ 反应在它们的二进制表示上，如果hctl->low_mask占m位(2^m - 1)，则hctl->high_mask占m + 1位。而hctl->max_bucket是在闭区间[low_mask,high_mask]之间的。所以要取得hash_val的bucket值应优先&上high_mask,如果发现得到的bucket的序号比max_bucket还大，则再&上low_mask。这一步为后面的扩展埋下了伏笔。在扩展的时候，也就是max_bucket增加的时候，可能会造成这种情况，扩展前后同一hash_val通过calc_bucket算出的值不一样。下面在叙述扩展的时候再详细解说其解决办法 。

@H_403_3@

@H_403_3@4. 动态扩展

@H_403_3@@H_403_3@5. 总结

原文链接：https://www.f2er.com/postgresql/194458.html