[解決済み] ハッシュテーブルは本当にO(1)になるのか？

質問

ハッシュテーブルがO(1)を達成できることは常識のようですが、私には意味が分かりませんでした。 どなたか説明していただけませんか。以下は、思い浮かぶ 2 つの状況です。

A. 値がハッシュテーブルのサイズより小さいintである。 したがって、値はそれ自身のハッシュなので、ハッシュテーブルは存在しない。しかし、もしあったとしてもO(1)となり、やはり非効率的です。

B. 値のハッシュを計算する必要がある。 この状況では、ルックアップされるデータのサイズに対してO(n)のオーダーになります。 O(n)の作業をした後のルックアップはO(1)になるかもしれませんが、それでも私の目にはO(n)に映ります。

また、完全なハッシュや大きなハッシュテーブルがない限り、バケットごとに数個のアイテムがあることでしょう。ですから、いずれにせよ、ある時点で小さな線形探索に発展してしまいます。

ハッシュテーブルはすごいと思うが、理論的なものでなければO(1)の指定はないだろう。

ウィキペディアの の記事で、ハッシュテーブルについて は一貫して一定のルックアップ時間を参照し、ハッシュ関数のコストを完全に無視しています。 これは本当に公正な測定なのでしょうか？

編集します。 私が学んだことをまとめると

• ハッシュ関数がキーのすべての情報を使用する必要がないため定数時間になりうること、また、十分に大きなテーブルでは衝突を定数時間近くまで下げることができるため、技術的には正しい。

• ハッシュ関数とテーブルのサイズが衝突を最小化するように選択される限り、たとえそれがしばしば定時間ハッシュ関数を使用しないことを意味するとしても、時間とともにうまくいくので、実際には真実です。

どのように解決するのですか?

ここではmとnという2つの変数があり、mは入力の長さ、nはハッシュの項目数です。

O(1) ルックアップ パフォーマンスの主張には、少なくとも 2 つの前提があります。

• オブジェクトは O(1) 時間で等価比較できる。
• ハッシュの衝突はほとんど起こりません。

オブジェクトのサイズが可変で、等価性チェックにすべてのビットを見る必要がある場合、パフォーマンスは O(m) になります。しかし、ハッシュ関数は O(m) である必要はなく、O(1) であってもかまいません。暗号ハッシュとは異なり、辞書で使用するハッシュ関数は、ハッシュを計算するために入力のすべてのビットを見る必要がない。実装では、固定数のビットだけを自由に見ることができます。

十分に多くのアイテムについて、アイテムの数は可能なハッシュの数よりも大きくなり、そして、O(1)を超えるパフォーマンスを引き起こす衝突が発生し、たとえば、単純なリンクリストトラバーサルについてはO(n) (または両方の仮定が誤っている場合はO(n*m))となります。

しかし実際には、技術的には間違っていますが、O(1) の主張は およそ であり、特に上記の前提が成立する状況においては真であると言えます。