HashMap چگونه در جاوا کار می کند

اکثر شما موافقید که HashMapامروز، مورد علاقه ترین موضوع برای بحث در طول مصاحبه است. گاهی اوقات با همکارانم بحث های مشابهی داشتم و واقعا کمک می کرد. حالا من چنین بحثی با شما خواهم داشت. من فرض می‌کنم که اگر به قسمت‌های داخلی و عملکرد HashMap علاقه‌مند هستید، از قبل با اصول HashMap آشنا هستید ، بنابراین از آن قسمت صرف نظر می‌کنم. اما اگر در این زمینه تازه کار هستید، پیشنهاد می کنم به سایت Java Docs سر بزنید . قبل از اینکه ادامه دهیم، به شدت توصیه می کنم مقاله قبلی من را بررسی کنید: کار با هش کد و متد برابر در جاوا. مطالب این مقاله:

1. تنها پاسخ ممکن
2. هشینگ چیست.
3. Entryکمی در مورد کلاس
4. چه می کند put().
5. روش چگونه کار می کند get().
6. یادداشت

تنها پاسخ ممکن

اگر کسی از من بخواهد توضیح دهم " HashMap چگونه کار می کند؟" "، من به سادگی پاسخ خواهم داد: " طبق اصول هشینگ ." ساده تر از این نمی توانست باشد. برای درک این موضوع و دریافت پاسخ گسترده، باید مطمئن شوید که اصول Hashing را می دانید. درست؟

هشینگ چیست

هش کردن در ساده‌ترین شکل خود راهی برای تبدیل هر متغیر/شیء به یک کد منحصر به فرد پس از اعمال هر فرمول/الگوریتم بر روی ویژگی‌های آن‌ها است. یک تابع هش واقعی باید از قانون زیر پیروی کند: یک تابع هش باید همان کد هش را هر زمان که برای اشیاء یکسان یا مساوی اعمال شود، برگرداند. به عبارت دیگر، دو شیء یکسان باید به نوبه خود کدهای هش یکسانی را برگردانند. در اینجا می توانید اطلاعات بیشتری در این مورد بخوانید: کار با متد hashCode و برابر در جاوا

کمی در مورد کلاس ورودی

طبق تعریف، نقشه «شیئی است که مقادیر و کلیدها را به صورت جفت ذخیره می‌کند». خیلی ساده، درست است؟ بنابراین، باید مکانیزمی در HashMap وجود داشته باشد که جفت مقادیر و کلیدها را ذخیره کند؟ پاسخ - بله. HashMapیک کلاس داخلی دارد Entryکه به شکل زیر است:

static class Entry implements Map.Entry
{
        final K key;
        V value;
        Entry next;
        final int hash;
        ...//остальной code тут…
}

به طور طبیعی، کلاس Entryدارای یک کلید و مقدار است که به عنوان ویژگی ذخیره می شود. کلید به عنوان علامت گذاری شده است finalو همچنین دو فیلد اضافی را مشاهده می کنیم: nextو hash. با پیشرفت مقاله سعی خواهیم کرد هدف این رشته ها را درک کنیم.

متد put() جاوا چه کاری انجام می دهد؟

قبل از اینکه به پیاده سازی متد بپردازیم put()، درک این نکته بسیار مهم است که نمونه های یک کلاس Entryدر یک آرایه ذخیره می شوند. کلاس HashMap این متغیر را به صورت زیر تعریف می کند:

/**
* Размер таблицы, изменяется при необходимости. Длина всегда должна быть
* кратна двум!
*/
    transient Entry[] table;

حالا به کد پیاده سازی متد نگاهی بیندازید put():

/**
* Связывает определенное meaning с определенным ключом в этой карте(map).
* Если карта перед этим содержала meaning для данного ключа, это meaning
* заменится на новое.
*
* @param key
*            ключ с которым указанное meaning должно быть связано.
* @param value
*            meaning которое должно быть связано с ключом.
* @return вернет предыдущее meaning связанное с key, or null
*         если не было значений связанных с key. (Вернет null
*         так же, если перед этим key был связан со meaningм null)
*/
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;
}

بیایید گام به گام آن را بفهمیم:

• اول از همه، بررسی می کنیم که آیا کلید وجود دارد یا خیر. اگر کلید ( null) وجود نداشته باشد، مقدار در جدول در موقعیت صفر قرار می گیرد زیرا کد هش برای مقدار null، است это – всегда 0.


• در مرحله بعد مقدار هش با استفاده از کد هش کلید بدست آمده با فراخوانی متد محاسبه می شود hashCode(). این مقدار هش برای محاسبه موقعیت آرایه ای که شی قرار می گیرد استفاده می شود Entry. طراحان JDK فرض کردند که یک تابع ضعیف hashCode()می تواند مقدار هش را که خیلی زیاد یا خیلی کم است برگرداند. برای حل این مشکل، تابع دیگری را معرفی کردند hash()و مقدار هش یک شی را به آن منتقل کردند تا مقدار هش با اندازه آرایه مطابقت داشته باشد.


• اکنون تابع فراخوانی می شود indexFor(hash, table.length)تا موقعیت دقیقی را که جسم در آن قرار می گیرد محاسبه کند Entry.


• اینجاست که قسمت اصلی شروع می شود. حال، بر اساس آنچه می دانیم که دو شی نابرابر می توانند کدهای هش مساوی داشته باشند، این سوال را مطرح می کنیم: آیا دو شی متفاوت در یک موقعیت در آرایه [سطل] قرار می گیرند؟ پاسخ این است LinkedList. اگر به خاطر داشته باشید، کلاس Entryیک ویژگی " next" دارد. این ویژگی همیشه به شی بعدی در زنجیره اشاره می کند. این دقیقاً رفتار است LinkedList.

بنابراین، اشیاء Entryدر فرم ذخیره می شوند LinkedList. وقتی قرار است یک شی Entryدر یک مکان خاص قرار گیرد، HashMap بررسی می کند که آیا قبلاً یک ورودی در آن مکان وجود دارد یا خیر. اگر ورودی وجود نداشته باشد، شی در این موقعیت قرار می گیرد. با این حال، اگر قبلاً یک شی در این موقعیت وجود داشته باشد، ویژگی بعدی بررسی می شود. اگر برگردد nullو شی فعلی Entryتبدیل به پیوند بعدی در شود LinkedList. اگر متغیر بعدی نباشد null، این روش برای متغیر بعدی تکرار می شود تا زمانی که آن را پیدا کند null. اگر شی دیگری را با مقدار متفاوت اما با همان کلید قبلی قرار دهیم چه می شود؟ منطقاً این باید منجر به جایگزینی مقدار قدیمی شود. چگونه این اتفاق می افتد؟ به طور کلی، پس از تعیین موقعیت یک شی Entry، هنگام پیمایش LinkedListبه موقعیت محاسبه شده، HashMapروش مقایسه کلید را برای هر شیء فراخوانی می کند Entry. همه این Entryاشیا LinkedListممکن است کدهای هش مشابهی داشته باشند، اما این روش equals()شباهت واقعی را بررسی می کند. این فقط مقدار را جایگزین می کند Entry. بنابراین، HashMap منحصر به فرد بودن همه کلیدها را تضمین می کند.

متد get() جاوا چگونه کار می کند؟

اکنون ایده ای داریم که چگونه جفت های کلید-مقدار در HashMap. سوال بزرگ بعدی این است: وقتی یک شی از یک HashMap به یک متد ارسال می شود چه اتفاقی می افتد get()؟ ارزش یک شی چگونه تعیین می شود؟ ما باید از قبل پاسخ را بدانیم، زیرا روشی که در آن منحصر به فرد بودن یک کلید در روش تعیین می شود، put()همان منطقی را دارد که روش اعمال می کند get(). هنگامی که HashMapکلید شیء ارسال شده را به عنوان آرگومان تعیین می کند، به سادگی مقدار مربوطه را برمی گرداند Entry. اگر هیچ منطبقی یافت نشد، روش get()برمی‌گردد null. بیایید نگاهی به کد بیندازیم:

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()تا این مرحله مشابه متد است if (e.hash == hash && ((k = e.key) == key || key.equals(k)))و پس از آن به سادگی مقدار شی را برمی گرداند.

یادداشت

• ساختار داده ای که در یک شی ذخیره می شود Entryآرایه ای با نام tableو نوع است Entry.
• هر موقعیت جداگانه در آرایه یک سطل نامیده می شود زیرا می تواند اولین عنصر LinkedListاشیاء را در خود داشته باشد Entry.
• hashCode()کلید برای محاسبه موقعیت جسم مورد نیاز است Entry.
• equals()از کلید برای بررسی منحصر به فرد بودن کلید در نقشه ( map) استفاده می شود.
• hashCode()و مقادیر در روش ها و در equals()استفاده نمی شوند .get()set()HashMap
• کد هش برای کلیدهای دارای مقدار nullهمیشه 0 است. و چنین شی Entryهمیشه در موقعیت صفر آرایه ذخیره می شود.

امیدوارم در این مقاله افکارم را به درستی بیان کرده باشم. اگر اشکالی پیدا کردید یا سؤالی دارید، لطفاً آنها را در نظرات مطرح کنید. یادگیری مبارک!