ハッシュマップの高速化

Question

ハッシュマップではバケットとハッシュコードを使用していますが、そうではないことを理解しています。私の経験から、Javaのハッシュコードは小さくはありませんが、通常はかなり大きな数なので、内部的には索引付けされていないと想定しています。ハッシュコードの品質が悪くてバケット長とバケット量がほぼ同じにならない限り、ハッシュマップは名前 - >値ペアのリストより高速になりますか？

Answer 1

ハッシュマップは、ハッシュ関数を使用して要素を「バケット」にマッピングすることで機能します。誰かが要素を挿入しようとすると、ハッシュコードが計算され、要素が挿入されるべきバケットインデックスを得るために、モジュラス演算がハッシュコードに適用されます（これが問題ではない理由ですハッシュコードの大きさ）。たとえば、4つのバケットがあり、ハッシュコードが40の場合、40 mod 4が0であるため、バケット0に挿入されます。

2つの要素が同じバケットにマップされると、その要素は同じバケットの下のリストに格納されます。

要素を取得しようとすると、キーはハッシュ関数を使用して再度マップされます。バケットに要素のリストが含まれている場合、どの要素が正しいかを識別するためにequals（）関数が使用されます（これがequals（）とhashcode（）を実装してカスタムオブジェクトをハッシュマップに挿入する必要がある理由です） ）。

要素を検索し、ハッシュマップにバケットのリストがない場合、コストはO（1）です。最悪の場合は、バケットが1つしかなく、要素の取得がリストO（N）での検索と同じになるすべての要素を含むリストです。

Answer 2

私はJavaの実装を見て、それがビット単位でモジュラスに似ていることを発見しました。これは、配列のサイズを小さくする意味があります。これにより、HashMapsを素敵にするO（1）アクセスが可能になります。