c - 動的ハッシュテーブルのサイズ変更における即時コピーと増分コピー

Question

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

重要な場合は、Cでこれを行っています。

Answer 1

すべてのハッシュテーブル操作に厳しい時間的制約がない限り、サイズ変更はおそらくすぐに最も理にかなっています。あなたが言うように、それはインクリメンタルなサイズ変更よりもルックアップ時間を改善し、一般的に挿入と削除のコストを償却します。増分サイズ変更は、すべての操作を一定の厳密に制限された時間内に続行する必要がある場合により適しています。