Javaハッシュ・ストレージの詳細と簡単な例

2308 ワード

Javaハッシュ・ストレージ
Javaにハッシュされて格納されるデータ構造は,主にHashSet,HashMap,LinkedHashSet,LinkedHashMapおよびHashTableなどを指す.Javaのハッシュ・ストレージ・メカニズムを理解するには、equals()とhashCode()の2つの方法を理解する必要があります.equals()メソッドと"=="関係オペレータとの違いについては,別の記事で説明した.hashCode()では、Objectクラスで定義されるメソッドです.

public native int hashCode();

これはint値を返すローカルメソッドであり,Objectクラスでは実現されていない.この方法は主にハッシュを用いたデータ構造に適用され,ハッシュベースの集合に合わせて正常に動作する.例えば,1つのコンテナ(HashMapと仮定する)に1つのオブジェクトを挿入した場合,コンテナに既にそのオブジェクトが存在するか否かをどのように判断するか.容器中の元素は数千に達する可能性があるため,equals()法を用いて順次比較することは非常に非効率である.ハッシュの価値は速度にあり、キーをすぐに見つけることができるように保存します.要素のセットを格納する最も速いデータ構造は配列であるため、キーの情報(キー自体ではなくキーの情報であることに注意)を格納するために使用されます.しかし、配列は容量を調整できないため、Mapに数の不確定な値を保存したいのですが、キーの数が配列の容量に制限されている場合、どうすればいいのでしょうか.
答えは、配列はキー自体を保存するのではなく、キーオブジェクトによって数値を生成し、配列の下付き文字として使用します.この数値はハッシュコード(hashcode)で、Objectに定義され、あなたのクラスで上書きされる可能性のあるhashCode()メソッドによって生成されます.配列容量が固定される問題を解決するために,異なるキーは同じ下付きスケールを生成することができ,この現象を衝突と呼ぶ.そこで、コンテナで値をクエリーするプロセスは、hashCode()を使用して挿入するオブジェクトのハッシュコードを計算し、ハッシュコードを使用して配列をクエリーすることです.競合する処理では、配列が直接値を保存するのではなく、値のlistを保存し、listの値を線形にクエリーすることがよくあります.このクエリーは自然に遅いです.しかし,ハッシュ関数が十分であれば,配列の各位置には少ない値しかない.したがって,ハッシュメカニズムは配列のある位置にすばやくジャンプし,少ない要素のみを比較することができる.これがHashMapがこんなに速い理由です.HashMap.put()の方法で理解できます.

public V put(K key, V value) {
  if (table == EMPTY_TABLE) {
   inflateTable(threshold);
  }
  if (key == null)
   return putForNullKey(value);
  int hash = hash(key);
  int i = indexFor(hash, table.length);
  for (Entry 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;
 }


キーが空でない場合、キーオブジェクトに基づいてハッシュコードhashを取得し、ハッシュコードによって配列の下付きiを得ることが主な考え方である.table[i]で表されるlistで反復し、equals()によりキーが存在するか否かを判断し、存在する場合は新しい値で古い値を更新し、古い値を返す.そうでなければ、新しいキー値ペアをHashMapに追加します.ここからhashCodeメソッドの存在はequalsメソッドの呼び出し回数を減らし,プログラム効率を向上させるためであることが分かる.
ここで、hashCode()は常に一意の識別コードを返す必要はないが、equals()メソッドは、2つのオブジェクトが同じかどうかを厳格に判断しなければならないことに注意する必要がある.
読書に感謝して、みんなを助けることができることを望んで、みんなの当駅に対する支持に感謝します!