ハッシュテーブル検索時間

Question

ハッシュテーブルにキーを挿入/検索するとき、教科書はO（1）時間だと言っています。しかし、O（1）ルックアップ時間はどのように可能ですか？ハッシュテーブルがキーをベクトルに格納すると、O（N）になります。バイナリツリーの場合はO（logN）になります。私はO（1）アクセス時間でいくつかのデータ構造をイメージすることはできません。

ありがとうございます！

Answer 1

ハッシュテーブルは、あなたのキーをハッシュして配列に入れます。

たとえば、hash（x）= 3（xはキーです）。テーブルはそれを配列[3]に入れます。配列からのアクセスはO（1）です。

Answer 2

少なくとも、ハッシュテーブルは配列とハッシュ関数で構成されています。オブジェクトがテーブルに追加されると、ハッシュ関数がオブジェクトで計算され、計算された対応する値のインデックスで配列に格納されます。例えば、hash(obj) = 2であれば、arr[2] = objである。

ハッシュテーブルの平均挿入/参照はO(1)です。

しかし、オブジェクトが同じハッシュ値を計算するときに衝突する可能性があります。

通常、これらの衝突を処理するためにアレイの各インデックスに「バケット」があります。つまり、3つのオブジェクトはすべて、ハッシュテーブルのインデックスにある別のデータ構造（リンクリストまたは別の配列）に格納されています。

したがって、ハッシュテーブルに格納されているすべてのオブジェクトが同じバケットに格納されている可能性があるため、ハッシュテーブルのルックアップで最悪のケースはO(n)です。