ทำเครื่องหมายและในเวลาเดียวกันคุณสามารถรวม HashCode () และวิธีการเท่ากับ () ได้ดีที่สุด HashCode () ไม่เท่ากันมันจะต้องแตกต่างกันเพื่อให้สามารถอนุมานได้เท่ากับ ();
เพราะเมื่อ hashmap ได้รับก่อนที่จะเปรียบเทียบ hashcode ก่อนจากนั้นเปรียบเทียบเท่ากับ hashcode == && equals ทั้งสองเป็นจริงดังนั้นจึงถือว่าเป็นคีย์เดียวกัน
1. ภาพรวม HASHMAP:
HashMap เป็นการใช้งานแบบอะซิงโครนัสของอินเทอร์เฟซแผนที่ตามตารางแฮช การใช้งานนี้ให้การดำเนินการแมปแบบเลือกทั้งหมดและอนุญาตให้ใช้ค่า NULL และปุ่ม NULL คลาสนี้ไม่รับประกันคำสั่งของการแมปโดยเฉพาะอย่างยิ่งไม่รับประกันว่าคำสั่งซื้อจะคงอยู่
2. โครงสร้างข้อมูลของ HashMap:
ในภาษาการเขียนโปรแกรม Java มีสองโครงสร้างพื้นฐานหนึ่งคืออาร์เรย์และอีกโครงสร้างหนึ่งคือตัวชี้จำลอง (อ้างอิง) HashMap เป็นโครงสร้างข้อมูล "รายการที่เชื่อมโยง" นั่นคือการรวมกันของอาร์เรย์และรายการที่เชื่อมโยง
ดังที่เห็นได้จากรูปด้านบนชั้นพื้นฐานของ HashMap เป็นโครงสร้างอาร์เรย์และแต่ละรายการในอาร์เรย์เป็นรายการที่เชื่อมโยงอีกรายการหนึ่ง เมื่อสร้าง HashMap ใหม่อาร์เรย์จะเริ่มต้น
ซอร์สโค้ดมีดังนี้:
/ ** * ตารางที่ปรับขนาดได้ตามความจำเป็น ค่า V;
จะเห็นได้ว่ารายการเป็นองค์ประกอบในอาร์เรย์
3. การใช้งาน HashMap Access:
1) ที่เก็บ:
Public V Put (k key, v value) {// hashmap อนุญาตให้คีย์ว่างและค่า NULL // เมื่อคีย์เป็น NULL ให้เรียกใช้วิธี PutforNullkey และวางค่าที่ตำแหน่งแรกของอาร์เรย์ ถ้า (key == null) return putfornullkey (ค่า); int hash = hash (key.hashcode ()); // ค้นหาดัชนีของค่าแฮชที่ระบุในตารางที่เกี่ยวข้อง int i = indexfor (แฮช, table.length); สำหรับ (รายการ <k, v> e = ตาราง [i]; e! = null; e = e.next) {วัตถุ k; || key.equals (k)) {v oldValue = e.value; ว่านี่ยังไม่มีรายการ Modcount ++; // เพิ่มคีย์และค่าลงในดัชนี I Addentry (แฮช, คีย์, ค่า, i); จากซอร์สโค้ดด้านบนเราจะเห็นว่าเมื่อเราใส่องค์ประกอบใน HASHMAP ก่อนอื่นเราคำนวณค่าแฮชใหม่ตามแฮชโฟตอนของคีย์และตามค่าแฮชตำแหน่งขององค์ประกอบนี้ในอาร์เรย์ (เช่นตัวห้อย ) หากอาร์เรย์มีองค์ประกอบอื่น ๆ ที่เก็บไว้อยู่ที่ตำแหน่งดังนั้นองค์ประกอบที่ตำแหน่งนี้จะถูกเก็บไว้ในรูปแบบของรายการที่เชื่อมโยง คนจะถูกวางไว้ที่ส่วนท้ายของโซ่ หากไม่มีองค์ประกอบที่ตำแหน่งนี้ในอาร์เรย์ให้วางองค์ประกอบโดยตรงที่ตำแหน่งนี้ในอาร์เรย์
Addentry (แฮช, คีย์, ค่า, i) วิธีการวางคู่คีย์-ค่าที่ดัชนี I ของตารางอาร์เรย์ตามค่าแฮชที่คำนวณได้ Addentry เป็นวิธีการอนุญาตการเข้าถึงแพ็คเกจที่จัดทำโดย HashMap รหัสมีดังนี้:
เป็นโมฆะ addentry (int hash, k, ค่า V, int bucketindex) {// รับรายการที่รายการดัชนี BucketIndex ที่ระบุ <k, v> e = ตาราง [Bucketindex]; ดัชนีและปล่อยให้จุดเริ่มต้นใหม่ไปยังตารางรายการดั้งเดิม [BucketIndex] = รายการใหม่ <k, v> (แฮช, คีย์, ค่า, e); (ขนาด ++> = เกณฑ์) // ขยายความยาวของวัตถุตารางเป็นสองเท่าของต้นฉบับ ปรับขนาด (2 * table.length); เมื่อระบบตัดสินใจที่จะจัดเก็บคู่คีย์-ค่าใน HashMap ค่าในรายการจะไม่ถูกพิจารณาเลยและมันก็คำนวณและกำหนดตำแหน่งที่เก็บข้อมูลของแต่ละรายการตามคีย์ เราสามารถรักษาค่าในการรวบรวมแผนที่เป็นไฟล์แนบไปยังคีย์ได้อย่างสมบูรณ์
วิธีแฮช (int h) คำนวณแฮชครั้งเดียวอีกครั้งตามแฮชโฟนของคีย์ อัลกอริทึมนี้เพิ่มการคำนวณบิตสูงเพื่อป้องกันความขัดแย้งแฮชที่เกิดขึ้นเมื่อบิตต่ำยังคงไม่เปลี่ยนแปลงและเมื่อการเปลี่ยนแปลงบิตสูง
hash int คงที่ (int h) {h ^ = (h >>> 20) ^ (h >>> 12); เราจะเห็นได้ว่าเพื่อค้นหาองค์ประกอบใน HashMap เราจำเป็นต้องค้นหาตำแหน่งที่สอดคล้องกันในอาร์เรย์ตามค่าแฮชของคีย์ วิธีการคำนวณตำแหน่งนี้คืออัลกอริทึมแฮช ดังที่ได้กล่าวไว้ก่อนหน้านี้โครงสร้างข้อมูลของ HashMap เป็นการรวมกันของอาร์เรย์และรายการที่เชื่อมโยงดังนั้นแน่นอนว่าเราหวังว่าตำแหน่งองค์ประกอบใน HashMap นี้ควรจะกระจายอย่างสม่ำเสมอที่สุดเท่าที่จะทำได้เพื่อให้จำนวนองค์ประกอบในแต่ละตำแหน่งเป็นเพียง หนึ่ง ประสิทธิภาพของการสืบค้น
สำหรับวัตถุใด ๆ ที่กำหนดตราบใดที่ค่าคืน HashCode () นั้นเท่ากันค่ารหัสแฮชที่คำนวณโดยโปรแกรมที่เรียกวิธีแฮช (int h) จะเหมือนกันเสมอ สิ่งแรกที่เราคิดว่าคือโมดูโลค่าแฮชกับความยาวอาร์เรย์เพื่อให้การกระจายขององค์ประกอบค่อนข้างสม่ำเสมอ อย่างไรก็ตามการดำเนินการ "modulo" ใช้มากและสิ่งนี้ทำใน HashMap: เรียกใช้วิธี indexfor (int h, ความยาว int) เพื่อคำนวณดัชนีใดที่ควรเก็บไว้ในอาร์เรย์ตาราง
รหัสของ indexfor (int h, ความยาว int) มีดังนี้:
INTATION Static (int H, ความยาว int) {return h & (length-1);วิธีนี้ฉลาดมาก เงื่อนไขของความเร็ว ในตัวสร้าง HashMap มีรหัสต่อไปนี้:
ความจุ int = 1;
รหัสนี้ทำให้มั่นใจได้ว่าความสามารถของ HashMap อยู่ที่พลัง N เสมอในระหว่างการเริ่มต้นนั่นคือความยาวของอาร์เรย์พื้นฐานอยู่ที่พลัง N เสมอ
เมื่อความยาวอยู่เสมอถึงพลัง N ของ 2 การดำเนินการ H & (ความยาว -1) จะเทียบเท่ากับความยาวโมดูโลนั่นคือความยาว h %แต่ & มีประสิทธิภาพสูงกว่า %
มันดูง่ายมาก แต่จริงๆแล้วมันค่อนข้างลึกลับ
สมมติว่าความยาวอาร์เรย์คือ 15 และ 16 และรหัสแฮชที่ได้รับการปรับปรุงคือ 8 และ 9 ตามลำดับจากนั้นผลลัพธ์หลังจาก & การดำเนินการมีดังนี้:
H & (table.length-1) Hash.length-1
8 & (15-1): 0100 & 1110 = 0100
9 & (15-1): 0101 & 1110 = 0100
------------------------------------------------------ ------------------------------------------------------ ------------------------ ---------------------------------------------------------------------------------------------------------------- ------------------------------------------------------ ------------------------------------------------------ ------ ---------------------------------------------------------------------------------------------------------------------------------------------------- ------------------------------------------------------ ------------------------------------------------------ ------------------------------------------------------ ------------------------------------------------------ ------------
8 & (16-1): 0100 & 1111 = 0100
9 & (16-1): 0101 & 1111 = 0101
ดังที่เห็นได้จากตัวอย่างข้างต้น: เมื่อพวกเขา "เป็น" กับ 15-1 (1110) ผลลัพธ์เดียวกันนั้นคือการผลิตนั่นคือพวกเขาจะอยู่ในตำแหน่งเดียวกันในอาร์เรย์ซึ่งสร้างการชนกัน 8 และ 9 จะถูกวางไว้ที่ตำแหน่งเดียวกันในอาร์เรย์เพื่อสร้างรายการที่เชื่อมโยง ในเวลาเดียวกันเรายังสามารถพบว่าเมื่อความยาวอาร์เรย์คือ 15 ค่าแฮชจะเป็น "เป็น" ด้วย 15-1 (1110) จากนั้นบิตสุดท้ายจะเป็น 0 และ 0001, 0011, 0101, 1001 , 1011, 0111, 0111, 1101 ไม่สามารถเก็บองค์ประกอบและพื้นที่นั้นสูญเปล่าไปมาก โอกาสในการชนเพิ่มขึ้นและประสิทธิภาพการสืบค้นช้า! เมื่อความยาวของอาร์เรย์คือ 16 นั่นคือเมื่อเป็นกำลัง n ของ 2 ค่าของแต่ละบิตของหมายเลขไบนารีที่ได้รับจาก 2N-1 คือ 1 ซึ่งทำให้บิตต่ำของผลรวมของแฮชดั้งเดิมเมื่อ มันคือ & ในบิตต่ำเพื่อให้บิตต่ำของแฮชผลรวมที่ได้รับเท่ากัน, ควบคู่ไปกับวิธีแฮช (int h) เพิ่มประสิทธิภาพ hashcode ของคีย์ต่อไปและเพิ่มการคำนวณบิตสูงเพื่อให้มีเพียงสองค่าเท่านั้น ของค่าแฮชเดียวกันจะถูกวางไว้ที่ตำแหน่งเดียวกันในอาร์เรย์เพื่อสร้างรายการที่เชื่อมโยง
ดังนั้นเมื่อความยาวของอาร์เรย์คือ N Powers เป็น 2 ความน่าจะเป็นที่ปุ่มที่แตกต่างกันสามารถคำนวณดัชนีเดียวกันนั้นมีขนาดเล็กลงดังนั้นข้อมูลจะถูกกระจายอย่างสม่ำเสมอในอาร์เรย์ซึ่งหมายความว่าความน่าจะเป็นของการชนมีขนาดเล็ก เวลานี้คุณไม่จำเป็นต้องสำรวจรายการที่เชื่อมโยงในสถานที่ที่แน่นอนดังนั้นประสิทธิภาพการสืบค้นจะสูงขึ้น
ตามซอร์สโค้ดของวิธีการที่วางไว้ข้างต้นเมื่อโปรแกรมพยายามที่จะใส่คู่คีย์-ค่าลงใน HashMap โปรแกรมแรกจะกำหนดตำแหน่งที่เก็บข้อมูลของรายการตามค่าคืน hashCode () ของคีย์: หากไฟล์ คีย์ของสองรายการค่าคืน HashCode () จะเหมือนกันและตำแหน่งที่เก็บข้อมูลของพวกเขาเหมือนกัน หากคีย์ของสองรายการกลับมาจริงผ่านการเปรียบเทียบเท่ากับค่าของรายการที่เพิ่มใหม่จะแทนที่ค่าของรายการต้นฉบับในคอลเลกชัน แต่คีย์จะไม่แทนที่ หากคีย์ของรายการสองรายการส่งคืน FALSE ผ่านการเปรียบเทียบเท่ากับรายการที่เพิ่มขึ้นใหม่จะเป็นห่วงโซ่รายการพร้อมรายการต้นฉบับในคอลเลกชันและรายการที่เพิ่มขึ้นใหม่จะอยู่ที่หัวของห่วงโซ่รายการ - รายละเอียดจะยังคงดูต่อไป คำอธิบายของวิธี Addentry ()
2) อ่าน:
Public V รับ (คีย์วัตถุ) {ถ้า (key == null) return getfornullkey (); . ส่งคืน e.value; ด้วยอัลกอริทึมแฮชที่เก็บไว้ด้านบนเป็นพื้นฐานมันเป็นเรื่องง่ายที่จะเข้าใจรหัสนี้ จากซอร์สโค้ดด้านบนเราจะเห็นว่าเมื่อได้รับองค์ประกอบใน HASHMAP ก่อนอื่นคำนวณ HashCode ของคีย์ค้นหาองค์ประกอบที่ตำแหน่งที่สอดคล้องกันในอาร์เรย์จากนั้นค้นหาองค์ประกอบที่ต้องการในรายการที่เชื่อมโยงของตำแหน่งที่เกี่ยวข้อง ผ่านวิธีการเท่ากับคีย์
3) เพื่อสรุป HashMap จะประมวลผลค่าคีย์โดยรวมที่ด้านล่างและทั้งหมดนี้เป็นวัตถุรายการ HashMap พื้นฐานใช้รายการ [] อาร์เรย์เพื่อจัดเก็บคู่คีย์-ค่าทั้งหมด วิธีการที่เท่าเทียมกัน
4. Resize ของ Hashmap (Rehash):
เนื่องจากมีองค์ประกอบมากขึ้นเรื่อย ๆ ใน HashMap โอกาสของความขัดแย้งแฮชจะสูงขึ้นเรื่อย ๆ เนื่องจากความยาวของอาร์เรย์ได้รับการแก้ไข ดังนั้นเพื่อปรับปรุงประสิทธิภาพของการสืบค้นอาร์เรย์ของ HashMap จะต้องขยายออกไป ปรากฏขึ้น: ข้อมูลในอาร์เรย์ดั้งเดิมจะต้องคำนวณใหม่และวางไว้ในอาร์เรย์ใหม่ซึ่งปรับขนาด
ดังนั้น HashMap จะขยายเมื่อไหร่? เมื่อจำนวนองค์ประกอบใน HashMap เกินขนาดอาร์เรย์ *loadfactor อาร์เรย์จะถูกขยาย โดยค่าเริ่มต้นขนาดอาร์เรย์คือ 16 จากนั้นเมื่อจำนวนองค์ประกอบใน HashMap เกิน 16*0.75 = 12 ขนาดของอาร์เรย์จะขยายเป็น 2*16 = 32 นั่นคือขนาดสองเท่า จากนั้นคำนวณใหม่ .
5. พารามิเตอร์ประสิทธิภาพ HASHMAP:
HashMap มีตัวสร้างต่อไปนี้:
HashMap (): สร้าง hashmap ด้วยความจุเริ่มต้นที่ 16 และปัจจัยโหลด 0.75
HASHMAP (int initialCapacity): สร้าง HASHMAP ที่มีความจุเริ่มต้นและปัจจัยโหลด 0.75
hashmap (int initialcapacity, float loadfactor): สร้าง hashmap ด้วยความจุเริ่มต้นที่ระบุและปัจจัยโหลดที่ระบุ
ตัวสร้างพื้นฐานของ HashMap, HASHMAP (Int InitialCapacity, Float LoadFactor) มีพารามิเตอร์สองตัวพวกเขาคือความจุเริ่มต้นความจุเริ่มต้นและตัวโหลดปัจจัยโหลด
การเริ่มต้น: ความจุสูงสุดของ HashMap นั่นคือความยาวของอาร์เรย์พื้นฐาน
LoadFactor: ตัวโหลดปัจจัยโหลดถูกกำหนดเป็น: จำนวนองค์ประกอบจริงของตารางแฮช (n)/ความจุของตารางแฮช (M)
ปัจจัยโหลดวัดระดับการใช้งานของตารางแฮช สำหรับตารางแฮชที่ใช้วิธีการที่เชื่อมโยงกันเวลาเฉลี่ยในการค้นหาองค์ประกอบคือ O (1+A) ปัจจัยโหลดนั้นเกินไปถ้ามีขนาดเล็กข้อมูลของตารางแฮชจะกระจัดกระจายเกินไปทำให้เกิดการเสียพื้นที่อย่างรุนแรง
ในการดำเนินการของ HASHMAP ความสามารถสูงสุดของ HASHMAP จะถูกกำหนดโดยฟิลด์ธรณีประตู:
การคัดลอกรหัสมีดังนี้:
threshold = (int) (ความจุ * loadfactor);
ขึ้นอยู่กับสูตรคำจำกัดความของปัจจัยการโหลดจะเห็นได้ว่าเกณฑ์คือจำนวนองค์ประกอบสูงสุดที่อนุญาตตามตัวโหลดและความจุ ปัจจัยโหลดเริ่มต้น 0.75 เป็นตัวเลือกที่สมดุลสำหรับประสิทธิภาพเชิงพื้นที่และเชิงเวลา เมื่อความจุสูงกว่ากำลังการผลิตสูงสุดนี้ความจุ HASHMAP ที่ปรับขนาดจะเพิ่มขึ้นเป็นสองเท่าของความจุ:
if (size ++> = threshold) ปรับขนาด (2 * table.length);
6. กลไกที่ล้มเหลวอย่างรวดเร็ว:
เรารู้ว่า java.util.hashmap ไม่ปลอดภัยกับเธรดดังนั้นหากเธรดอื่น ๆ แก้ไขแผนที่ในระหว่างกระบวนการใช้ตัววนซ้ำจะมีการโยนตัววนซ้ำมาพร้อมกันซึ่งเป็นกลยุทธ์ที่ล้มเหลวอย่างรวดเร็ว
กลยุทธ์นี้ถูกนำไปใช้ในฟิลด์ Modcount Iterator's คาดหวัง
Hashiterator () {คาดว่าจะมี modcount; ; ในระหว่างกระบวนการวนซ้ำให้ตรวจสอบว่า Modcount และที่คาดหวังว่าจะมีค่าเท่ากันหรือไม่
โปรดทราบว่า Modcount นั้นถูกประกาศว่ามีความผันผวนเพื่อให้แน่ใจว่าการมองเห็นการปรับเปลี่ยนระหว่างเธรด
รายการสุดท้าย <k, v> nextEntry () {ถ้า (modcount! = คาดหวัง modcount) โยนใหม่พร้อมกันใหม่ Exception (); ใน API ของ HashMap มีการระบุไว้:
ตัววนซ้ำที่ส่งคืนโดย "วิธีการรวบรวมคอลเลกชัน" ของคลาส HashMap ทั้งหมดล้มเหลวอย่างรวดเร็ว: หลังจากสร้างตัววนซ้ำหากการแมปถูกแก้ไขจากโครงสร้างเว้นแต่จะผ่านวิธีการลบของตัววนซ้ำของตัวเอง โยนการแก้ไขพร้อมกันหากมีการปรับเปลี่ยน ดังนั้นเมื่อเผชิญกับการดัดแปลงพร้อมกันผู้วนซ้ำจะล้มเหลวอย่างสมบูรณ์ในไม่ช้าโดยไม่ต้องเสี่ยงกับพฤติกรรมที่ไม่แน่นอนโดยพลการในอนาคต
โปรดทราบว่าพฤติกรรมความล้มเหลวอย่างรวดเร็วของตัววนซ้ำไม่สามารถรับประกันได้ Fast Fail Iterator พ่นการปรับเปลี่ยนพร้อมกันเมื่อทำงานได้ดีที่สุด ดังนั้นจึงเป็นความผิดที่จะเขียนโปรแกรมที่พึ่งพาข้อยกเว้นนี้และวิธีที่ถูกต้องคือ: พฤติกรรมความล้มเหลวอย่างรวดเร็วของตัววนซ้ำควรใช้เพื่อตรวจสอบข้อผิดพลาดของโปรแกรมเท่านั้น