get
」、「HashMapでのメソッドの動作の内部メカニズムは何ですかput
?」。ここでは、簡単な例を使用して内部機能を説明してみます。あまり多くの理論には立ち入らずに、理解を深めるために例から始めて、Java でもget
メソッドがどのように機能するかを見ていきます。put
非常に簡単な例を見てみましょう。クラスCountry
(英語の「国」) があり、クラス オブジェクトをキーとして使用しCountry
、この国の首都の名前を値として使用します。以下は、キーと値のペアがハッシュ マップにどのように格納されるかを理解するのに役立つ例です。
1.国.java
package org.arpit.javapostsforlearning;
public class Country {
String name;
long population;
public Country(String name, long population) {
super();
this.name = name;
this.population = population;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public long getPopulation() {
return population;
}
public void setPopulation(long population) {
this.population = population;
}
// если длина имени в an objectе Country - четное число,
// то возвращаем 31(любое случайное число), а если нечетное - 95 (любое случайное число).
// указанный ниже метод - это не самый лучший способ генерации хеш-codeа,
// но мы воспользуемся им для более четкого понимания хеш-карт.
@Override
public int hashCode() {
if(this.name.length()%2==0)
return 31;
else
return 95;
}
@Override
public boolean equals(Object obj) {
Country other = (Country) obj;
if (name.equalsIgnoreCase((other.name)))
return true;
return false;
}
}
メソッドとイコールについてさらに詳しく知りたい場合は、このリンクhashcode
を参照してください。
2. HashMapStructure.java(メインクラス)
import java.util.HashMap;
import java.util.Iterator;
public class HashMapStructure {
/**
* @author Arpit Mandliya
*/
public static void main(String[] args) {
Country india=new Country("India",1000);
Country japan=new Country("Japan",10000);
Country france=new Country("France",2000);
Country russia=new Country("Russia",20000);
HashMap<country,string> countryCapitalMap=new HashMap<country,string>();
countryCapitalMap.put(india,"Delhi");
countryCapitalMap.put(japan,"Tokyo");
countryCapitalMap.put(france,"Paris");
countryCapitalMap.put(russia,"Moscow");
Iterator<country> countryCapitalIter=countryCapitalMap.keySet().iterator();//установите
//debug-точку на этой строке(23)
while(countryCapitalIter.hasNext())
{
Country countryObj=countryCapitalIter.next();
String capital=countryCapitalMap.get(countryObj);
System.out.println(countryObj.getName()+"----"+capital);
}
}
}
次に、ブレークポイントを 23 行目に設定し、run -> debug as -> Java applicationを実行します(翻訳者注 - Eclipse で有効です)。プログラムは 23 行目で実行を停止し、その後countryCapitalMapを右クリックしてwatchを選択します。次のようなテーブルが表示されます。 ここでは、次のことがわかります。
-
Entry[]
という名前の 16 個のセルの配列がありますtable
。 -
この配列には、クラスのオブジェクトが格納されます
Entry
。このクラスにHashMap
は内部クラス - がありますEntry
。このクラスのインスタンスはキーと値のペアです。クラス構造を見てみましょうEntry
。 -
ハッシュ マップでキーと値のペアを作成しようとするたびに、そのペアのクラス オブジェクトが作成され
Entry
、上記のテーブルに格納されますEntry[]
。ここで、このオブジェクトがこのテーブルのどこ (どのセル) に正確に書き込まれるのか疑問に思うはずです。キーと値のペアのキーの場合、ハッシュ コードは を使用して計算されますhashcode()
。そして、このハッシュ コードはテーブルのセル番号を計算するために使用されますEntry[]
。 -
ここで表のセル 10 を見ると、
Entry
という名前のクラス オブジェクトが表示されますHashMap$Entry
。 - 4 つのキーと値のペアを追加しましたが、配列には 2 つしかありません。これは、2 つのオブジェクトが同じハッシュ コードを持つ場合、それらは同じセルに格納されるためです。しかし、どうやって?オブジェクトはリンクされたリスト (
LinkedList
) として保存されます。
static class Entry implements Map.Entry
{
final K key;
V value;
Entry next;
final int hash;
...//продолжение codeа
}
Hashcode for Japan = 95 так How длина слова Japan имеет нечетное количество букв.
Hashcode for India = 95 так How длина слова India имеет нечетное количество букв.
HashCode for Russia = 31 так How длина слова Russia имеет четное количество букв.
HashCode for France = 31 так How длина слова France имеет четное количество букв.
次の図は、リンク リストの概念を説明します。 ハッシュ マップの構造についてはすでに理解できたので、と のメソッドに進みましょう。 put
get
置く:
このメソッドがどのように使用されるかを見てみましょう。/**
* Метод связывает указанное meaning с указанным ключом в данной хэш-карте. Если
* карта до этого уже содержала некоторое meaning, соответствующее этому ключу,
* то старое meaning заменяется на указанное.
* @param key
* ключ, с которым связывается указанное meaning
* @param value
* meaning, связываемое с указанным ключом
* @возвращает meaning связанное с <tt>ключом</tt>, or <tt>null</tt>,
* если ниHowое meaning не соответствует <tt>ключу</tt>. ( Возврат <tt>null</tt>
* может так же говорить о том, что в карте заведомо <tt>null</tt> был связан с
* <tt>ключом</tt>.)
*/
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;
}
では、このコードを段階的に理解してみましょう。
-
オブジェクトが
key
等しいかどうかをチェックしますnull
。そうであれば、オブジェクトのハッシュ コードは常に 0 であるため、オブジェクトはkey
location に保存されます。table[0]
null
-
次に、オブジェクトの
key
メソッドを呼び出してhashcode()
、そのハッシュ コードを計算します。このハッシュ コードは、クラス オブジェクトが格納される配列セルを決定するために使用されますEntry
。場合によっては、この関数があまり巧みに記述されていないことが発生するため、JDK 開発者は、以前に計算されたハッシュ コードを引数として受け取るhashcode
別の関数 - を作成しました。hash()
この関数についてさらに詳しく知りたい場合は、リンクをクリックしてください。 -
indexFor(hash,table.length)
table
クラスオブジェクトが格納されるように定義される配列内の特定のセルを定義するために使用されますEntry
。 -
この例で見たように、2 つのオブジェクトが
key
同じハッシュ コードを持つ場合 (この状況は衝突と呼ばれます)、それらはリンク リストの形式で保存されます。したがって、この段階ではリストを繰り返します。 -
新しく計算されたセルが空の場合、クラス オブジェクトは
Entry
このセルに直接保存されます。 -
next
このセルにすでに何らかのオブジェクトが含まれている場合は、フィールドがに等しい要素を反復処理しますnull
。この後、クラス オブジェクトがEntry
リストの次になります。 -
同じオブジェクトを
key
再度追加するとどうなるでしょうか? 論理的には、古い値を置き換える必要があります。はい、そうなります。反復中に、キーはequals()
(key.equals(k)
) メソッドを使用して比較されます。結果が true の場合、古い値は現在のオブジェクトの値に置き換えられますEntry
。
得る:
次に、このメソッドの応用を見てみましょう/**
* returns meaning, которое соответствует указанному ключу, or {@code null}, если
* данная карта не содержит пары с указанным ключом.
*
*
* <p>
* Более точно, если в данной карте содержится такой ключ {@code k}
* с соответствующим ему meaningм {@code v}, что {@code (key==null ? k==null : key.equals(k))},
* то метод возвращает {@code v}; в противном случае возвращается {@code null}.
* (может быть не более одной такой пары)
*
* </p><p>
* Возвращенное meaning {@code null} не <i>обязательно</i> говорит о том, что
* в карте нет пары с таким указанным ключом; а возможно, что в карте однозначно
* указано соответствие этого ключа со meaningм {@code null}.
* Можно воспользоваться операцией {@link #containsKey containsKey}, чтобы
* отличить эти два случая
* @see #put(Object, Object)
*/
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 メソッドがハッシュマップでどのように動作するかを理解できたので、put メソッドがどのように動作するかを理解するのは
get
非常に簡単です。ハッシュ マップから値を取得するためにメソッドにキーを渡すと、次のようになります。
-
オブジェクト
Ekey は等しいかどうかテストされます null
。そうであれば、セルに格納されているオブジェクトの値が返されますtable[0]
。 -
キー オブジェクトには、
hashcode()
ハッシュ コードを計算するメソッドが呼び出されます。 -
indexFor(hash,table.length)
table
クラス オブジェクトを取得する特定の配列セルを決定するために使用されますEntry
。 -
配列のセル番号を受け取った後、
table
メソッドを使用してリストを反復処理し、キーを比較しますequals()
。結果が true の場合はオブジェクトの値が返されEntry
、そうでない場合は -が返されますnull
。
覚えておくべきこと:
-
このクラスには、キーと値のペアを格納する
HashMap
内部クラスがありますEntry
。 -
クラスのオブジェクトは;という
Entry
配列に格納されます。Entry[ ]
table
-
配列セルはバケットと呼ばれ、リンクされたリストの最初の要素を格納します。
-
hashcode()
objectメソッドは、key
このクラス オブジェクトのバケットを見つけるために使用されますEntry
。 -
2 つのオブジェクトのキーが同じハッシュ コードを持つ場合、それらは同じ配列バケットに格納されます
table
。 -
equals()
オブジェクトのメソッドは、key
その一意性を確認するために使用されます。 -
メソッド
equals()
やhashcode()
オブジェクトはvalue
まったく使用されません。
GO TO FULL VERSION