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 -> отладка ретінде-> java қолданбасын іске қосыңыз (аудармашының ескертпесі - Eclipse үшін жарамды). Бағдарлама 23-жолда орындалуды тоқтатады, содан кейін countryCapitalMap белгішесін тінтуірдің оң жақ түймешігімен басып, қарауды таңдаңыз . Сіз келесідей кестені көресіз: Мұнда біз келесіні көреміз:
-
Entry[]
деп аталатын 16 ұяшықтан тұратын массив барtable
; -
Бұл массив сынып an objectілерін сақтайды
Entry
. СыныптыңHashMap
ішкі класы бар -Entry
. Және бұл сыныптың даналары кілт-мән жұптары болып табылады. Сынып құрылымын қарастырайықEntry
: -
Хэш картада кілт-мән жұбын жасауға тырысқан сайын, сол жұп үшін сынып нысаны жасалады
Entry
және ол жоғарыдағы кестеде сақталадыEntry[]
. Ал енді осы кестенің қай жерінде (қай ұяшықта) бұл нысан жазылады деген сұрақ туындауы керек. Кілт-мән жұбындағы кілт үшін хэш codeы арқылы есептеледіhashcode()
. Және бұл хэш-code кесте ұяшығының нөмірін есептеу үшін қолданыладыEntry[]
; -
Енді кестенің 10 ұяшығын қарасаңыз,
Entry
атты класс нысанын көресізHashMap$Entry
; - Біз 4 кілт-мән жұбын қостық, бірақ массивте тек 2 ғана бар!!! Себебі 2 нысанның хэш-codeы бірдей болса, олар бір ұяшықта сақталады. Бірақ қалай? Нысандар байланыстырылған тізім ( ) ретінде сақталады
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;
}
Енді осы codeты кезең-кезеңімен түсінуге тырысайық:
-
key
Нысанның теңдігін тексеремізnull
. Олай болса, нысанkey
орнында сақталады,table[0]
себебі хэш codeыnull
әрқашан 0 болады; -
Әрі қарай, біз хэш codeын есептейтін нысан
key
әдісін шақырамыз.hashcode()
Бұл хэш codeы сынып нысаны сақталатын жиым ұяшығын анықтау үшін пайдаланыладыEntry
.hashcode
Кейде бұл функция өте шебер жазылмаған кезде болады , сондықтан JDK әзірлеушілеріhash()
аргумент ретінде бұрын есептелген хэш-codeты қабылдайтын басқа функцияны жасады - . Егер сізді осы функция туралы толығырақ оқығыңыз келсе, сілтеме бойынша өтуіңізге болады ; -
indexFor(hash,table.length)
алаптағы белгілі бір ұяшықты анықтау үшін пайдаланылады,table
онда сақталатын сынып нысаны анықталадыEntry
; -
Біздің мысалда көргеніміздей, егер екі нысанның
key
хэш-codeы бірдей болса (бұл жағдай соқтығыс деп аталады), онда олар байланыстырылған тізім түрінде сақталады. Сондықтан, осы кезеңде біз тізімді қайталаймыз: -
егер жаңадан есептелген ұяшық бос болса, сынып нысаны
Entry
тікелей осы ұяшықта сақталады; -
next
егер бұл ұяшық әлдеқашан нысанды қамтыса, өрісі -ге тең элементке қайталанадыnull
. Осыдан кейін біздің сынып an objectісіEntry
тізімде келесі болады; -
сол нысанды қайта қоссақ ше
key
? Логикалық түрде ол ескі мәнді ауыстыруы керек. Иә, солай болады.equals()
Итерация кезінде пернелер ( ) әдісі арқылы салыстырыладыkey.equals(k)
. Нәтиже ақиқат болса, ескі мән ағымдағы нысанның мәнімен ауыстырылады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 әдісінің хэшмаптарда қалай жұмыс істейтінін түсінген болсаңыз, қою әдісі қалай жұмыс істейтінін түсіну
get
өте қарапайым. Хэш картасынан мән алу әдісіне кез келген кілтті бергенде:
-
Объект
Екей теңдік үшін сыналады null
. Олай болса, ұяшықта сақталған нысанның мәні қайтарыладыtable[0]
; -
hashcode()
Негізгі нысанда хэш codeын есептейтін әдіс бар ; -
indexFor(hash,table.length)
table
класс an objectісін алуға болатын нақты массив ұяшығын анықтау үшін пайдаланыладыEntry
; -
Жиым ұяшығының нөмірін алғаннан кейін
table
ол тізім бойынша қайталанады және әдісті пайдаланып кілттерді салыстырадыequals()
. Егер нәтиже ақиқат болса, онда нысанның мәні қайтарыладыEntry
, әйтпесе -null
.
Есте сақтау керек нәрселер:
-
Сыныпта кілт-мән жұптарын сақтайтын
HashMap
ішкі класс бар ;Entry
-
Кластың an objectілері деп аталатын
Entry
массивте сақталады ;Entry[ ]
table
-
Жиым ұяшығы шелек деп аталады және байланыстырылған тізімнің бірінші элементін сақтайды;
-
hashcode()
Объект әдісіkey
осы класс an objectінің шелегін табу үшін қолданыладыEntry
; -
Егер екі нысанның кілттерінің хэш-codeы бірдей болса, олар бір массив шелегінде сақталады
table
; -
equals()
Объектінің әдісіkey
оның бірегейлігін растау үшін қолданылады; -
Әдістер
equals()
менhashcode()
an objectілерvalue
мүлдем қолданылмайды.
GO TO FULL VERSION