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中 這些基本概念的定義:??????
typedef struct HASHELEMENT?
{?
??? struct HASHELEMENT *link;?? /* link to next entry in same bucket */?
??? uint32????? hashvalue;????? /* hash function result for this entry */?
} HASHELEMENT;
/* A hash bucket is a linked list of HASHELEMENTs */?
typedef HASHELEMENT *HASHBUCKET;?
?
?
/* A hash segment is an array of bucket headers */?
typedef HASHBUCKET *HASHSEGMENT;
這些定義都可以和上圖相對應，不再多說。
3. 給定hash value，如何找到與其對應的Bucket
先看一下實現吧:
/* Convert a hash value to a bucket number */?
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;?
}?
hctl->max_bucket 指的是bucket總數減1，對于圖2來說，這個值為15
hctl->low_mask 是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。更新代碼如下:
/*
* If we crossed a power of 2, readjust masks.
*/?
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
>
2) 如果segndx沒有超出已分配的segment的容量，轉入5),否則繼續;
3) 檢查segndx是否超出了現有的dir大小，如是，將dir的大小擴展為以前的2倍；
4) 給dir[segndx]分配一個新的segment;
>
5) 計算max_bucket + 1在沒有擴展前的bucket號old_bucket;
6) max_bucket++后檢查max_bucket是否成了2的整數次冪，若是，修改low_mask和high_mask;
7) 計算新的bucket號new_bucket;
>
8) 遍歷old_bucket鏈表，重新計算他們所應該在的bucket,將需要移動的移到到new_bucket中。
這個過程中只有步驟8需要說明一下。為什么只是本次擴展前的old_bucket,而沒有檢查，前一次，前兩次擴展的old_bucket呢？這是由calc_bucket中計算bucket的方法所決定的，其實你想的沒有錯，是應該去遍歷前一次，兩次，擴展的那些old_bucket,但是沒有必要，即使你這樣做了，你也從這些bucket中找不到一個可以入到new_bucket中的元素。我們只需要證明經過一次擴展，留在old_bucket中的元素的hash值對應的bucket從些以后不會再改變就行了。
擴展前后bucket計算路徑可以用下面矩陣來表示:
擴展后 &high_mask??????????? 擴展后 &low_mask
擴展前? &high_mask??????????????????? (1)???????????????????????????????????? (2)
擴展前? &low_mask????????????????????? (3)???????????????????????????????????? (4)
這其中(2)是不可能出現的，因為擴展前的high_mask與擴展后low_mask相等，如果(2)成立就出出現max_bucket > (max_bucket + 1)的矛盾。而對于 情況(1),由于high_mask和max_bucket只會增加，把以bucket號從些不會改變, 而(3)和(4)實際上就是本次擴展需要移動的項。所以已經證明那些留在 old_bucket中的元素不會變。
5.? 總結
pg實現的這個動態hash保證填充因子不超過設定值，其檢索效率不會因插入元素的增多而降低，同時其擴展的代價也不是十分地大，每次只需要移動一個bucket中的某些項到新的bucket中。
