get
"، "مکانیسم داخلی نحوه عملکرد متدها در HashMap چیست put
؟". در اینجا سعی می کنم با استفاده از یک مثال ساده عملکرد داخلی را توضیح دهم. بدون پرداختن به تئوری زیاد، با یک مثال شروع می کنیم تا بهتر متوجه شوید و سپس ببینید که روش ها در جاوا get
نیز چگونه کار می کنند. put
بیایید یک مثال بسیار ساده بزنیم. ما یک کلاس داریم Country
(کشور انگلیسی)، از شی کلاس Country
به عنوان کلید و نام پایتخت این کشور به عنوان مقدار استفاده می کنیم. در زیر مثالی آورده شده است تا به ما کمک کند بفهمیم چگونه یک جفت کلید-مقدار در یک نقشه هش ذخیره می شود.
1. Country.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 کلیک راست کرده و ساعت را انتخاب کنید . جدولی مانند این را مشاهده خواهید کرد: در اینجا موارد زیر را مشاهده می کنیم:
-
آرایه ای
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
. اگر چنین است، آنگاه شیkey
در مکان ذخیره می شودtable[0]
زیرا کد هش برایnull
همیشه 0 است. -
key
در مرحله بعد، متد شی را فراخوانی می کنیمhashcode()
که کد هش آن را محاسبه می کند. این کد هش برای تعیین سلول آرایه ای که شی کلاس در آن ذخیره می شود استفاده می شودEntry
. گاهی اوقات اتفاق می افتد که این تابعhashcode
خیلی ماهرانه نوشته نشده است، بنابراین توسعه دهندگان JDK یک تابع متفاوت ایجاد می کنند -hash()
که کد هش محاسبه شده قبلی را به عنوان آرگومان می گیرد. اگر علاقه مند به مطالعه جزئیات بیشتر در مورد این عملکرد هستید، می توانید پیوند را دنبال کنید . -
indexFor(hash,table.length)
برای تعریف یک سلول خاص در آرایه استفاده می شودtable
که در آن یک شی کلاس تعریف می شود تا ذخیره شودEntry
. -
همانطور که در مثال خود دیدیم، اگر دو شی
key
دارای کد هش یکسانی باشند (این وضعیت به عنوان یک برخورد شناخته میشود)، در قالب یک لیست پیوندی ذخیره میشوند. بنابراین، در این مرحله ما لیست خود را تکرار می کنیم: -
اگر سلول تازه محاسبه شده خالی باشد، شی کلاس
Entry
مستقیماً در این سلول ذخیره می شود. -
اگر این سلول قبلاً حاوی شیء باشد، در عنصری که میدان آن
next
برابر است تکرار می شودnull
. پس از این، شی کلاس ما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 در هش مپ دارید، درک نحوه عملکرد متد put
get
بسیار ساده است. وقتی کلیدی را به یک متد ارسال می کنید تا مقداری از نقشه هش بدست آورید:
-
یک شی
Ekey برای برابری آزمایش می شود null
. در این صورت، مقدار شی ذخیره شده در سلول برگردانده می شودtable[0]
. -
شی کلید متدی به نام دارد
hashcode()
که کد هش را محاسبه می کند. -
indexFor(hash,table.length)
برای تعیین یک سلول آرایه خاصtable
که از آن یک شی کلاس گرفته شود استفاده می شودEntry
. -
پس از دریافت شماره سلول آرایه،
table
در لیست تکرار می شود و کلیدها را با استفاده از روش مقایسه می کندequals()
. اگر نتیجه درست باشد، مقدار شی برگردانده می شودEntry
، در غیر این صورت -null
.
چیز هایی برای به یاد آوردن:
-
کلاس
HashMap
دارای یک کلاس داخلی استEntry
که جفت های کلید-مقدار را ذخیره می کند. -
اشیاء کلاس
Entry
در آرایه ایEntry[ ]
به نامtable
; -
یک سلول آرایه یک سطل نامیده می شود و اولین عنصر یک لیست پیوندی را ذخیره می کند.
-
متد
hashcode()
شیءkey
برای یافتن سطل شیء این کلاس استفاده می شودEntry
. -
اگر کلیدهای دو شی دارای کد هش یکسانی باشند، در یک سطل آرایه ذخیره می شوند
table
. -
روش یک
equals()
شیkey
برای تایید منحصر به فرد بودن آن استفاده می شود. -
از روش ها
equals()
وhashcode()
اشیاvalue
اصلا استفاده نمی شود.
GO TO FULL VERSION