hashmap - 別の Hashmap ではなく、HashMap のバケット実装として LinkedList を使用するのはなぜですか?

Question

HashMaps のバケットが、別の Hashmap ではなく LinkedList を介して実装されるように選択された理由を知っている人はいますか? バケットが HashMaps 自体になった場合、contains または get は O(1) であり、償却された O(1) ではないようです。

Answer 1

バケットが HashMap を使用して実装され、多くの衝突があると想像してください。優れたハッシュ関数は衝突を排除しようとするはずですが、非常に多数の要素について考えています。衝突はバケットの HashMap 実装に保存されます。この HashMap には、独自のバケットを保持するためのスペースが必要です。この HashMap のバケット内でもいくつかの衝突が発生するほど多数の要素があった場合はどうなるでしょうか? 非常に優れたハッシュ関数を使用しても、どこかでバケット HashMap (たとえば B など) のバケットが、いくつかのバケットを持ち、そのうちの 1 つが B によって実装されている HashMap A のバケットと干渉し始めます。

LinkedList にはこの問題はありません。また、バケットが HashMap に割り当てられると、たとえそれが空であっても、外部に対してブロックされるのはメモリであることに注意してください。LinkedList は動的に大きくなり、エントリ数以上のメモリは必要ありません。

要約すると、もちろん、必要なものは何でも実装できます。ArrayList または単なる配列を使用できます。しかし、それらにも独自の問題があります (削除すると O(n) 時間のサイズ変更につながり、配列は固定サイズにする必要があります)。したがって、すべてのトレードオフを考慮すると、LinkedList が最善の策であることがわかりました。

Answer 2

HashMap が別の HashMap でバケットとして実装されている場合、HashMap は引き続き O(1) に償却されます。2 つの文字列が HashMap の内部データ構造の同じインデックスにハッシュされるとします。そのインデックスに別の HashMap が含まれていた場合、2 つの文字列は同じインデックスに再度ハッシュされますが、バケット HashMap にも含まれます。次に、バケット HashMap で衝突を処理する方法を決定する必要があります。そのため、バケットとして HashMap を使用して HashMap を実装すると、1 つではなく 2 つの衝突が発生します。さらに、HashMap は、特定のデータ セットに対して LinkedList よりもはるかに多くのメモリを使用します。償却された O(1) ランタイムを保証するために、データ エントリよりも多くのメモリ スロットが必要です。

はい、適切な値を取得するにはバケットのサイズで O(n) 時間がかかるため、LinkedLists はバケットには理想的ではありません。ただし、衝突の頻度が最小限になるように HashMap を十分に大きくする必要があるため、LinkedList バケットはあまり大きくしないでください。