衝突のあるハッシュ テーブルが与えられた場合、リンクリストが使用されていると仮定すると、一般的なハッシュ テーブルの実装により、バケット内のルックアップが O(n) で実行されます。
二分探索木の連結リストを切り替えると、O(log n) になります。これが私たちにできる最善のことですか、それともこのユースケースに適したデータ構造はありますか?
バケット自体にハッシュ テーブルを使用すると、ルックアップ時間が O(1) になりますが、それにはハッシュ関数を巧妙に修正する必要があります。
質問する
175 次
3 に答える
1
ソリューションでは、挿入時間とルックアップ時間の間にトレードオフがあります。(バケツを整理しておく)
すべてのバケットを並べ替えておきたい場合は、バイナリ検索を使用して O(log n) のルックアップ時間を取得します。ただし、新しい要素を挿入するときは、適切な場所に配置する必要があります。そのため、バケットは引き続きソートされます。新しい要素を配置するための O(log n) 検索時間。
したがって、ソリューションでは、挿入とルックアップの両方で総複雑度 O(log n) が得られます。(最悪の場合、ルックアップに O(n) を使用し、挿入に O(1) を使用する従来のソリューションとは対照的)
編集 ：
ソートされたバケットを使用することを選択した場合、当然、LinkedList は使用できなくなります。他の適切なデータ構造に切り替えることができます。
于 2012-08-09T15:05:42.740 に答える
1
完全ハッシュは、ハッシュ関数の構築時に既知の限られたキー セットの衝突のない O(1) ハッシュを実現することが知られています。ウィキペディアの記事では、これらのアイデアを動的な完全ハッシュやカッコウハッシュなどの動的なキーのセットに適用するためのいくつかのアプローチについて言及しています。
于 2012-08-09T16:23:05.970 に答える
0
あなたは自分の質問にほとんど答えました。ハッシュ テーブルは他のデータ構造の単なる配列であるため、ルックアップ時間は、セカンダリ データ構造のルックアップ時間と、ハッシュ関数がバケット間でアイテムをどれだけうまく分散させるかに依存します。
于 2012-08-09T14:39:23.037 に答える