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

Question

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

それが重要な場合、私はこれをCでやっています。

Answer 1

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