คำนำ: มีสิ่งใหม่ ๆ เพิ่มขึ้นหลังจาก Java 8 ฉันพบข้อมูลที่เกี่ยวข้องออนไลน์ หลังจาก HashMap ถูกทารุณกรรมฉันตัดสินใจที่จะแยกแยะความรู้ที่เกี่ยวข้องสำหรับตัวเอง บทความนี้สำหรับการอ้างอิงในรูปภาพและเนื้อหาบางส่วน: http://www.vevb.com/article/80446.htm
โครงสร้างการจัดเก็บของ HashMap จะแสดงในรูป: หากมีมากกว่า 8 โหนดบนถังโครงสร้างการจัดเก็บเป็นต้นไม้สีแดงและสีดำและน้อยกว่า 8 เป็นรายการที่เชื่อมโยงทางเดียว
1: คุณสมบัติบางอย่างของ hashmap
คลาสสาธารณะ HASHMAP <k, v> ขยายบทคัดย่อ <k, v> ใช้แผนที่ <k, v>, cloneable, serializable {ส่วนตัวคงที่สุดท้ายสุดท้าย serialversionuid = 362498820763181265l; 30; // ปัจจัยการเติมเริ่มต้น (เวอร์ชันก่อนหน้านี้เรียกอีกอย่างว่าโหลดปัจจัย) Float float float default_load_factor = 0.75f; // นี่คือเกณฑ์ เมื่อจำนวนรายการที่เชื่อมโยงบนถังมากกว่าค่านี้มันจะถูกแปลงเป็นต้นไม้สีแดงและสีดำ รหัสของวิธีการใช้ใช้ int สุดท้าย int treeify_threshold = 8; // นอกจากนี้ยังเป็นเกณฑ์ เมื่อจำนวนรายการที่เชื่อมโยงบนถังน้อยกว่าค่านี้ต้นไม้จะถูกแปลงเป็นรายการที่เชื่อมโยงสุดท้าย int untreeify_threshold = 6; // มีการกล่าวในความคิดเห็นของซอร์สโค้ดว่า: ความจุต่ำสุดของต้นไม้อย่างน้อย 4 x treeify_threshold = 32 อาร์เรย์ขององค์ประกอบจะถูกเก็บไว้มักจะมีหลายโหนดชั่วคราว 2 โหนด <k, v> [] ตาราง; ชุดชั่วคราว <map.entry <k, v >> entryset; // จำนวนองค์ประกอบที่เก็บไว้โปรดทราบว่าสิ่งนี้ไม่เท่ากับความยาวของอาร์เรย์ ขนาด int ชั่วคราว; // ตัวนับสำหรับการขยายแต่ละครั้งและการเปลี่ยนแปลงของโครงสร้างแผนที่คือ int modcount ชั่วคราว; // ค่าวิกฤตจะถูกขยายเมื่อขนาดจริง (ความจุ * ปัจจัยเติม) เกินค่าวิกฤตความจุจะขยายเกณฑ์ int; // ปัจจัยการเติมสุดท้าย2: วิธีการก่อสร้าง HashMap
// ตัวสร้างสำหรับการระบุความสามารถเริ่มต้นและปัจจัยเติม hashmap สาธารณะ (int initialcapacity, float loadfactor) {// ความจุเริ่มต้นที่ระบุนั้นไม่เป็นลบถ้า (เริ่มต้นความสามารถ <0) โยนความผิดกฎหมายใหม่ที่ผิดกฎหมาย (ความจุเริ่มต้นที่ผิดกฎหมาย maximum_capacity; // อัตราส่วนการเติมเป็นค่าบวกถ้า (loadfactor <= 0 || float.isnan (loadfactor)) โยน unlegalargumentException ใหม่ (ปัจจัยโหลดที่ผิดกฎหมาย: +loadfactor); this.loadfactor = loadfactor; // หลังจากระบุความจุเมธอด tableizefor จะคำนวณค่าวิกฤต หากเกินค่าเมื่อใส่ข้อมูลมันจะขยาย ค่าเป็นแบบหลายอย่างของ 2.// ความจุเริ่มต้นที่ระบุยังไม่ได้รับการบันทึกและใช้เพื่อสร้างค่าวิกฤตนี้เท่านั้น threshold = tableizefor (เริ่มต้นความสามารถ);} // วิธีนี้ทำให้มั่นใจได้ว่ามันจะส่งคืนค่าที่สูงกว่า cap n | = n >>> 1; n | = n >>> 2; n | = n >>> 4; n | = n >>> 8; n | = n >>> 16; // ซ้อนกลับของผู้ประกอบการตรีโกณมิติ (n <0)? 1: (n> = maximum_capacity)? maximum_capacity: n + 1;} // constructor 2public hashmap (int initialcapacity) {this (initialcapacity, default_load_factor);} // constructor 3public hashmap () {this.loadfactor = default_load_factor; // ฟิลด์อื่น ๆ ทั้งหมดเริ่มต้น}3: กำหนดตำแหน่งขององค์ประกอบในอาร์เรย์เมื่อได้รับและวาง
hash int สุดท้ายคงที่ (คีย์วัตถุ) {int h; return (key == null)? 0: (h = key.hashCode ()) ^ (h >>> 16);}เพื่อกำหนดตำแหน่ง
ขั้นตอนแรก: สิ่งแรกคือการคำนวณรหัสแฮชของคีย์ซึ่งเป็นหมายเลขประเภท int H >>> 16 ความคิดเห็นของซอร์สโค้ดกล่าวว่า: เพื่อหลีกเลี่ยงการชนกันของแฮชตำแหน่งสูงจะแพร่กระจายไปยังตำแหน่งต่ำซึ่งเกิดขึ้นหลังจากคำนึงถึงปัจจัยต่าง ๆ เช่นความเร็วและประสิทธิภาพ
ขั้นตอนที่ 2: H คือรหัสแฮชความยาวคือความยาวของโหนด [] อาร์เรย์ด้านบนทำการทำงานเดียวกัน H & (ความยาว -1) เนื่องจากความยาวเป็นหลายตัวของ 2 -1 รหัสไบนารีของมันคือ 1 และผลลัพธ์ของ 1 กับตัวเลขอื่น ๆ ที่อาจเป็น 0 หรือ 1 เพื่อให้แน่ใจว่ามีความสม่ำเสมอหลังจากการดำเนินการ นั่นคือวิธีการแฮชทำให้มั่นใจได้ถึงความสม่ำเสมอของผลลัพธ์ซึ่งสำคัญมากและจะส่งผลกระทบอย่างมากต่อการวางและรับประสิทธิภาพของ Hashmap ดูภาพต่อไปนี้สำหรับการเปรียบเทียบ:
รูปที่ 3.1 เป็นผลลัพธ์แฮชแบบไม่สมมาตร
รูปที่ 3.2 เป็นผลลัพธ์แฮชที่สมดุล
มีข้อมูลไม่มากในกราฟทั้งสองนี้ หากรายการที่เชื่อมโยงนานกว่า 8 จะถูกแปลงเป็นต้นไม้สีแดงและสีดำ มันจะชัดเจนมากขึ้นในเวลานั้น JDK8 เคยเป็นรายการที่เชื่อมโยงมาก่อน ความซับซ้อนของการสืบค้นรายการที่เชื่อมโยงคือ o (n) และความซับซ้อนของต้นไม้สีแดงและสีดำเนื่องจากลักษณะของตัวเองคือ o (log (n)) หากผลลัพธ์แฮชไม่สม่ำเสมอมันจะส่งผลกระทบอย่างมากต่อความซับซ้อนของการดำเนินการ มี <a href = "http://blog.chinaunix.net/uid-26575352-id-3061918.html"> บล็อกความรู้พื้นฐานของต้นไม้สีแดงและสีดำ </a> มีอีกตัวอย่างหนึ่งในการตรวจสอบ: วัตถุที่กำหนดเอง
คลาสสาธารณะ MutableKeyTest {โมฆะคงที่สาธารณะหลัก (สตริง args []) {คลาส myKey {จำนวนเต็ม i; โมฆะสาธารณะ seti (จำนวนเต็ม i) {this.i = i;} สาธารณะของฉัน (จำนวนเต็ม i) {this.i = i; ต้องใช้วิธี Equals @Overridepublic Boolean เท่ากับ (Object OBJ) {ถ้า (OBJ InstanceOf MyKey) {return i.equals ((((myKey) obj .i);} else {return false;}}} // การกำหนดค่าเครื่องของฉันไม่สูง แผนที่ <mykey, string> map = new hashmap <> (25000,1); วันที่เริ่มต้น = วันที่ใหม่ (); สำหรับ (int i = 0; i <20000; i ++) {map.put (ใหม่ของ mykey (i), "test" + i);} วันที่สิ้นสุด = วันที่ใหม่ ();4: รับวิธีการ
สาธารณะ 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; // hash & (length -1) รับตำแหน่งรูทของต้นไม้สีแดงและสีดำหรือส่วนหัวของรายการที่เชื่อมโยงถ้า ((แท็บ = ตาราง)! = null && (n = tab.length)> 0 && (first = tab [n - 1) & hash])! = null) key.equals (k)))) กลับก่อน; ถ้า ((e = first.next)! = null) {// ถ้าเป็นต้นไม้ความซับซ้อนของการข้ามต้นไม้สีแดงและสีดำคือ o (log (n)) เพื่อรับค่าโหนดถ้า (อินสแตนซ์แรกของ treenode) กลับ (treenode <k, v>) == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) return e;} ในขณะที่ ((e = e.next)! = null);}} return null;}5: ใส่วิธีการเมื่อใส่ให้ค้นหาถังตาม H & (ความยาว 1) จากนั้นดูว่ามันเป็นต้นไม้สีแดงและสีดำหรือรายการที่เชื่อมโยงและ putval
Public V Put (k key, v value) {return putval (แฮช (คีย์), คีย์, ค่า, เท็จ, จริง);} สุดท้าย v putval (int hash, k key, v ค่า V, บูลีนเฉพาะผู้ที่มีการขับไล่บูลีน) {node <k, v> [] แท็บ; โหนด <k, v> p; int n, i; // ถ้าแท็บว่างเปล่าหรือความยาวคือ 0, หน่วยความจำที่จัดสรร resize () ถ้า ((แท็บ = ตาราง) == null || (n = tab.length) == 0) n = (แท็บ = resize ()). ความยาว; // (n - 1) & แฮชค้นหาตำแหน่ง ถ้ามันว่างเปล่า putif โดยตรง ((p = tab [i = (n - 1) & แฮช]) == null) แท็บ [i] = newNode (แฮช, คีย์, ค่า, ค่า null); อื่น ๆ {node <k, v> e; k k; // ค่าแฮชของโหนดแรกเหมือนกันและค่าคีย์เหมือนกับปุ่มแทรกถ้า (p.hash == hash && ((k = p.key) == key || (key! = null && key.equals (k))) e = p; หลังจาก Putval คุณต้องสำรวจต้นไม้ทั้งหมด เมื่อจำเป็นให้ปรับเปลี่ยนค่าเพื่อให้แน่ใจว่าลักษณะของต้นไม้สีแดงและสีดำ E = ((treenode <k, v>) p) .puttreeval (นี่, แท็บ, แฮช, คีย์, ค่า); อื่น ๆ {// รายการที่เชื่อมโยงสำหรับ (int bincount = 0; จุดสิ้นสุดของตารางจากนั้นสร้างโหนดใหม่ p.next = newNode (แฮชคีย์ค่า null); // หลังจากเพิ่มโหนดใหม่หากจำนวนโหนดถึงขีด จำกัด ให้แปลงรายการที่เชื่อมโยงเป็นต้นไม้สีแดงและสีดำถ้า (bincount> = treeify_threshold - 1) // -1 == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) break; p = e;}} // อัปเดตค่าโหนดด้วยค่าแฮชเดียวกันและค่าคีย์ถ้า (e! = null) {// การแมปที่มีอยู่ ค่า; ช่วงบ่าย (e); return oldValue;}} ++ modcount; if (++ ขนาด> threshold) ปรับขนาด (); ช่วงบ่าย (evict); return null;}6: วิธีการปรับขนาด
โหนดสุดท้าย <k, v> [] resize () {node <k, v> [] oldtab = table; int oldcap = (oldtab == null)? 0: oldtab.length; int oldtr = threshold; int newcap, newtr = 0; ถ้า (oldcap> 0) {ถ้า (oldcap> = maximum_capacity) {threshold = integer.max_value; returntab;} // ประโยคนี้มีความสำคัญมากกว่า maximum_capacity && oldcap> = default_initial_capacity) newThr = oldtr << 1; // double threshold} else ถ้า (oldthr> 0) // ความจุเริ่มต้นถูกวางไว้ใน thresholdNewCap = oldTHR; else {// zero threshold เริ่มต้นหมายถึงการใช้ defaultSNewCap = default_initial_capacity; newTHR = (int) (int) loadfactor; newTHR = (newCap <maximum_capacity && ft <(float) maximum_capacity? (int) ft: integer.max_value);} threshold = newtr; @suppresswarnings ({"newtab (new) Node [newCap]; table = newTab; if (oldTab! = null) {สำหรับ (int j = 0; j <oldcap; ++ j) {node <k, v> e; ถ้า ((e = oldtab [j])! = null) {oldtab [j] = null; treenode) ((treenode <k, v>) e) .split (this, newtab, j, oldcap); else {// preserve ordernode <k, v> lohead = null, lotail = null; node <k, v> hihead = null, hitail = null; (lotail == null) lohead = e; elselotail.next = e; lotail = e;} else {ถ้า (hitail == null) hihead = e; elsehitail.next = e; hitail = e;}} ในขณะที่ (e = next)! = null) null) {hitail.next = null; newtab [j + oldcap] = hihead;}}}}} return newtab;}ข้างต้นเป็นความรู้ที่เกี่ยวข้องเกี่ยวกับการวิเคราะห์หลักการดำเนินการของ Java8 HashMap ที่แนะนำโดยบรรณาธิการ ฉันหวังว่ามันจะเป็นประโยชน์กับคุณ!