หากใครให้ฉันอธิบายกลไกการทำงานของแผนที่แฮชฉันจะตอบง่ายๆ: "กฎที่ใช้แฮช" ประโยคนี้ง่ายมาก แต่ก่อนที่จะเข้าใจประโยคนี้ก่อนอื่นเราต้องเข้าใจสิ่งที่ ISH ใช่มั้ย
Beh คืออะไร
แฮชเป็นเพียงสตริงที่ไม่ซ้ำกันที่ได้รับหลังจากแอตทริบิวต์ของตัวแปร/วัตถุถูกนำไปใช้กับอัลกอริทึมที่แน่นอนและสตริงนี้ใช้เพื่อกำหนดเอกลักษณ์ของตัวแปร/วัตถุ ฟังก์ชั่นแฮชที่ถูกต้องจะต้องปฏิบัติตามเกณฑ์นี้
เมื่อฟังก์ชั่นแฮชถูกนำไปใช้กับวัตถุเดียวกันหรือวัตถุเท่ากันการดำเนินการแต่ละครั้งควรส่งคืนค่าเดียวกัน กล่าวอีกนัยหนึ่งวัตถุที่เท่าเทียมกันสองชิ้นควรมี hashcode เดียวกัน
หมายเหตุ: วัตถุ Java ทั้งหมดสืบทอดเมธอด hashCode () เริ่มต้นจากคลาสวัตถุ วิธีนี้ส่งคืนที่อยู่ของวัตถุในหน่วยความจำเป็นจำนวนเต็ม
บทนำสู่ชั้นเรียน
คำจำกัดความของแผนที่คือ: วัตถุจากคีย์การแมปถึงค่า ง่ายมากใช่มั้ย
ดังนั้นจะต้องมีกลไกบางอย่างใน HASHMAP เพื่อจัดเก็บคู่ค่าคีย์เหล่านี้ Make HashMap มีรายการภายในชั้นเรียนซึ่งมีลักษณะเช่นนี้
รายการระดับคงที่ <k, v> ใช้ map.entry <k, v> {key สุดท้าย k;แน่นอนคลาสรายการมีคุณสมบัติในการจัดเก็บค่าคีย์ คีย์ถูกทำเครื่องหมายโดยสุดท้าย ต่อไปเราพยายามเข้าใจความหมายของตัวแปรเหล่านี้
วิธีการใส่ () ทำอะไรจริง?
ก่อนที่จะดูการใช้วิธีการพัตต์มีความจำเป็นที่จะต้องดูที่การจัดเก็บของอินสแตนซ์รายการในอาร์เรย์
/ ** * ตารางการปรับขนาดความยาว /*** เชื่อมโยงค่าที่ระบุกับคีย์ที่ระบุในแผนที่นี้* หากแผนที่ที่มีอยู่ก่อนหน้านี้สำหรับคีย์ค่าเก่า* จะเป็น CED ค่าค่าที่จะเชื่อมโยงกับคีย์ระบุ* @return ค่าก่อนหน้านี้ที่เกี่ยวข้องกับ </tt> หรือ* <tt> null </tt> Return ยังสามารถระบุได้ว่าแผนที่* ก่อนหน้านี้เชื่อมโยง <tt> null </tt> คีย์ </tt>.)*/public v ใส่ (k key, value) {if (key == null) return putfornullkey (ค่า); int hash = มี (key.hashcode ()); && (K = E.Key) == KEY || key.equals (k)) {v oldValue = e.value; คีย์ทั้งหมด); ให้เราดูทีละขั้นตอน
ก่อนอื่นให้ตรวจสอบว่าคีย์เป็น NULL หรือไม่
ถัดไปค่าแฮชของคีย์นี้จะถูกคำนวณผ่านเมธอด hashCode () คีย์ซึ่งใช้ในการคำนวณตำแหน่งในอาร์เรย์ของวัตถุรายการ นักออกแบบของ JDK สันนิษฐานว่าบางคนอาจเขียนวิธีการ HashCode () ที่แย่มากและจะมีค่าแฮชขนาดใหญ่หรือเล็กมาก เพื่อแก้ปัญหานี้พวกเขาได้แนะนำฟังก์ชั่นแฮชอื่น ๆ เพื่อยอมรับ hashcode () ของวัตถุและแปลงเป็นความสามารถของอาร์เรย์
ถัดไปคือ indexfor (แฮชตารางความยาว) ซึ่งคำนวณตำแหน่งที่แม่นยำของที่เก็บอ็อบเจ็กต์รายการ
ต่อไปเป็นส่วนหลัก
คำตอบคือ LinkedList หากคุณจำได้ว่าคลาสรายการจะมีตัวแปรถัดไปตัวแปรนี้จะชี้ไปที่ตัวแปรถัดไปในห่วงโซ่ซึ่งตรงกับลักษณะของรายการที่เชื่อมโยงอย่างเต็มที่
ดังนั้นเมื่อมีการชนกันวัตถุจะถูกเก็บไว้ในรูปแบบของรายการที่เชื่อมโยง วัตถุรายการปัจจุบันถูกใช้เป็นโหนดถัดไปของวัตถุรายการที่เก็บไว้
ถ้าเราบันทึกคีย์ที่มีอยู่ในค่าอื่น อย่างมีเหตุผลค่าเก่าจะถูกแทนที่ หลังจากตรวจจับตำแหน่งที่เก็บข้อมูลของวัตถุรายการ HashMap จะสำรวจรายการที่เชื่อมโยงในตำแหน่งนั้น หากคุณพบว่าวิธีการเท่ากับเท่ากันการเปลี่ยนจะดำเนินการ
ด้วยวิธีนี้ HashMap สามารถรับรองความเป็นเอกลักษณ์ของคีย์ได้
กลไกการทำงานของวิธีการรับ
ตอนนี้เราได้เรียนรู้กลไกการจัดเก็บ -คู่ใน HashMap คำถามต่อไปคือ: วิธีการสอบถามผลลัพธ์จาก HashMap
ในความเป็นจริงตรรกะนั้นเหมือนกับการใส่
/*** ส่งคืนค่าที่คีย์ระบุถูกแมป,* หรือ {@code null} หากแผนที่นี้ไม่มีการแมปสำหรับคีย์ * {@code k} ถึงค่า {@code v} เช่นนั้น {@code (key == null? k == null:* key.equals (k)} จากนั้นวิธีนี้จะส่งคืน {@code v}; o; Theerwise* มันส่งคืน {@code null} ใช้* แยกแยะสองกรณี ); = คีย์ ||รหัสด้านบนมีลักษณะคล้ายกับวิธีการพัต () ยกเว้นถ้า (e.hash == hash && ((k = ekey) == key || key.equals (k)))
ใส่ใจ