HashMap ทำงานอย่างไรใน Java

พวกคุณส่วนใหญ่จะยอมรับว่าHashMapวันนี้ เป็นหัวข้อสนทนาที่ชื่นชอบมากที่สุดระหว่างการสัมภาษณ์ บางครั้งฉันก็มีการสนทนาคล้าย ๆ กันกับเพื่อนร่วมงานและมันช่วยได้มาก ตอนนี้ฉันจะพูดคุยกับคุณเช่นนี้ ฉันคิดว่าหากคุณสนใจภายในและการทำงานของ HashMap แสดงว่าคุณคุ้นเคยกับพื้นฐานของHashMap แล้ว ดังนั้นฉันจะข้ามส่วนนั้นไป แต่ถ้าคุณยังใหม่กับสิ่ง นี้ฉันขอแนะนำให้คุณไปที่ ไซต์ Java Docs ก่อนที่เราจะไปต่อ ฉันขอแนะนำให้คุณอ่านบทความก่อนหน้าของฉัน: การทำงานกับ hashCode และวิธีเท่ากับใน Java เนื้อหาของบทความนี้:

1. คำตอบเดียวที่เป็นไปได้
2. การแฮชคืออะไร
3. เล็กน้อยเกี่ยวกับชั้นEntryเรียน
4. อะไรput().
5. วิธีการทำงานอย่างไรget().
6. หมายเหตุ

คำตอบเดียวที่เป็นไปได้

หากใครขอให้อธิบาย " HashMap ทำงานอย่างไร?" " ฉันจะตอบง่ายๆ ว่า: " ตามหลักการของ Hashing " มันไม่ง่ายไปกว่านี้อีกแล้ว เพื่อทำความเข้าใจสิ่งนี้และรับคำตอบเพิ่มเติม คุณต้องแน่ใจว่าคุณรู้พื้นฐานของ Hashing ขวา?

การแฮชคืออะไร

การแฮชในรูปแบบที่ง่ายที่สุดคือวิธีการแปลงตัวแปร/อ็อบเจ็กต์ให้เป็นโค้ดที่ไม่ซ้ำใคร หลังจากใช้สูตร/อัลกอริธึมกับคุณสมบัติแล้ว ฟังก์ชันแฮชที่แท้จริงต้องเป็นไปตามกฎต่อไปนี้: ฟังก์ชันแฮชจะต้องส่งคืนรหัสแฮชเดียวกันทุกครั้งที่ใช้กับวัตถุที่เหมือนกันหรือเท่ากัน กล่าวอีกนัยหนึ่งวัตถุสองชิ้นที่เหมือนกันจะต้องส่งคืนรหัสแฮชเดียวกันตามลำดับ คุณสามารถอ่านเพิ่มเติมเกี่ยวกับสิ่งนี้ได้ที่นี่:การทำงานกับ hashCode และวิธีเท่ากับใน Java

เล็กน้อยเกี่ยวกับชั้นเรียนรายการ

ตามคำจำกัดความ แผนที่คือ "วัตถุที่เก็บค่าและคีย์เป็นคู่" ค่อนข้างง่ายใช่มั้ย? แล้วใน HashMap จะต้องมีกลไกอะไรสักอย่างที่เก็บคู่ของ Values ​​และ Keys ไว้บ้างหรือเปล่า? ตอบ - ใช่ HashMapมีคลาสภายในEntryที่มีลักษณะดังนี้:

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

โดยปกติแล้วคลาสEntryจะมีคีย์และค่าเก็บไว้เป็นแอตทริบิวต์ คีย์ถูกทำเครื่องหมายเป็นfinalและเรายังเห็นฟิลด์เพิ่มเติมอีกสองฟิลด์: nextและhash. เราจะพยายามทำความเข้าใจวัตถุประสงค์ของฟิลด์เหล่านี้ในขณะที่บทความดำเนินไป

Java 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


• นี่คือจุดเริ่มต้นของส่วนหลัก ตอนนี้ จากสิ่งที่เรารู้แล้วว่าวัตถุสองตัวที่ไม่เท่ากันสามารถมีรหัสแฮชเท่ากันได้ เราถามคำถาม: วัตถุสองชิ้นที่แตกต่างกันจะถูกวางในตำแหน่งเดียวกันในอาร์เรย์ [bucket] หรือไม่ คำตอบLinkedListคือ หากคุณจำได้ คลาสนั้นEntryมีแอตทริบิวต์ " next" คุณลักษณะนี้จะชี้ไปที่วัตถุถัดไปในห่วงโซ่เสมอ LinkedListตรง นี้แหละคือพฤติกรรม

ดังนั้นวัตถุจึงEntryถูกจัดเก็บอยู่ในรูปแบบ LinkedListเมื่อวัตถุEntryถูกวางในตำแหน่งเฉพาะ HashMap จะตรวจสอบเพื่อดูว่ามีรายการอยู่ที่ตำแหน่งนั้นหรือไม่ หากไม่มีทางเข้า วัตถุก็จะวางอยู่ที่ตำแหน่งนี้ อย่างไรก็ตาม หากมีวัตถุอยู่ที่ตำแหน่งนี้อยู่แล้ว คุณลักษณะถัดไปจะถูกเลือก ถ้ามันกลับมาnullและวัตถุปัจจุบันEntryกลายเป็นลิงค์ถัดไปในไฟล์LinkedList. ถ้าตัวแปรถัดไปไม่ใช่ ขั้นตอนnullจะถูกทำซ้ำสำหรับตัวแปรถัดไปจนกว่าจะnullพบ จะเกิดอะไรขึ้นถ้าเราใส่วัตถุอื่นที่มีค่าแตกต่างออกไปแต่ใช้คีย์เดียวกันกับเมื่อก่อน? ตามหลักเหตุผลแล้ว สิ่งนี้ควรส่งผลให้มีการแทนที่ค่าเก่า สิ่งนี้เกิดขึ้นได้อย่างไร? โดยทั่วไป หลังจากกำหนดตำแหน่งของวัตถุEntryขณะเคลื่อนที่LinkedListไปยังตำแหน่งที่คำนวณHashMapจะเรียกวิธีการเปรียบเทียบคีย์สำหรับแต่ละEntryวัตถุ Entryออบเจ็กต์ทั้งหมดเหล่านี้LinkedListอาจมีรหัสแฮชที่คล้ายกัน แต่วิธีการequals()จะตรวจสอบความคล้ายคลึงกันที่แท้จริง สิ่งนี้จะแทนที่เฉพาะค่าภายในEntry. ดังนั้น HashMap จึงรับประกันความเป็นเอกลักษณ์ของคีย์ทั้งหมด

วิธีการ Java 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จะถูกจัดเก็บไว้ในตำแหน่งศูนย์ของอาร์เรย์เสมอ

ฉันหวังว่าฉันจะถ่ายทอดความคิดของฉันอย่างถูกต้องในบทความนี้ หากคุณพบข้อผิดพลาดหรือมีคำถามโปรดทิ้งไว้ในความคิดเห็น มีความสุขในการเรียนรู้!