ハッシュテーブルバケット用の配列を使用したキューに対するリンクリストの利点

Question

リンクリストや配列を使用してキューを実装する方法は2つあります。バケットがエントリの制限を超えたときにハッシュテーブルを再ハッシュする必要があるハッシュテーブルでバケットを作成するために使用する必要があるのはどれですか。他のデータ構造を使ってO（1）en-queueとde-queueを索引付けすることは可能ですか？

アレイを使用するとバケットサイズを大きくすることができます。配列のインデックスを作成すると、キー（バイナリ検索）を並べ替え順に挿入できます。バケツサイズが1000になると、検索はln（1000）vs 1000になります。挿入操作はO（n）になりますが、参照はより一般的で挿入されます。

リンクされたリストを使用すると、私はO（1）を挿入して削除しますが、O（n）も取得します。

私の質問では、他のデータ構造を使用することのメリットを得ることはできますか？

Answer 1

あなたは間違った質問をしていると思います。バケット内の多数のアイテムを処理する方法を心配するのではなく、バケツが過度に大量になった理由に気を付ける必要があります。あなたがバケツの中のアイテムの良好な分布を提供ハッシュ関数を選択した

1. ：

   ハッシュテーブルは2つのことを前提としています。

2. 負荷係数が高くなりすぎることはありません。良いハッシュテーブルの実装は、約0.8までの負荷係数でかなりまともなパフォーマンスを提供しますが、そのパフォーマンスを急激に下回ります。ほとんどの実装で負荷率を0.7以下に抑えたいと思う。したがって、ハッシュテーブルのアイテム数がテーブルの容量の70％を超える場合は、容量を増やすことを検討する必要があります。ほとんどのハッシュテーブルの実装では、負荷率があるしきい値を超えると自動的に容量が増加します。

ハッシュテーブルを使用する場合は、両方の条件が満たされていることを確認する責任があります。貧弱なハッシュ関数を選択した場合、または設計された負荷率を超えると、のパフォーマンスはになり、バケツ構造の最適化は役に立ちません。

バケットのリスト構造の実装は、バケットがパフォーマンスの違いを生ずるのに十分な大きさであってはならないため、重要ではありません。単純なリンクリストには、O（1）挿入とO（k）検索（kはバケット内の項目数）が表示されます。しかし、kは2または3を超えてはならないので、漸近的により効率的なデータ構造を使用することは意味がありません。

バケットの実装方法にかかわらず、ハッシュテーブルの容量（またはハッシュテーブルの実装ではロードファクタのしきい値を超えた場合）のO（n）サイズの価格を払う予定です。自動サイズ変更）。

Answer 2

ハッシュテーブルのバケットを実装するときは、サイズ変更可能なのでリンクリストを使用する必要があります。ハッシュマップ内のバケットで行う必要のある操作は、トラバースして新しい項目を追加することだけです（両方とも要素ごとにO(1)で実行できます）。配列を使用するときは、メモリを不必要に割り当てるか小さすぎるかは、メモリのサイズを変更できないため、割り当てます。さらに、キューを使用すべきではありません。通常のリンクリストを使用する方がよいでしょう。