ก่อนอื่นดูคำถามสัมภาษณ์:
ชุดของคู่คีย์-ค่าที่เก็บไว้ใน HashMap ซึ่งคีย์เป็นประเภทหนึ่งที่เราปรับแต่ง หลังจากใส่ HashMap เราเปลี่ยนคุณลักษณะของคีย์ภายนอกจากนั้นเราใช้คีย์นี้เพื่อลบองค์ประกอบออกจาก HashMap HASHMAP จะกลับมาอีกครั้งในเวลานี้?
มีการให้รหัสตัวอย่างและคำตอบในบทความ แต่ไม่มีคำอธิบายเกี่ยวกับหลักการของ HASHMAP
1. คุณสมบัติ
เราสามารถใช้คลาสใด ๆ เป็นคีย์ HASHMAP แต่ข้อ จำกัด ในคลาสเหล่านี้คืออะไร? มาดูรหัสต่อไปนี้:
บุคคลชั้นเรียนสาธารณะ {ชื่อสตริงส่วนตัว; บุคคลสาธารณะ (ชื่อสตริง) {this.name = name; }} แผนที่ <คน, สตริง> testmap = ใหม่ hashmap <> (); testmap.put (คนใหม่ ("สวัสดี"), "โลก"); testmap.get (คนใหม่ ("สวัสดี")); // ----> nullตอนแรกฉันต้องการที่จะได้รับค่าของคลาสบุคคลที่มีค่าฟิลด์เท่ากัน แต่ผลลัพธ์คือโมฆะ ใครก็ตามที่มีความรู้เพียงเล็กน้อยเกี่ยวกับ HashMap สามารถเห็นได้ว่าคลาสบุคคลนั้นไม่มีวิธี HashCode แทนที่ซึ่งนำไปสู่การสืบทอดของวัตถุ HashCode (การส่งคืนเป็นที่อยู่หน่วยความจำ) นี่คือเหตุผลที่คลาสที่ไม่แปรเปลี่ยนเช่นสตริง (หรือจำนวนเต็ม ฯลฯ ) มักใช้เป็นกุญแจสำคัญของ HashMap ดังนั้น HashMap ใช้ HashCode เพื่อจัดทำดัชนีคีย์ได้อย่างรวดเร็วได้อย่างไร
2. หลักการ
ก่อนอื่นมาดูโซลูชันการใช้งาน HashMap ที่เรียบง่ายใน "การคิดใน Java":
//: คอนเทนเนอร์/simplehashmap.java // การสาธิต hashed map.import java.util.*; นำเข้า net.mindview.util.*; คลาสสาธารณะ simplemap <k, v> ขยายบทคัดย่อ <k, v> {// เลือกจำนวนที่สำคัญสำหรับขนาดตาราง HASH // คุณไม่สามารถมีอาร์เรย์ทั่วไปทางกายภาพ แต่คุณสามารถ upcast ไปที่หนึ่ง: @suppresswarnings ("ไม่ได้ตรวจสอบ") linkedList <mapentry <k, v >> [] buckets = new LinkedList [ขนาด]; Public V Put (k key, v value) {v oldValue = null; INT INDEX = Math.ABS (key.hashCode ()) ขนาด %; if (buckets [index] == null) buckets [index] = new linkedList <mapentry <k, v >> (); LinkedList <mapentry <k, v >> bucket = buckets [index]; MapEntry <k, v> pair = mapentry ใหม่ <k, v> (คีย์, ค่า); บูลีนพบ = เท็จ; listiterator <mapentry <k, v >> it = bucket.listiterator (); ในขณะที่ (it.hasnext ()) {mapentry <k, v> ipair = it.next (); if (ipair.getKey (). เท่ากับ (คีย์)) {oldValue = ipair.getValue (); it.set (pair); // แทนที่เก่าด้วย found ใหม่ = true; หยุดพัก; }} if (พบ) buckets [index] .add (pair); กลับ OldValue; } สาธารณะ v รับ (คีย์วัตถุ) {int index = math.Abs (key.hashCode ()) ขนาด; if (buckets [index] == null) return null; สำหรับ (mapentry <k, v> ipair: buckets [index]) ถ้า (ipair.getKey (). เท่ากับ (คีย์)) ส่งคืน ipair.getValue (); คืนค่า null; } ชุดสาธารณะ <map.entry <k, v >> entrySet () {set <map.entry <k, v >> set = new hashset <map.entry <k, v >> (); สำหรับ (linkedList <mapentry <k, v >> bucket: buckets) {ถ้า (bucket == null) ดำเนินการต่อ; สำหรับ (mapentry <k, v> mpair: bucket) set.add (mpair); } return set; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {simplehashmap <string, string> m = ใหม่ simplehashmap <สตริง, สตริง> (); m.putall (ประเทศที่มีความสามารถ (25)); System.out.println (M); System.out.println (M.Get ("Eritrea")); System.out.println (m.entryset ()); -SimpleHashMap สร้างตารางแฮชเพื่อเก็บกุญแจ ฟังก์ชั่นแฮชคือขนาดโมดูลัส Math.ABS (key.hashCode ()) %และความขัดแย้งแฮชได้รับการแก้ไขโดยใช้วิธีการที่เชื่อมโยง แต่ละช่องเก็บของจัดเก็บ map.entry ที่มีค่าดัชนี (แฮช) เดียวกันดังแสดงในรูปด้านล่าง:
หลักการใช้งานของ HashMap ของ JDK นั้นคล้ายคลึงกับที่ใช้ตารางแฮชของที่อยู่เชนเพื่อจัดเก็บ map.entry:
/*** ตารางปรับขนาดตามความจำเป็น ความยาวจะต้องเป็นพลังของสองเสมอ */รายการชั่วคราว <k, v> [] table = (รายการ <k, v> []) emport_table; รายการคลาสคงที่ <k, v> ใช้ map.entry <k, v> {คีย์สุดท้าย k; ค่า V; รายการ <k, v> ถัดไป; แฮช int; -ดัชนีของ map.entry ได้รับจากการแฮชโฟนของคีย์ เมื่อคุณต้องการรับค่าที่สอดคล้องกับคีย์ให้คำนวณดัชนีสำหรับคีย์จากนั้นนำแผนที่เข้ามาในตารางเพื่อรับ สำหรับรายละเอียดดูรหัส:
สาธารณะ v รับ (คีย์วัตถุ) {ถ้า (key == null) return getForNullKey (); รายการ <k, v> entry = getentry (คีย์); ส่งคืน null == รายการ? null: entry.getValue ();} รายการสุดท้าย <k, v> getEntry (คีย์วัตถุ) {ถ้า (ขนาด == 0) {return null; } int hash = (key == null)? 0: แฮช (กุญแจ); สำหรับ (รายการ <k, v> e = ตาราง [indexfor (แฮช, table.length)]; e! = null; e = e.next) {object k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) กลับ e; } return null;}จะเห็นได้ว่า HashCode ส่งผลโดยตรงต่อประสิทธิภาพของฟังก์ชั่นแฮชแฮชของ HashMap - HashCode ที่ดีจะลดความขัดแย้งแฮชอย่างมากและปรับปรุงประสิทธิภาพการค้นหา ในเวลาเดียวกันสิ่งนี้ยังอธิบายถึงคำถามสองข้อที่เกิดขึ้นในตอนต้น: หากคลาสที่กำหนดเองมีคีย์ HashMap การคำนวณ HashCode ควรครอบคลุมฟิลด์ทั้งหมดของตัวสร้างมิฉะนั้นจะเป็นไปได้ที่จะได้รับ NULL