再ハッシュを行う最も簡単な方法は何ですか？マーク・ワイスのデータ構造から

Question

およびC++でのアルゴリズム分析：

/** 
* Rehashing for quadratic probing hash table. 
*/ 
void rehash() 
{ 
    vector<HashEntry> oldArray = array; 

    // Create new double-sized, empty table 
    array.resize(nextPrime(2 * oldArray.size())); 
    for(auto & entry : array) 
     entry.info = EMPTY; 

    // Copy table over 
    currentSize = 0; 
    for(auto & entry : oldArray) 
     if(entry.info == ACTIVE) 
      insert(std::move(entry.element)); 
} 

それは表にておきの要素を移動すること、及び要素がアクティブであるかどうかをチェックするかの本当に痛みを伴う操作のように思えますない。特に、（テーブル全体とは対照的に）挿入された要素の数だけを通すことを意味する実装がありますか？

Answer 1

参照、Per-Ake Larson、ダイナミックハッシング、 CACM April 1988、pp 446-457を参照してください。彼は、バケットを分割し、スプレットバケットのハッシュコードだけを再計算する必要があるハッシュシステムについて説明します。

'C' version of it coded as an hsearch(3) replacementは、1998年7月のUsenet comp.sources.miscアーカイブにejp@ausmelb.oz（me）が寄稿しています。このコードは、その後、Berkeley DBやOpenLDAPをはじめとするさまざまな場所への道を開いた。申し訳ありませんが、元のソースコードはまだありませんが、私はJavaの実装があります。