?
???? hash表實際上由size個的桶組成一個桶數組table[0...size-1] 。
當一個對象經過哈希之后。得到一個對應的value , 于是我們把這個對象放到桶table[ value ]中。當一個桶中有多個對象時。我們把桶中的對象組織成為一個鏈表。
這在沖突處理上稱之為拉鏈法。
?
負載因子（load factor）
?
??? ?如果一個hash表中桶的個數為 size , 存儲的元素個數為used .則我們稱 used / size 為負載因子loadFactor?. 一般的情況下，當loadFactor<=1時，hash表查找的期望復雜度為O(1).?因此。每次往hash表中加入元素時。我們必須保證是在loadFactor <1的情況下，才可以加入。
?
容量擴張（Expand）&?分攤轉移
?
????? 當我們加入一個新元素時。一旦loadFactor大于等于1了，我們不能單純的往hash表里邊加入元素。
由于加入完之后，loadFactor將大于1，這樣也就不能保證查找的期望時間復雜度為常數級了。這時。我們應該對桶數組進行一次容量擴張，讓size增大 。
這樣就能保證加入元素后 used / size 仍然小于等于1 ， 從而保證查找的期望時間復雜度為O(1).可是。怎樣進行容量擴張呢？ C++中的vector的容量擴張是一種好方法。
于是有了例如以下思路 ： Hash表中每次發現loadFactor==1時，就開辟一個原來桶數組的兩倍空間（稱為新桶數組），然后把原來的桶數組中元素所有轉移過來到新的桶數組中。注意這里轉移是須要元素一個個又一次哈希到新桶中的。原因后面會講到。
????? 這樣的方法的缺點是，容量擴張是一次完畢的，期間要花非常長時間一次轉移hash表中的全部元素。這樣在hash表中loadFactor==1時。往里邊插入一個元素將會等候非常長的時間。
????redis中的dict.c中的設計思路是用兩個hash表來進行進行擴容和轉移的工作：當從第一個hash表的loadFactor=1時，假設要往字典里插入一個元素。首先為第二個hash表開辟2倍第一個hash表的容量。同一時候將第一個hash表的一個非空桶中元素所有轉移到第二個hash表中。然后把待插入元素存儲到第二個hash表里。繼續往字典里插入第二個元素，又會將第一個hash表的一個非空桶中元素所有轉移到第二個hash表中，然后把元素存儲到第二個hash表里……直到第一個hash表為空。
???? ?這樣的策略就把第一個hash表全部元素的轉移分攤為多次轉移，并且每次轉移的期望時間復雜度為O(1)。
這樣就不會出現某一次往字典中插入元素要等候非常長時間的情況了。
為了更深入的理解這個過程。先看看在dict.h中的兩個結構體：
????dictEntry?**table;
????unsigned?long?size;
????unsigned?long?sizemask;
????unsigned?long?used;
}?dictht;
typedef?struct?dict?{
????dictType?*type;
????void?*privdata;
????dictht?ht[2];
????int?rehashidx;?/*?rehashing?not?in?progress?if?rehashidx?==?-1?*/
????int?iterators;?/*?number?of?iterators?currently?running?*/
}?dict;
dictht指的就是上面說的桶數組，size用來表示容量，一般為2^n?，sizemask（一般為2^n-1,二進制表示為n個1）用來對哈希值取模?, used表示hash表中存儲了多少個元素。
??????????? dict表示字典，由兩個桶數組組成。type是一些函數指針（哈希函數及key。value的一些處理函數）。
d->rehashidx
?
這個變量的理解非常關鍵：
d->rehashidx?表明了新元素究竟是存儲到桶數組0中。還是桶數組1中，同一時候指明了d->h[0]中究竟是哪一個桶轉移到d->h[1]中。
當d->rehashidx==-1時，這時新加入的元素應該存儲在桶數組0里邊。
當d->rehashidx!=-1?時，表示應該將桶數組0中的第一個非空桶元素所有轉移到桶數組1中來(最好還是稱這個過程為桶轉移，或者稱為rehash)。這個過程必須將非空桶中的元素一個個又一次哈希放到桶數組1中，由于d->h[1]->sizemask已經不同于d->h[0]->sizemask了。
這時新加入的元素應該存儲在桶數組1里邊，由于此刻的桶數組0的loadFactor為1?。而桶數組1的loadFactor小于1?。
?
當發現桶數組0中的元素所有都轉移到桶數組1中，即桶數組0為空時。釋放桶數組0的空間。把桶數組0的指針指向桶數組1。將d->rehashidx賦值為-1?，這樣桶數組1就空了，下次加入元素時。仍然加入到桶數組0中。直到桶數組0的元素個數超過桶的個數，我們又又一次開辟桶數組0的2倍空間給桶數組1?，同一時候改動d->rehashidx=0。這樣下次加入元素是就加入到桶數組1中去了。
?
值得注意的是。在每次刪除、查找、替換操作進行之前，依據d->rehashidx的狀態來推斷是否須要進行桶轉移。這能夠加快轉移速度。
?
以下是一份精簡的偽代碼，通過依次插入element[1..n]這n個元素到dict來具體描寫敘述容量擴張及轉移的過程：
d->h[0].size?=?4?;?d->h[1].used?=?0?;??//分配四個空桶
d->h[1].size?=?0?;?d->h[1].used?=?0?;??//初始化一個空表
?
for(i?=?1?;?i?<=?n?;?++?i){
??????if(?d->rehashidx?!=-1?){
??????????????????if(d->h[0]->used?!=?0){
????????????????????????????把?d->h[0]中一個非空桶元素轉移（又一次hash）到?d->h[1]中??。??
????????????????????????????//?上一步會使得:
????????????????????????????//?d->h[0]->used?-=?轉移的元素個數?
????????????????????????????//?d->h[1]->used?+=?轉移的元素個數?。
????????????????????????????把?element[i]?哈希到?d->h[1]中??;??//?d->h[1]->used?++?
??????????????????}else{
????????????????????????????//用桶數組1覆蓋桶數組0；?賦值前要釋放d->h[0]的空間，賦值后重置d->h[1])
????????????????????????????d->h[0]?=?d->h[1]?;?
????????????????????????????d->rehashidx?=?-1?;?
????????????????????????????把element[i]哈希到d->h[0]中；//?d->h[0]->used?++?;?
?????????????????}
??????}else?if(?d->h[0]->used?>=?d->h[0]->size?)
????????????????d->h[1]?=?new?bucket[2*d->h[0]->size?];????
????????????????//?d->h[0]->size?等于d->h[0]->size的2倍?
????????????????把element[i]哈希到d->h[1]中?;??//?d->h[1]->used?++?
????????????????d->rehashidx?=?0?;?????????????????????????????
??????}else{
????????????????把element[i]哈希到d->h[0]中;??//?d->h[0]->used?++?
??????}
}
字典的迭代器（Iterator）
?
分為安全迭代器( safe Iterator )和非安全迭代器。
安全迭代器可以保證在迭代器未釋放之前，字典兩個hash表之間不會進行桶轉移。
桶轉移對迭代器的影響是很大的，如果一個迭代器指向d->h[0]的某個桶中的元素實體。在一次桶轉移后，這個實體被rehash到d->h[1]中。
而在d->h[1]中根本不知道哪些元素被迭代器放過過，哪些沒有被訪問過，這樣有可能讓迭代器反復訪問或者缺失訪問字典中的一些元素。
所以安全迭代器可以保證不多不少不反復的訪問到全部的元素（當然在迭代過程中。不能涉及插入新元素和刪除新元素的操作）。
本文轉自mfrbuaa博客園博客，原文鏈接：http://www.cnblogs.com/mfrbuaa/p/5245064.html，如需轉載請自行聯系原作者
)
![bzoj 2752: [HAOI2012]高速公路(road)](http://pic.xiahunao.cn/bzoj 2752: [HAOI2012]高速公路(road))
