arrays - ハッシュテーブルがバケットの配列ではなく連結リストを使用するのはなぜですか?

Question

値が同じ値にハッシュされると、ハッシュ値によって参照されるリンク リストに追加されます。ハッシュテーブルの実装で、配列に対してリンクリストをバケットとして使用するのはなぜですか?

配列は初期化時に所定のサイズを持っているため、バケットに追加された要素が多すぎるとサイズを変更する必要がありますか?

Answer 1

はい：一般的に、アレイのサイズは事前に決定されているためです。バケットにリンクリストまたは配列を使用する必要はありません。一部の巧妙な実装では、別のハッシュテーブルを使用します。このハッシュテーブルは、バケットにリンクリストまたは配列を使用します。

配列を使用する場合、ハッシュテーブルには配列要素ごとに事前に定義されたサイズがあります。可能なすべてのバケットが割り当てられ、ハッシュテーブルはかなり大きくなる可能性があります。大量のメモリがある場合、または非常に完全なハッシュテーブルが必要な場合は、これで問題ない可能性があります。配列へのポインタを保持し、必要に応じて割り当てることで、これを軽減できます。

配列にはインデックスを付けることができるため、配列を並べ替えたままにしておくことができます。次に、それが大きくなった場合は、バイナリ検索を実行して、必要なキーを見つけることができます。

リンクリストを使用する場合は、リンクリストをたどって、必要な一致を直線的に見つける必要があります。これはあまり効率的ではありませんが、メモリ使用量を最小限に抑えます。

すべてのデータ構造の問題と同様に、どのようなアクセスパターンを使用するか、および構造をどのように使用して埋めるかを検討する必要があります。あなたが勝ちたいトレードオフは何ですか、そしてあなたがそれほど気にしないものはどれですか？

Answer 2

彼らはしません。

「ハッシュテーブルの実装」が連結リストを使用すると主張するのは過度の一般化です。Javaはそうします。他の多くの言語はそうではありません。たとえば、Python はオープン ハッシュを使用します。この質問に対する回答を参照してください。Pythonの組み込み辞書はどのように実装されていますか?

一般に、汎用 API の設計者は、ユーザーのユースケースを知らないため、非常に難しい選択に直面しています。さまざまなトレードオフを持つさまざまな実装の選択肢があります。たとえば、要素を追加するだけで削除しない場合、頻繁に変更されるハッシュマップとは異なる選択肢が適用されます。など。