เราได้วิเคราะห์ ArrayList และ LinkedList สองชุด เรารู้ว่า ArrayList ถูกนำไปใช้ตามอาร์เรย์และ LinkedList จะถูกนำไปใช้ตามรายการที่เชื่อมโยง แต่ละคนมีข้อดีและข้อเสียของตัวเอง ตัวอย่างเช่น ArrayList จะดีกว่า LinkedList เมื่อวางตำแหน่งและมองหาองค์ประกอบในขณะที่ LinkedList จะดีกว่า ArrayList เมื่อเพิ่มและลบองค์ประกอบ HASHMAP ที่แนะนำในบทความนี้รวมข้อดีของทั้งคู่ เลเยอร์พื้นฐานของมันถูกนำไปใช้ตามตารางแฮช หากไม่ได้พิจารณาความขัดแย้งแฮชความซับซ้อนของเวลาของ HashMap นอกจากนี้การลบการปรับเปลี่ยนและการดำเนินการค้นหาสามารถเข้าถึง O (1) ที่น่าอัศจรรย์ ก่อนอื่นให้ดูโครงสร้างของตารางแฮชที่ใช้
ดังที่เห็นได้จากรูปด้านบนตารางแฮชเป็นโครงสร้างที่ประกอบด้วยอาร์เรย์และรายการที่เชื่อมโยง แน่นอนตัวเลขด้านบนเป็นตัวอย่างที่ไม่ดี ฟังก์ชั่นแฮชที่ดีควรพยายามที่จะเฉลี่ยการกระจายขององค์ประกอบในอาร์เรย์ลดความขัดแย้งแฮชและลดความยาวของรายการที่เชื่อมโยง ยิ่งความยาวของรายการที่เชื่อมโยงนานขึ้นหมายความว่ายิ่งมีโหนดมากเท่าไหร่ก็ต้องผ่านการสำรวจในระหว่างการค้นหายิ่งประสิทธิภาพของตารางแฮชยิ่งแย่ลงเท่านั้น ถัดไปลองดูที่ตัวแปรสมาชิกของ HashMap
// ค่าเริ่มต้นความจุเริ่มต้นคงที่ int final default_initial_capacity = 1 << 4; // ค่าเริ่มต้นความจุสูงสุดคงที่ int สุดท้าย int maximum_capacity = 1 << 30; // ปัจจัยการโหลดเริ่มต้นหมายถึงตารางแฮชเท่าใด รายการ <k, v> [] table = (รายการ <k, v> []) emport_table; // ขนาด hashmap นั่นคือจำนวนคู่คีย์-ค่าที่เก็บไว้ในขนาด hashmap transient int; กลไกที่ล้มเหลวอย่างรวดเร็ว transient int modcount; // ใช้เกณฑ์เริ่มต้นของทางเลือกแฮชคงที่ int final int Alternative_hashing_threshold_default = integer.max_value; // เมล็ดแฮชแบบสุ่มช่วยลดจำนวนการชนกันของแฮช
ดังที่เห็นได้จากตัวแปรสมาชิกความจุเริ่มต้นเริ่มต้นของ HASHMAP คือ 16 และปัจจัยการโหลดเริ่มต้นคือ 0.75 Threshold เป็นเกณฑ์ของคู่คีย์-ค่าที่สามารถเก็บไว้ในชุด ค่าเริ่มต้นคือความจุเริ่มต้น*ปัจจัยการโหลดนั่นคือ 16*0.75 = 12 เมื่อคู่คีย์-ค่าต้องการเกินขีด จำกัด นั่นหมายความว่าตารางแฮชนั้นอิ่มตัวแล้วในเวลานี้ หากมีการเพิ่มองค์ประกอบอย่างต่อเนื่องจะมีการเพิ่มความขัดแย้งแฮชซึ่งจะลดประสิทธิภาพของ HashMap ในเวลานี้กลไกการขยายกำลังการผลิตอัตโนมัติจะถูกกระตุ้นเพื่อให้แน่ใจว่าประสิทธิภาพของ HashMap นอกจากนี้เรายังสามารถเห็นได้ว่าตารางแฮชเป็นอาร์เรย์รายการจริงและแต่ละรายการที่เก็บไว้ในอาร์เรย์คือโหนดส่วนหัวของรายการที่เชื่อมโยงทางเดียว รายการนี้เป็นคลาสชั้นในแบบคงที่ของ HashMap ลองมาดูตัวแปรสมาชิกของรายการ
รายการคลาสคงที่ <k, v> ใช้ map.entry <k, v> {คีย์สุดท้าย k; // ค่า V คีย์ V; // รายการค่า <k, v> next; // การอ้างอิงไปยังแฮช int รายการถัดไป; // histocode ... // ละเว้นรหัสต่อไปนี้}อินสแตนซ์รายการคือคู่คีย์-ค่าที่มีคีย์และค่า แต่ละอินสแตนซ์มีการอ้างอิงถึงอินสแตนซ์รายการถัดไป เพื่อหลีกเลี่ยงการคำนวณซ้ำ ๆ แต่ละอินสแตนซ์ยังเก็บรหัสแฮชที่เกี่ยวข้อง อาจกล่าวได้ว่าอาร์เรย์รายการเป็นแกนหลักของ HashMap และการดำเนินการทั้งหมดจะทำสำหรับอาร์เรย์นี้ เนื่องจากซอร์สโค้ด HASHMAP ค่อนข้างยาวจึงเป็นไปไม่ได้ที่จะแนะนำวิธีการทั้งหมดในแบบที่ครอบคลุมดังนั้นเราจึงมุ่งเน้นประเด็นสำคัญที่จะแนะนำ ต่อไปเราจะมุ่งเน้นปัญหาและสำรวจกลไกภายในของ HASHMAP ในเชิงลึกสำหรับปัญหาต่อไปนี้
1. HashMap ทำอะไรในระหว่างการก่อสร้าง?
// constructor, ส่งผ่านในความสามารถในการเริ่มต้นและปัจจัยการโหลด public hashmap (int initialcapacity, float loadfactor) {ถ้า (เริ่มต้นความสามารถ <0) {โยน unlegalargumentException ใหม่ ("ความจุเริ่มต้นที่ผิดกฎหมาย:" + การเริ่มต้น); } // หากความสามารถในการเริ่มต้นมีค่ามากกว่าความจุสูงสุดให้ตั้งค่าเป็นความจุสูงสุดถ้า (เริ่มต้นความสามารถ> maximum_capacity) {initialCapacity = maximum_capacity; } // หากปัจจัยการโหลดน้อยกว่า 0 หรือปัจจัยโหลดไม่ใช่หมายเลขจุดลอยตัวข้อยกเว้นจะถูกโยนลงถ้า (loadfactor <= 0 || float.isnan (loadfactor)) {โยน unlegalargumentException ใหม่ ("ปัจจัยโหลดผิดกฎหมาย:" + loadfactor); } // ตั้งค่าปัจจัยโหลด this.loadfactor = loadfactor; // เกณฑ์คือเกณฑ์ความจุเริ่มต้น = การเริ่มต้นความจุ; init ();} void init () {}ตัวสร้างทั้งหมดจะเรียกตัวสร้างนี้ ในตัวสร้างนี้เราจะเห็นว่านอกเหนือจากการตรวจสอบพารามิเตอร์แล้วมันทำสองสิ่ง: ตั้งค่าปัจจัยโหลดเป็นปัจจัยโหลดที่เข้ามาและตั้งค่าเกณฑ์เป็นขนาดการเริ่มต้นที่เข้ามา วิธีการเริ่มต้นว่างเปล่าและไม่ทำอะไรเลย โปรดทราบว่าในเวลานี้ไม่มีการสร้างอาร์เรย์ใหม่ตามขนาดการเริ่มต้นที่เข้ามา แล้วเราจะสร้างอาร์เรย์ใหม่เมื่อใด อ่านต่อไป
2. การดำเนินการใดจะดำเนินการเมื่อ HASHMAP เพิ่มคู่คีย์-ค่า?
// ใส่คู่คีย์-ค่าลงใน hashmap สาธารณะ v ใส่ (k key, v value) {// เริ่มต้นถ้า (ตาราง == emport_table) {// เริ่มต้นตารางแฮชที่ได้รับการพองตัว (เกณฑ์); } if (key == null) {return putfornullkey (ค่า); } // คำนวณรหัสแฮชของคีย์ int แฮช = แฮช (คีย์); // ตำแหน่งตำแหน่งของตารางแฮชตามรหัสแฮช int i = indexfor (แฮช, table.length); สำหรับ (รายการ <k, v> e = ตาราง [i]; e! = null; e = e.next) {วัตถุ k; // หากคีย์ที่เกี่ยวข้องมีอยู่แล้วให้แทนที่ค่าของมันและส่งคืนค่าดั้งเดิมถ้า (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.value; e.value = ค่า; E.RecordAccess (นี่); กลับ OldValue; }} ModCount ++; // หากไม่มีคีย์ที่สอดคล้องกันให้เพิ่มรายการไปยัง Addentry HashMap (แฮช, คีย์, ค่า, i); // return null return null;}คุณจะเห็นว่าเมื่อเพิ่มคู่คีย์-ค่าคุณจะตรวจสอบก่อนว่าตารางแฮชเป็นตารางที่ว่างเปล่าและถ้าเป็นตารางที่ว่างเปล่ามันจะเริ่มต้นหรือไม่ จากนั้นดำเนินการต่อไปและเรียกใช้ฟังก์ชันแฮชเพื่อคำนวณรหัสแฮชของคีย์ที่ผ่าน วางตำแหน่งสล็อตที่ระบุของอาร์เรย์รายการตามรหัสแฮชจากนั้นสำรวจรายการที่เชื่อมโยงทางเดียวของสล็อต หากมีการส่งผ่านไปแล้วให้ดำเนินการทดแทนมิฉะนั้นจะมีการสร้างและเพิ่มรายการใหม่ลงในตารางแฮช
3. ตารางแฮชเริ่มต้นอย่างไร?
// เริ่มต้นตารางแฮชและความจุตารางแฮชจะขยายตัวเนื่องจากเป็นไปได้ว่าความสามารถในการเข้ามาไม่ได้เป็นพลังของโมฆะส่วนตัว 2 โมฆะ // ตั้งค่าเกณฑ์นี่คือความจุโดยทั่วไป * loadfactor threshold = (int) math.min (ความจุ * loadfactor, maximum_capacity + 1); // สร้างตารางแฮชใหม่ด้วยตารางกำลังการผลิตที่ระบุ = รายการใหม่ [ความจุ]; // เริ่มต้นเมล็ดแฮช inithseedasneeded (ความจุ);}
ดังที่เราทราบไว้ข้างต้นเมื่อสร้าง HashMap เราจะไม่สร้างอาร์เรย์รายการใหม่ แต่ตรวจสอบว่าตารางแฮชปัจจุบันเป็นตารางที่ว่างเปล่าในระหว่างการดำเนินการวางหรือไม่ หากเป็นตารางที่ว่างเปล่าให้เรียกใช้วิธีการพองข้อมูลสำหรับการเริ่มต้น รหัสสำหรับวิธีนี้โพสต์ด้านบน คุณจะเห็นว่าความจุของอาร์เรย์รายการจะถูกคำนวณใหม่ภายในวิธีการเนื่องจากขนาดการเริ่มต้นที่ผ่านเข้ามาเมื่อการสร้าง HashMap อาจไม่ได้เป็นพลังของ 2 ดังนั้นคุณต้องแปลงหมายเลขนี้ให้เป็นพลังของ 2 จากนั้นสร้างอาร์เรย์รายการใหม่ตามความจุใหม่ เมื่อเริ่มต้นตารางแฮชให้รีเซ็ตเกณฑ์อีกครั้งและเกณฑ์โดยทั่วไปจะมีความจุ*โหลด นอกจากนี้เมล็ดแฮช (แฮชซีด) จะเริ่มต้นเมื่อเริ่มต้นตารางแฮช แฮชซ่านี้ใช้เพื่อเพิ่มประสิทธิภาพฟังก์ชั่นแฮช ค่าเริ่มต้นคือ 0 และไม่มีการใช้อัลกอริทึมแฮชทางเลือก แต่คุณยังสามารถตั้งค่าแฮชซีดได้ด้วยตัวเองเพื่อให้ได้เอฟเฟกต์การเพิ่มประสิทธิภาพ จะมีการหารือในรายละเอียดด้านล่าง
4. HASHMAP กำหนดเมื่อใดที่จำเป็นต้องขยายกำลังการผลิตและขยายกำลังการผลิตได้อย่างไร
// เพิ่มวิธีการป้อนข้อมูลและก่อนที่คุณต้องการขยายความจุ Addentry (int hash, k key, ค่า v, int bucketindex) {// ถ้าขนาดของ hashmap มากกว่าเกณฑ์และค่าของสล็อตที่สอดคล้องกันของตาราง hash) Threshold มันบ่งชี้ว่าเกิดความขัดแย้งแฮชกำลังจะเกิดขึ้นดังนั้นขยายการปรับขนาดกำลังการผลิต (2 * table.length); hash = (null! = key)? แฮช (กุญแจ): 0; BucketIndex = indexfor (แฮช, table.length); } // มันแสดงที่นี่ว่าขนาดของ HASHMAP ไม่เกินเกณฑ์ดังนั้นจึงไม่จำเป็นต้องขยายความสามารถในการสร้าง (แฮชคีย์ค่า bucketIndex);} // ขยายโมฆะตารางแฮช int oldcapacity = oldTable.length; // หากความจุสูงสุดปัจจุบันมีการใช้งานอยู่แล้วคุณสามารถเพิ่มเกณฑ์ถ้า (oldCapacity == maximum_capacity) {threshold = integer.max_value; กลับ; } // มิฉะนั้นขยายรายการความจุ [] newTable = รายการใหม่ [newCapacity]; // วิธีการโยกย้ายการถ่ายโอนตารางแฮช (newtable, inithseedasneeded (newcapacity)); // ตั้งค่าตารางแฮชปัจจุบันเป็นตารางแฮชใหม่ = newTable; // อัปเดตเกณฑ์ตารางแฮช = (int) math.min (newcapacity * loadfactor, maximum_capacity + 1);}เมื่อเรียกใช้เมธอดใส่เพื่อเพิ่มคู่คีย์-ค่าหากไม่มีคีย์ในคอลเลกชันให้เรียกใช้วิธีการเสริมและสร้างรายการใหม่ เมื่อคุณเห็นรหัส addentry ที่โพสต์ด้านบนก่อนที่จะสร้างรายการใหม่คุณจะพิจารณาว่าขนาดขององค์ประกอบการรวบรวมปัจจุบันเกินขีด จำกัด หรือไม่ หากเกณฑ์เกินขีด จำกัด การโทรขนาดการโทรสำหรับการขยายตัว กำลังการผลิตใหม่ที่ผ่านมาคือตารางแฮชดั้งเดิมสองครั้ง ในวิธีการปรับขนาดอาร์เรย์รายการใหม่ที่มีความจุสองเท่าของตารางแฮชดั้งเดิมจะถูกสร้างขึ้น จากนั้นองค์ประกอบทั้งหมดในตารางแฮชเก่าจะถูกอพยพไปยังตารางแฮชใหม่ซึ่งอาจดำเนินการ rehash และจะดำเนินการ rehash จะดำเนินการตามค่าที่คำนวณโดยวิธี inithseedasneeded หรือไม่ หลังจากการโยกย้ายตารางแฮชเสร็จสมบูรณ์ตารางแฮชปัจจุบันจะถูกแทนที่ด้วยตารางใหม่และในที่สุดค่าเกณฑ์ของ HashMap จะถูกคำนวณใหม่ตามความจุตารางแฮชใหม่
5. ทำไมขนาดของอาร์เรย์รายการจึงต้องมีพลัง 2?
// ส่งคืนดัชนีอาร์เรย์ที่สอดคล้องกับดัชนี int แบบคงที่แฮช (int h, ความยาว int) {return h & (length-1); -Method indexfor คำนวณตัวห้อยที่เกี่ยวข้องในอาร์เรย์ตามรหัสแฮช เราจะเห็นได้ว่ามีการใช้ตัวดำเนินการ (&) ภายในวิธีนี้ การดำเนินการคือการดำเนินการบิตในสองตัวถูกดำเนินการ หากสองบิตที่สอดคล้องกันคือ 1 ผลลัพธ์คือ 1 มิฉะนั้นจะเป็น 0 การดำเนินการมักจะใช้เพื่อลบค่าบิตสูงของตัวถูกดำเนินการเช่น: 01011010 & 00001111 = 00001010 กลับไปที่รหัสและดูว่า H & (ความยาว 1) ทำอะไร
เป็นที่ทราบกันดีว่าความยาวที่ผ่านคือความยาวของอาร์เรย์รายการ เรารู้ว่าตัวห้อยอาร์เรย์คำนวณจาก 0 ดังนั้นตัวห้อยสูงสุดของอาร์เรย์คือความยาว -1 หากความยาวเป็นกำลังของ 2 ดังนั้นบิตไบนารีของความยาว -1 จะตามด้วย 1 ในเวลานี้ฟังก์ชั่นของ H & (ความยาว -1) คือการลบค่าบิตสูงของ H และปล่อยให้ค่าบิตต่ำของ H เป็นตัวห้อยของอาร์เรย์ จากนี้เราจะเห็นได้ว่าขนาดของอาร์เรย์รายการถูกกำหนดเป็นพลังของ 2 เพื่อใช้อัลกอริทึมนี้เพื่อกำหนดตัวห้อยของอาร์เรย์
6. ฟังก์ชั่นแฮชคำนวณรหัสแฮชอย่างไร?
// ฟังก์ชั่นที่สร้างรหัสแฮชสุดท้ายแฮช int (วัตถุ K) {int h = hashseed; // ถ้าคีย์เป็นประเภทสตริงให้ใช้อัลกอริทึมแฮชอื่นถ้า (0! = h && k อินสแตนซ์ของสตริง) {return sun.misc.hashing.stringhash32 ((สตริง) k); } h ^= k.hashCode (); // ฟังก์ชั่นการก่อกวน h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}สองบรรทัดสุดท้ายของวิธีแฮชคืออัลกอริทึมที่คำนวณค่าแฮชอย่างแท้จริง อัลกอริทึมที่คำนวณรหัสแฮชเรียกว่าฟังก์ชันการก่อกวน ฟังก์ชั่นการก่อกวนที่เรียกว่าเป็นการผสมผสานทุกอย่างเข้าด้วยกัน คุณจะเห็นว่ามีการใช้งานการเปลี่ยนแปลงแบบขวาไปขวาสี่แบบที่นี่ วัตถุประสงค์คือเพื่อผสมค่าสูงของ H และค่าต่ำเพื่อเพิ่มการสุ่มของค่าต่ำ ดังกล่าวข้างต้นเรารู้ว่าตัวห้อยของอาร์เรย์การวางตำแหน่งจะถูกกำหนดตามค่าบิตต่ำของรหัสแฮช รหัสแฮชของคีย์ถูกสร้างขึ้นโดยวิธีการ HashCode และค่าต่ำของรหัสแฮชที่สร้างขึ้นโดยวิธี HashCode ที่ไม่ดีอาจมีการทำซ้ำจำนวนมาก เพื่อที่จะทำให้รหัสแฮชแมปค่อนข้างสม่ำเสมอในอาร์เรย์ฟังก์ชั่นการก่อกวนมีประโยชน์รวมถึงลักษณะของค่าบิตสูงในค่าบิตต่ำเพิ่มการสุ่มของค่าบิตต่ำซึ่งทำให้การแจกแจงแฮชหลวมมากขึ้น รูปต่อไปนี้ให้ตัวอย่างเพื่อช่วยให้เข้าใจ
7. เกิดอะไรขึ้นกับแฮชทดแทน?
เราเห็นว่าในวิธีแฮชแฮชซ่าจะได้รับมอบหมายให้ H ก่อน แฮชซ่านี้เป็นเมล็ดแฮชซึ่งเป็นค่าสุ่มและใช้เพื่อช่วยเพิ่มประสิทธิภาพฟังก์ชั่นแฮช แฮชเซดเริ่มต้นคือ 0 ซึ่งหมายความว่าอัลกอริทึมแฮชทางเลือกไม่ได้ใช้โดยค่าเริ่มต้น ดังนั้นเมื่อใดที่จะใช้แฮชซีด? ก่อนอื่นคุณต้องตั้งค่าแฮชทางเลือกเพื่อเปิดใช้งานและตั้งค่าของ jdk.map.althashing.hreshold ในคุณสมบัติของระบบ ค่านี้คือ -1 โดยค่าเริ่มต้นในคุณสมบัติระบบ เมื่อเป็น -1 ค่าเกณฑ์ของการใช้แฮชทางเลือกคือจำนวนเต็ม max_value นี่ก็หมายความว่าคุณอาจไม่เคยใช้แฮชทดแทน แน่นอนว่าคุณสามารถตั้งค่าเกณฑ์นี้ให้เล็กลงเล็กน้อยเพื่อให้แฮชซ่าแบบสุ่มจะถูกสร้างขึ้นเมื่อองค์ประกอบที่กำหนดถึงเกณฑ์ สิ่งนี้จะเพิ่มการสุ่มของฟังก์ชันแฮช ทำไมต้องใช้แฮชทางเลือก? เมื่อองค์ประกอบที่กำหนดถึงเกณฑ์ที่คุณตั้งไว้นั่นหมายความว่าตารางแฮชค่อนข้างอิ่มตัวและความเป็นไปได้ของความขัดแย้งแฮชจะเพิ่มขึ้นอย่างมาก ในเวลานี้การใช้ฟังก์ชั่นแฮชแบบสุ่มมากขึ้นสำหรับองค์ประกอบที่เพิ่มเข้ามาสามารถทำให้องค์ประกอบเพิ่มเติมกระจายแบบสุ่มมากขึ้นในตารางแฮช
หมายเหตุ: การวิเคราะห์ทั้งหมดข้างต้นขึ้นอยู่กับ JDK1.7 และจะมีการเปลี่ยนแปลงที่สำคัญระหว่างเวอร์ชันที่แตกต่างกันผู้อ่านจำเป็นต้องให้ความสนใจ