int 配列変数 x[] を考えてみましょう。変数 X には開始アドレス参照があります。配列が x[2] であるインデックス 2 でアクセスされる場合、そのメモリ位置は次のように計算されます。
x[2] のアドレスは、開始アドレス + インデックス * int のサイズです。
すなわち。x[2]=x + 2*4.
ただし、ハッシュマップの場合、メモリアドレスが内部でどのようにマップされるか。
以前の多くの投稿を読んで、HashMap がリンクされたリストを使用してキーと値のリストを格納していることに気付きました。しかし、その場合は、キーを見つけるためにハッシュコードを生成し、リスト内の等しいハッシュ コードをチェックして値を取得します。
これには O(n) の複雑さが必要です。上記の観察が間違っている場合は、訂正してください... 私は初心者です。ありがとうございました
HashMap の従来の実装では、関数を使用してキーを生成し、そのキーを使用して値に直接アクセスします。配列インデックスに変換される何かを生成すると考えてください。要素ハッシュと生成されたハッシュを比較するハッシュマップは調べません。ハッシュを生成し、ハッシュを使用して要素に直接アクセスします。
あなたが話していると思うのは、HashMap の 2 つの値が同じキーを生成する場合です。次に、それらのリストを使用し、それらを調べて、必要なものを決定する必要があります。しかし、それは O(n) ではなく、n は HashMap 内の要素の数であり、m は同じハッシュを持つ要素の数である O(m) です。明らかに、ゲームの名前は、生成されたハッシュが可能な限りすべての要素に対して一意であるハッシュ関数を見つけることです。
--- 説明を拡張するために編集 ---
あなたの投稿では、次のように述べています。
以前の多くの投稿を読んで、HashMap がリンクされたリストを使用してキーと値のリストを格納していることに気付きました。
これは、HashMap 全体では正しくありません。HashMap が合理的に機能するには、HashMap 内のすべての値を検索するのではなく、キーを使用して対応する要素に直接アクセスする方法を計算する方法が必要です。
「完全な」ハッシュ計算は、可能な各キーを、他のキーでは計算されなかったハッシュ値に変換します。これは通常実行可能ではないため、通常、2 つの異なるキーがハッシュ計算で同じ結果になる可能性があります。この場合、HashMap 実装は値のリンクされたリストを使用でき、探している値を見つけるためにそのようなすべての値を調べる必要があります。しかし、この数は HashMap 全体の値の数よりもはるかに少ないです。
文字列がキーで、文字列の最初の文字が配列インデックスとして使用される数値に変換されるハッシュを作成できます。すべての文字列の最初の文字が異なる限り、値へのアクセスは単純な計算と配列アクセス -- O(1) です。または、文字列インデックスのすべての文字値を合計して、最後の 2 (または 3) 桁を取ることができます。これがハッシュ計算になります。追加によって各インデックス文字列に一意の値が生成される限り、リストを調べる必要はありません。再び、O(1)。
実際、ハッシュ計算がほぼ完璧である限り、ルックアップは全体として O(1) のままです。これは、短いリストを調べなければならない回数が制限されていても、全体的な効率が変わらないためです。