Postgresql源码分析: 动态Hash

概述1. 为什么需要动态hash     平常的hash，大多是下面这样一副面孔:                                                               图1         一个静态hash结构        这种Hash维护着一些桶，就是图上左边的部分，每一个桶中装着hash值相同的数据。 这些具有相同hash值的数据形成一个链表。这种hash 1. 为什么需要动态hash

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

图1 一个静态hash结构

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

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

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

2.动态hash的结构

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

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

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

图2 postgresql 动态hash结构

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

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

[cpp] view plain copy <spanstyle="@R_403_6837@-size:18px;">typedefstructHASHELEMENT { structHASHELEMENT*link;/*linktonextentryinsamebucket*/ uint32hashvalue;/*hashfunctionresultforthisentry*/ }HASHELEMENT; </span> [cpp] view plain copy <spanstyle="@R_403_6837@-size:18px;">/*AhashbucketisalinkedlistofHASHELEMENTs*/ typedefHASHELEMENT*HASHBUCKET; /*Ahashsegmentisanarrayofbucketheaders*/ typedefHASHBUCKET*HASHSEGMENT;</span> 这些定义都可以和上图相对应，不再多说。

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

先看一下实现吧:

[cpp] view plain copy /*Convertahashvaluetoabucketnumber*/ staticinlineuint32 calc_bucket(HASHHDR*hctl,uint32hash_val) { uint32bucket; bucket=hash_val&hctl->high_mask; if(bucket>hctl->max_bucket) bucket=bucket&hctl->low_mask; returnbucket; }

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

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

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

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

[cpp] view plain copy /* *Ifwecrossedapowerof2,readjustmasks. */ if((uint32)new_bucket>hctl->high_mask) { hctl->low_mask=hctl->high_mask; hctl->high_mask=(uint32)new_bucket|hctl->low_mask; } 我们回头继续看那个calc_bucket函数,因为理解这个函数是理解动态扩展的关键。从上面关于max_bucket,low_mask和high_mask的介绍，可以得出下面的结论:

hctl->high_mask >= hctl->max_bucket >= hctl->low_mask

反应在它们的二进制表示上，如果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算出的值不一样。下面在叙述扩展的时候再详细解说其解决办法 。

4. 动态扩展 在弄清楚动态hash的结构以及如何从hash值得到其所在的bucket后，hash表的查找，删除以及通常情况下的插入 *** 作就非常地容易啦。比如删除，就先是调用 cal_bucket找到所在的桶，然后在这个桶中一个个地找，找到具有相同键值的元素，就从桶所对应的链表中删除。 下面来说一下动态扩展的问题，毕竟这才是pg动态hash的核心。
说到动态扩展，就得说扩展时机，什么时候我们的hash表需要增大容量呢？ 我们增大容量是为了保证其查找的效率。而hash表的查找效率是与一个叫做填充因子东西有很大关系的。pg的填充因子定义为: 填充因子 =hctl->nentrIEs / (hctl->max_bucket + 1) 从这个公式可以看出填充因子会随着插入元素的增多而增加， 当增大到比hctl->ffactor还要大的时候就需要扩展了，这里的扩展的意思是指hctl->max_bucket要增加1个。其步骤如下: 1) 计算出 max_bucket + 1所在的segment索引值segndx <<扩展dir和segment>> 2) 如果segndx没有超出已分配的segment的容量，转入5),否则继续; 3) 检查segndx是否超出了现有的dir大小，如是，将dir的大小扩展为以前的2倍； 4) 给dir[segndx]分配一个新的segment; <<计算新旧bucket>> 5) 计算max_bucket + 1在没有扩展前的bucket号old_bucket; 6) max_bucket++后检查max_bucket是否成了2的整数次幂，若是，修改low_mask和high_mask; 7) 计算新的bucket号new_bucket;
<<将old_bucket中满足条件的元素移动new_bucket中>> 8) 遍历old_bucket链表，重新计算他们所应该在的bucket,将需要移动的移到到new_bucket中。
这个过程中只有步骤8需要说明一下。为什么只是本次扩展前的old_bucket 。这是由calc_bucket的实现来决定的。假定high_mask = 2^K - 1,这个函数告诉我们，old_bucket中存放着两类元素: 1) hash值后k位值为old_bucket; 2) hash值后k位值为old_bucket + 2^(k - 1)的那些元素 在扩展后，hash表中只有第2)元素的桶号应该变为new_bucket。所以只要移动一个old_bucket中第2)类到new_bucket中就可以啦。
5. 总结 pg实现的这个动态hash保证填充因子不超过设定值，其检索效率不会因插入元素的增多而降低，同时其扩展的代价也不是十分地大，每次只需要移动一个bucket中的某些项到新的bucket中 总结

以上是内存溢出为你收集整理的Postgresql源码分析: 动态Hash全部内容，希望文章能够帮你解决Postgresql源码分析: 动态Hash所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。