ภาพรวม hashmap
HashMap เป็นการใช้งานแบบอะซิงโครนัสของอินเทอร์เฟซแผนที่ตามตารางแฮช การใช้งานนี้ให้การดำเนินการแมปแบบเลือกทั้งหมดและอนุญาตให้ใช้ค่า NULL และปุ่ม NULL คลาสนี้ไม่รับประกันคำสั่งของการแมปโดยเฉพาะอย่างยิ่งไม่รับประกันว่าคำสั่งซื้อจะคงอยู่
โครงสร้างข้อมูลของ HashMap
ในภาษาการเขียนโปรแกรม Java มีโครงสร้างพื้นฐานสองโครงสร้างหนึ่งคืออาร์เรย์และอีกอันคือตัวชี้จำลอง (อ้างอิง) โครงสร้างข้อมูลทั้งหมดสามารถสร้างได้โดยใช้โครงสร้างพื้นฐานทั้งสองนี้และ HASHMAP ก็ไม่มีข้อยกเว้น HashMap เป็นโครงสร้างข้อมูล "รายการที่เชื่อมโยง" นั่นคือโครงสร้างของอาร์เรย์และรายการที่เชื่อมโยง แต่ใน JDK1.8
มีการเพิ่มการใช้งานของต้นไม้สีแดงและสีดำ เมื่อความยาวของรายการที่เชื่อมโยงมากกว่า 8 มันจะถูกแปลงเป็นโครงสร้างของต้นไม้สีแดงและสีดำ
ดังที่เห็นได้จากรูปด้านบน HashMap ใช้วิธีการที่อยู่โซ่ใน Java วิธีการที่อยู่ลิงค์คือการรวมกันของอาร์เรย์และรายการที่เชื่อมโยง มีโครงสร้างรายการที่เชื่อมโยงในแต่ละองค์ประกอบอาร์เรย์ เมื่อข้อมูลถูกแฮชจะได้รับอาร์เรย์ตัวห้อยและข้อมูลจะถูกวางไว้ในรายการที่เชื่อมโยงขององค์ประกอบตัวห้อยที่เกี่ยวข้อง
*/ โหนดคลาสคงที่ <k, v> ใช้ map.entry <k, v> {สุดท้าย int hash; // ใช้เพื่อค้นหาตำแหน่งของดัชนีอาร์เรย์ key สุดท้าย k key; ค่า V; โหนด <k, v> next; // โหนดถัดไปในโหนดรายการที่เชื่อมโยง (int แฮช, คีย์ k, ค่า V, โหนด <k, v> ถัดไป) {this.hash = hash; this.key = key; this.value = ค่า; this.next = ถัดไป; -Node เป็นคลาสภายในของ HashMap ซึ่งใช้อินเตอร์เฟส Map.entry ซึ่งเป็นแผนที่เป็นหลัก (คู่คีย์-ค่า)
บางครั้งปุ่มสองปุ่มอยู่ในตำแหน่งเดียวกันซึ่งบ่งบอกถึงการชนกันของแฮช แน่นอนยิ่งผลลัพธ์การคำนวณของอัลกอริทึมแฮชเท่าใดก็ยิ่งมีความน่าจะเป็นของการชนกันของแฮชที่เล็กลงและประสิทธิภาพการเข้าถึงของแผนที่ก็ยิ่งสูงขึ้นเท่านั้น
มีฟิลด์ที่สำคัญมากในคลาส HashMap ซึ่งเป็นตารางโหนด [] นั่นคืออาร์เรย์ที่เก็บแฮช เห็นได้ชัดว่ามันเป็นอาร์เรย์ของโหนด
หากอาร์เรย์ถังแฮชมีขนาดใหญ่แม้แต่อัลกอริทึมแฮชที่น่าสงสารก็จะกระจัดกระจายมากขึ้น หากอาร์เรย์อาร์เรย์ของถังแฮชมีขนาดเล็กแม้อัลกอริทึมแฮชที่ดีจะมีการชนกันมากขึ้นดังนั้นจึงจำเป็นต้องชั่งน้ำหนักต้นทุนพื้นที่และเวลา ในความเป็นจริงมันคือการกำหนดขนาดของอาร์เรย์แฮชถังตามสถานการณ์จริงและบนพื้นฐานนี้อัลกอริทึมแฮชที่ออกแบบมาจะลดการชนกันของแฮช ดังนั้นเราจะควบคุมแผนที่เพื่อให้ความน่าจะเป็นของการชนกันของแฮชเล็ก ๆ และตารางถังแฮช (ตารางโหนด []) ใช้พื้นที่น้อยลง? คำตอบคืออัลกอริทึมแฮชที่ดีและกลไกการขยายกำลังการผลิต
ก่อนที่จะเข้าใจกระบวนการแฮชและการขยายตัวเราจำเป็นต้องเข้าใจ HASHMAP หลายสาขา จากซอร์สโค้ดของตัวสร้างเริ่มต้นของ HashMap จะเห็นได้ว่าตัวสร้างเริ่มต้นฟิลด์ต่อไปนี้ซอร์สโค้ดมีดังนี้:
เกณฑ์ int; // ค่าคีย์ที่สามารถรองรับได้คือ Ultimate Float Loadfactor; // factor factor int modcount; ขนาด int;
ขั้นแรกความยาวการเริ่มต้นของตารางโหนด [] (ค่าเริ่มต้นคือ 16) ปัจจัยโหลดคือปัจจัยโหลด (ค่าเริ่มต้นคือ 0.75) และเกณฑ์คือจำนวนโหนด (คู่คีย์-ค่า) ของจำนวนข้อมูลสูงสุดที่ HashMap สามารถรองรับได้ threshold = ความยาว * ปัจจัยโหลด กล่าวคือหลังจากอาร์เรย์ได้กำหนดความยาวของมันมากเท่าไหร่ปัจจัยโหลดที่ใหญ่ขึ้น
ขึ้นอยู่กับสูตรนิยามของปัจจัยโหลดจะเห็นได้ว่าเกณฑ์คือจำนวนองค์ประกอบสูงสุดที่อนุญาตตามปัจจัยการโหลดและความยาวนี้ (ความยาวอาร์เรย์) หากตัวเลขนี้เกินกว่านี้ให้ปรับขนาด (ขยายความจุ) กำลังการผลิต HashMap ที่ขยายตัวเป็นสองเท่าของความจุก่อนหน้านี้ ปัจจัยโหลดเริ่มต้น 0.75 เป็นตัวเลือกที่สมดุลสำหรับพื้นที่และประสิทธิภาพเวลา ขอแนะนำให้คุณไม่แก้ไขเว้นแต่ในกรณีของเวลาและพื้นที่พิเศษหากมีพื้นที่หน่วยความจำจำนวนมากและข้อกำหนดด้านประสิทธิภาพเวลาสูงค่าของปัจจัยโหลดปัจจัยโหลดสามารถลดลงได้ ในทางตรงกันข้ามหากพื้นที่หน่วยความจำแน่นและข้อกำหนดด้านประสิทธิภาพเวลาไม่สูงค่าของตัวโหลดปัจจัยโหลดสามารถเพิ่มขึ้นได้ซึ่งอาจมากกว่า 1
ฟิลด์ขนาดเป็นเรื่องง่ายที่จะเข้าใจมันเป็นจำนวนคู่คีย์-ค่าที่มีอยู่จริงใน HashMap สังเกตความแตกต่างระหว่างความยาวของตารางและจำนวนเกณฑ์ที่รองรับคู่คีย์สูงสุด ฟิลด์ ModCount ส่วนใหญ่จะใช้เพื่อบันทึกจำนวนการเปลี่ยนแปลงในโครงสร้างภายในของ HASHMAP และส่วนใหญ่จะใช้สำหรับความล้มเหลวอย่างรวดเร็วของการทำซ้ำ เพื่อเน้นการเปลี่ยนแปลงโครงสร้างภายในหมายถึงการเปลี่ยนแปลงในโครงสร้างเช่นใส่คู่คีย์-ค่าใหม่ แต่ค่าที่สอดคล้องกับคีย์ถูกเขียนทับและไม่ได้อยู่ในการเปลี่ยนแปลงโครงสร้าง
ใน HashMap ความยาวของตารางอาร์เรย์แฮชจะต้องอยู่ในพลังงาน n ของ 2 (ต้องเป็นหมายเลขคอมโพสิต) นี่คือการออกแบบที่ไม่เป็นทางการ การออกแบบทั่วไปคือการออกแบบขนาดของถังเป็นจำนวนที่สำคัญ ค่อนข้างพูดความน่าจะเป็นของความขัดแย้งที่เกิดจากจำนวนนายกมีขนาดเล็กกว่าจำนวนคอมโพสิต สำหรับการพิสูจน์เฉพาะโปรดดู //www.vevb.com/article/100911.htm Hashtable เริ่มต้นขนาดของถังเป็น 11 ซึ่งเป็นแอปพลิเคชันของขนาดถังที่ออกแบบมาเป็นตัวเลขที่สำคัญ (ไม่สามารถรับประกันได้ว่าเป็นตัวเลขที่สำคัญหลังจากการขยายตัว) HashMap ใช้การออกแบบที่ไม่เป็นทางการนี้ส่วนใหญ่เพื่อเพิ่มประสิทธิภาพเมื่อโมดูโลและการขยายตัว ในเวลาเดียวกันเพื่อลดความขัดแย้ง HASHMAP ยังเพิ่มกระบวนการมีส่วนร่วมในการคำนวณระดับสูงในการคำนวณเมื่อค้นหาตำแหน่งดัชนีถังแฮช
มีปัญหาที่นี่ แม้ว่าอัลกอริทึมการโหลดและอัลกอริทึมแฮชได้รับการออกแบบอย่างสมเหตุสมผล แต่ก็จะเป็นสถานการณ์ที่ซิปยาวเกินไป เมื่อซิปยาวเกินไปมันจะส่งผลกระทบต่อประสิทธิภาพของ HashMap อย่างจริงจัง ดังนั้นในรุ่น JDK1.8 โครงสร้างข้อมูลได้รับการปรับให้เหมาะสมต่อไปและมีการแนะนำต้นไม้สีแดงและสีดำ เมื่อความยาวของรายการที่เชื่อมโยงยาวเกินไป (ค่าเริ่มต้นมากกว่า 8) รายการที่เชื่อมโยงจะถูกแปลงเป็นต้นไม้สีแดงและสีดำ ลักษณะของการเพิ่มอย่างรวดเร็วของต้นไม้สีแดงและสีดำการลบการดัดแปลงและการค้นหาจะถูกนำมาใช้เพื่อปรับปรุงประสิทธิภาพของ HASHMAP การแทรกการลบและการค้นหาต้นไม้สีแดงและสีดำจะถูกใช้เพื่อแทรกลบและอัลกอริทึมการค้นหาเช่นต้นไม้สีแดงและสีดำ
กำหนดตำแหน่งดัชนีของอาร์เรย์ถังแฮช
การใช้รหัส:
// วิธีที่ 1: hash int สุดท้ายคงที่ (คีย์วัตถุ) {//jdk1.8 & jdk1.7 int h; // h = key.hashCode () ได้รับค่า hashCode สำหรับขั้นตอนแรก // h ^ (h >>> 16) เข้าร่วมในการทำงานของการส่งคืนขั้นตอนที่สอง (key == null)? 0: (h = key.hashCode ()) ^ (h >>> 16);} // วิธีที่ 2: intative inticed indexfor (int h, ความยาว int) {//jdk1.7 รหัสแหล่งที่มา, jdk1.8 ไม่มีวิธีนี้ // ขั้นตอนที่สามใช้การดำเนินการโมดูลัส}อัลกอริทึมแฮชที่นี่เป็นหลักสามขั้นตอนคือการใช้ค่าแฮชโฟตอนของคีย์การดำเนินการบิตสูงและการทำงานของโมดูลัส
สำหรับวัตถุใด ๆ ที่กำหนดตราบใดที่ค่าคืน HashCode () นั้นเท่ากันรหัสแฮชที่คำนวณโดยวิธีการเรียกโปรแกรมหนึ่งจะเหมือนกันเสมอ สิ่งแรกที่เราคิดว่าคือโมดูโลค่าแฮชกับความยาวอาร์เรย์เพื่อให้การกระจายขององค์ประกอบค่อนข้างสม่ำเสมอ อย่างไรก็ตามการบริโภคการดำเนินงานของโมดูลัสค่อนข้างใหญ่ สิ่งนี้ทำใน HASHMAP: วิธีการโทรสองเพื่อคำนวณดัชนีใดที่ควรเก็บไว้ในอาร์เรย์ตาราง
วิธีนี้ฉลาดมาก มันได้รับบิตที่บันทึกไว้ของวัตถุผ่าน H & (table.length -1) และความยาวของอาร์เรย์พื้นฐานของ Hashmap มักจะเป็น N -power ของ 2 ซึ่งเป็นการเพิ่มประสิทธิภาพของ Hashmap ในแง่ของความเร็ว เมื่อความยาวอยู่เสมอถึงพลัง N ของ 2 การดำเนินการ H & (ความยาว -1) จะเทียบเท่ากับความยาวโมดูโลนั่นคือความยาว h %แต่ & มีประสิทธิภาพสูงกว่า %
ในการดำเนินการของ JDK1.8 อัลกอริทึมสำหรับการดำเนินการบิตสูงได้รับการปรับให้เหมาะสมและการใช้ HashCode (HASHCODE (HASHCODE ()) ^ (h >>> 16) ซึ่งได้รับการพิจารณาจากความเร็วความเร็วและคุณภาพ สิ่งนี้สามารถมั่นใจได้ว่าเมื่อความยาวของตารางอาร์เรย์มีขนาดค่อนข้างเล็กมันยังสามารถตรวจสอบให้แน่ใจว่าบิตมีส่วนร่วมในการคำนวณแฮชโดยคำนึงถึงสูงต่ำและจะไม่มีค่าใช้จ่ายมากเกินไป
นี่คือตัวอย่าง N คือความยาวของตาราง
การติดตั้งวิธีการ HashMap
แนวคิดทั่วไปของฟังก์ชั่นใส่คือ:
รหัสเฉพาะถูกนำไปใช้ดังนี้:
Public V Put (k key, v value) {return putval (แฮช (คีย์), คีย์, ค่า, เท็จ, จริง); } / ***เมธอดสำหรับการสร้างแฮช* / คงที่ int สุดท้ายแฮช (คีย์วัตถุ) {int h; return (key == null)? 0: (h = key.hashCode ()) ^ (h >>> 16); } สุดท้าย v putval (int hash, k key, v ค่า V, บูลีนเฉพาะอย่างเดียว, การขับไล่บูลีน) {node <k, v> [] แท็บ; โหนด <k, v> p; int n, i; // ตัดสินว่าตารางว่างเปล่าถ้า ((แท็บ = ตาราง) == null || (n = tab.length) == 0) n = (tab = resize ()). ความยาว; // สร้างอาร์เรย์ตารางใหม่และรับความยาวของอาร์เรย์ // คำนวณค่าแฮชไปที่ดัชนีอาร์เรย์ที่แทรก ถ้าตาราง [i] == null สร้างโหนดใหม่โดยตรงและเพิ่ม if ((p = tab [i = (n - 1) & hash]) == null) แท็บ [i] = newNode (แฮชคีย์ค่า null); else {// ถ้าโหนดที่เกี่ยวข้องมีโหนด <k, v> e; K K; // ตัดสินว่าองค์ประกอบแรกของตาราง [i] เหมือนกับคีย์หรือไม่ถ้าเหมือนกันจะเขียนทับค่าโดยตรงถ้า (p.hash == hash && ((k = p.key) == คีย์ || (key! = null && key.equals (k)))) e = p; // ตัดสินว่าตาราง [i] เป็น treenode นั่นคือไม่ว่าจะเป็นตาราง [i] เป็นต้นไม้สีแดงดำหรือไม่ หากเป็นต้นไม้สีแดงดำให้ใส่คู่คีย์-ค่าโดยตรงในต้นไม้อื่นถ้า (p instanceof treenode) e = ((treenode <k, v>) p) .puttreeval (นี่, แท็บ, แฮช, คีย์, ค่า); // โซ่นี้เป็นรายการที่เชื่อมโยง {// transipate ผ่านตาราง [i] เพื่อตรวจสอบว่าความยาวของรายการที่เชื่อมโยงมากกว่า treeify_threshold (ค่าเริ่มต้นคือ 8) หากมากกว่า 8 ให้แปลงรายการที่เชื่อมโยงเป็นต้นไม้สีแดงดำและดำเนินการแทรกในต้นไม้สีแดงดำ มิฉะนั้นการดำเนินการแทรกของรายการที่เชื่อมโยงจะดำเนินการ; หากพบว่าคีย์มีค่าการเขียนทับโดยตรงแล้วในระหว่างกระบวนการสำรวจ สำหรับ (int bincount = 0;; ++ bincount) {ถ้า ((e = p.next) == null) {p.next = newNode (แฮช, คีย์, ค่า, null); ถ้า (bincount> = treeify_threshold - 1) // -1 สำหรับ 1st treeifybin (แท็บ, แฮช); หยุดพัก; } if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) break; P = E; }} // เขียนถ้า (e! = null) {// การแมปที่มีอยู่สำหรับคีย์ v oldValue = e.value; if (! onlyifabsent || oldValue == null) e.value = ค่า; ช่วงบ่าย (E); กลับ OldValue; }} ++ modcount; // หลังจากการแทรกสำเร็จให้ตรวจสอบว่าจำนวนคู่ของค่าคีย์ที่แท้จริงเกินกว่าเกณฑ์ความจุสูงสุดหรือไม่ หากเกินความจุให้ขยายถ้า (++ ขนาด> เกณฑ์) ปรับขนาด (); ช่วงบ่าย (ขับไล่); คืนค่า null; -การติดตั้งวิธีการ hashmap get
แนวคิดมีดังนี้:
1. โหนดแรกในถังกดโดยตรง;
2. หากมีความขัดแย้งให้ใช้ key.equals (k) เพื่อค้นหารายการที่เกี่ยวข้อง
หากเป็นต้นไม้ให้ค้นหาในต้นไม้ผ่าน key.equals (k), o (logn);
หากเป็นรายการที่เชื่อมโยงให้ค้นหาผ่าน key.equals (k) ในรายการที่เชื่อมโยง o (n)
สาธารณะ v รับ (คีย์วัตถุ) {node <k, v> e; return (e = getNode (แฮช (คีย์), คีย์)) == null? NULL: E.Value; } โหนดสุดท้าย <k, v> getNode (int แฮช, คีย์วัตถุ) {node <k, v> [] แท็บ; โหนด <k, v> ก่อน, e; int n; K K; if ((tab = table)! = null && (n = tab.length)> 0 && (first = tab [(n - 1) & hash])! = null) {// hit โดยตรงถ้า (first.hash == hash && // ทุกครั้งที่มีการตรวจสอบโหนดแรก (k = first.key) // พลาดถ้า ((e = first.next)! = null) {// get if (อินสแตนซ์แรกของ treenode) return ((treenode <k, v>) ก่อน) .getTreenode (แฮชคีย์); // รับ do {ถ้า (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) ส่งคืน e; } ในขณะที่ ((e = e.next)! = null); }} return null; -กลไกการขยายกำลังการผลิต
การปรับขนาดหมายถึงการคำนวณความสามารถใหม่และเพิ่มองค์ประกอบลงในวัตถุ HashMap อย่างต่อเนื่อง เมื่ออาร์เรย์ภายในวัตถุ HashMap ไม่สามารถโหลดองค์ประกอบได้มากขึ้นวัตถุจะต้องขยายความยาวของอาร์เรย์เพื่อให้สามารถโหลดองค์ประกอบเพิ่มเติมได้ แน่นอนอาร์เรย์ใน Java ไม่สามารถขยายได้โดยอัตโนมัติ วิธีการคือการใช้อาร์เรย์ใหม่แทนอาร์เรย์ที่มีอยู่ที่มีความจุขนาดเล็กเช่นเดียวกับที่เราใช้ถังขนาดเล็กเพื่อเติมน้ำ หากเราต้องการเติมน้ำให้มากขึ้นเราต้องแทนที่ด้วยถังขนาดใหญ่
เราวิเคราะห์ซอร์สโค้ดของการปรับขนาด เนื่องจาก JDK1.8 รวมต้นไม้สีแดงและสีดำมันซับซ้อนกว่า เพื่ออำนวยความสะดวกในการทำความเข้าใจเรายังคงใช้รหัส JDK1.7 ซึ่งเข้าใจได้ง่ายขึ้น มีความแตกต่างเล็กน้อยในสาระสำคัญ มาพูดถึงความแตกต่างเฉพาะในภายหลัง
โมฆะปรับขนาด (int newCapacity) {// หยุดรายการความจุใหม่ชั่วคราว [] oldTable = ตาราง; // อ้างอิงอาร์เรย์รายการก่อนการขยายตัว int oldcapacity = oldtable.length; if (oldcapacity == maximum_capacity) {// ถ้าขนาดอาร์เรย์ก่อนการขยายถึงสูงสุด (2^30) threshold = integer.max_value; // แก้ไขเกณฑ์เป็นค่าสูงสุดของ int (2^31-1) เพื่อให้กำลังการผลิตจะไม่ถูกขยายในผลตอบแทนในอนาคต } รายการ [] newTable = รายการใหม่ [newCapacity]; // เริ่มต้นการถ่ายโอนอาร์เรย์รายการใหม่ (newTable); - - ถ่ายโอนข้อมูลไปยังตารางอาร์เรย์รายการใหม่ = newTable; // แอตทริบิวต์ตารางของ HashMap หมายถึง threshold Array entres ใหม่ = (int) (newCapacity * loadfactor); // แก้ไขเกณฑ์}ที่นี่เราใช้อาร์เรย์ที่มีความจุมากขึ้นแทนที่จะเป็นอาร์เรย์ที่มีอยู่ที่มีความจุน้อยกว่า วิธีการถ่ายโอน () คัดลอกองค์ประกอบของอาร์เรย์รายการต้นฉบับไปยังอาร์เรย์รายการใหม่
โมฆะการถ่ายโอน (รายการ [] newTable) {entry [] src = ตาราง; // SRC หมายถึงอาร์เรย์รายการเก่า int newCapacity = newTable.length; สำหรับ (int j = 0; j <src.length; j ++) {// ความเงียบสงบผ่านรายการอาร์เรย์รายการเก่า <k, v> e = src [j]; // รับแต่ละองค์ประกอบของอาร์เรย์รายการเก่าถ้า (e! = null) {src [j] = null; // ปล่อยการอ้างอิงวัตถุของอาร์เรย์รายการเก่า (หลังจากสำหรับลูป, อาร์เรย์รายการเก่าไม่ได้หมายถึงวัตถุใด ๆ อีกต่อไป) ทำ {รายการ <k, v> next = e.next; int i = indexfor (e.hash, newcapacity); - - คำนวณตำแหน่งของแต่ละองค์ประกอบในอาร์เรย์ e.Next = newTable [i]; // tag [1] newTable [i] = e; // วางองค์ประกอบบนอาร์เรย์ e = ถัดไป; // เข้าถึงองค์ประกอบในห่วงโซ่รายการถัดไป} ในขณะที่ (e! = null); -การอ้างอิงถึง newTable [i] ถูกกำหนดให้กับ E.NEXT ซึ่งหมายความว่าวิธีการแทรกส่วนหัวของรายการที่เชื่อมโยงเดียวถูกใช้ องค์ประกอบใหม่ที่ตำแหน่งเดียวกันจะถูกวางไว้ที่หัวของรายการที่เชื่อมโยงเสมอ ด้วยวิธีนี้องค์ประกอบที่วางไว้ในดัชนีจะถูกวางในที่สุดเมื่อสิ้นสุดห่วงโซ่รายการ (หากเกิดความขัดแย้งแฮช) สิ่งนี้แตกต่างจาก JDK1.8 ซึ่งอธิบายรายละเอียดด้านล่าง องค์ประกอบในห่วงโซ่รายการเดียวกันในอาร์เรย์เก่าอาจถูกวางไว้ที่ตำแหน่งที่แตกต่างกันในอาร์เรย์ใหม่หลังจากคำนวณตำแหน่งดัชนีใหม่
นี่คือตัวอย่างเพื่อแสดงกระบวนการขยายกำลังการผลิต สมมติว่าอัลกอริทึมแฮชของเราใช้คีย์ mod เพื่อรับขนาดของตาราง (นั่นคือความยาวของอาร์เรย์) ขนาดของตารางอาร์เรย์ที่เก็บของแฮช = 2 ดังนั้นคีย์ = 3, 7, 5 และคำสั่งซื้อคือ 5, 7 และ 3 หลังจาก mod 2 ความขัดแย้งอยู่ในตาราง [1] ที่นี่สันนิษฐานว่าโหลดปัจจัยโหลด factor = 1 นั่นคือเมื่อขนาดที่แท้จริงของคู่คีย์-ค่ามากกว่าขนาดจริงของตารางมันจะถูกขยาย สามขั้นตอนต่อไปคือกระบวนการปรับขนาดอาร์เรย์แฮชเป็น 4 จากนั้นทำการปรับปรุงโหนดทั้งหมด
มาอธิบายว่ามีการปรับให้เหมาะสมใน JDK1.8 หลังจากการสังเกตเราสามารถพบว่าเรากำลังใช้กำลังของการขยายตัวสองครั้ง (หมายถึงความยาวของสองเท่าของต้นฉบับ) ดังนั้นตำแหน่งขององค์ประกอบจึงอยู่ในตำแหน่งเดิมหรือย้ายตำแหน่งของพลังของสองอีกครั้งที่ตำแหน่งเดิม เมื่อดูรูปด้านล่างคุณสามารถเข้าใจความหมายของประโยคนี้ n คือความยาวของตาราง รูปที่ (a) แสดงตัวอย่างของตำแหน่งดัชนีของสองปุ่มที่กำหนดตำแหน่งดัชนีของ KEY1 และ KEY2 ก่อนการขยายตัว รูปที่ (b) แสดงตัวอย่างของตำแหน่งดัชนีของ Key1 และ Key2 หลังจากการขยายตัว โดยที่ HASH1 คือผลการทำงานของแฮชและบิตสูงที่สอดคล้องกับคีย์ 1
หลังจากที่องค์ประกอบใหม่คำนวณแฮชเนื่องจาก N กลายเป็น 2 ครั้งช่วงหน้ากากของ N-1 คือ 1 บิต (สีแดง) ที่จุดสูงดังนั้นดัชนีใหม่จะเปลี่ยนเช่นนี้:
ดังนั้นเมื่อเราขยาย HASHMAP เราไม่จำเป็นต้องคำนวณแฮชใหม่เช่นการใช้งาน JDK1.7 เราเพียงแค่ต้องดูว่าบิตที่เพิ่มลงในค่าแฮชดั้งเดิมคือ 1 หรือ 0 ถ้าเป็น 0 ดัชนีจะไม่เปลี่ยนแปลง ถ้าเป็น 1 ดัชนีจะกลายเป็น "ดัชนีดั้งเดิม + oldcap" คุณสามารถดูรูปต่อไปนี้เป็นไดอะแกรม Resize ที่มีการขยาย 16 ถึง 32:
การออกแบบนี้ฉลาดมากซึ่งไม่เพียง แต่ช่วยประหยัดเวลาในการคำนวณค่าแฮชใหม่ แต่ยังรวมถึง 1 บิตที่เพิ่มขึ้นใหม่คือ 0 หรือ 1 จึงสามารถพิจารณาแบบสุ่มได้ดังนั้นกระบวนการปรับขนาดจะกระจายโหนดที่ขัดแย้งกันก่อนหน้านี้ไปยังถังใหม่ นี่คือจุดเพิ่มประสิทธิภาพใหม่ที่เพิ่มโดย JDK1.8 มีความสนใจเล็กน้อยต่อความแตกต่าง เมื่อ rehash ใน jdk1.7 เมื่อรายการที่เชื่อมโยงเก่าจะย้ายรายการที่เชื่อมโยงใหม่หากตำแหน่งดัชนีอาร์เรย์ของตารางใหม่เหมือนกันองค์ประกอบรายการที่เชื่อมโยงจะถูกคว่ำ แต่สามารถเห็นได้จากรูปด้านบน JDK1.8 จะไม่ถูกคว่ำ นักเรียนที่สนใจสามารถศึกษาซอร์สโค้ด Resize ของ JDK1.8 ซึ่งเป็นสิ่งที่ดีมากดังนี้:
โหนดสุดท้าย <k, v> [] resize () {node <k, v> [] oldTab = ตาราง; int oldcap = (oldtab == null)? 0: oldtab.length; int oldthr = threshold; int newcap, newtHr = 0; ถ้า (oldcap> 0) {// ถ้าค่าสูงสุดเกินกว่านั้นจะไม่ถูกขยายอีกต่อไปดังนั้นฉันต้องชนกับคุณถ้า (oldcap> = maximum_capacity) {threshold = integer.max_value; กลับ oldtab; } // หากไม่เกินค่าสูงสุดจะมีการขยายเป็น 2 เท่าของต้นฉบับถ้า ((newCap = oldCap << 1) <maximum_capacity && oldcap> = default_initial_capacity) newthr = oldthr << 1; // double threshold} else ถ้า (oldthr> 0) // ความจุเริ่มต้นถูกวางไว้ใน threshold newCap = oldTHR; อื่น {// zero เกณฑ์เริ่มต้นหมายถึงการใช้ค่าเริ่มต้น newCap = default_initial_capacity; newTHR = (int) (default_load_factor * default_initial_capacity); } // คำนวณขีด จำกัด บน resize ใหม่ถ้า (newTHR == 0) {float ft = (float) newCap * loadfactor; newTHR = (newCap <maximum_capacity && ft <(float) maximum_capacity? (int) ft: integer.max_value); } threshold = newTHR; @suppresswarnings ({"rawtypes", "unchecked"}) โหนด <k, v> [] newtab = (โหนด <k, v> []) โหนดใหม่ [newcap]; ตาราง = newTab; if (oldtab! = null) {// ย้ายแต่ละถังไปยังถังใหม่สำหรับ (int j = 0; j <oldcap; ++ j) {node <k, v> e; if ((e = oldtab [j])! = null) {oldtab [j] = null; if (e.next == null) newtab [e.hash & (newCap - 1)] = e; อื่นถ้า (e instanceof treenode) ((treenode <k, v>) e) .split (นี่, newtab, j, oldcap); อื่น {// รักษาโหนดลำดับ <k, v> lohead = null, lotail = null; โหนด <k, v> hihead = null, hitail = null; โหนด <k, v> ถัดไป; ทำ {next = e.next; // ดัชนีดั้งเดิมถ้า ((e.hash & oldcap) == 0) {ถ้า (lotail == null) lohead = e; else lotail.next = e; lotail = e; } // ดัชนีดั้งเดิม + oldcap else {ถ้า (hitail == null) hihead = e; else hitail.next = e; hitail = e; }} ในขณะที่ ((e = ถัดไป)! = null); // ใส่ดัชนีดั้งเดิมลงในถังถ้า (lotail! = null) {lotail.next = null; newtab [j] = lohead; } // ใส่ดัชนีดั้งเดิม + oldcap ลงในถังถ้า (hitail! = null) {hitail.next = null; newtab [j + oldcap] = hihead; }}}}} ส่งคืน newtab;}สรุป
ตอนนี้เราสามารถตอบคำถามหลายข้อในตอนแรกเพื่อให้เข้าใจ HashMap ได้อย่างลึกซึ้งยิ่งขึ้น:
1. จะใช้ HashMap เมื่อไหร่? ลักษณะของเขาคืออะไร?
มันขึ้นอยู่กับการใช้งานอินเทอร์เฟซแผนที่ เมื่อจัดเก็บคู่คีย์-ค่าจะได้รับค่าคีย์ Null ซึ่งเป็นแบบอะซิงโครนัส รายการ HashMap เก็บ (แฮชคีย์ค่าค่าถัดไป) วัตถุ
2. คุณรู้หรือไม่ว่า HASHMAP ทำงานอย่างไร?
ด้วยวิธีแฮชวัตถุจะถูกจัดเก็บและได้รับผ่านการใส่และรับ เมื่อจัดเก็บวัตถุเมื่อเราผ่าน k/v ไปยังวิธีการวางจะเรียกแฮชโค้ดเพื่อคำนวณแฮชเพื่อรับตำแหน่งที่เก็บข้อมูลและเก็บไว้เพิ่มเติม HashMap จะปรับความจุโดยอัตโนมัติตามอาชีพที่ฝากข้อมูลปัจจุบัน (ถ้าเกินโหลด facotr การปรับขนาดจะเป็นสองเท่าของต้นฉบับ) เมื่อได้รับวัตถุเราจะผ่าน K เพื่อรับซึ่งการเรียก HashCode เพื่อคำนวณแฮชเพื่อรับตำแหน่งที่เก็บข้อมูลและเรียกใช้เมธอด Equals () เพิ่มเติมเพื่อกำหนดคู่คีย์-ค่า หากเกิดการชนกัน HashMap จะจัดองค์ประกอบที่สร้างความขัดแย้งในการชนผ่านรายการที่เชื่อมโยง ใน Java 8 หากองค์ประกอบที่ชนกันในถังเกินขีด จำกัด ที่แน่นอน (ค่าเริ่มต้นคือ 8) จะใช้ต้นไม้สีแดงและสีดำเพื่อแทนที่รายการที่เชื่อมโยงเพื่อเพิ่มความเร็ว
3. คุณรู้หลักการของการรับและใส่หรือไม่? ฟังก์ชั่นของ Equals () และ hashcode () คืออะไร?
โดยการแฮช hashcode () ของคีย์และคำนวณตัวห้อย (N-1 & แฮช) ตำแหน่งของถังจะได้รับ หากเกิดการชนให้ใช้เมธอด key.equals () เพื่อค้นหาโหนดที่เกี่ยวข้องในรายการที่เชื่อมโยงหรือต้นไม้
4. คุณรู้จักการใช้แฮชหรือไม่? ทำไมฉันต้องทำสิ่งนี้?
ในการใช้งานของ Java 1.8 จะถูกนำไปใช้ผ่าน HashCode (HashCode (HASHCODE ต่ำ 16 บิตต่ำ 16 บิตสูง 16 บิต (H = K.HASHCODE ()) ^ (h >>> 16) ซึ่งส่วนใหญ่จะพิจารณาจากความเร็วประสิทธิภาพและคุณภาพ สิ่งนี้สามารถมั่นใจได้ว่าเมื่อ n ของถังมีขนาดค่อนข้างเล็กมันยังสามารถตรวจสอบให้แน่ใจว่าบิตสูงและต่ำมีส่วนร่วมในการคำนวณแฮชและจะไม่มีค่าใช้จ่ายมากเกินไป
5. จะเกิดอะไรขึ้นถ้าขนาดของ HashMap เกินความจุที่กำหนดโดยปัจจัยโหลด?
หากเกินปัจจัยการโหลด (ค่าเริ่มต้น 0.75) แฮชแมปที่มีความยาวเดิมสองเท่าจะถูกปรับขนาดและวิธีแฮชจะถูกเรียกอีกครั้ง
แผ่นโกงเกี่ยวกับคอลเลกชัน Java ได้อธิบายไว้ดังนี้:
อาร์เรย์ที่เก็บแฮชที่ใช้งานกับอาร์เรย์ [] รายการและค่าแฮชของคีย์สามารถใช้เพื่อรับตัวห้อยอาร์เรย์
เมื่อแทรกองค์ประกอบหากปุ่มสองปุ่มตกอยู่ในถังเดียวกัน (ตัวอย่างเช่นหลังจากค่าแฮช 1 และ 17 เป็นโมดูโล 16 ทั้งคู่เป็นของถังแฮชแรก) รายการจะใช้คุณสมบัติถัดไปเพื่อใช้หลายรายการในรายการที่เชื่อมโยงทางเดียว
เมื่อมองหาคีย์ที่มีค่าแฮช 17 ก่อนค้นหาถังแฮชแรกก่อนจากนั้นวนซ้ำทุกองค์ประกอบในถังด้วยรายการที่เชื่อมโยงและเปรียบเทียบค่าคีย์ของพวกเขาทีละตัว
เมื่อจำนวนรายการถึง 75% ของถัง (บทความจำนวนมากบอกว่าจำนวนถังที่ใช้ถึง 75% แต่ตามรหัสอาร์เรย์ถังจะขยายออกไปทวีคูณและรายการเดิมทั้งหมดจะถูกกำหนดใหม่ดังนั้นจึงเป็นการดีที่สุดที่จะมีค่าโดยประมาณที่นี่
การดำเนินการบิต (Hash & (arraylength-1)) จะเร็วขึ้นดังนั้นขนาดของอาร์เรย์จะอยู่ที่ n กำลัง n เสมอของ 2 ถ้าคุณให้ค่าเริ่มต้นเช่น 17 มันจะถูกแปลงเป็น 32 ค่าเริ่มต้นเริ่มต้นเมื่อองค์ประกอบแรกคือ 16
Iterator () ข้ามไปตามอาร์เรย์ของถังแฮชซึ่งดูเหมือนว่าจะไม่เป็นระเบียบ
6. จะเกิดอะไรขึ้นเมื่อแฮชโค้ดของวัตถุสองชิ้นเหมือนกัน?
เนื่องจาก hashcode เหมือนกันตำแหน่งถังของพวกเขาเหมือนกันและ 'การชน' จะเกิดขึ้น เนื่องจาก HashMap ใช้รายการที่เชื่อมโยงเพื่อจัดเก็บวัตถุรายการนี้ (วัตถุ Map.entry ที่มีคู่คีย์-ค่า) ถูกเก็บไว้ในรายการที่เชื่อมโยง
7. ถ้าแฮชโฟนของสองปุ่มเหมือนกันคุณจะได้รับวัตถุค่าได้อย่างไร?
หลังจากค้นหาตำแหน่งที่เก็บข้อมูลจะมีการเรียกวิธีการคีย์คีย์ () เพื่อค้นหาโหนดที่ถูกต้องในรายการที่เชื่อมโยงและในที่สุดก็พบวัตถุค่าที่จะพบ ดังนั้นเมื่อออกแบบประเภทคีย์ของ HASHMAP หากมีการประกาศวัตถุที่ไม่เปลี่ยนรูปเป็นขั้นสุดท้ายและใช้วิธีการที่เหมาะสม () และวิธีการ HashCode () การเกิดการชนจะลดลงและประสิทธิภาพจะดีขึ้น ความไม่สามารถเปลี่ยนแปลงได้สามารถแคชแฮชโค้ดสำหรับคีย์ที่แตกต่างกันซึ่งจะเพิ่มความเร็วในการรับวัตถุทั้งหมด การใช้คลาส wrapper เช่นสตริงและ interger เป็นคีย์เป็นตัวเลือกที่ดีมาก
8. จะเกิดอะไรขึ้นถ้าขนาดของ HASHMAP เกินความสามารถที่กำหนดโดยปัจจัยโหลด?
ขนาดปัจจัยโหลดเริ่มต้นคือ 0.75 กล่าวคือเมื่อแผนที่เติมถัง 75% เช่นเดียวกับคลาสคอลเลกชันอื่น ๆ (เช่น ArrayList ฯลฯ ) อาร์เรย์ถังที่มีขนาดเท่ากันสองเท่าของ HashMap ดั้งเดิมจะถูกสร้างขึ้นเพื่อปรับขนาดแผนที่และใส่วัตถุดั้งเดิมลงในอาร์เรย์ถังใหม่ กระบวนการนี้เรียกว่า rehashing เนื่องจากเรียกวิธีแฮชเพื่อค้นหาตำแหน่งถังใหม่
9. คุณเข้าใจไหมว่ามีอะไรผิดปกติกับการปรับขนาด HASHMAP หรือไม่?
เมื่อปรับขนาด HashMap มีการแข่งขันแบบมีเงื่อนไขอย่างแท้จริงเพราะหากทั้งสองเธรดพบว่าต้องมีการปรับขนาด HashMap พวกเขาจะพยายามปรับขนาดในเวลาเดียวกัน ในระหว่างกระบวนการปรับขนาดลำดับขององค์ประกอบที่เก็บไว้ในรายการที่เชื่อมโยงจะถูกย้อนกลับเพราะเมื่อย้ายไปยังตำแหน่งถังใหม่ HashMap ไม่ได้วางองค์ประกอบในตอนท้ายของรายการที่เชื่อมโยง แต่ที่หัวซึ่งจะหลีกเลี่ยงการข้ามหาง หากการแข่งขันแบบมีเงื่อนไขเกิดขึ้นจะมีวงจรอุบาทว์ ดังนั้นในสภาพแวดล้อมที่เกิดขึ้นพร้อมกันเราใช้ CurrentHashMap เพื่อแทนที่ HashMap
10. เหตุใดคลาส wrapper จึงชอบสตริงและ Interger เหมาะกับปุ่ม?
เนื่องจากสตริงไม่เปลี่ยนรูปและสุดท้ายและวิธีการ Equals () และ HashCode () ได้รับการเขียนใหม่ คลาส wrapper อื่น ๆ ยังมีคุณสมบัตินี้ ความไม่สามารถเปลี่ยนแปลงได้เป็นสิ่งจำเป็นเนื่องจากเพื่อคำนวณ HashCode () คุณต้องป้องกันไม่ให้ค่าคีย์เปลี่ยน หากค่าคีย์ส่งคืนแฮชโค้ดที่แตกต่างกันเมื่อใส่และรับคุณไม่พบวัตถุที่คุณต้องการจากแฮชแมป ความไม่สามารถเปลี่ยนแปลงได้มีข้อได้เปรียบอื่น ๆ เช่นความปลอดภัยของด้าย หากคุณสามารถรับประกันได้ว่า hashcode ไม่เปลี่ยนแปลงเพียงแค่ประกาศฟิลด์เป็นขั้นสุดท้ายโปรดทำเช่นนั้น เนื่องจากวิธี Equals () และ hashCode () ถูกใช้เมื่อได้รับวัตถุจึงเป็นสิ่งสำคัญมากที่จะเขียนทั้งสองวิธีนี้ใหม่อย่างถูกต้อง หากวัตถุที่ไม่เท่ากันสองรายการส่งคืน hashcodes ที่แตกต่างกันโอกาสของการชนจะเล็กลงซึ่งจะปรับปรุงประสิทธิภาพของ HashMap
ขอบคุณสำหรับการอ่านฉันหวังว่ามันจะช่วยคุณได้ ขอบคุณสำหรับการสนับสนุนเว็บไซต์นี้!