0001 /****************************************************************************************** 0002 * 重散列算法:装填因子过大时,采取“逐一取出再插入”的朴素策略,对桶数组扩容 0003 * 因散列函数的定址与表长M直接相关,既然M已改变,就不可简单地批量复制原桶数组 0004 ******************************************************************************************/ 0005 template <typename K, typename V> void Hashtable<K, V>::rehash() { 0006 int old_capacity = M; Entry<K, V>** old_ht = ht; 0007 M = primeNLT ( 2 * M, 1048576, "../../_input/prime-1048576-bitmap.txt" ); //容量至少加倍 0008 N = 0; ht = new Entry<K, V>*[M]; memset ( ht, 0, sizeof ( Entry<K, V>* ) * M ); //新桶数组 0009 release ( lazyRemoval ); lazyRemoval = new Bitmap ( M ); //新开懒惰删除标记比特图 0010 for ( int i = 0; i < old_capacity; i++ ) //扫描原桶数组 0011 if ( old_ht[i] ) //将非空桶中的词条逐一 0012 put ( old_ht[i]->key, old_ht[i]->value ); //插入至新的桶数组 0013 release ( old_ht ); //释放原桶数组——由于其中原先存放的词条均已转移,故只需释放桶数组本身 0014 }