ในบทความนี้เราเริ่มวิเคราะห์ซอร์สโค้ดของ LinkedHashMap LinkedHashMap สืบทอด HashMap ซึ่งหมายความว่า LinkedHashMap จะขยายตาม HashMap ดังนั้นก่อนที่จะดูซอร์สโค้ดของ LinkedHashMap ผู้อ่านจำเป็นต้องเข้าใจซอร์สโค้ดของ HASHMAP คุณสามารถตรวจสอบการแนะนำบทความก่อนหน้าของฉัน "Java Collection Series [3] ---- การวิเคราะห์ซอร์สโค้ด HashMap" ตราบใดที่คุณมีความเข้าใจอย่างลึกซึ้งเกี่ยวกับหลักการดำเนินการของ HashMap จากนั้นดูที่ซอร์สโค้ดของ LinkedHashMap, Hashset และ LinkedHashset นั้นง่ายมาก ดังนั้นผู้อ่านควรเป็นผู้ป่วยและศึกษาซอร์สโค้ด HASHMAP นี่เป็นธุรกิจที่ดีในการซื้อหนึ่งได้ฟรี เมื่อวิเคราะห์ซอร์สโค้ด HashMap ก่อนหน้านี้ฉันใช้การวิเคราะห์ที่เน้นปัญหาของซอร์สโค้ดเพื่อที่ฉันจะไม่วิเคราะห์แบบสุ่มเหมือนแมลงวันหัวขาดและผู้อ่านอาจมีความเข้าใจที่ลึกซึ้งยิ่งขึ้นเกี่ยวกับปัญหา ในบทความนี้ฉันตัดสินใจใช้วิธีนี้เพื่อวิเคราะห์ LinkedHashMap
1. โครงสร้างแบบไหนที่ใช้ภายใน LinkedHashMap?
อย่างที่คุณเห็นเนื่องจาก LinkedHashMap สืบทอดมาจาก HashMap ยังมีตารางแฮชภายใน LinkedHashMap แต่ LinkedHashMap ได้เขียนรายการใหม่และเพิ่มตัวแปรสมาชิกสองตัวลงในรายการ HashMap ดั้งเดิมคือการอ้างอิงโหนดก่อนหน้าและการอ้างอิงโหนด ด้วยวิธีนี้โหนดทั้งหมดจะเชื่อมโยงเข้าด้วยกันเพื่อสร้างรายการที่เชื่อมโยงสองทาง เมื่อได้รับองค์ประกอบเพียงสำรวจรายการที่เชื่อมโยงสองทางโดยตรง มาดูกันว่าการใช้งาน LinkedHashMap ของรายการเป็นอย่างไร
รายการคลาสคงที่ส่วนตัว <k, v> ขยาย hashmap.entry <k, v> {// การอ้างอิงของโหนดก่อนหน้าของโหนดปัจจุบันในรายการรายการที่เชื่อมโยงสองทิศทาง <k, v> ก่อน; // การอ้างอิงของโหนดที่ตามมาของโหนดปัจจุบันในรายการรายการที่เชื่อมโยงสองทิศทาง <k, v> หลังจาก; รายการ (int hash, k key, v value, hashmap.entry <k, v> next) {super (แฮช, คีย์, ค่า, ถัดไป); } // ลบโหนดนี้ออกจากรายการที่เชื่อมโยงแบบสองทิศทางโมฆะส่วนตัวลบ () {ก่อนหน้า = หลังจาก; หลังจากนั้นก่อน = ก่อน; } // แทรกโหนดปัจจุบันลงในโหนดที่มีอยู่ในรายการที่เชื่อมโยงแบบสองทิศทางเป็นโมฆะส่วนตัว addbefore (รายการ <k, v> applient entingentry) {// การอ้างอิงของโหนดถัดไปของโหนดปัจจุบันชี้ไปที่โหนดที่กำหนด // การอ้างอิงของโหนดก่อนหน้าของโหนดปัจจุบันชี้ไปที่โหนดก่อนหน้าของโหนดที่กำหนดก่อน = appive entingEntry. ก่อนหน้า; // การอ้างอิงของโหนดถัดไปของโหนดที่กำหนดจะชี้ไปที่โหนดปัจจุบันก่อนหน้า = สิ่งนี้; // การอ้างอิงของโหนดก่อนหน้าของโหนดที่กำหนดชี้ไปที่โหนดปัจจุบันหลังจากนั้นก่อน = สิ่งนี้; } // เรียงลำดับตามลำดับของการเข้าถึงบันทึกทุกครั้งที่การดำเนินการได้รับ void recordAccess (hashmap <k, v> m) {linkedhashmap <k, v> lm = (linkedhashmap <k, v>) m; // ถ้าเรียงลำดับในลำดับการเข้าถึงถ้า (lm.accessorder) {lm.modcount ++; // ลบตัวเองออกจากรายการที่เชื่อมโยงแบบสองทิศทางก่อน; // วางตัวเองไปที่หางของรายการที่เชื่อมโยงแบบสองทิศทาง Addbefore (LM.Header); }} void recordRemoval (hashmap <k, v> m) {ลบ (); -2. LinkedHashMap ใช้การเรียงลำดับในลำดับการแทรกอย่างไร
// วิธีการที่จะถูกเรียกในวิธีการใส่ของโมฆะคลาสแม่ที่เป็นโมฆะ (int แฮชคีย์ k, ค่า V, int bucketIndex) {// การเรียกใช้วิธีการเสริมของคลาสแม่ super.addentry (แฮช, คีย์, ค่า, bucketindex); // การดำเนินการต่อไปนี้สะดวกสำหรับการใช้งานแคช LRU หากความจุแคชไม่เพียงพอให้ลบรายการองค์ประกอบที่เก่าแก่ที่สุด <k, v> ผู้สูงอายุ = header.fter; if (removeEldestentry (eldest)) {removeentryforkey (eldest.key); }} // วิธีการเป็นโมฆะ createentry (int hash, key, k, v ค่า V, int bucketindex) {// ก่อนอื่นรับรายการ hashmap ของ hashmap.entry <k, v> old = table [bucketindex]; // ห่อลงในรายการของ LinkedHashMap <k, v> e = รายการใหม่ <> (แฮช, คีย์, ค่า, เก่า); ตาราง [BucketIndex] = E; // แทรกโหนดปัจจุบันไปที่หางของรายการที่เชื่อมโยงสองทิศทาง e.addbefore (ส่วนหัว); ขนาด ++;}LinkedHashMap แทนที่วิธีการเสริมและวิธีการสร้างของ HASHMAP คลาสแม่ เมื่อคุณต้องการแทรกคู่คีย์-ค่าวิธีการวางของคลาสแม่ HASHMAP จะถูกเรียกก่อน ในวิธีการวางเราจะตรวจสอบว่าคีย์ที่เกี่ยวข้องมีอยู่ในตารางแฮชหรือไม่ หากมีอยู่ให้แทนที่ค่าโดยตรง หากไม่มีอยู่ให้โทรหาวิธี Addentry เพื่อสร้างรายการใหม่ โปรดทราบว่าในเวลานี้วิธีการเสริมของ LinkedHashMap นั้นเรียกว่า เราเห็นรหัสด้านบน นอกเหนือจากการโทรกลับวิธี Addeldestentry ของคลาสแม่แล้ว Addeldestentry นี้จะเรียก removeeldestentry เพื่อลบองค์ประกอบที่เก่าแก่ที่สุด การดำเนินการนี้ส่วนใหญ่จะใช้อัลกอริทึม LRU ซึ่งจะกล่าวถึงด้านล่าง เราเห็นว่า LinkedHashMap ยังเขียนวิธีการสร้างใหม่อีกครั้ง เมื่อคุณต้องการสร้างรายการใหม่วิธีนี้จะถูกเรียก หลังจากแต่ละครั้งที่มีการใส่รายการลงในตารางแฮชวิธี Addbefore จะถูกเรียกให้แทรกโหนดปัจจุบันลงในหางของรายการที่เชื่อมโยงสองทิศทาง ด้วยวิธีนี้รายการที่เชื่อมโยงแบบสองทิศทางจะบันทึกลำดับของแต่ละโหนดที่แทรก เมื่อได้รับองค์ประกอบเพียงสำรวจรายการที่เชื่อมโยงแบบสองทิศทาง รูปต่อไปนี้แสดงการดำเนินการของการโทรแต่ละครั้งเพื่อเพิ่มก่อน เนื่องจากเป็นรายการที่เชื่อมโยงแบบสองทิศทางก่อนที่จะแทรกโหนดปัจจุบันลงในโหนดหัวจึงมีการแทรกโหนดปัจจุบันลงในหางของรายการที่เชื่อมโยงสองทิศทาง
3. วิธีใช้ LinkedHashMap เพื่อใช้ Cache LRU ได้อย่างไร?
เรารู้ว่าการใช้แคชขึ้นอยู่กับหน่วยความจำของคอมพิวเตอร์และทรัพยากรหน่วยความจำค่อนข้าง จำกัด และเป็นไปไม่ได้ที่จะจัดเก็บองค์ประกอบโดยไม่ จำกัด ดังนั้นเราจำเป็นต้องลบองค์ประกอบบางอย่างอย่างเหมาะสมเมื่อความสามารถไม่เพียงพอ องค์ประกอบใดที่ดีกว่าในการลบ? แนวคิดของอัลกอริทึม LRU คือหากมีการเข้าถึงข้อมูลเมื่อเร็ว ๆ นี้โอกาสในการเข้าถึงในอนาคตก็สูงขึ้นเช่นกัน ดังนั้นเราสามารถลบข้อมูลที่ไม่สามารถเข้าถึงได้บ่อยครั้ง จากนั้นมาดูกันว่า LinkedHashMap ใช้กลไก LRU อย่างไร
คลาสสาธารณะ LinkedHashMap <k, v> ขยาย hashmap <k, v> ใช้แผนที่ <k, v> {// ทั้งรายการที่เชื่อมโยงทั้งรายการส่วนหัวส่วนตัวชั่วคราว <k, v> ส่วนหัว; // เรียงลำดับการเข้าถึงบูลีนสุดท้ายส่วนตัวตามลำดับการเข้าถึง; ... Public LinkedHashMap (int initialcapacity, float loadfactor, boolean accessorder) {super (เริ่มต้นความสามารถ, loadfactor); this.AccessOrder = AccessOrder; } // รับค่าตามคีย์สาธารณะ v รับ (คีย์วัตถุ) {// การเรียกใช้เมธอดคลาสแม่เพื่อรับรายการที่เกี่ยวข้อง <k, v> e = (รายการ <k, v>) getentry (คีย์); if (e == null) {return null; } // หากมีการเรียงลำดับในลำดับการเข้าถึงโหนดหลังจากการใช้งานแต่ละครั้งจะถูกวางไว้ที่ส่วนท้ายของรายการที่เชื่อมโยงสองทิศทาง e.RecordAccess (นี้); ส่งคืน e.value; } รายการคลาสสแตติกส่วนตัว <k, v> ขยาย hashmap.entry <k, v> {... // แทรกโหนดปัจจุบันลงในด้านหน้าของโหนดที่มีอยู่ในรายการที่เชื่อมโยงสองทิศทางเป็นโมฆะส่วนตัว addbefore (รายการ <k, v> appive entingentry) {// การอ้างอิงของโหนดต่อไปของโหนดปัจจุบัน // การอ้างอิงของโหนดก่อนหน้าของโหนดปัจจุบันชี้ไปที่โหนดก่อนหน้าของโหนดที่กำหนดก่อน = appive entingEntry. ก่อนหน้า; // การอ้างอิงของโหนดถัดไปของโหนดที่กำหนดจะชี้ไปที่โหนดปัจจุบันก่อนหน้า = สิ่งนี้; // การอ้างอิงของโหนดก่อนหน้าของโหนดที่กำหนดชี้ไปที่โหนดปัจจุบันหลังจากนั้นก่อน = สิ่งนี้; } // เรียงลำดับในลำดับการเข้าถึงบันทึกทุกครั้งที่การดำเนินการเป็นโมฆะ recordAccess (hashmap <k, v> m) {linkedhashmap <k, v> lm = (linkedhashmap <k, v>) m; // ถ้าเรียงลำดับในลำดับการเข้าถึงถ้า (lm.accessorder) {lm.modcount ++; // ลบตัวเองออกจากรายการที่เชื่อมโยงแบบสองทิศทางก่อน; // วางตัวเองไปที่หางของรายการที่เชื่อมโยงแบบสองทิศทาง Addbefore (LM.Header); }} ... } // วิธีนี้จะถูกเรียกในคลาสพาเรนต์ให้ใช้วิธีการเป็นโมฆะ addentry (int แฮชคีย์ k, ค่า V, int bucketindex) {// คำนวณวิธี addentry ของคลาสแม่ super.addentry (แฮชคีย์ค่า bucketindex); // การดำเนินการต่อไปนี้สะดวกสำหรับการใช้งานแคช LRU หากความจุแคชไม่เพียงพอให้ลบรายการองค์ประกอบที่เก่าแก่ที่สุด <k, v> ผู้สูงอายุ = header.fter; if (removeeldestentry (eldest)) {removeeldestforkey (eldest.key); }} // จะลบองค์ประกอบที่เก่าแก่ที่สุดได้ที่ไหน? วิธีนี้ได้รับการออกแบบให้ถูกเขียนทับโดย subclasses boolean removeldestentry (map.entry <k, v> ผู้สูงอายุ) {return false; -เพื่อให้เข้าใจง่ายกว่านี้ฉันละเว้นรหัสที่ไม่เกี่ยวข้องบางอย่างในรหัสที่โพสต์ด้านบน เราจะเห็นได้ว่า LinkedHashMap มีตัวแปร AccessOress ของสมาชิกซึ่งบันทึกว่าจำเป็นต้องจัดเรียงตามลำดับการเข้าถึงหรือไม่ มันมีตัวสร้างที่สามารถระบุค่าของ AccessOrder เอง ทุกครั้งที่คุณเรียกวิธีการรับเพื่อรับองค์ประกอบ e.recordaccess (นี้) เรียกว่าซึ่งจะย้ายโหนดปัจจุบันไปยังจุดสิ้นสุดของรายการที่เชื่อมโยงสองทิศทาง ตอนนี้เรารู้แล้วว่าหาก AccessOrment เป็นจริงทุกครั้งที่เราได้รับองค์ประกอบเราจะย้ายองค์ประกอบนี้ไปยังจุดสิ้นสุดของรายการลิงก์แบบสองทิศทาง จุดประสงค์ของขั้นตอนนี้คือการแยกแยะองค์ประกอบที่ใช้กันมากที่สุดจากองค์ประกอบที่ไม่ได้ใช้บ่อยและองค์ประกอบที่ใช้บ่อยจะถูกวางไว้ในตอนท้ายและองค์ประกอบที่ใช้กันทั่วไปน้อยกว่าจะถูกวางไว้ที่หัว ลองกลับไปที่รหัสด้านบนและดูว่าทุกครั้งที่มีการเรียกใช้วิธีการเสริมเราจะพิจารณาว่าองค์ประกอบที่เก่าแก่ที่สุดจะต้องถูกลบหรือไม่ ตรรกะของการตัดสินถูกนำมาใช้โดย RemoveEldestentry ซึ่งได้รับการออกแบบให้ถูกแทนที่ด้วยคลาสย่อยและเขียนตรรกะภายใน โปรดทราบว่าเนื่องจากโหนดที่เข้าชมเมื่อเร็ว ๆ นี้ถูกย้ายไปที่หางของรายการที่เชื่อมโยงสองทิศทางโหนดที่เก่าแก่ที่สุดจะถูกนำออกมาจากหัวของรายการที่เชื่อมโยงสองทิศทางสำหรับการลบ ตัวอย่างต่อไปนี้ใช้แคช LRU อย่างง่าย
ชั้นเรียนสาธารณะ lrumap <k, v> ขยาย linkedhashmap <k, v> {ความจุ int ส่วนตัว; LRUMAP (ความจุ int) {// การเรียกตัวสร้างคลาสแม่, ตั้งค่าให้เรียงลำดับในลำดับการเข้าถึง super (ความจุ, 1f, true); this.capacity = ความจุ; } @Override บูลีนสาธารณะ removeldestentry (map.entry <k, v> ผู้สูงอายุ) {// เมื่อคู่คีย์-ค่ามากกว่าหรือเท่ากับความจุตารางแฮชส่งคืนสิ่งนี้ขนาด ()> = ความจุ; } โมฆะคงที่สาธารณะหลัก (สตริง [] args) {lrumap <จำนวนเต็ม, สตริง> map = ใหม่ lrumap <จำนวนเต็ม, สตริง> (4); map.put (1, "a"); map.put (2, "B"); map.put (3, "C"); System.out.println ("คอลเลกชันดั้งเดิม:" + แผนที่); สตริง s = map.get (2); System.out.println ("รับองค์ประกอบ:" + แผนที่); map.put (4, "d"); System.out.println ("หลังการแทรก:" + แผนที่); -ผลลัพธ์มีดังนี้:
หมายเหตุ: การวิเคราะห์ทั้งหมดข้างต้นขึ้นอยู่กับ JDK1.7 และจะมีความแตกต่างระหว่างเวอร์ชันที่แตกต่างกันผู้อ่านจำเป็นต้องให้ความสนใจ
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น