เรารู้ว่าตารางแฮชเป็นโครงสร้างข้อมูลที่มีประสิทธิภาพมากและการออกแบบฟังก์ชั่นแฮชที่ยอดเยี่ยมสามารถทำการเพิ่มการลบการปรับเปลี่ยนและการดำเนินการค้นหาในระดับ O (1) Java มอบโครงสร้างแฮชสำเร็จรูปให้เรานั่นคือคลาส HashMap ในบทความก่อนหน้านี้ฉันแนะนำคลาส HashMap และรู้ว่าวิธีการทั้งหมดไม่ได้ซิงโครไนซ์ดังนั้นจึงไม่ปลอดภัยในสภาพแวดล้อมแบบมัลติเธรด ด้วยเหตุนี้ Java ให้เรามีคลาสแฮชช์อีกอันซึ่งง่ายมากและหยาบในการจัดการการซิงโครไนซ์แบบมัลติเธรดนั่นคือเพื่อล็อควิธีการทั้งหมดโดยใช้คำหลักที่ซิงโครไนซ์ตาม HashMap แม้ว่าวิธีนี้จะง่าย แต่ก็นำไปสู่ปัญหานั่นคือมีเพียงเธรดเดียวเท่านั้นที่สามารถใช้งานตารางแฮชได้ในเวลาเดียวกัน แม้ว่าเธรดเหล่านี้จะเป็นเพียงการอ่านการดำเนินการ แต่ก็ต้องเข้าคิวซึ่งส่งผลกระทบอย่างมากต่อประสิทธิภาพในสภาพแวดล้อมแบบมัลติเธรดที่มีการแข่งขันสูง พร้อมกันที่แนะนำในบทความนี้คือการแก้ปัญหานี้ มันใช้ล็อคแบบแบ่งส่วนเพื่อล็อคเม็ดละเอียดเพื่อให้หลายเธรดสามารถใช้งานตารางแฮชในเวลาเดียวกันซึ่งปรับปรุงประสิทธิภาพอย่างมาก รูปต่อไปนี้เป็นแผนผังแผนผังของโครงสร้างภายใน
1. ตัวแปรสมาชิกใดบ้างที่เกิดขึ้นพร้อมกันมี?
// ค่าเริ่มต้นความจุเริ่มต้นคงที่ int final default_initial_capacity = 16; // ค่าเริ่มต้นปัจจัยการโหลดเริ่มสุดท้าย float float default_load_factor = 0.75f; // ระดับการเกิดขึ้นพร้อมกันเริ่มต้นสุดท้าย int default_concurrency_level = 16; // ตั้งค่าความจุสูงสุด 2; // จำนวนสูงสุดของการล็อคส่วนสุดท้าย int max_segments = 1 << 16; // จำนวนการกลับมาก่อนที่จะล็อค int สุดท้ายคงที่ retries_before_lock = 2; // ค่าหน้ากากของการล็อคส่วนสุดท้าย int segmentmask;
ก่อนที่จะอ่านบทความนี้ฉันเชื่อว่าผู้อ่านไม่สามารถเข้าใจความหมายและฟังก์ชั่นเฉพาะของตัวแปรสมาชิกเหล่านี้ได้ แต่ผู้อ่านควรอ่านอย่างอดทน บทบาทของตัวแปรสมาชิกเหล่านี้จะได้รับการแนะนำทีละหนึ่งในสถานการณ์เฉพาะในภายหลัง ที่นี่ผู้อ่านจะต้องออกจากตัวแปรสมาชิกเหล่านี้ที่คุ้นเคยเท่านั้น อย่างไรก็ตามยังมีตัวแปรบางอย่างที่เราต้องรู้ตอนนี้ ตัวอย่างเช่นอาร์เรย์เซ็กเมนต์แสดงถึงชุดของการล็อคเซ็กเมนต์ระดับการเกิดขึ้นพร้อมกันแสดงถึงจำนวนของการล็อคเซ็กเมนต์ (ซึ่งหมายถึงจำนวนเธรดที่สามารถทำงานได้ในเวลาเดียวกัน) ความสามารถในการเริ่มต้นแสดงถึงความสามารถของภาชนะทั้งหมดและปัจจัยการโหลดแสดงถึงระดับขององค์ประกอบของคอนเทนเนอร์
2. โครงสร้างภายในของการล็อคเซ็กเมนต์คืออะไร?
// การล็อคเซกเมนต์สเตทคลาสสุดท้ายระดับสุดท้าย <k, v> ขยาย reentrantlock ใช้ serializable {// หมายเลขสปินสูงสุดคงที่สุดท้าย int max_scan_retries = runtime.getRuntime (). arightprocessors ()> 1? 64: 1; // hast ตารางการระเหยชั่วคราว hashentry <k, v> [] ตาราง; // จำนวนทั้งหมดขององค์ประกอบชั่วคราวจำนวน int; // จำนวนของการแก้ไขชั่วคราว int modcount; // Element Threshold threshold trimient int; // โหลดปัจจัยสุดท้ายลอยตัวโหลด; // ละเว้นเนื้อหาต่อไปนี้ ... }เซ็กเมนต์เป็นคลาสภายในแบบสแตติกของพร้อมกันกับมาใช้คุณจะเห็นว่ามันสืบทอดมาจาก reentrantlock ดังนั้นมันจึงเป็นล็อคเป็นหลัก มันถืออาร์เรย์แฮชรีย์ (ตารางแฮช) ภายในและทำให้มั่นใจได้ว่าวิธีการทั้งหมดของการเพิ่มการลบการแก้ไขและการค้นหาอาร์เรย์นั้นปลอดภัย การดำเนินการเฉพาะจะมีการหารือในภายหลัง การดำเนินการทั้งหมดเกี่ยวกับการเพิ่มการลบการแก้ไขและการตรวจสอบการเกิดขึ้นพร้อมกันสามารถมอบหมายให้เซ็กเมนต์ได้ดังนั้นพร้อมกันดังนั้นจึงสามารถมั่นใจได้ว่าปลอดภัยในสภาพแวดล้อมแบบมัลติเธรด นอกจากนี้เนื่องจากกลุ่มที่แตกต่างกันเป็นล็อคที่แตกต่างกัน multithreads สามารถใช้งานเซ็กเมนต์ที่แตกต่างกันในเวลาเดียวกันซึ่งหมายความว่ามัลติเธรดสามารถทำงานร่วมกันได้ในเวลาเดียวกันซึ่งสามารถหลีกเลี่ยงข้อบกพร่องของแฮชช์ที่ดีและปรับปรุงประสิทธิภาพอย่างมาก
3. การเริ่มต้นพร้อมกันเกิดอะไรขึ้น?
// core constructor @suppresswarnings ("unchected") สาธารณะพร้อมกัน public (int initialcapacity, float loadfactor, int concurrencylevel) {ถ้า (! (loadfactor> 0) || การเริ่มต้น <0 || concurrencylevel <= 0) } // ตรวจสอบให้แน่ใจว่าระดับการเกิดขึ้นพร้อมกันไม่เกินขีด จำกัด หาก (พร้อมกัน iscurrencyLevel> max_segments) {ConcurrencyLevel = max_segments; } int sshift = 0; int ssize = 1; // ตรวจสอบให้แน่ใจว่า SSIZE เป็นพลังของ 2 และเป็นจำนวนที่ใกล้เคียงที่สุดหรือเท่ากับระดับการเกิดขึ้นพร้อมกันในขณะที่ (SSIZE <CONECRENCYLEVEL) {++ SSHIFT; ssize << = 1; } // คำนวณค่ากะของการล็อคเซ็กเมนต์ this.segmentshift = 32 - sshift; // คำนวณค่าหน้ากากของการล็อคเซ็กเมนต์ this.segmentmask = ssize - 1; // ความจุเริ่มต้นทั้งหมดไม่สามารถมากกว่าค่าขีด จำกัด ถ้า (เริ่มต้นความสามารถ> maximum_capacity) {initialCapacity = maximum_capacity; } // รับความจุเริ่มต้นของแต่ละเซ็กเมนต์ล็อค int c = initialCapacity /ssize; // ผลรวมของความสามารถในการล็อคแบบแบ่งส่วนไม่น้อยกว่าความจุรวมเริ่มต้นถ้า (c * ssize <initialcapacity) {++ c; } int cap = min_segment_table_capacity; // ตรวจสอบให้แน่ใจว่าหมวกเป็นกำลังของ 2 และเป็นจำนวนที่ใกล้เคียงที่สุดมากกว่าหรือเท่ากับ C ในขณะที่ (cap <c) {cap << = 1; } // สร้างเซ็กเมนต์เทมเพลตวัตถุเซ็กเมนต์ใหม่ <k, v> s0 = เซ็กเมนต์ใหม่ <k, v> (loadfactor, (int) (cap * loadfactor), (hashentry <k, v> []) ใหม่ hashentry [cap]); // สร้างอาร์เรย์ล็อคเซ็กเมนต์ใหม่ของเซ็กเมนต์ขนาดที่ระบุ <k, v> [] ss = (เซ็กเมนต์ <k, v> []) เซ็กเมนต์ใหม่ [ssize]; // ใช้ unsafe เพื่อกำหนดองค์ประกอบ 0th ของอาร์เรย์ unsafe.putOrderEdObject (SS, SBase, S0); this.sgments = ss;}ConcurrentHashMap มีตัวสร้างหลายตัว แต่สิ่งที่โพสต์ด้านบนเป็นตัวสร้างหลักและตัวสร้างอื่น ๆ เริ่มต้นอย่างสมบูรณ์โดยเรียกมัน ตัวสร้างหลักจำเป็นต้องผ่านในพารามิเตอร์สามตัวคือความจุเริ่มต้นปัจจัยการโหลดและระดับการเกิดขึ้นพร้อมกัน เมื่อแนะนำตัวแปรสมาชิกก่อนหน้านี้เราสามารถรู้ได้ว่าความจุเริ่มต้นเริ่มต้นคือ 16 ปัจจัยการโหลดคือ 0.75F และระดับการเกิดขึ้นพร้อมกันคือ 16 ตอนนี้เราเห็นรหัสของตัวสร้างหลัก อันดับแรกเราคำนวณ SSIZE ผ่านการเกิดขึ้นพร้อมกันที่เข้ามา SSIZE คือความยาวของอาร์เรย์เซ็กเมนต์ มันจะต้องรับประกันว่าจะเป็นพลังของ 2 ด้วยวิธีนี้ตัวห้อยของส่วนที่ถูกล็อคในอาร์เรย์สามารถคำนวณได้โดย Hash & Ssize-1 เนื่องจากการเกิดขึ้นพร้อมกันที่เข้ามาไม่สามารถรับประกันได้ว่าเป็นพลังของ 2 จึงไม่สามารถใช้งานได้โดยตรงเป็นความยาวของอาร์เรย์เซ็กเมนต์ ดังนั้นเราจำเป็นต้องค้นหาพลังของ 2 ที่ใกล้เคียงกับการทำพร้อมกันและใช้เป็นความยาวของอาร์เรย์ หากการทำงานพร้อมกัน = 15 ถูกส่งผ่านในขณะนี้รหัสด้านบนสามารถคำนวณ SSIZE = 16 และ SSHIFT = 4 ถัดไปคุณสามารถคำนวณ segmentshift = 16 และ segmentmask = 15 ได้ทันที โปรดทราบว่าการแบ่งส่วนที่นี่คือค่าการเปลี่ยนแปลงของการล็อคเซ็กเมนต์และเซ็กเมนต์มาสค์เป็นค่าหน้ากากของการล็อคเซ็กเมนต์ ค่าทั้งสองนี้ใช้ในการคำนวณตัวห้อยของการล็อคเซ็กเมนต์ในอาร์เรย์ซึ่งเราจะพูดถึงด้านล่าง หลังจากคำนวณจำนวนของการล็อคเซ็กเมนต์ SSIZE ความสามารถของการล็อคแต่ละเซ็กเมนต์สามารถคำนวณได้ตามความสามารถในการเข้ามาทั้งหมดและค่า C = การเริ่มต้น/SSIZE ความสามารถของการล็อคส่วนคือความยาวของอาร์เรย์แฮชรีนและจะต้องรับประกันว่าจะเป็นกำลังของ 2 ค่าของ C ที่คำนวณไว้ข้างต้นไม่สามารถรับประกันได้ดังนั้น C ไม่สามารถใช้ได้โดยตรงเนื่องจากความยาวของอาร์เรย์แฮเชนทรี คุณต้องหาพลังอื่นที่อยู่ใกล้กับ C มากที่สุดกำหนดค่านี้ให้กับ CAP จากนั้นใช้ CAP เป็นความยาวของอาร์เรย์ Hashentry ตอนนี้เรามี SSIZE และ CAP แล้วเราสามารถสร้างเซ็กเมนต์ล็อคเซ็กเมนต์ใหม่ [] และอาร์เรย์องค์ประกอบแฮเชนทรี [] โปรดทราบว่าแตกต่างจาก JDK1.6 มีเพียงอาร์เรย์เซ็กเมนต์ที่สร้างขึ้นใน JDK1.7 และไม่ได้เริ่มต้น การทำงานของการเริ่มต้นเซ็กเมนต์ถูกทิ้งไว้ในการดำเนินการแทรก
4. วิธีการค้นหาล็อคและค้นหาองค์ประกอบ?
// รับการล็อคเซ็กเมนต์ตามรหัสแฮช @suppresswarnings ("ไม่ถูกตรวจสอบ") เซ็กเมนต์ส่วนตัว <k, v> segmentforhash (int h) {long u = (((h >>> segmentshift) & segmentmask) << sshift) + sbase; return (เซ็กเมนต์ <k, v>) unsafe.getObjectVolatile (ส่วน, u);} // รับองค์ประกอบตามรหัสแฮช @suppresswarnings ("unchecked") สุดท้าย <k, v> hashentry <k, v> entryforhash (เซกเมนต์ <k, v> seg return (seg == null || (tab = seg.table) == null)? NULL: (hashentry <k, v>) unsafe.getObjectVolatile (แท็บ, ((ยาว) ((tab.length - 1) & h)) << tshift) + tbase);} ใน JDK1.7 ไม่ปลอดภัยใช้เพื่อรับองค์ประกอบอาร์เรย์ดังนั้นนี่คือรหัสเพิ่มเติมในการคำนวณองค์ประกอบอาร์เรย์มากกว่า JDK1.6 เราจะไม่ให้ความสนใจกับรหัสเหล่านี้ในขณะนี้ ตอนนี้เราจำเป็นต้องรู้สองจุดต่อไปนี้:
. คำนวณตัวห้อยของเซ็กเมนต์ที่ล็อคไว้ในอาร์เรย์ผ่านรหัสแฮช: (h >>> segmentshift) & segmentmask
ข. คำนวณตัวห้อยขององค์ประกอบในอาร์เรย์โดยรหัสแฮช: (tab.length - 1) & h
ตอนนี้สมมติว่าพารามิเตอร์ทั้งสองที่ส่งผ่านไปยังคอนสตรัคเตอร์นั้นเป็นจุดเริ่มต้น = 128, ConcurrencyLevel = 16 ตามการคำนวณเราสามารถรับ ssize = 16, sshift = 4, segmentshift = 28, segmentmask = 15 ในทำนองเดียวกันความยาวของอาร์เรย์ hashentry ในการล็อคแต่ละเซ็กเมนต์จะคำนวณเป็น 8 ดังนั้น tab.length-1 = 7 จากค่าเหล่านี้เราอธิบายวิธีการค้นหาส่วนล็อคส่วนและองค์ประกอบตามรหัสแฮชเดียวกันผ่านรูปด้านล่าง
จะเห็นได้ว่าการล็อคเซ็กเมนต์และการวางตำแหน่งองค์ประกอบจะถูกกำหนดโดยรหัสแฮชขององค์ประกอบ การล็อคเซ็กเมนต์การวางตำแหน่งเป็นค่าสูงของรหัสแฮช (เริ่มต้นจาก 32 บิต) และองค์ประกอบการวางตำแหน่งเป็นค่าต่ำของรหัสแฮช ตอนนี้มีคำถาม พวกเขาเริ่มต้นจากปลายซ้ายของ 32 บิตและปลายด้านขวาของ 32 บิต จะมีความขัดแย้งในบางจุดหรือไม่? เราสามารถค้นหา maximum_capacity = 1 << 30, max_segments = 1 << 16 ในตัวแปรสมาชิกซึ่งหมายความว่าจำนวนบิตทั้งหมดที่ใช้สำหรับการวางตำแหน่งการล็อคเซ็กเมนต์และองค์ประกอบการวางตำแหน่งไม่เกิน 30 และจำนวนบิตที่ใช้สำหรับการวางตำแหน่ง
5. วิธีการค้นหาองค์ประกอบโดยเฉพาะ?
// รับ ValuePublic V รับ (คีย์วัตถุ) {เซ็กเมนต์ <k, v> s; hashentry <k, v> [] แท็บ; // คำนวณรหัสแฮชโดยใช้ฟังก์ชันแฮช int h = แฮช (คีย์); // คำนวณดัชนีของการล็อคเซ็กเมนต์ตามรหัสแฮชยาว u = (((h >>> segmentshift) & segmentmask) << sshift) + sbase; // รับการล็อคเซ็กเมนต์และตารางแฮชที่สอดคล้องกันถ้า ((s = (เซ็กเมนต์ <k, v>) unsafe.getObjectVolatile (เซ็กเมนต์ u))! = null && (tab = s.table)! = null) {// รับโหนดส่วนหัวของรายการที่เชื่อมโยง (Hashentry <k, v>) unsafe.getobjectvolatile (แท็บ, (ยาว) ((tab.length - 1) & h)) << tshift) + tbase); // ทำตามค่าขององค์ประกอบที่สอดคล้องกันตามคีย์และแฮชและส่งคืนค่าถ้า ((k = E.key) == คีย์ || (e.hash == h && key.equals (k))) {return e.value; }}} return null;}ใน JDK1.6 วิธี GET ของการล็อคเซ็กเมนต์เข้าถึงองค์ประกอบอาร์เรย์ผ่านตัวห้อยในขณะที่อยู่ใน JDK1.7 องค์ประกอบในอาร์เรย์จะถูกอ่านผ่านวิธี GetObjectVolatile ของ Unsafe ทำไมถึงทำเช่นนี้? เรารู้ว่าแม้ว่าการอ้างอิงอาร์เรย์แฮชรีนที่จัดขึ้นโดยวัตถุเซ็กเมนต์นั้นเป็นประเภทของความผันผวน แต่การอ้างอิงองค์ประกอบในอาร์เรย์ไม่ได้มีความผันผวนประเภทดังนั้นการดัดแปลงมัลติเธรดไปยังองค์ประกอบอาร์เรย์นั้นไม่ปลอดภัยและอาจอ่านวัตถุที่ยังไม่ได้สร้างในอาร์เรย์ ใน JDK1.6 การอ่านล็อคครั้งที่สองรับประกันได้ว่าจะปลอดภัยและใน JDK1.7 วิธีการอ่านผ่าน GetObjectVolatile ของ UNSAFE ก็เพื่อให้แน่ใจว่าสิ่งนี้ การอ่านองค์ประกอบอาร์เรย์โดยใช้วิธี getObjectVolatile ต้องได้รับการชดเชยขององค์ประกอบในอาร์เรย์ก่อน ที่นี่ตามรหัสแฮชการชดเชยของการล็อคเซ็กเมนต์ในอาร์เรย์คือ U และจากนั้นออฟเซ็ต U จะถูกใช้เพื่อพยายามอ่านการล็อคเซ็กเมนต์ เนื่องจากอาร์เรย์ล็อคเซ็กเมนต์ไม่ได้เริ่มต้นในระหว่างการก่อสร้างค่าว่างอาจถูกอ่านออกดังนั้นจึงจำเป็นต้องมีการตัดสินก่อน หลังจากยืนยันว่าการล็อคเซ็กเมนต์และตารางแฮชภายในไม่ว่างองค์ประกอบของอาร์เรย์แฮชรีจะอ่านผ่านรหัสแฮช ตามแผนภาพโครงสร้างด้านบนคุณจะเห็นว่าโหนดส่วนหัวของรายการที่เชื่อมโยงจะได้รับในเวลานี้ จากนั้นสำรวจและค้นหารายการที่เชื่อมโยงตั้งแต่ต้นจนจบ หากพบค่าที่สอดคล้องกันมันจะถูกส่งคืนมิฉะนั้นจะถูกส่งคืนค่าโมฆะ ข้างต้นเป็นกระบวนการทั้งหมดของการค้นหาองค์ประกอบ
6. จะใช้องค์ประกอบการแทรกอย่างไร?
// เพิ่มคู่คีย์-ค่าลงในชุด (แทนที่ถ้ามี) @suppresswarnings ("ไม่ได้ตรวจสอบ") สาธารณะ v ใส่ (k key, v value) {เซ็กเมนต์ <k, v> s; // ค่าที่ผ่านไม่สามารถว่างเปล่าได้หาก (value == null) โยน nullpointerexception ใหม่ (); // คำนวณรหัสแฮชโดยใช้ฟังก์ชันแฮช int hash = แฮช (คีย์); // คำนวณตัวห้อยของการล็อคเซ็กเมนต์ตามรหัสแฮช int j = (แฮช >>> segmentshift) & segmentmask; // พยายามรับการล็อคเซ็กเมนต์ตามตัวห้อยถ้า ((s = (เซ็กเมนต์ <k, v>) unsafe.getObject (เซ็กเมนต์, (j << sshift) + sbase)) == null) {// ถ้าล็อคเซ็กเมนต์ที่ได้รับว่าง } // เรียกวิธีการใส่ของการล็อคเซ็กเมนต์ส่งคืน s.put (คีย์, แฮช, ค่า, เท็จ);} // เพิ่มคู่คีย์ค่าเข้ากับชุด (เพิ่มถ้าไม่มีอยู่) @suppresswarnings ("ไม่ถูกตรวจสอบ") สาธารณะ v putifabsent (k key, v value) // ค่าที่ผ่านไม่สามารถว่างเปล่าได้หาก (value == null) โยน nullpointerexception ใหม่ (); // คำนวณรหัสแฮชด้วยแฮช = แฮช (คีย์); // คำนวณตัวห้อยของการล็อคเซ็กเมนต์ตามรหัสแฮช int j = (แฮช >>> segmentshift) & segmentmask; // พยายามรับการล็อคเซ็กเมนต์ตามตัวห้อยถ้า ((s = (เซ็กเมนต์ <k, v>) unsafe.getObject (เซ็กเมนต์, (j << sshift) + sbase)) == null) {// สร้าง s = ensuresegment (j); } // ปฏิทินวิธีการใส่ของการล็อคเซ็กเมนต์ส่งคืน s.put (คีย์แฮชค่าจริง);}มีสองวิธีในการเกิดขึ้นพร้อมกันเพื่อเพิ่มคู่คีย์-ค่า หากมีอยู่มันจะถูกเขียนทับเมื่อเพิ่มผ่านวิธีการใส่ วิธีการ IFABSENT จะถูกเพิ่มผ่านวิธีการใส่ iFABSENT มันจะไม่ถูกเขียนทับ ทั้งสองวิธีเรียกวิธีการใส่ของการล็อคเซ็กเมนต์เพื่อให้การดำเนินการเสร็จสมบูรณ์ แต่พารามิเตอร์สุดท้ายที่ส่งผ่านจะแตกต่างกัน ในรหัสข้างต้นเราจะเห็นว่าก่อนอื่นเราคำนวณตัวห้อยของการล็อคเซ็กเมนต์ในอาร์เรย์ตามรหัสแฮชของคีย์จากนั้นใช้เมธอด GetObject คลาสที่ไม่ปลอดภัยเพื่ออ่านการล็อคเซ็กเมนต์ตามตัวห้อย เนื่องจากองค์ประกอบในอาร์เรย์เซ็กเมนต์ไม่ได้เริ่มต้นเมื่อสร้างการเกิดขึ้นพร้อมกันอาจมีการอ่านค่า NULL และล็อคเซ็กเมนต์ใหม่จะถูกสร้างขึ้นผ่านวิธีการ ensuresegment หลังจากได้รับการล็อคเซ็กเมนต์ให้โทรหาวิธีการเพื่อให้การดำเนินการเพิ่มเติมเสร็จสมบูรณ์ ลองมาดูวิธีการใช้งาน
// เพิ่มคู่คีย์คู่สุดท้าย v ใส่ (k key, int hash, v value, boolean onlyifabsent) {// ลองรับการล็อคถ้ามันล้มเหลว null: scanandlockforput (คีย์, แฮช, ค่า); v oldvalue; ลอง {hashentry <k, v> [] tab = table; // คำนวณดัชนี int ตัวห้อยขององค์ประกอบ = (tab.length - 1) & แฮช; // รับโหนดส่วนหัวของรายการที่เชื่อมโยงตามตัวห้อย subscript hashentry <k, v> first = entryat (แท็บ, ดัชนี); สำหรับ (hashentry <k, v> e = ก่อน ;;) {// transf รายการที่เชื่อมโยงเพื่อค้นหาองค์ประกอบและถ้า (e! = null) {k k; if ((k = E.key) == key || (e.hash == hash && key.equals (k)))) {oldValue = e.value; // ตัดสินใจว่าจะแทนที่ค่าเก่าตามพารามิเตอร์หรือไม่ถ้า (! onlyifabsent) {e.value = ค่า; ++ modcount; } หยุดพัก; } E = E.Next; // หากไม่พบให้เพิ่มโหนดลงในรายการที่เชื่อมโยง} else {// แทรกโหนดโหนดลงในส่วนหัวของรายการที่เชื่อมโยงถ้า (Node! = null) {node.setNext (ก่อน); } else {node = new hashentry <k, v> (แฮช, คีย์, ค่า, ก่อน); } // หลังจากแทรกโหนดให้เพิ่ม 1 int c = count + 1 เสมอ; // ถ้าองค์ประกอบเกินขีด จำกัด ให้ขยายความจุถ้า (C> threshold && tab.length <maximum_capacity) {rehash (โหนด); // มิฉะนั้นให้แทนที่ตารางแฮชที่ระบุตัวห้อยที่ระบุด้วยโหนดโหนด} อื่น {setEntryat (แท็บดัชนี, โหนด); } ++ modcount; นับ = C; oldValue = null; หยุดพัก; }}} ในที่สุด {ปลดล็อค (); } return oldValue;}เพื่อให้แน่ใจว่ามีความปลอดภัยของเธรดใส่การดำเนินการในการล็อคแบบแบ่งส่วนจะต้องถูกล็อคดังนั้นเธรดจะได้รับการล็อคที่จุดเริ่มต้นและดำเนินการต่อเพื่อดำเนินการหากการได้มานั้นสำเร็จ หากการได้มาล้มเหลวให้โทรหาวิธี ScanandlockForput เพื่อหมุน ในระหว่างกระบวนการหมุนให้สแกนตารางแฮชเพื่อค้นหาคีย์ที่ระบุ หากคีย์ไม่มีอยู่แฮเชนทรีใหม่จะถูกสร้างขึ้นเพื่อไม่จำเป็นต้องสร้างอีกครั้งหลังจากได้รับการล็อค ในการทำบางสิ่งบางอย่างในขณะที่รอล็อคมันจะไม่เสียเวลาอย่างไร้ประโยชน์ สิ่งนี้แสดงให้เห็นถึงความตั้งใจที่ดีของผู้เขียน เราจะอธิบายวิธีการหมุนเฉพาะในรายละเอียดในภายหลัง ตอนนี้ดึงโฟกัสกลับมาก่อน หลังจากเธรดได้รับการล็อคสำเร็จจะได้รับองค์ประกอบของตัวห้อยที่ระบุตามตัวห้อยที่คำนวณได้ ในเวลานี้จะได้รับโหนดส่วนหัวของรายการที่เชื่อมโยง หากโหนดส่วนหัวไม่ว่างเปล่ารายการที่เชื่อมโยงจะถูกสำรวจและค้นหา หลังจากค้นหาแล้วให้ตัดสินใจว่าจะแทนที่ตามค่าของพารามิเตอร์เฉพาะที่มีความชัดเจนหรือไม่ หากไม่พบการสำรวจการเดินสายใหม่ Hashentry ใหม่จะชี้ไปที่โหนดส่วนหัว ในเวลานี้หากมีการสร้างแฮเชนทรีระหว่างการหมุนให้ชี้โดยตรงถัดจากโหนดส่วนหัวปัจจุบัน หากไม่ได้สร้างสปินจะสร้างแฮเชนทรีใหม่ที่นี่และชี้ไปที่โหนดส่วนหัว หลังจากเพิ่มองค์ประกอบในรายการที่เชื่อมโยงให้ตรวจสอบว่าจำนวนองค์ประกอบทั้งหมดเกินเกณฑ์หรือไม่ หากเกินกว่าที่จะโทรหา Rehash สำหรับการขยายตัว หากไม่เกินมันให้ดูที่องค์ประกอบตัวห้อยที่เกี่ยวข้องโดยตรงของอาร์เรย์ไปยังโหนดที่เพิ่มใหม่ เมธอด setEntryat จะเปลี่ยนการอ้างอิงองค์ประกอบอาร์เรย์โดยการเรียกใช้วิธีการ PutorderEdObject ของ Unsafe ซึ่งทำให้มั่นใจได้ว่าเธรดอื่น ๆ สามารถอ่านค่าล่าสุดเมื่ออ่าน
7. จะใช้การลบองค์ประกอบได้อย่างไร?
// ลบองค์ประกอบที่ระบุ (ลบโดยตรงหลังจากค้นหาองค์ประกอบที่เกี่ยวข้อง) สาธารณะ v ลบ (คีย์วัตถุ) {// ใช้ฟังก์ชันแฮชเพื่อคำนวณรหัสแฮช int hash = แฮช (คีย์); // ได้รับดัชนีของการล็อคเซ็กเมนต์ตามส่วนโค้ดแฮช <k, v> s = segmentforhash (แฮช); // ปฏิทินวิธีลบวิธีการล็อคเซ็กเมนต์ส่งคืน s == null? null: s.remove (คีย์, แฮช, null);} // ลบองค์ประกอบที่ระบุ (ลบค่าเท่ากับค่าที่กำหนด) บูลีนสาธารณะลบ (คีย์วัตถุค่าวัตถุ) {// ใช้ฟังก์ชันแฮชเพื่อคำนวณรหัสแฮช int hash = แฮช (คีย์); เซ็กเมนต์ <k, v> s; // สามารถตรวจสอบให้แน่ใจว่าการล็อคเซ็กเมนต์ไม่ว่างเปล่าก่อนที่จะเรียกค่ารีคืนค่าของวิธีการส่งคืน! = null && (s = segmentforhash (แฮช))! = null && s.remove (คีย์แฮชค่า)! = null;}ConcurrentHashMap ให้การลบสองครั้งหนึ่งคือการลบมันโดยตรงหลังจากค้นหามันและอีกอันคือการเปรียบเทียบก่อนแล้วลบออกหลังจากค้นหา วิธีการลบทั้งสองนี้คือการค้นหาการล็อคเซ็กเมนต์ที่สอดคล้องกันตามรหัสแฮชของคีย์จากนั้นดำเนินการลบโดยเรียกใช้วิธีลบของการล็อคเซ็กเมนต์ มาดูวิธีการลบการล็อคเซ็กเมนต์
// ลบองค์ประกอบที่ระบุสุดท้าย v ลบ (คีย์วัตถุ, int แฮช, ค่าวัตถุ) {// ลองรับการล็อคถ้ามันล้มเหลวหมุนถ้า (! trylock ()) {scanandlock (คีย์แฮช); } v oldValue = null; ลอง {hashentry <k, v> [] tab = table; // คำนวณดัชนี int ตัวห้อยขององค์ประกอบ = (tab.length - 1) & แฮช; // รับองค์ประกอบอาร์เรย์ตามโหนดตัวห้อย (ลิงก์รายการส่วนหัว) Hashentry <k, v> e = entryat (แท็บ, ดัชนี); Hashentry <k, v> pred = null; // โอนรายการที่เชื่อมโยงเพื่อค้นหาองค์ประกอบที่จะลบในขณะที่ (e! = null) {k k; // ชี้ไปที่โหนดผู้สืบทอดของโหนดปัจจุบัน hashentry <k, v> next = e.next; // ค้นหาโหนดที่สอดคล้องกันตามคีย์และแฮชถ้า ((k = E.key) == คีย์ || (e.hash == hash && key.equals (k))) {v v = e.value; // ข้ามค่าที่ส่งผ่านถ้าไม่เท่ากับ V และลบในกรณีอื่น ๆ ถ้า (value == null || value == V || value.equals (v)) {// ถ้า pred ว่างเปล่าหมายความว่าโหนดที่จะลบเป็นโหนดส่วนหัว (pred == null) } else {// ตั้งค่าการสืบทอดของโหนด pred เป็นโหนดถัดไป pred.setNext (ถัดไป); } ++ modcount; --นับ; // บันทึกค่าของการลบองค์ประกอบ oldValue = v; } หยุดพัก; } // ถ้า e ไม่ใช่โหนดที่คุณกำลังมองหาให้ชี้การอ้างอิงที่คาดการณ์ไว้ที่ pred = e; // ตรวจสอบโหนดถัดไป e = ถัดไป; }} ในที่สุด {ปลดล็อค (); } return oldValue;}เมื่อลบองค์ประกอบในการล็อคเซ็กเมนต์คุณจะต้องได้รับการล็อคก่อน หากการได้มาล้มเหลวให้โทรหาวิธี Scanandlock สำหรับการปั่น หากการซื้อกิจการสำเร็จให้ดำเนินการขั้นตอนต่อไป ครั้งแรกที่คำนวณตัวห้อยอาร์เรย์จากนั้นรับองค์ประกอบของอาร์เรย์แฮชรีนผ่านตัวห้อย ที่นี่จะได้รับโหนดส่วนหัวของรายการที่เชื่อมโยง ถัดไป Traversal และค้นหารายการที่เชื่อมโยง ก่อนหน้านี้ให้ใช้ตัวชี้ถัดไปเพื่อบันทึกโหนดผู้สืบทอดของโหนดปัจจุบันจากนั้นเปรียบเทียบคีย์และแฮชเพื่อดูว่าเป็นโหนดที่คุณกำลังมองหาหรือไม่ ถ้าเป็นเช่นนั้นให้ดำเนินการต่อไปหากการตัดสิน หากค่าว่างเปล่าหรือค่าเท่ากับค่าปัจจุบันของโหนดมันจะป้อนคำสั่ง IF สำหรับการลบมิฉะนั้นจะถูกข้ามโดยตรง มีสองสถานการณ์เมื่อทำการลบการดำเนินการในคำสั่ง IF หากโหนดปัจจุบันเป็นโหนดส่วนหัวให้ตั้งค่าโหนดถัดไปเป็นโหนดส่วนหัวโดยตรง หากโหนดปัจจุบันไม่ใช่โหนดส่วนหัวให้ตั้งผู้สืบทอดของโหนด pred เป็นโหนดถัดไป โหนด pred ที่นี่แสดงถึงรุ่นก่อนของโหนดปัจจุบัน แต่ละครั้งก่อนที่จะตรวจสอบโหนดถัดไป Pred จะถูกชี้ไปที่โหนดปัจจุบันซึ่งทำให้มั่นใจได้ว่าโหนด Pred จะเป็นรุ่นก่อนของโหนดปัจจุบันเสมอ โปรดทราบว่าต่างจาก JDK1.6 ใน JDK1.7 ตัวแปรถัดไปของวัตถุ Hashentry ไม่สิ้นสุดดังนั้นคุณสามารถลบองค์ประกอบได้โดยการแก้ไขค่าที่อ้างอิงโดยตรงโดยถัดไป เนื่องจากตัวแปรถัดไปเป็นประเภทที่ผันผวนเธรดการอ่านสามารถอ่านค่าล่าสุดได้ทันที
8. องค์ประกอบการเปลี่ยนมาใช้โดยเฉพาะอย่างไร?
// แทนที่องค์ประกอบที่ระบุ (การดำเนินการ CAS) บูลีนสาธารณะแทนที่ (k key, v oldValue, v newValue) {// ใช้ฟังก์ชันแฮชเพื่อคำนวณรหัสแฮช int แฮช = แฮช (คีย์); // ตรวจสอบให้แน่ใจว่า oldValue และ newValue จะไม่ว่างถ้า (oldValue == null || newValue == null) โยน nullpointerexception ใหม่ (); // รับดัชนีของการล็อคเซ็กเมนต์ตามส่วนรหัสแฮช <k, v> s = segmentforhash (แฮช); // การเรียกใช้วิธีการแทนที่ของการล็อคเซ็กเมนต์ส่งคืน s! = null && s.replace (กุญแจ, แฮช, oldValue, newValue);} // แทนที่การทำงานขององค์ประกอบ (การดำเนินการ CAS) บูลีนสุดท้ายแทนที่ (k key, int hash, v oldValue, v NewValue) } บูลีนแทนที่ = false; ลอง {hashentry <k, v> e; // ค้นหาโหนดส่วนหัวโดยตรงผ่านแฮชจากนั้นสำรวจรายการที่เชื่อมโยงสำหรับ (e = entryforhash (นี่, แฮช); e! = null; e = e.next) {k k; // ค้นหาโหนดที่จะถูกแทนที่ตามคีย์และแฮชถ้า ((k = e.key) == คีย์ || (e.hash == hash && key.equals (k))) {// ถ้าค่าปัจจุบันที่ระบุถูกต้องแทนที่ถ้า (oldValue.equals (e.value)) ++ modcount; แทนที่ = true; } // มิฉะนั้นหากไม่มีการดำเนินการให้กลับมาพัก }}} ในที่สุด {ปลดล็อค (); } return แทนที่;}ConcurrentHashMap ยังมีการดำเนินการทดแทนสองครั้งหนึ่งคือการแทนที่โดยตรงหลังจากการค้นหาและอื่น ๆ คือการเปรียบเทียบก่อนจากนั้นแทนที่ (การดำเนินการ CAS) การดำเนินการของการดำเนินการทั้งสองนี้จะเหมือนกันยกเว้นว่าการดำเนินการ CAS มีเลเยอร์การดำเนินการเปรียบเทียบเพิ่มเติมก่อนที่จะเปลี่ยนดังนั้นเราจึงต้องเข้าใจการดำเนินการสั้น ๆ ที่นี่เราใช้การดำเนินการ CAS สำหรับการวิเคราะห์ซึ่งยังคงเป็นกิจวัตรเก่า ขั้นแรกให้ค้นหาการล็อคเซ็กเมนต์ที่สอดคล้องกันตามรหัสแฮชของคีย์จากนั้นเรียกใช้วิธีการแทนที่ หลังจากป้อนวิธีการแทนที่ในการล็อคเซ็กเมนต์คุณจะต้องได้รับการล็อคก่อน หากการได้มาล้มเหลวให้หมุน หากการได้มาประสบความสำเร็จให้ดำเนินการต่อไปในขั้นตอนต่อไป ขั้นแรกให้รับโหนดส่วนหัวของรายการที่เชื่อมโยงตามรหัสแฮชจากนั้นสำรวจและค้นหาตามคีย์และแฮช หลังจากค้นหาองค์ประกอบที่เกี่ยวข้องให้เปรียบเทียบว่า OldValue ที่กำหนดเป็นค่าปัจจุบันหรือไม่ ถ้าไม่ยอมแพ้การดัดแปลงและถ้าเป็นเช่นนั้นให้แทนที่ด้วยค่าใหม่ เนื่องจากฟิลด์ค่าของวัตถุ Hashentry เป็นประเภทผันผวนจึงสามารถแทนที่ได้โดยตรง
9. คุณทำอะไรกันแน่เมื่อหมุน?
// สปินรอที่จะได้รับการล็อค (การดำเนินการ) hashentry ส่วนตัว <k, v> scanandlockforput (k key, int hash, v value) {// รับโหนดส่วนหัวตามรหัสแฮชแฮเชนทรี <k, v> first = entryforhash (hash, hash); hashentry <k, v> e = ก่อน; hashentry <k, v> node = null; int retries = -1; // หมุนในขณะที่ (! trylock ()) {hashentry <k, v> f; if (retries <0) {// ถ้าโหนดส่วนหัวว่างเปล่าให้สร้างโหนดใหม่ถ้า (e == null) {ถ้า (node == null) {node = new hashentry <k, v> (แฮช, คีย์, ค่า, null); } retries = 0; // มิฉะนั้นสำรวจรายการที่เชื่อมโยงเพื่อค้นหาโหนด} อื่นถ้า (key.equals (e.key)) {retries = 0; } else {e = e.next; } // retries เพิ่ม 1 ที่นี่ทุกครั้งและตรวจสอบว่าเกินค่าสูงสุด} อื่น ๆ ถ้า (++ retries> max_scan_retries) {lock (); หยุดพัก; // เมื่อการลองกลับมาเป็นตัวเลขให้ตรวจสอบว่าครั้งแรกมีการเปลี่ยนแปลง} อื่นถ้า ((retries & 1) == 0 && (f = entryforhash (นี่, แฮช))! = ก่อน) {e = first = f; retries = -1; }} ส่งคืนโหนด;} // สปินรอรับล็อค (ลบและแทนที่การดำเนินการ) โมฆะส่วนตัว scanandlock (คีย์วัตถุ, แฮช int) {// รับโหนดส่วนหัวของรายการที่เชื่อมโยงตามรหัสแฮชแฮช <k, v> first = entryforhash hashentry <k, v> e = ก่อน; int retries = -1; // หมุนในขณะที่ (! trylock ()) {hashentry <k, v> f; if (retries <0) {// โอนรายการที่เชื่อมโยงเพื่อค้นหาโหนดถ้า (e == null || key.equals (e.key)) {retries = 0; } else {e = e.next; } // retries เพิ่ม 1 ที่นี่ทุกครั้งและตรวจสอบว่าเกินค่าสูงสุด} อื่น ๆ ถ้า (++ retries> max_scan_retries) {lock (); หยุดพัก; // เมื่อการลองกลับมาเป็นตัวเลขให้ตรวจสอบว่าครั้งแรกมีการเปลี่ยนแปลง} อื่นถ้า ((retries & 1) == 0 && (f = entryforhash (นี่, แฮช))! = ก่อน) {e = first = f; retries = -1; -ดังที่เราได้กล่าวไว้ก่อนหน้านี้ให้วางลบและแทนที่การดำเนินการในล็อคที่แบ่งเป็นส่วน ๆ จะต้องล็อคที่จะได้รับก่อน หลังจากได้รับการล็อคการดำเนินการครั้งต่อไปสำเร็จแล้ว หากการได้มาล้มเหลวการหมุนจะดำเนินการ การดำเนินการหมุนจะถูกเพิ่มใน JDK1.7 เพื่อหลีกเลี่ยงการระงับและปลุกของเธรดบ่อยครั้งสามารถปรับปรุงประสิทธิภาพในระหว่างการดำเนินการพร้อมกัน scanandlockforput เรียกว่าในวิธีการและ scanandlock เรียกว่าในวิธีการลบและแทนที่ วิธีการหมุนสองวิธีนั้นประมาณเดียวกันที่นี่เราวิเคราะห์วิธี ScanandlockForput เท่านั้น ก่อนอื่นคุณควรได้รับโหนดส่วนหัวของรายการที่เชื่อมโยงตามรหัสแฮช จากนั้นเธรดจะป้อนขณะลูปเพื่อดำเนินการ วิธีเดียวที่จะออกจากลูปคือการรับล็อคสำเร็จและเธรดจะไม่ถูกระงับในช่วงเวลานี้ เมื่อเข้าสู่การวนซ้ำค่าของการลองใหม่คือ -1 ในเวลานี้เธรดจะไม่พยายามรับล็อคทันที แต่จะพบโหนดที่สอดคล้องกับคีย์ก่อน (หากไม่พบจะมีการสร้างใหม่) จากนั้นตั้งค่าการลองใหม่เป็น 0 ถัดไปมันจะพยายามรับการล็อคอีกครั้งและอีกครั้ง ค่า retries ที่สอดคล้องกันจะถูกเพิ่ม 1 ในแต่ละครั้งจนกว่าจำนวนสูงสุดของความพยายามจะเกินจำนวนความพยายามสูงสุด หากยังไม่ได้รับการล็อควิธีการล็อคจะถูกเรียกให้ปิดกั้นและรับ ในระหว่างความพยายามที่จะได้รับการล็อคมันจะตรวจสอบว่าโหนดส่วนหัวมีการเปลี่ยนแปลงทุกครั้ง (ลองอีกครั้ง) หากมีการเปลี่ยนแปลงให้รีเซ็ตการลองกลับไปที่ -1 แล้วทำซ้ำกระบวนการตอนนี้ นี่คือสิ่งที่เธรดทำเมื่อหมุน ควรสังเกตว่าหากตรวจพบโหนดศีรษะที่จะเปลี่ยนแปลงในระหว่างการหมุนเวลาหมุนของเธรดจะถูกขยายออกไป
10. การดำเนินการใดที่ทำเมื่อขยายตารางแฮช?
// แฮชอีกครั้ง @suppresswarnings ("ไม่ได้ตรวจสอบ") โมฆะส่วนตัว rehash (hashentry <k, v> node) {// รับการอ้างอิงไปยังตารางแฮชแฮชแฮชแฮช <k, v> [] oldtable = ตาราง; // รับความสามารถของตารางแฮชเก่า int oldcapacity = oldtable.length; // คำนวณความสามารถของตารางแฮชใหม่ (2 เท่าของตารางแฮชเก่า) int newCapacity = oldCapacity << 1; // คำนวณเกณฑ์เกณฑ์องค์ประกอบใหม่ = (int) (newCapacity * loadfactor); // สร้างอาร์เรย์ Hashentry ใหม่ Hashentry <K, V> [] newTable = (hashentry <k, v> []) ใหม่ hashentry [newcapacity]; // สร้างค่าหน้ากากใหม่ int sizemask = newCapacity - 1; // ความเงียบสงบผ่านองค์ประกอบทั้งหมดของตารางเก่าสำหรับ (int i = 0; i <oldcapacity; i ++) {// รับโหนดส่วนหัวของรายการที่เชื่อมโยงกัน hashentry <k, v> e = oldtable [i]; ถ้า (e! = null) {hashentry <k, v> next = e.next; // คำนวณดัชนีขององค์ประกอบในตารางใหม่ int IDX = e.hash & sizemask; // ถัดไปว่างเปล่าเพื่อระบุว่ามีเพียงหนึ่งโหนดในรายการที่เชื่อมโยงถ้า (ถัดไป == null) {// ใส่โหนดลงในตารางใหม่ใหม่ newTable [idx] = e; } else {hashentry <k, v> lastrun = e; int lastIdx = idx; // วางตำแหน่งโหนด Lastrun และวางโหนดโดยตรงหลังจาก Lastrun ลงในตารางใหม่สำหรับ (hashentry <k, v> last = ถัดไป; สุดท้าย! = null; last = last.next) {int k = last.hash & sizeMask; if (k! = lastIdx) {lastIdx = k; lastrun = สุดท้าย; }} newTable [lastIdx] = lastrun; // การถ่ายโอนองค์ประกอบก่อนที่โหนด Lastrun ของรายการที่เชื่อมโยงคัดลอกลงในตารางใหม่ในการกลับมาสำหรับ (hashentry <k, v> p = e; p! = lastrun; p = p.next) {v v = p.value; int h = p.hash; int k = h & sizemask; hashentry <k, v> n = newtable [k]; newtable [k] = new hashentry <k, v> (h, p.key, v, n); }}}}} // คำนวณตัวห้อยของโหนดขาเข้าในตารางใหม่ int nodeIndex = node.hash & sizemask; // เพิ่มโหนดขาเข้าไปยังโหนดส่วนหัวของรายการที่เชื่อมโยง Node.SetNext (newTable [nodeIndex]); // สลับตารางใหม่ที่ระบุองค์ประกอบตัวห้อยที่ระบุด้วยโหนดขาเข้า newTable [nodeIndex] = node; // ชี้ตารางแฮชอ้างอิงไปยังตารางตารางใหม่ = newTable;}วิธีการ rehash เรียกว่าในวิธีการ เรารู้ว่าเมื่อใส่วิธีการแล้วองค์ประกอบใหม่จะถูกสร้างและเพิ่มลงในอาร์เรย์แฮช ยิ่งความเป็นไปได้ของความขัดแย้งแฮชเกิดขึ้นมากเท่าใดประสิทธิภาพของตารางแฮชก็จะยิ่งลดลงเช่นกัน ดังนั้นทุกครั้งที่การดำเนินการจะตรวจสอบว่าจำนวนองค์ประกอบทั้งหมดเกินเกณฑ์หรือไม่ หากเกินเกณฑ์วิธีการ rehash จะถูกเรียกให้ขยายกำลังการผลิต เนื่องจากความยาวของอาร์เรย์ไม่สามารถเปลี่ยนแปลงได้อีกต่อไปเมื่อมีการกำหนดจึงจำเป็นต้องสร้างอาร์เรย์ใหม่เพื่อแทนที่อาร์เรย์ดั้งเดิม จากรหัสคุณสามารถรู้ได้ว่าอาร์เรย์ที่สร้างขึ้นใหม่นั้นมีความยาวสองเท่าของอาร์เรย์ดั้งเดิม (OldCapacity << 1) After creating a new array, you need to move all elements in the old array into the new array, so you need to calculate the subscript of each element in the new array. The process of calculating the new subscript is shown in the figure below.
我们知道下标直接取的是哈希码的后几位，由于新数组的容量是直接用旧数组容量右移1位得来的，因此掩码位数向右增加1位，取到的哈希码位数也向右增加1位。如上图，若旧的掩码值为111，则元素下标为101，扩容后新的掩码值为1111，则计算出元素的新下标为0101。由于同一条链表上的元素下标是相同的，现在假设链表所有元素的下标为101，在扩容后该链表元素的新下标只有0101或1101这两种情况，因此数组扩容会打乱原先的链表并将链表元素分成两批。在计算出新下标后需要将元素移动到新数组中，在HashMap中通过直接修改next引用导致了多线程的死锁。虽然在ConcurrentHashMap中通过加锁避免了这种情况，但是我们知道next域是volatile类型的，它的改动能立马被读线程读取到，因此为保证线程安全采用复制元素来迁移数组。但是对链表中每个元素都进行复制有点影响性能，作者发现链表尾部有许多元素的next是不变的，它们在新数组中的下标是相同的，因此可以考虑整体移动这部分元素。具统计实际操作中只有1/6的元素是必须复制的，所以整体移动链表尾部元素(lastRun后面的元素)是可以提升一定性能的。
注：本篇文章基于JDK1.7版本。
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น