get
w put
HashMap?”. Tutaj postaram się wyjaśnić wewnętrzną funkcjonalność na prostym przykładzie. Nie wdając się zbytnio w teorię, zaczniemy od przykładu, abyś mógł lepiej zrozumieć, a następnie zobaczyć, jak metody działają get
również put
w Javie . Weźmy bardzo prosty przykład. Mamy klasę Country
(angielski „kraj”), użyjemy obiektu klasy Country
jako klucza, a nazwę stolicy tego kraju jako wartości. Poniżej znajduje się przykład, który pomoże nam zrozumieć, w jaki sposób para klucz-wartość będzie przechowywana na mapie skrótów.
1. Kraj.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;
}
// если длина имени в obiektе Country - четное число,
// то возвращаем 31(любое случайное число), а если нечетное - 95 (любое случайное число).
// указанный ниже метод - это не самый лучший способ генерации хеш-kodа,
// но мы воспользуемся им для более четкого понимания хеш-карт.
@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;
}
}
Jeśli chcesz zrozumieć i dowiedzieć się więcej na temat metod hashcode
i równości, możesz kliknąć ten link .
2. HashMapStructure.java (klasa główna)
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);
}
}
}
Teraz ustaw punkt przerwania na linię 23 i uruchom polecenie run -> debug as-> aplikacja Java (uwaga tłumacza - dotyczy Eclipse). Program zatrzyma wykonywanie w linii 23, po czym kliknij prawym przyciskiem myszy countryCapitalMap i wybierz opcję watch . Zobaczysz następującą tabelę: Tutaj widzimy, co następuje:
-
Istnieje tablica
Entry[]
złożona z 16 komórek o nazwachtable
; -
Tablica ta przechowuje obiekty klasy
Entry
. KlasaHashMap
ma klasę wewnętrzną -Entry
. Instancje tej klasy to pary klucz-wartość. Przyjrzyjmy się strukturze klasEntry
: -
Za każdym razem, gdy spróbujemy utworzyć parę klucz-wartość na mapie skrótów, dla tej pary zostanie utworzony obiekt klasy,
Entry
który będzie przechowywany w powyższej tabeliEntry[]
. A teraz powinieneś się zastanawiać, gdzie dokładnie w tej tabeli ten obiekt zostanie zapisany (w której komórce). W przypadku klucza w parze klucz-wartość kod skrótu jest obliczany przy użyciu metodyhashcode()
. Ten kod skrótu jest używany do obliczenia numeru komórki tabeliEntry[]
; -
Teraz, jeśli spojrzysz na komórkę 10 tabeli, zobaczysz obiekt klasy
Entry
o nazwieHashMap$Entry
; - Dodaliśmy 4 pary klucz-wartość, ale w tablicy są tylko 2!!! Dzieje się tak dlatego, że jeśli 2 obiekty mają ten sam kod skrótu, wówczas będą przechowywane w tej samej komórce. Ale jak? Obiekty będą przechowywane jako lista połączona (
LinkedList
).
static class Entry implements Map.Entry
{
final K key;
V value;
Entry next;
final int hash;
...//продолжение kodа
}
Hashcode for Japan = 95 так Jak длина слова Japan имеет нечетное количество букв.
Hashcode for India = 95 так Jak длина слова India имеет нечетное количество букв.
HashCode for Russia = 31 так Jak длина слова Russia имеет четное количество букв.
HashCode for France = 31 так Jak длина слова France имеет четное количество букв.
Poniższy rysunek wyjaśni ideę listy połączonej: Teraz, gdy masz już wiedzę na temat struktury map skrótów, przejdźmy do metod put
i get
.
Umieścić:
Zobaczmy, jak stosowana jest ta metoda:/**
* Метод связывает указанное oznaczający с указанным ключом в данной хэш-карте. Если
* карта до этого уже содержала некоторое oznaczający, соответствующее этому ключу,
* то старое oznaczający заменяется на указанное.
* @param key
* ключ, с которым связывается указанное oznaczający
* @param value
* oznaczający, связываемое с указанным ключом
* @возвращает oznaczający связанное с <tt>ключом</tt>, Lub <tt>null</tt>,
* если ниJakое oznaczający не соответствует <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;
}
Spróbujmy teraz zrozumieć ten kod krok po kroku:
-
Sprawdzamy obiekt
key
pod kątem równościnull
. Jeśli tak, to obiektkey
zostanie zapisany w lokalizacji,table[0]
ponieważ kod skrótu dlanull
ma zawsze wartość 0; -
key
Następnie wywołujemy metodę obiektuhashcode()
, która obliczy jego kod skrótu. Ten kod skrótu służy do określenia komórki tablicy, w której będzie przechowywany obiekt klasyEntry
. Czasami zdarza się, że funkcja tahashcode
nie jest napisana zbyt umiejętnie, dlatego twórcy JDK stworzyli inną funkcję -hash()
, która jako argument przyjmuje wcześniej obliczony kod skrótu. Jeśli chcesz przeczytać więcej o tej funkcji, kliknij link ; -
indexFor(hash,table.length)
używany do zdefiniowania konkretnej komórki w tablicy,table
w której zdefiniowany zostanie obiekt klasy, który ma być przechowywanyEntry
; -
Jak widzieliśmy w naszym przykładzie, jeśli dwa obiekty
key
mają ten sam kod skrótu (taka sytuacja jest nazywana kolizją), to zostaną one zapisane w formie połączonej listy. Dlatego na tym etapie iterujemy naszą listę: -
jeżeli nowo obliczona komórka jest pusta, to obiekt klasy
Entry
zostanie zapisany bezpośrednio w tej komórce; -
jeśli ta komórka zawiera już jakiś obiekt, iteruje do elementu, którego pole jest
next
równenull
. Następnie obiekt naszej klasyEntry
będzie następny na liście; -
key
co jeśli ponownie dodamy ten sam obiekt ? Logicznie rzecz biorąc, powinna zastąpić starą wartość. Tak, tak będzie. W trakcie iteracji klucze będą porównywane metodąequals()
(key.equals(k)
). Jeśli wynik będzie prawdziwy, wówczas stara wartość zostanie zastąpiona wartością bieżącego obiektuEntry
.
Dostawać:
Przyjrzyjmy się teraz zastosowaniu tej metody/**
* zwroty oznaczający, которое соответствует указанному ключу, Lub {@code null}, если
* данная карта не содержит пары с указанным ключом.
*
*
* <p>
* Более точно, если в данной карте содержится такой ключ {@code k}
* с соответствующим ему oznaczającyм {@code v}, что {@code (key==null ? k==null : key.equals(k))},
* то метод возвращает {@code v}; в противном случае возвращается {@code null}.
* (может быть не более одной такой пары)
*
* </p><p>
* Возвращенное oznaczający {@code null} не <i>обязательно</i> говорит о том, что
* в карте нет пары с таким указанным ключом; а возможно, что в карте однозначно
* указано соответствие этого ключа со oznaczającyм {@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;
}
Teraz, gdy już wiesz, jak działa metoda put w mapach skrótów, zrozumienie, jak działa metoda put, jest
get
bardzo proste. Kiedy przekazujesz dowolny klucz do metody, aby uzyskać wartość z mapy skrótów:
-
Obiekt
Ekey jest testowany pod kątem równości null
. Jeżeli tak, to zwrócona zostanie wartość obiektu zapisanego w komórcetable[0]
; -
Obiekt klucza ma metodę
hashcode()
, która oblicza kod skrótu; -
indexFor(hash,table.length)
używany do określenia konkretnej komórki tablicy,table
z której ma zostać pobrany obiekt klasyEntry
; -
Po otrzymaniu numeru komórki tablicy
table
będzie iterował po liście i porównał klucze metodąequals()
. Jeżeli wynik będzie prawdziwy to zwrócona zostanie wartość obiektuEntry
, w przeciwnym wypadku -null
.
Rzeczy do zapamiętania:
-
Klasa
HashMap
ma klasę wewnętrznąEntry
, która przechowuje pary klucz-wartość; -
Obiekty klasy
Entry
przechowywane są w tablicyEntry[ ]
zwanejtable
; -
Komórka tablicowa nazywana jest wiadrem i przechowuje pierwszy element połączonej listy;
-
Do znalezienia zasobnika obiektu tej klasy używana jest metoda
hashcode()
obiektowa ;key
Entry
-
Jeśli klucze dwóch obiektów mają ten sam kod skrótu, będą one przechowywane w tym samym wiadrze tablicy
table
; -
Metoda
equals()
obiektukey
służy do potwierdzenia jego unikalności; -
Metody
equals()
ihashcode()
obiektyvalue
nie są w ogóle używane.
GO TO FULL VERSION