0001 /******************************************************************************************
0002  * 重散列：空桶太少时对散列表重新整理：扩容，再将词条逐一移入新表
0003  * 散列函数的定址与表长M直接相关，故不可简单地批量复制原桶数组
0004  ******************************************************************************************/
0005 template <typename K, typename V> void Hashtable<K, V>::rehash() {
0006    Rank oldM = M; Entry<K, V>** oldHt = ht;
0007    M = primeNLT( 4 * N, 1048576, PRIME_TABLE ); //容量至少加倍（若懒惰删除很多，可能反而缩容）
0008    ht = new Entry<K, V>*[M]; N = 0; memset( ht, 0, sizeof( Entry<K, V>* ) * M ); //桶数组
0009    delete removed; removed = new Bitmap( M ); //懒惰删除标记
0010    for ( Rank i = 0; i < oldM; i++ ) //扫描原表
0011       if ( oldHt[i] ) //将每个非空桶中的词条
0012          put( oldHt[i]->key, oldHt[i]->value ); //转入新表
0013    delete[] oldHt; //释放——因所有词条均已转移，故只需释放桶数组本身
0014 }