เมื่อใช้ HashMap ในสภาพแวดล้อมแบบมัลติเธรด Java ส่วนใหญ่จะมีตัวเลือกต่อไปนี้: ใช้ java.util.Hashtable แบบเธรดที่ปลอดภัยเป็นทางเลือก ใช้เมธอด java.util.Collections.synchronizedMap เพื่อล้อมอ็อบเจ็กต์ HashMap ที่มีอยู่เป็นเธรด -ปลอดภัย. ใช้คลาส java.util.concurrent.ConcurrentHashMap เป็นทางเลือก ซึ่งมีประสิทธิภาพที่ดีมาก
วิธีการข้างต้นทั้งหมดใช้การล็อค mutex ไม่มากก็น้อยในรายละเอียดเฉพาะของการนำไปใช้งาน การล็อค Mutex จะทำให้เกิดการบล็อกเธรด ลดประสิทธิภาพการทำงาน และอาจทำให้เกิดปัญหาต่างๆ เช่น การหยุดชะงักและการพลิกลำดับความสำคัญ
CAS (เปรียบเทียบและสลับ) เป็นฟังก์ชันที่มาจากฮาร์ดแวร์พื้นฐาน ซึ่งสามารถทำให้การดำเนินการตัดสินและการเปลี่ยนแปลงค่าเป็นแบบอะตอมมิก
การดำเนินการของอะตอมใน Java
ในแพ็คเกจ java.util.concurrent.atomic นั้น Java ได้จัดเตรียมอะตอมมิกประเภทต่างๆ ที่สะดวกสบายให้เรา ซึ่งทั้งหมดขึ้นอยู่กับการทำงานของ CAS
ตัวอย่างเช่น หากเราต้องการใช้ตัวนับสาธารณะทั่วโลก เราสามารถ:
คัดลอกรหัสรหัสดังต่อไปนี้:
ตัวนับ privateAtomicInteger = newAtomicInteger (3);
publicvoidaddCounter() {
สำหรับ(;;) {
intoldValue = counter.get();
intnewValue = ค่าเก่า +1;
ถ้า (counter.compareAndSet (oldValue, newValue))
กลับ;
-
-
ในหมู่พวกเขา วิธีการเปรียบเทียบ AndSet จะตรวจสอบว่าค่าที่มีอยู่ของตัวนับเป็น oldValue หรือไม่ หากเป็นเช่นนั้น การดำเนินการจะสำเร็จและส่งกลับค่าจริง
เมื่อคำนวณค่าใหม่ของตัวนับ หากเธรดอื่นเปลี่ยนค่าของตัวนับ การเปรียบเทียบ AndSwap จะล้มเหลว ณ จุดนี้ เราเพียงแต่ต้องเพิ่มเลเยอร์ของการวนซ้ำภายนอกและลองกระบวนการนี้ต่อไป จากนั้นเราจะเพิ่มค่าตัวนับได้สำเร็จ 1 ในที่สุด (อันที่จริง AtomicInteger ได้กำหนดเมธอด increationAndGet และ decreationAndGet ไว้แล้วสำหรับการดำเนินการ +1/-1 ที่ใช้กันทั่วไป เราเพียงแต่เรียกพวกมันง่ายๆ ในอนาคตเท่านั้น)
นอกจาก AtomicInteger แล้ว แพ็กเกจ java.util.concurrent.atomic ยังมีประเภท AtomicReference และ AtomicReferenceArray ซึ่งแสดงถึงการอ้างอิงอะตอมมิกและอาร์เรย์อ้างอิงอะตอมมิก (อาร์เรย์ของการอ้างอิง) ตามลำดับ
การดำเนินการตามรายการเชื่อมโยงที่ไม่มีการล็อค
ก่อนที่จะใช้ HashMap ที่ไม่มีการล็อค ให้เราดูวิธีการใช้งานที่ค่อนข้างง่ายของรายการลิงค์ที่ไม่มีการล็อคก่อน
ใช้การดำเนินการแทรกเป็นตัวอย่าง:
ก่อนอื่น เราต้องค้นหาโหนด A ด้านหน้าตำแหน่งที่จะแทรกและโหนด B ด้านหลัง
จากนั้นสร้างโหนด C ใหม่และทำให้ตัวชี้ถัดไปชี้ไปที่โหนด B (ดูรูปที่ 1)
สุดท้ายให้ตัวชี้ถัดไปของโหนด A ชี้ไปที่โหนด C (ดูรูปที่ 2)
อย่างไรก็ตาม ในระหว่างการดำเนินการ มีความเป็นไปได้ที่เธรดอื่นแทรกโหนดบางส่วนใน A และ B โดยตรง (ซึ่งถือว่าเป็น D) หากเราไม่ตัดสินใดๆ อาจทำให้สูญเสียโหนดที่แทรกโดยเธรดอื่น (ดูรูปที่ 3) เราสามารถใช้การดำเนินการ CAS เพื่อตรวจสอบว่าตัวชี้ถัดไปของโหนด A ยังคงชี้ไปที่ B เมื่อกำหนดค่าหรือไม่ หากตัวชี้ถัดไปของโหนด A เปลี่ยนแปลง ให้ลองดำเนินการแทรกทั้งหมดอีกครั้ง รหัสโดยประมาณมีดังนี้:
คัดลอกรหัสรหัสดังต่อไปนี้:
privatevoidlistInsert (ส่วนหัวของโหนด, โหนด c) {
สำหรับ(;;) {
โหนด a = findInsertionPlace (หัว), b = a.next.get ();
c.next.set(ข);
ถ้า(a.next.compareAndSwap(b,c))
กลับ;
-
-
(ฟิลด์ถัดไปของคลาส Node เป็นประเภท AtomicReference<Node> ซึ่งเป็นการอ้างอิงอะตอมมิกที่ชี้ไปที่ประเภท Node)
การดำเนินการค้นหารายการลิงก์ที่ไม่มีการล็อคไม่แตกต่างจากรายการลิงก์ทั่วไป การดำเนินการลบจำเป็นต้องค้นหาโหนด A ที่ด้านหน้าของโหนดที่จะลบและโหนด B ที่อยู่ด้านหลัง และใช้การดำเนินการ CAS เพื่อตรวจสอบและอัปเดตตัวชี้ถัดไปของโหนด A เพื่อให้ชี้ไปที่โหนด B
ความยากและความก้าวหน้าของ HashMap ที่ไม่มีการล็อค
HashMap มีการดำเนินการพื้นฐานสี่ประการ ได้แก่ การแทรก การลบ การค้นหา และ ReHash การใช้งาน HashMap โดยทั่วไปจะใช้อาร์เรย์ และแต่ละองค์ประกอบของอาร์เรย์จะเป็นรายการโหนดที่เชื่อมโยงกัน สำหรับรายการที่เชื่อมโยงนี้ เราสามารถใช้วิธีดำเนินการที่กล่าวถึงข้างต้นเพื่อดำเนินการแทรก การลบ และการค้นหา แต่การดำเนินการ ReHash นั้นยากกว่า
ดังที่แสดงในรูปที่ 4 ในระหว่างกระบวนการ ReHash การดำเนินการทั่วไปคือการสำรวจแต่ละโหนดในตารางเก่า คำนวณตำแหน่งในตารางใหม่ จากนั้นย้ายไปยังตารางใหม่ ในช่วงเวลานี้ เราจำเป็นต้องจัดการตัวชี้สามครั้ง:
ตัวชี้ถัดไปของจุด A ไปยัง D
ตัวชี้ถัดไปของจุด B ไปยัง C
ตัวชี้ถัดไปของจุด C ไปยัง E
การดำเนินการของตัวชี้ทั้งสามนี้จะต้องเสร็จสิ้นในเวลาเดียวกันเพื่อให้แน่ใจว่าการดำเนินการย้ายเป็นแบบอะตอมมิก แต่ก็ไม่ใช่เรื่องยากที่จะเห็นว่าการดำเนินการ CAS สามารถรับประกันได้ว่าค่าของตัวแปรหนึ่งตัวจะได้รับการตรวจสอบและอัปเดตแบบอะตอมมิกในแต่ละครั้ง และไม่สามารถตอบสนองความต้องการในการตรวจสอบและอัปเดตตัวชี้สามตัวพร้อมกันได้
ดังนั้นเราอาจเปลี่ยนความคิดของเราได้เช่นกัน เนื่องจากการดำเนินการของการย้ายโหนดนั้นยากมาก เราจึงสามารถรักษาโหนดทั้งหมดให้อยู่ในสถานะที่ได้รับคำสั่งตลอดเวลา จึงหลีกเลี่ยงการดำเนินการย้าย ในการใช้งาน HashMap โดยทั่วไป ความยาวของอาเรย์จะเป็น 2i เสมอ และกระบวนการแมปค่าแฮชกับตัวห้อยอาเรย์จะทำการดำเนินการแบบโมดูโลกับความยาวของอาเรย์ (นั่นคือ เฉพาะ i บิตสุดท้ายของไบนารี Hash เท่านั้นที่ เก็บไว้) เมื่อ ReHash ความยาวของอาเรย์จะเพิ่มเป็นสองเท่าเป็น 2i+1 และแต่ละโหนดในรายการสร้อยคอ j-th ของอาเรย์เก่าจะถูกย้ายไปยังรายการ j-th ในอาเรย์ใหม่ หรือย้ายไปที่ j+2i-th รายการในอาร์เรย์ใหม่และความแตกต่างเพียงอย่างเดียวอยู่ที่บิต i+1 ของค่าแฮช (หากบิต i+1 เป็น 0 ก็ยังคงเป็นรายการ jth มิฉะนั้นจะเป็นรายการ j+2th)
ดังแสดงในรูปที่ 5 เราจัดเรียงโหนดทั้งหมดจากน้อยไปมากตามลำดับกลับหัวของค่าแฮช (เช่น 1101->1011) เมื่อขนาดอาเรย์คือ 8, 2 และ 18 อยู่ในกลุ่มเดียว 3, 11 และ 27 อยู่ในอีกกลุ่มหนึ่ง ที่จุดเริ่มต้นของแต่ละกลุ่ม จะมีการแทรกโหนดแมวมองเพื่ออำนวยความสะดวกในการปฏิบัติงานในภายหลัง เพื่อที่จะจัดเรียงโหนดแมวมองที่ด้านหน้าของกลุ่มอย่างถูกต้อง เราได้ตั้งค่าบิตสูงสุดของโหนดปกติ Hash (ซึ่งจะกลายเป็นบิตต่ำสุดหลังจากการพลิก) เป็น 1 ในขณะที่โหนดแมวมองไม่ได้ตั้งค่าบิตนี้
เมื่ออาร์เรย์ถูกขยายเป็น 16 (ดูรูปที่ 6) กลุ่มที่สองจะถูกแบ่งออกเป็นกลุ่มที่มีเพียง 3 และกลุ่มที่มี 11 และ 27 แต่ลำดับสัมพัทธ์ระหว่างโหนดไม่มีการเปลี่ยนแปลง ด้วยวิธีนี้ เราไม่จำเป็นต้องย้ายโหนดระหว่าง ReHash
รายละเอียดการดำเนินการ
เนื่องจากการคัดลอกอาเรย์ใช้เวลานานมากในระหว่างการขยาย เราจึงนำวิธีการแบ่งอาเรย์ทั้งหมดออกเป็นบล็อกและสร้างขึ้นอย่างเกียจคร้าน ด้วยวิธีนี้ เมื่อมีการเข้าถึงตัวห้อยบางตัว จะต้องตัดสินเพียงว่ามีการสร้างบล็อกที่ตัวห้อยอยู่หรือไม่ (หากไม่ใช่ ให้สร้างมันขึ้นมา)
นอกจากนี้ ขนาดถูกกำหนดเป็นช่วงตัวห้อยที่ใช้อยู่ในปัจจุบัน และค่าเริ่มต้นคือ 2 เมื่อขยายอาร์เรย์ ขนาดจะต้องเพิ่มเป็นสองเท่าเท่านั้น จำนวนจะถูกกำหนดเพื่อแสดงจำนวนโหนดทั้งหมดที่มีอยู่ใน HashMap ( ไม่นับโหนดแมวมอง)
เริ่มแรก รายการทั้งหมดในอาร์เรย์ยกเว้นรายการที่ 0 จะเป็นโมฆะ รายการ 0 ชี้ไปยังรายการที่เชื่อมโยงซึ่งมีโหนดแมวมองเพียงโหนดเดียว ซึ่งแสดงถึงจุดเริ่มต้นของห่วงโซ่ทั้งหมด รูปภาพเต็มเริ่มต้นจะแสดงในรูปที่ 7 ซึ่งสีเขียวอ่อนแสดงถึงช่วงตัวห้อยที่ไม่ได้ใช้ในปัจจุบัน และลูกศรประแสดงถึงบล็อกที่มีอยู่ตามตรรกะ แต่ไม่ได้ถูกสร้างขึ้นจริง
เริ่มต้นการดำเนินการตัวห้อย
รายการ Null ในอาร์เรย์จะถือว่าอยู่ในสถานะที่ไม่ได้เตรียมใช้งาน การเริ่มต้นตัวห้อยบางตัวหมายถึงการสร้างโหนด Sentinel ที่สอดคล้องกัน การกำหนดค่าเริ่มต้นจะดำเนินการแบบวนซ้ำ นั่นคือ หากตัวห้อยพาเรนต์ไม่ได้เตรียมใช้งาน ตัวห้อยพาเรนต์จะถูกเตรียมใช้งานก่อน (ตัวห้อยพาเรนต์ของตัวห้อยคือตัวห้อยที่ได้รับโดยการเอาบิตไบนารีสูงสุดออก) รหัสโดยประมาณจะเป็นดังนี้:
คัดลอกรหัสรหัสดังต่อไปนี้:
ส่วนตัวโมฆะเริ่มต้นถัง (intbucketIdx) {
intparentIdx = bucketIdx ^ จำนวนเต็ม.highestOneBit(bucketIdx);
ถ้า(getBucket(parentIdx) ==null)
InitializeBucket (parentIdx);
โหนดจำลอง = newNode ();
dummy.hash = จำนวนเต็มย้อนกลับ (bucketIdx);
dummy.next = newAtomicReference<>();
setBucket(bucketIdx, listInsert(getBucket(parentIdx), จำลอง));
-
ในบรรดาวิธีเหล่านั้น getBucket เป็นวิธีการแบบห่อหุ้มเพื่อรับเนื้อหาของตัวห้อยบางตัวในอาร์เรย์ และ setBucket ก็เหมือนกัน listInsert จะแทรกโหนดที่กำหนดไปยังตำแหน่งที่เหมาะสมโดยเริ่มจากตำแหน่งที่ระบุ หากมีโหนดที่มีแฮชเดียวกันอยู่แล้วในรายการที่เชื่อมโยง มันจะส่งคืนโหนดที่มีอยู่ มิฉะนั้น มันจะส่งคืนโหนดที่แทรกใหม่
การดำเนินการแทรก
ขั้นแรก ใช้ขนาดของ HashMap เพื่อปรับ hashCode ของคีย์เพื่อรับตัวห้อยอาร์เรย์ที่ควรแทรก
จากนั้นตรวจสอบว่าตัวห้อยเป็นโมฆะหรือไม่ และหากเป็นโมฆะ ให้เตรียมใช้งานตัวห้อย
สร้างโหนดใหม่และแทรกลงในตำแหน่งที่เหมาะสม โปรดทราบว่าค่าแฮชในโหนดควรเป็นค่าของ hashCode ดั้งเดิมหลังจากพลิกบิตและตั้งค่าตำแหน่งต่ำสุดเป็น 1
เพิ่ม 1 ลงในตัวนับหมายเลขโหนด หากมีโหนดมากเกินไปหลังจากเพิ่ม 1 คุณจะต้องเปลี่ยนขนาดเป็นขนาด*2 ซึ่งหมายถึงการขยายอาร์เรย์ (ReHash)
ค้นหาการดำเนินการ
ค้นหาดัชนีของโหนดที่จะพบในอาร์เรย์
ตรวจสอบว่าตัวห้อยเป็นโมฆะหรือไม่ หากเป็นโมฆะ การค้นหาที่ล้มเหลวจะถูกส่งกลับ
ป้อนรายการที่เชื่อมโยงจากตำแหน่งที่เกี่ยวข้องและค้นหาตามลำดับจนกว่าจะพบโหนดที่จะพบหรือเกินช่วงของกลุ่มโหนดนี้
ลบการดำเนินการ
ค้นหาดัชนีของโหนดในอาร์เรย์ที่ควรลบ
ตรวจสอบว่าตัวห้อยเป็นโมฆะหรือไม่ และถ้าเป็นโมฆะ ให้เตรียมใช้งานตัวห้อย
ค้นหาโหนดที่จะลบและลบออกจากรายการที่เชื่อมโยง (โปรดทราบว่าเนื่องจากการมีอยู่ของโหนด Sentinel องค์ประกอบปกติใดๆ จะถูกอ้างอิงโดยโหนดก่อนหน้าเท่านั้น ไม่มีสถานการณ์ที่จะถูกอ้างอิงโดยโหนดก่อนหน้าและตัวชี้ในอาเรย์ในเวลาเดียวกัน ดังนั้นจึงมี ไม่จำเป็นต้องแก้ไขพอยน์เตอร์หลายตัวพร้อมกัน)
ลดตัวนับหมายเลขโหนดลง 1