ハッシュテーブルにキーを挿入/検索するとき、教科書はO（1）時間だと言いました。しかし、O(1) のルックアップ時間を実現するにはどうすればよいでしょうか? ハッシュ テーブルがキーをベクトルに格納する場合、コストは O(N) になります。バイナリ ツリーの場合、O(logN) になります。O（1）アクセス時間でデータ構造をイメージすることはできません。
ありがとう！
12228 次
3 に答える
13
ハッシュテーブルはキーをハッシュして配列に入れます。
たとえば、hash(x) = 3 の場合、x はキーです。次に、テーブルはそれを配列 [3] に入れます。配列からのアクセスはO(1)です。
于 2013-01-17T05:59:12.667 に答える
12
少なくとも、ハッシュ テーブルは配列とハッシュ関数で構成されます。オブジェクトがテーブルに追加されると、ハッシュ関数がオブジェクトに対して計算され、計算された対応する値のインデックスで配列に格納されます。たとえば、もしそうhash(obj) = 2ならarr[2] = obj。
ハッシュ テーブルの平均挿入/検索はO(1).
ただし、オブジェクトが同じハッシュ値を計算するときに衝突が発生する可能性があります。
一般に、これらの衝突を処理するために、配列の各インデックスに「バケット」があります。つまり、3 つのオブジェクトはすべて、ハッシュ テーブルのインデックスにある他のデータ構造 (おそらくリンク リストまたは別の配列) に格納されます。
したがって、ハッシュ テーブルでのルックアップの最悪のケースは、ハッシュ テーブルにO(n)格納されているすべてのオブジェクトが衝突し、同じバケットに格納されている可能性があるためです。
于 2013-10-28T04:55:02.653 に答える