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.标准库中的散列表
    标准库中不包括set和map的散列表实现。但是，许多的编译器提供具有与set和map类相同的成员函数的hash_set和hash_map.
    要使用hash_set和hash_map，就必须有相应的包含指令，而且，可能也需要相应的命名空间。这两者都是和编译器相关的。接下来还必须提供相应的类型参数来说明
hash_set和hash_map。对于hash_map，这些类型参数包括键的类型，值的类型，散列函数(返回无符号整数)和一个相等性操作符。遗憾的是，至于键和值的类型参数如何
表示还是编译器相关的。
    下一次c++的较大的修订将不可避免地包括这些hash_set和hash_map中的一个。

3.可扩散列
    最后讨论数据量太大以至于装不进主存的情况，此时主要考虑的是检索数据所需的磁盘存取次数。假设在任意时刻都有N个记录要存储，N的值随时间而变化。此外，最多可把M个记录放入一个磁盘区块，设M=4,如果使用探测散列或分离链接散列，那么主要的问题在于，即使是理想分布的散列表，在一次查找操作中，冲突也可能引起对多个区块的访问。不仅如此，当表变得过慢的时候，必须执行代价巨大的再散列这一步，它需要O(N)的磁盘访问。
    一种聪明的选择成为可扩散列(extendible hashing),它允许用两次磁盘访问执行一次查找。插入操作也需要很少的磁盘访问.
   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.