พวกคุณส่วนใหญ่จะยอมรับว่า
ฉันคิดว่าหากคุณสนใจภายในและการทำงานของ HashMap แสดงว่าคุณคุ้นเคยกับพื้นฐานของHashMap แล้ว ดังนั้นฉันจะข้ามส่วนนั้นไป แต่ถ้าคุณยังใหม่กับสิ่ง นี้ฉันขอแนะนำให้คุณไปที่ ไซต์ Java Docs ก่อนที่เราจะไปต่อ ฉันขอแนะนำให้คุณอ่านบทความก่อนหน้าของฉัน: การทำงานกับ hashCode และวิธีเท่ากับใน Java เนื้อหาของบทความนี้:
คุณสามารถอ่านเพิ่มเติมเกี่ยวกับสิ่งนี้ได้ที่นี่:การทำงานกับ hashCode และวิธีเท่ากับใน Java
HashMap
วันนี้ เป็นหัวข้อสนทนาที่ชื่นชอบมากที่สุดระหว่างการสัมภาษณ์ บางครั้งฉันก็มีการสนทนาคล้าย ๆ กันกับเพื่อนร่วมงานและมันช่วยได้มาก ตอนนี้ฉันจะพูดคุยกับคุณเช่นนี้ - คำตอบเดียวที่เป็นไปได้
- การแฮชคืออะไร
- เล็กน้อยเกี่ยวกับชั้น
Entry
เรียน - อะไร
put()
. - วิธีการทำงานอย่างไร
get()
. - หมายเหตุ
คำตอบเดียวที่เป็นไปได้
หากใครขอให้อธิบาย " HashMap ทำงานอย่างไร?" " ฉันจะตอบง่ายๆ ว่า: " ตามหลักการของ Hashing " มันไม่ง่ายไปกว่านี้อีกแล้ว เพื่อทำความเข้าใจสิ่งนี้และรับคำตอบเพิ่มเติม คุณต้องแน่ใจว่าคุณรู้พื้นฐานของ Hashing ขวา?การแฮชคืออะไร
การแฮชในรูปแบบที่ง่ายที่สุดคือวิธีการแปลงตัวแปร/อ็อบเจ็กต์ให้เป็นโค้ดที่ไม่ซ้ำใคร หลังจากใช้สูตร/อัลกอริธึมกับคุณสมบัติแล้ว ฟังก์ชันแฮชที่แท้จริงต้องเป็นไปตามกฎต่อไปนี้: ฟังก์ชันแฮชจะต้องส่งคืนรหัสแฮชเดียวกันทุกครั้งที่ใช้กับวัตถุที่เหมือนกันหรือเท่ากัน กล่าวอีกนัยหนึ่งวัตถุสองชิ้นที่เหมือนกันจะต้องส่งคืนรหัสแฮชเดียวกันตามลำดับหมายเหตุ: ออบเจ็กต์ทั้งหมดใน Java สืบทอดการใช้งานมาตรฐานhashCode() ของฟังก์ชันที่อธิบายไว้ในObject คลาส ฟังก์ชันนี้ส่งคืนรหัสแฮชที่ได้รับโดยการแปลงที่อยู่ภายในของวัตถุเป็นตัวเลข ซึ่งนำไปสู่การสร้างรหัสเฉพาะสำหรับวัตถุแต่ละรายการ |
เล็กน้อยเกี่ยวกับชั้นเรียนรายการ
ตามคำจำกัดความ แผนที่คือ "วัตถุที่เก็บค่าและคีย์เป็นคู่" ค่อนข้างง่ายใช่มั้ย? แล้วใน 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
จะถูกจัดเก็บไว้ในตำแหน่งศูนย์ของอาร์เรย์เสมอ
GO TO FULL VERSION