動的ハッシュテーブルの即時コピーと増分コピーのサイズ変更

Question

それぞれの長所と短所は何ですか？高速検索時間が重要なハッシュテーブルを実装している場合は、挿入や削除時にのみ発生するため、即時に使う必要がありますが、インクリメンタルな検索では検索が遅くなるためです。それは理にかなっていますか？

問題がある場合、Cでこれをやっています。

Answer 1

ハッシュテーブル操作ごとに厳しい制限がない限り、すぐにリサイズするのが最も理にかなっています。あなたが言うように、それはインクリメンタルリサイズに比べてルックアップ時間を改善し、挿入と削除のコストを一般に償却します。増分リサイズは、すべての操作を固定して厳密に制限された時間内に進めなければならない場合に適用できます。