HashMap は Java でどのように機能しますか

皆さんのほとんどはHashMap、今日、面接中に最もよく議論されるトピックであることに同意するでしょう。同僚と同じような議論をすることもありましたが、それは本当に役に立ちました。それでは、このような議論をさせていただきます。 HashMap の内部と仕組みに興味がある方は、HashMapの基本についてはすでによくご存じだと思いますので、その部分は省略します。ただし、これを初めて使用する場合は、 Java Docsサイトにアクセスすることをお勧めします。次に進む前に、私の以前の記事「Java での hashCode と平等メソッドの使用」を参照することを強くお勧めします。 この記事の内容:

1. 考えられる唯一の答え。
2. ハッシュとは何ですか。
3. クラスについて少しEntry。
4. put().とは何ですか？
5. メソッドの仕組みget()。
6. ノート

考えられる唯一の答えは

誰かが私に「 HashMap はどのように機能するのか?」と説明してほしいと尋ねたら、「」という質問に対して、私は単純に「ハッシュの原則に従って」と答えます。これ以上にシンプルなことはありません。これを理解して詳細な答えを得るには、ハッシュの基本を確実に知っている必要があります。右？

ハッシュとは何ですか

最も単純な形式のハッシュは、プロパティに式やアルゴリズムを適用した後、変数やオブジェクトを一意のコードに変換する方法です。真のハッシュ関数は、次の規則に従う必要があります。ハッシュ関数は、同じまたは等しいオブジェクトに適用される場合は常に同じハッシュ コードを返さなければなりません。言い換えれば、2 つの同一のオブジェクトは同じハッシュ コードを順番に返さなければなりません。 詳細については、ここで読むことができます: Java での hashCode およびquals メソッドの操作

エントリークラスについて少し

定義上、マップは「値とキーをペアで格納するオブジェクト」です。とてもシンプルですよね？ということは、HashMap には値とキーのペアを保存する何らかのメカニズムがあるはずです。答え - はい。次のような HashMap内部クラスがあります。Entry

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

当然、クラスにはEntry属性として保存された Key と Value があります。キーは としてマークされており、とfinalという 2 つの追加フィールドも表示されます。記事を読み進めるにつれて、これらのフィールドの目的を理解していきます。 nexthash

Javaのput()メソッドは何をするのでしょうか?

メソッドの実装に入る前にput()、クラスのインスタンスがEntry配列に格納されることを理解することが非常に重要です。HashMap クラスは、この変数を次のように定義します。

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

次に、メソッドの実装コードを見てみましょうput()。

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
public V put(K key, V value) {
if (key == null)
return putForNullKey(value);
int hash = hash(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<k , V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}

modCount++;
addEntry(hash, key, value, i);
return null;
}

段階的に理解してみましょう。

• まず、キーが存在するかどうかを確認します。キーが存在しない場合 ( )、値のハッシュ コードは , であるため、null値はテーブルの位置 0 に配置されます。nullэто – всегда 0


• 次のステップでは、メソッドを呼び出して取得したキーのハッシュ コードを使用してハッシュ値を計算しますhashCode()。このハッシュ値は、オブジェクトが配置される配列内の位置を計算するために使用されますEntry。JDK設計者は、関数の作成が適切でないと、hashCode()高すぎる、または低すぎるハッシュ値が返される可能性があると想定していました。この問題を解決するために、彼らは別のhash()関数を導入し、オブジェクトのハッシュ値をその関数に渡して、ハッシュ値を配列のサイズと一致させるようにしました。


• indexFor(hash, table.length)ここで、オブジェクトが配置される正確な位置を計算するために関数が呼び出されますEntry。


• ここから本編が始まります。ここで、等しくない 2 つのオブジェクトが等しいハッシュ コードを持つ可能性があるということを知っていることに基づいて、「2 つの異なるオブジェクトは [bucket] 配列内の同じ位置に配置されますか?」という質問をします。答えは ですLinkedList。覚えていると思いますが、クラスにはEntry属性「next」があります。この属性は常にチェーン内の次のオブジェクトを指します。これはまさにその動作ですLinkedList。

したがって、オブジェクトはEntryという形式で保存されますLinkedList。オブジェクトをEntry特定の場所に配置する場合、HashMap はその場所にすでにエントリがあるかどうかを確認します。エントリがない場合、オブジェクトはこの位置に配置されます。ただし、この位置にすでにオブジェクトが存在する場合は、次の属性がチェックされます。それが返されnull、現在のオブジェクトが のEntry次のリンクになりますLinkedList。次の変数が存在しない場合はnull、次の変数が見つかるまでこの手順が繰り返されますnull。値は異なるが、前と同じキーを持つ別のオブジェクトを配置した場合はどうなるでしょうか? 論理的には、これにより古い値が置き換えられるはずです。これはどうして起こるのでしょうか? 一般に、オブジェクトの位置を決定した後、計算された位置までEntry移動しながら、各オブジェクトのキー比較メソッドを呼び出します。これらのオブジェクトはすべて類似のハッシュ コードを持つ可能性がありますが、メソッドは真の類似性をチェックします。これは、 内の値のみを置き換えます。したがって、HashMap はすべてのキーの一意性を保証します。 LinkedListHashMapEntryEntryLinkedListequals()Entry

Javaのget()メソッドはどのように機能するのでしょうか?

これで、キーと値のペアがどのように に保存されるかがわかりましたHashMap。次の大きな疑問は、オブジェクトが HashMap からメソッドに渡されると何が起こるかということですget()。オブジェクトの価値はどのように決定されるのでしょうか? メソッド内でキーの一意性を決定する方法は、put()メソッドが適用するロジックと同じであるため、答えはすでにわかっているはずですget()。引数として渡されたオブジェクトのキーを決定するとHashMap、対応する の値を返すだけですEntry。一致するものが見つからない場合、メソッドはget()を返しますnull。コードを見てみましょう:

public V get(Object key) {
if (key == null)
return getForNullKey();
int hash = hash(key.hashCode());
for (Entry<k,V>e=table[indexFor(hash,table.length)];e!=null;e=e.next){
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

put()上記のコードはここまでの メソッドと同様でif (e.hash == hash && ((k = e.key) == key || key.equals(k)))、後はオブジェクトの値を返すだけです。

ノート

• オブジェクトに格納されるデータ構造は、名前と型Entryを持つ配列です。tableEntry
• 配列内の個々の位置は、LinkedListオブジェクトの最初の要素を含むことができるため、バケットと呼ばれますEntry。
• hashCode()キーはオブジェクトの位置を計算するために必要ですEntry。
• equals()キーは、map() 内のキーの一意性をチェックするために使用されますmap。
• hashCode()と値はメソッドとではequals()使用されません。get()set()HashMap
• 値を持つキーのハッシュ コードはnull常に 0 です。そして、そのようなオブジェクトはEntry常に配列の 0 の位置に格納されます。

この記事で私の考えが正しく伝われば幸いです。間違いを見つけた場合や質問がある場合は、コメントに残してください。 楽しく学習しましょう！