ハッシュテーブルの償却パフォーマンスは、ほとんどの操作でO（1）とよく言われます。
たとえば、標準のLinkedList実装での検索操作の償却パフォーマンスはどれくらいですか？O（n）ですか？
最悪の場合（常に衝突するハッシュ関数を想定）、ハッシュテーブルは検索操作（標準を想定）という点でLinkedListとほぼ同等であるため、これがどのように計算されるかについて少し混乱しています。バケットの実装）。
実際には、ハッシュ関数が壊れていない限り、これは決して起こらないことを私は知っています。したがって、衝突はまれであるため、平均パフォーマンスは一連の操作にわたってほぼ一定の時間です。しかし、償却されたワーストケースのパフォーマンスを計算するとき、ワーストケースの実装でワーストケースのシーケンスを考慮すべきではありませんか？
「償却された最悪の場合のパフォーマンス」のようなものはありません。償却パフォーマンスは、一連の長い操作における一種の「平均」パフォーマンスです。
ハッシュテーブルを使用すると、挿入の長いシーケンスの後にハッシュテーブルのサイズを変更する必要があり、これにはO（n）時間がかかります。ただし、これはO（n）挿入ごとにのみ発生するため、その操作のコストはすべての挿入に分散され、O（1）の償却時間が取得されます。
はい、ハッシュテーブルは、ハッシュ関数が壊れた場合の最悪の場合、すべての操作でO（n）になる可能性があります。ただし、このようなハッシュテーブルを分析することは、通常の使用法には当てはまらないため、意味がありません。
「最悪のケース」は、「どのような制約の下での最悪のケース」に依存することがあります。
すべてのキーを 0 にマッピングする、有効だが愚かなハッシュ関数を持つハッシュテーブルのケースは、一般的に意味のある「最悪のケース」ではなく、十分に興味深いものではありません。そのため、ハッシュ関数がすべてのキーのセットをすべてのハッシュ値のセットに均一に分散するという最小限の仮定の下で、ハッシュテーブルの平均パフォーマンスを分析できます (実用的な目的のため)。
ハッシュ関数が妥当なものであるが、暗号学的に安全でない場合、考慮すべき別の「最悪のケース」があります。悪意のある、または無意識のユーザーが、ハッシュが衝突するデータを体系的に提供する可能性があります。「最悪の場合の入力」と「十分に分散されたハッシュを持つ入力を想定した場合の最悪の場合」では、異なる答えを思い付くでしょう。
ハッシュテーブルへの特定の一連の挿入では、そのうちの 1 つが再ハッシュを引き起こす可能性があります。次に、それをその特定の「最悪のケース」と見なします。これは、入力データ全体とはほとんど関係ありません。負荷率が十分に高くなると、最終的に再ハッシュすることになりますが、めったにありません。そのため、「償却された」実行時間は、 1 つの操作の最も厳しい上限を掛けるnだけでなく、操作の総コストに厳しい上限を設定できる場合はいつでも興味深い尺度です。n
ハッシュ関数が暗号的に安全であっても、すべてのハッシュが衝突する入力を得る可能性はごくわずかです。これが、「考えられるすべての入力の平均化」と「最悪の入力による一連の操作の平均化」の違いです。したがって、「償却」という言葉にも小さな活字が付いています。私の経験では、これは通常、一連の操作の平均を意味し、データが良いケースか悪いケースかという問題は償却の一部ではありません。nneonneo は「償却された最悪のパフォーマンスなどというものはありません」と言っていますが、私の経験では、最悪のパフォーマンスの償却されたパフォーマンスは確かに存在します。ですから、正確である価値があります。
O(1)ハッシュテーブルが償却された挿入を思いついた場合、(a) ハッシュ関数で病理学的に悪いことが起こらないと仮定するか、(b)ランダムな入力を仮定して挿入に予想される時間のいずれかで、n挿入に時間がかかることを意味します。どちらの方法でもハッシュテーブルに対して同じ答えが得られるため、どちらについて話しているかを怠りがちです。O(n)n