step by step

 1//對探測散列表和分離鏈接散列表的再散列
 2void rehash()
 3{
 4    vector<HashEntry> oldArray = array;
 5    array.resize( nextPrime( 2* oldArray.size() ) );
 6    for( int j = 0; j<array.size(); j++ )
 7        array[j].info = EMPTY;
 8    currentSize = 0;
 9    for( int i = 0; i<oldArray.size(); i++ )
10        if( oldArray[i].info == ACTIVE )
11            insert( oldArray[i].element );
12}
13
14void rehash()
15{
16    vector<list<HashedObj> > oldLists = theLists;
17    theLists.resize( nextPrime( 2* theLists.size() ) );
18    for( int j = 0; j<theLists.size(); j++ )
19        theLists[j].clear();
20    currentSize = 0;
21    for( int i = 0; i<oldLists.size(); i++ )
22    {
23        list<HashedObj>::iterator itr = OldLists[i].begin();
24        while ( itr != oldLists[i].end() )
25            insert( *itr++ );
26    }
27}

2.標(biāo)準(zhǔn)庫中的散列表
    標(biāo)準(zhǔn)庫中不包括set和map的散列表實(shí)現(xiàn)。但是，許多的編譯器提供具有與set和map類相同的成員函數(shù)的hash_set和hash_map.
    要使用hash_set和hash_map，就必須有相應(yīng)的包含指令，而且，可能也需要相應(yīng)的命名空間。這兩者都是和編譯器相關(guān)的。接下來還必須提供相應(yīng)的類型參數(shù)來說明
hash_set和hash_map。對于hash_map，這些類型參數(shù)包括鍵的類型，值的類型，散列函數(shù)(返回?zé)o符號整數(shù))和一個(gè)相等性操作符。遺憾的是，至于鍵和值的類型參數(shù)如何
表示還是編譯器相關(guān)的。
    下一次c++的較大的修訂將不可避免地包括這些hash_set和hash_map中的一個(gè)。

3.可擴(kuò)散列
    最后討論數(shù)據(jù)量太大以至于裝不進(jìn)主存的情況，此時(shí)主要考慮的是檢索數(shù)據(jù)所需的磁盤存取次數(shù)。假設(shè)在任意時(shí)刻都有N個(gè)記錄要存儲，N的值隨時(shí)間而變化。此外，最多可把M個(gè)記錄放入一個(gè)磁盤區(qū)塊，設(shè)M=4,如果使用探測散列或分離鏈接散列，那么主要的問題在于，即使是理想分布的散列表，在一次查找操作中，沖突也可能引起對多個(gè)區(qū)塊的訪問。不僅如此，當(dāng)表變得過慢的時(shí)候，必須執(zhí)行代價(jià)巨大的再散列這一步，它需要O(N)的磁盤訪問。
    一種聰明的選擇成為可擴(kuò)散列(extendible hashing),它允許用兩次磁盤訪問執(zhí)行一次查找。插入操作也需要很少的磁盤訪問.
   Extendible hashing from Wikipedia
   Extendible hashing is a type of hash system which treats a hash as a bit string, and uses a trie for bucket lookup. Because of the hierarchal nature of the system, re-hashing is an incremental operation (done one bucket at a time, as needed). This means that time-sensitive applications are less affected by table growth than by standard full-table rehashes.

   

This is a more simplistic example from Fagin et al. (1979).

Assume that the hash function h(k) returns a binary number. The first i bits of each string will be used as indices to figure out where they will go in the "directory" (hash table). Additionally, i is the smallest number such that the first i bits of all keys are different.

Keys to be used:

h(k₁) = 100100
h(k₂) = 010110
h(k₃) = 110110

Let's assume that for this particular example, the bucket size is 1. The first two keys to be inserted, k₁ and k₂, can be distinguished by the most significant bit, and would be inserted into the table as follows:

 directory
---------
|    0    |-----------> Bucket A (contains k2)
|---------|
|    1    |-----------> Bucket B (contains k1)
---------

Now, if k₃ were to be hashed to the table, it wouldn't be enough to distinguish all three keys by one bit (because k₃ and k₁ have 1 as their leftmost bit. Also, because the bucket size is one, the table would overflow. Because comparing the first two most significant bits would give each key a unique location, the directory size is doubled as follows:

  directory
----------
|    00    |-----\
|----------|      ----------> Bucket A (contains k2)
|    01    |-----/
|----------|
|    10    |-----------> Bucket B (contains k1)
|----------|
|    11    |-----------> Bucket C (contains k3)
----------

And so now k₁ and k₃ have a unique location, being distinguished by the first two leftmost bits. Because k₂ is in the top half of the table, both 00 and 01 point to it because there is no other key to compare to that begins with a 0.