นักพัฒนา Java ส่วนใหญ่ใช้แผนที่โดยเฉพาะ HashMap HashMap เป็นวิธีที่ง่าย แต่ทรงพลังในการจัดเก็บและรับข้อมูล แต่มีนักพัฒนากี่คนที่รู้ว่า HASHMAP ทำงานภายในได้อย่างไร? ไม่กี่วันที่ผ่านมาฉันอ่านซอร์สโค้ดจำนวนมากของ java.util.hashmap (รวมถึง Java 7 และ Java 8) เพื่อทำความเข้าใจอย่างลึกซึ้งเกี่ยวกับโครงสร้างข้อมูลพื้นฐานนี้ ในโพสต์นี้ฉันจะอธิบายการใช้งานของ java.util.hashmap อธิบายคุณสมบัติใหม่ที่เพิ่มเข้ามาในการใช้งาน Java 8 และหารือเกี่ยวกับประสิทธิภาพหน่วยความจำและปัญหาบางอย่างที่ทราบเมื่อใช้ HashMap
ที่เก็บข้อมูลภายใน
คลาส Java HashMap ใช้อินเทอร์เฟซแผนที่ <k, v> วิธีการหลักในอินเทอร์เฟซนี้รวมถึง:
V Put (k key, v value) v get (คีย์วัตถุ) v ลบ (คีย์วัตถุ) บูลีนประกอบด้วยคีย์ (คีย์วัตถุ)
HashMap ใช้รายการภายในคลาส <k, v> เพื่อจัดเก็บข้อมูล คลาสด้านในนี้เป็นคู่คีย์-ค่าคู่ที่มีข้อมูลเพิ่มเติมสองข้อมูล:
การอ้างอิงไปยังรายการอื่นเพื่อให้ HashMap สามารถจัดเก็บวัตถุเช่นรายการลิงก์
ค่าแฮชที่ใช้แทนคีย์ การจัดเก็บค่านี้สามารถป้องกัน HashMap จากการสร้างค่าแฮชที่สอดคล้องกับคีย์ทุกครั้งที่จำเป็น
นี่คือส่วนหนึ่งของรหัสสำหรับรายการ <k, v> ภายใต้ java 7:
รายการคลาสคงที่ <k, v> ใช้ map.entry <k, v> {สุดท้าย k key; v value; entry <k, v> next; int hash; …}HashMap เก็บข้อมูลไว้ในรายการทิศทางเดียวหลายรายการ (บางครั้งเรียกว่าถังหรือคอนเทนเนอร์ Orbins) รายการทั้งหมดลงทะเบียนในอาร์เรย์รายการ (รายการ <k, v> [] อาร์เรย์) และความยาวเริ่มต้นของอาร์เรย์ภายในนี้คือ 16
รูปต่อไปนี้อธิบายการจัดเก็บภายในของอินสแตนซ์ HashMap ซึ่งมีอาร์เรย์ของวัตถุที่ไม่มีค่าใช้จ่าย แต่ละวัตถุเชื่อมต่อกับวัตถุอื่นดังนั้นจึงสร้างรายการที่เชื่อมโยง
คีย์ทั้งหมดที่มีค่าแฮชเดียวกันจะถูกวางไว้ในรายการที่เชื่อมโยงเดียวกัน (ถัง) กุญแจที่มีแฮชที่แตกต่างกันอาจจบลงในถังเดียวกัน
เมื่อการโทรของผู้ใช้ใส่ (k คีย์ k ค่า V) หรือรับ (คีย์วัตถุ) โปรแกรมจะคำนวณดัชนีของถังที่วัตถุควรอยู่ในโปรแกรมจะวนซ้ำรายการที่เกี่ยวข้องเพื่อค้นหาวัตถุรายการที่มีคีย์เดียวกัน (ใช้วิธีการเท่ากับ () ของคีย์)
ในกรณีของการโทร GET () โปรแกรมจะส่งคืนวัตถุรายการที่สอดคล้องกับค่า (หากมีวัตถุรายการอยู่)
สำหรับการโทรไปที่จะใส่ (k คีย์ k ค่า V) หากวัตถุรายการมีอยู่แล้วโปรแกรมจะแทนที่ค่าด้วยค่าใหม่มิฉะนั้นโปรแกรมจะสร้างรายการใหม่ (คีย์และค่าในพารามิเตอร์) ที่ส่วนหัวของรายการที่เชื่อมโยงทางเดียว
ดัชนีของถัง (รายการที่เชื่อมโยง) ถูกสร้างขึ้นผ่าน 3 ขั้นตอนของแผนที่:
ก่อนอื่นรับรหัสแฮชของคีย์
โปรแกรมทำซ้ำรหัสแฮชเพื่อบล็อกฟังก์ชั่นแฮชที่ไม่ดีสำหรับคีย์เนื่องจากสิ่งนี้มีศักยภาพที่จะนำข้อมูลทั้งหมดลงในดัชนีเดียวกัน (ถัง) ของอาร์เรย์ภายใน
โปรแกรมใช้รหัสแฮชซ้ำและใช้ bitmask ของความยาวอาร์เรย์ (ขั้นต่ำ 1) สำหรับมัน การดำเนินการนี้ทำให้มั่นใจได้ว่าดัชนีจะไม่ใหญ่กว่าขนาดของอาร์เรย์ คุณสามารถคิดว่ามันเป็นฟังก์ชั่นโมดูลัสที่ดีที่สุดที่คำนวณได้
นี่คือซอร์สโค้ดสำหรับการสร้างดัชนี:
// ฟังก์ชั่น "rehash" ใน java 7 ที่ใช้ hashcode ของ keystatic int hash (int h) {h ^ = (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}; 0: (h = key.hashCode ()) ^ (h >>> 16);} // ฟังก์ชั่นที่ส่งคืนดัชนีจากดัชนี hashstatic int rehashed (int h, ความยาว int) {return h & (length-1);};เพื่อให้ทำงานได้อย่างมีประสิทธิภาพมากขึ้นขนาดของอาร์เรย์ด้านในจะต้องเป็นพลังของ 2 มาดูกันว่าทำไม:
สมมติว่าความยาวของอาร์เรย์คือ 17 ค่าของหน้ากากคือ 16 (ความยาวอาร์เรย์ -1) การเป็นตัวแทนไบนารีของ 16 คือ 0 … 010000 ดังนั้นสำหรับค่าใด ๆ H ผลลัพธ์ของ "H & 16" คือ 16 หรือ 0 ซึ่งหมายความว่าอาร์เรย์ที่มีความยาว 17 สามารถนำไปใช้กับสองถังเท่านั้น: หนึ่งคือ 0 และอีก 16 ซึ่งไม่มีประสิทธิภาพมากนัก แต่ถ้าคุณตั้งค่าความยาวของอาร์เรย์เป็นพลังงาน 2 ตัวอย่างเช่น 16 ดังนั้นการจัดทำดัชนีบิตจะทำงานเป็น "H & 15" การเป็นตัวแทนไบนารีของ 15 คือ 0 … 001111 และเอาต์พุตค่าโดยสูตรดัชนีสามารถอยู่ในช่วงตั้งแต่ 0 ถึง 15 เพื่อให้อาร์เรย์ของความยาว 16 สามารถใช้งานได้อย่างเต็มที่ ตัวอย่างเช่น:
ถ้า h = 952 การเป็นตัวแทนไบนารีของมันคือ 0..01110111000 และดัชนีที่สอดคล้องกันคือ 0 … 01000 = 8
ถ้า h = 1576 การเป็นตัวแทนไบนารีของมันคือ 0..011000101000 และดัชนีที่สอดคล้องกันคือ 0 … 01000 = 8
ถ้า h = 12356146 การเป็นตัวแทนไบนารีของมันคือ 0..01011110010001010010 ดัชนีที่สอดคล้องกันคือ 0 … 00010 = 2
ถ้า h = 59843 การเป็นตัวแทนไบนารีของมันคือ 0..01110100111000011 ดัชนีที่สอดคล้องกันคือ 0 … 00011 = 3
กลไกนี้มีความโปร่งใสสำหรับนักพัฒนา: หากเขาเลือก Hashmap ที่มีความยาว 37 แผนที่จะเลือกค่าพลังงานถัดไปโดยอัตโนมัติมากกว่า 37 (64) โดยอัตโนมัติเป็นความยาวของอาร์เรย์ภายใน
ปรับขนาดโดยอัตโนมัติ
หลังจากได้รับดัชนีแล้ววิธีการรับ (), put () หรือลบ () จะเข้าถึงรายการที่เชื่อมโยงที่เกี่ยวข้องเพื่อดูว่าวัตถุรายการสำหรับคีย์ที่ระบุมีอยู่แล้วหรือไม่ กลไกนี้อาจทำให้เกิดปัญหาด้านประสิทธิภาพเนื่องจากวิธีนี้ต้องการการวนซ้ำในรายการทั้งหมดเพื่อดูว่ามีวัตถุรายการอยู่หรือไม่ สมมติว่าความยาวของอาร์เรย์ภายในใช้ค่าเริ่มต้นที่ 16 และคุณต้องเก็บบันทึก 2,000,000 รายการ ในกรณีที่ดีที่สุดจะมีวัตถุรายการ 125,000 รายการต่อรายการที่เชื่อมโยง (2,000,000/16) วิธี Get (), ลบ () และ put () ต้องใช้การวนซ้ำ 125,000 ครั้งในแต่ละครั้งที่พวกเขาถูกดำเนินการ เพื่อหลีกเลี่ยงสิ่งนี้ HashMap สามารถเพิ่มความยาวของอาร์เรย์ภายในได้ดังนั้นจึงมั่นใจได้ว่ามีเพียงไม่กี่วัตถุรายการที่ถูกเก็บไว้ในรายการที่เชื่อมโยง
เมื่อคุณสร้าง HashMap คุณสามารถระบุความยาวเริ่มต้นและตัวโหลดผ่านตัวสร้างต่อไปนี้:
</dres> hashmap สาธารณะ (int initialcapacity, float loadfactor) <pre>
หากคุณไม่ได้ระบุพารามิเตอร์ค่าเริ่มต้นเริ่มต้นเริ่มต้นคือ 16 และค่าตัวโหลดเริ่มต้นคือ 0.75 การเริ่มต้นแสดงถึงความยาวของรายการที่เชื่อมโยงของอาร์เรย์ภายใน
เมื่อคุณใช้วิธีการใส่ (…) เพื่อเพิ่มคู่คีย์ค่าใหม่ลงในแผนที่วิธีการตรวจสอบว่าความยาวของอาร์เรย์ด้านในจะต้องเพิ่มขึ้นหรือไม่ เพื่อให้ได้สิ่งนี้แผนที่เก็บข้อมูล 2 ข้อมูล:
ขนาดแผนที่: มันแสดงจำนวนระเบียนใน HashMap เราอัปเดตค่าเมื่อเราแทรกหรือลบลงใน HashMap
Threshold: มันเท่ากับความยาวของอาร์เรย์ภายใน*loadfactor และเกณฑ์นี้จะได้รับการปรับปรุงในเวลาเดียวกันทุกครั้งที่มีการปรับความยาวของอาร์เรย์ภายใน
ก่อนที่จะเพิ่มวัตถุรายการใหม่เมธอด (…) จะตรวจสอบว่าขนาดของแผนที่ปัจจุบันมากกว่าเกณฑ์หรือไม่ หากมากกว่าเกณฑ์มันจะสร้างอาร์เรย์ใหม่ที่มีความยาวเป็นสองเท่าของอาร์เรย์ภายในปัจจุบัน เนื่องจากขนาดของอาร์เรย์ใหม่มีการเปลี่ยนแปลงฟังก์ชันดัชนี (นั่นคือผลการดำเนินการบิตที่ส่งคืน "ค่าแฮชของคีย์ & (ความยาวอาร์เรย์ -1)") จึงเปลี่ยนไป การปรับขนาดอาร์เรย์สร้างถังใหม่สองตัว (รายการที่เชื่อมโยง) และกำหนดวัตถุรายการรายการที่มีอยู่ทั้งหมดให้กับถังทั้งหมด เป้าหมายของการปรับขนาดอาร์เรย์คือการลดขนาดของรายการที่เชื่อมโยงซึ่งจะช่วยลดเวลาในการดำเนินการของ Put (), ลบ () และรับ () วิธีการ สำหรับวัตถุรายการทั้งหมดที่สอดคล้องกับคีย์ที่มีค่าแฮชเดียวกันพวกเขาจะถูกจัดสรรให้กับถังเดียวกันหลังจากปรับขนาด อย่างไรก็ตามหากค่าแฮชของวัตถุทั้งสองรายการแตกต่างกัน แต่พวกเขาอยู่ในถังเดียวกันก่อนหน้านี้หลังจากการปรับเปลี่ยนไม่มีการรับประกันว่าพวกเขายังคงอยู่ในถังเดียวกัน
ภาพนี้อธิบายถึงสถานการณ์ของอาร์เรย์ภายในที่ปรับล่วงหน้าและการปรับหลัง ก่อนที่จะปรับความยาวอาร์เรย์เพื่อให้ได้วัตถุรายการ E แผนที่จำเป็นต้องทำซ้ำผ่านรายการที่เชื่อมโยงที่มี 5 องค์ประกอบ หลังจากปรับความยาวอาร์เรย์วิธี GET () เดียวกันจะต้องผ่านรายการที่เชื่อมโยงที่มี 2 องค์ประกอบดังนั้นความเร็วในการเรียกใช้ของวิธี GET () หลังจากปรับความยาวอาร์เรย์เพิ่มขึ้น 2 เท่า
ความปลอดภัยด้าย
หากคุณคุ้นเคยกับ HashMap อยู่แล้วคุณจะรู้ว่ามันไม่ปลอดภัย แต่ทำไม? ตัวอย่างเช่นสมมติว่าคุณมีเธรดนักเขียนที่จะแทรกข้อมูลที่มีอยู่ลงในแผนที่เท่านั้นเธรดผู้อ่านที่จะอ่านข้อมูลจากแผนที่ดังนั้นทำไมมันไม่ทำงาน
เนื่องจากภายใต้กลไกการปรับขนาดอัตโนมัติหากเธรดพยายามเพิ่มหรือรับวัตถุแผนที่อาจใช้ค่าดัชนีเก่าเพื่อให้ไม่พบที่เก็บข้อมูลใหม่ที่วัตถุรายการจะไม่พบ
ในกรณีที่เลวร้ายที่สุดเมื่อ 2 เธรดแทรกข้อมูลในเวลาเดียวกันการโทร 2 ครั้ง () จะเริ่มต้นในเวลาเดียวกันและอาร์เรย์จะปรับขนาดโดยอัตโนมัติ เนื่องจากสองเธรดจะแก้ไขรายการที่เชื่อมโยงในเวลาเดียวกันจึงเป็นไปได้ว่าแผนที่จะออกในลูปภายในของรายการที่เชื่อมโยง หากคุณพยายามรับข้อมูลจากรายการที่มีลูปด้านในวิธีการรับ () จะไม่สิ้นสุด
Hashtable ให้การใช้งานแบบเธรดที่ปลอดภัยซึ่งป้องกันไม่ให้เกิดขึ้นข้างต้น อย่างไรก็ตามเนื่องจากการดำเนินการ CRUD แบบซิงโครนัสทั้งหมดช้ามาก ตัวอย่างเช่นหากเธรด 1 การโทรรับ (คีย์ 1) ดังนั้นเธรด 2 การโทร Get (key2) และเธรด 2 การโทรรับ (key3) จากนั้นในเวลาที่กำหนดมีเพียง 1 เธรดเท่านั้นที่สามารถรับค่าได้ แต่เธรดทั้ง 3 ทั้งหมดสามารถเข้าถึงข้อมูลเหล่านี้ได้ในเวลาเดียวกัน
ตั้งแต่ Java 5 เรามีการใช้งาน HashMap ที่ดีกว่าและปลอดภัย: พร้อมกัน: พร้อมกัน สำหรับ MAP พร้อมกันมีเฉพาะถังเท่านั้นที่ซิงโครไนซ์ดังนั้นหากหลายเธรดไม่ได้ใช้ถังเดียวกันหรือปรับขนาดอาร์เรย์ภายในพวกเขาสามารถเรียกว่า Get () ลบ () หรือใส่ () วิธีการในเวลาเดียวกัน ในแอปพลิเคชันแบบมัลติเธรดวิธีนี้เป็นตัวเลือกที่ดีกว่า
ความแปรปรวนของพันธบัตร
เหตุใดจึงเป็นการใช้งานที่ดีในการใช้สตริงและจำนวนเต็มเป็นกุญแจสู่ HashMap ส่วนใหญ่เป็นเพราะพวกเขาไม่เปลี่ยนรูป! หากคุณเลือกที่จะสร้างคลาสด้วยตัวคุณเองเป็นคีย์ แต่คุณไม่สามารถรับประกันได้ว่าชั้นเรียนไม่เปลี่ยนรูปคุณอาจสูญเสียข้อมูลภายใน HashMap
มาดูกรณีการใช้งานต่อไปนี้:
คุณมีคีย์ที่มีค่าภายในคือ "1"
หากคุณแทรกวัตถุลงใน HashMap คีย์ของมันคือ "1"
HashMap สร้างค่าแฮชจากรหัสแฮชของคีย์ (เช่น "1")
แผนที่เก็บค่าแฮชนี้ในบันทึกที่สร้างขึ้นใหม่
คุณเปลี่ยนค่าภายในของคีย์และเปลี่ยนเป็น "2"
ค่าแฮชของคีย์เปลี่ยนไป แต่ HashMap ไม่ทราบสิ่งนี้ (เพราะเก็บค่าแฮชเก่าไว้)
คุณพยายามรับวัตถุที่เกี่ยวข้องโดยคีย์ที่แก้ไขแล้ว
แผนที่คำนวณค่าแฮชของคีย์ใหม่ (เช่น "2") เพื่อค้นหารายการที่เชื่อมโยง (ถัง) ซึ่งวัตถุรายการอยู่
กรณีที่ 1: เนื่องจากคุณได้แก้ไขคีย์แผนที่จะพยายามค้นหาวัตถุรายการในถังที่ไม่ถูกต้อง แต่ไม่พบ
กรณีที่ 2: คุณโชคดีที่ถังที่สร้างขึ้นโดยคีย์ที่แก้ไขและถังที่สร้างโดยคีย์เก่านั้นเหมือนกัน แผนที่จะสำรวจรายการที่เชื่อมโยงและวัตถุรายการที่มีคีย์เดียวกัน แต่เพื่อที่จะค้นหาคีย์แผนที่จะเปรียบเทียบค่าแฮชของคีย์ก่อนโดยเรียกวิธี Equals () เนื่องจากคีย์ที่ได้รับการแก้ไขจะสร้างค่าแฮชที่แตกต่างกัน (ค่าแฮชเก่าถูกเก็บไว้ในระเบียน) ดังนั้นแผนที่จึงไม่มีวิธีค้นหาวัตถุรายการที่เกี่ยวข้องในรายการที่เชื่อมโยง
นี่คือตัวอย่าง Java ที่เราใส่คู่คีย์-ค่าสองคู่ลงในแผนที่และจากนั้นฉันแก้ไขคีย์แรกและพยายามรับวัตถุทั้งสอง คุณจะพบว่ามีเพียงวัตถุที่สองที่ส่งคืนจากแผนที่วัตถุแรกนั้น "หายไป" ใน HashMap:
คลาสสาธารณะ MutableKeyTest {โมฆะสาธารณะคงที่หลัก (String [] args) {คลาส myKey {จำนวนเต็ม i; โมฆะสาธารณะ seti (จำนวนเต็ม i) {this.i = i;} สาธารณะของฉัน (จำนวนเต็ม i) {this.i = i;}@overridepublic int อินสแตนซ์ของ mykey) {return i.equals (((mykey) obj) .i);} elsereturn false;}} แผนที่ <mykey, string> mymap = hashmap ใหม่ <> (); mykey key1 = mykey ใหม่ (1); mykey key2 = new mykey (2); mymap.put (key1 key1key1.seti (3); String test1 = mymap.get (key1); string test2 = mymap.get (key2); system.out.println ("test1 =" + test1 + "test2 =" + test2);}}}}เอาต์พุตของรหัสด้านบนคือ "test1 = null test2 = test 2" อย่างที่เราคาดหวังแผนที่ไม่มีความสามารถในการรับสตริง 1 ที่สอดคล้องกับคีย์ที่แก้ไขแล้ว 1
การปรับปรุงใน Java 8
ใน Java 8 การใช้งานภายในใน HashMap ได้รับการแก้ไขมาก อันที่จริงแล้ว Java 7 ใช้รหัส 1,000 บรรทัดในการใช้งานในขณะที่ Java 8 ใช้รหัส 2,000 บรรทัด สิ่งที่ฉันอธิบายไว้ก่อนหน้านี้ส่วนใหญ่ยังคงถูกต้องใน Java 8 ยกเว้นการใช้รายการที่เชื่อมโยงเพื่อบันทึกวัตถุรายการ ใน Java 8 เรายังคงใช้อาร์เรย์ แต่จะถูกบันทึกไว้ในโหนดซึ่งมีข้อมูลเดียวกันกับวัตถุรายการก่อนหน้าและยังใช้รายการที่เชื่อมโยง:
นี่คือส่วนหนึ่งของรหัสที่ใช้โหนดใน Java 8:
โหนดคลาสคงที่ <k, v> ใช้ map.entry <k, v> {hash int สุดท้าย; คีย์ k สุดท้าย; v value; node <k, v> next;แล้วความแตกต่างใหญ่เมื่อเทียบกับ Java 7 คืออะไร? โหนดสามารถขยายไปยัง treenode Treenode เป็นโครงสร้างข้อมูลของต้นไม้สีแดงและสีดำที่สามารถเก็บข้อมูลเพิ่มเติมได้ดังนั้นเราจึงสามารถเพิ่มลบหรือรับองค์ประกอบภายใต้ความซับซ้อนของ O (log (n)) ตัวอย่างต่อไปนี้อธิบายข้อมูลทั้งหมดที่บันทึกโดย Treenode:
คลาสสุดท้ายของ TREENODE <k, v> ขยาย linkedhashmap.entry <k, v> {hash int สุดท้าย; // สืบทอดมาจากโหนด <k, v> คีย์ k สุดท้าย; // สืบทอดมาจากโหนด <k, v> v ค่า; // สืบทอดมาจากโหนด <k, v> node <k, v> next; // สืบทอดมาจากโหนด <k, v> รายการ <k, v> ก่อน, หลังจาก; // สืบทอดมาจาก linkedhashmap.entry <k, v> parent; treenode <k, v> ซ้าย; treenode <k, v> ขวา; treenode <k, v> prev;ต้นไม้สีแดงและสีดำเป็นต้นไม้ค้นหาไบนารีที่มีความสมดุล กลไกภายในของมันทำให้มั่นใจได้ว่าความยาวของมันอยู่เสมอ (n) ไม่ว่าเราจะเพิ่มหรือลบโหนด ประโยชน์ที่สำคัญที่สุดของการใช้ต้นไม้ประเภทนี้คือกรณีที่ข้อมูลจำนวนมากในตารางภายในมีดัชนีเดียวกัน (ถัง) ในเวลานี้ความซับซ้อนของการค้นหาต้นไม้คือ o (log (n)) และสำหรับรายการที่เชื่อมโยงความซับซ้อนคือ o (n) สำหรับการดำเนินการเดียวกัน
อย่างที่คุณเห็นเราจะเก็บข้อมูลในต้นไม้มากกว่ารายการที่เชื่อมโยง ตามหลักการการสืบทอดตารางภายในสามารถมีโหนด (รายการที่เชื่อมโยง) หรือ treenode (ต้นไม้สีแดงและสีดำ) Oracle ตัดสินใจใช้โครงสร้างข้อมูลทั้งสองนี้ตามกฎต่อไปนี้:
- สำหรับดัชนีที่ระบุ (ถัง) ในตารางภายในหากจำนวนโหนดมากกว่า 8 รายการที่เชื่อมโยงจะถูกแปลงเป็นต้นไม้สีแดงและสีดำ
- สำหรับดัชนีที่ระบุ (ถัง) ในตารางภายในหากจำนวนโหนดน้อยกว่า 6 ต้นไม้สีแดงและสีดำจะถูกแปลงเป็นรายการที่เชื่อมโยง
ภาพนี้อธิบายอาร์เรย์ภายในใน Java 8 Hashmap ซึ่งมีทั้งต้นไม้ (Bucket 0) และรายการที่เชื่อมโยง (Bucket 1, 2 และ 3) Bucket 0 เป็นโครงสร้างต้นไม้เพราะมีมากกว่า 8 โหนด
หน่วยความจำค่าใช้จ่าย
Java 7
การใช้ HashMap ใช้หน่วยความจำบางอย่าง ใน Java 7, HashMap ห่อหุ้มคู่คีย์-ค่าลงในวัตถุรายการวัตถุรายการมีข้อมูลต่อไปนี้:
อ้างอิงถึงบันทึกถัดไปค่าแฮชที่คำนวณล่วงหน้า (จำนวนเต็ม)
การอ้างอิงถึงคีย์และการอ้างอิงถึงค่า
นอกจากนี้ HashMap ใน Java 7 ใช้อาร์เรย์ภายในของวัตถุรายการ สมมติว่า Java 7 HashMap มีองค์ประกอบ N และอาร์เรย์ภายในมีความจุจากนั้นการใช้หน่วยความจำเพิ่มเติมเป็นเรื่องเกี่ยวกับ:
sizeof (จำนวนเต็ม)* n + sizeof (อ้างอิง)* (3* n + c)
ใน:
ขนาดของจำนวนเต็มคือ 4 ไบต์
ขนาดของการอ้างอิงขึ้นอยู่กับ JVM ระบบปฏิบัติการและโปรเซสเซอร์ แต่มักจะเป็น 4 ไบต์
ซึ่งหมายความว่าค่าใช้จ่ายหน่วยความจำทั้งหมดมักจะเป็น 16 * n + 4 * ไบต์ความจุ
หมายเหตุ: หลังจากได้รับการปรับขนาดแผนที่โดยอัตโนมัติค่าความจุคือกำลังที่เล็กที่สุดถัดไปของ 2 มากกว่า N
หมายเหตุ: เริ่มต้นจาก Java 7, HashMap ใช้กลไกการโหลดขี้เกียจ ซึ่งหมายความว่าแม้ว่าคุณจะระบุขนาดของ HASHMAP อาร์เรย์ภายในที่ใช้ (บริโภค 4*ไบต์ความจุ 4 ไบต์) ที่ไม่ได้จัดสรรในหน่วยความจำก่อนที่เราจะใช้วิธี PUT () เป็นครั้งแรก
Java 8
ในการใช้งาน Java 8 การคำนวณการใช้หน่วยความจำมีความซับซ้อนมากขึ้นเนื่องจากโหนดอาจจัดเก็บข้อมูลเดียวกันกับรายการหรือเพิ่ม 6 การอ้างอิงและคุณสมบัติบูลีน (ระบุว่าเป็น treenode)
หากโหนดทั้งหมดเป็นเพียงโหนดดังนั้นหน่วยความจำที่ใช้โดย Java 8 Hashmap จะเหมือนกับที่ Java 7 Hashmap บริโภค
หากโหนดทั้งหมดเป็น treenode ดังนั้นหน่วยความจำที่ใช้โดย Java 8 HashMap จะกลายเป็น:
n * sizeof (จำนวนเต็ม) + n * sizeof (บูลีน) + sizeof (อ้างอิง) * (9 * n + ความจุ)
ใน JVMs มาตรฐานส่วนใหญ่ผลลัพธ์ของสูตรข้างต้นคือ 44 * n + 4 * ไบต์ความจุ
ปัญหาด้านประสิทธิภาพ
hashmap แบบไม่สมมาตรกับ hashmap ที่สมดุล
ในกรณีที่ดีที่สุดทั้งสองได้รับ () และ put () มีความซับซ้อนเพียง O (1) เท่านั้น อย่างไรก็ตามหากคุณไม่สนใจฟังก์ชั่นแฮชของคีย์วิธีการของคุณ () และรับ () อาจดำเนินการช้ามาก วิธีการดำเนินการที่มีประสิทธิภาพของวิธีการใส่ () และ GET () ขึ้นอยู่กับข้อมูลที่จัดสรรให้กับดัชนีที่แตกต่างกันของอาร์เรย์ภายใน (bucket) หากฟังก์ชั่นแฮชของคีย์ไม่ได้รับการออกแบบอย่างถูกต้องคุณจะได้รับพาร์ติชันแบบไม่สมมาตร (โดยไม่คำนึงถึงขนาดของข้อมูลภายใน) วิธีการทั้งหมด () และรับ () จะใช้รายการที่เชื่อมโยงที่ใหญ่ที่สุดซึ่งจะดำเนินการช้าเพราะต้องมีการวนซ้ำทุกเร็กคอร์ดทั้งหมดในรายการที่เชื่อมโยง ในกรณีที่เลวร้ายที่สุด (หากข้อมูลส่วนใหญ่อยู่ในถังเดียวกัน) ความซับซ้อนของเวลาของคุณจะกลายเป็น o (n)
นี่คือตัวอย่างภาพ กราฟแรกอธิบายแฮชแมปแบบไม่สมมาตรและกราฟที่สองอธิบายถึงแฮชแมปที่เท่าเทียมกัน
เบ้
ใน HashMap แบบไม่สมมาตรนี้จะต้องใช้เวลาในการเรียกใช้วิธีการรับ () และใส่ () บนถัง 0. การได้รับการบันทึก K ใช้การวนซ้ำ 6 ครั้ง
ใน HashMap ที่สมดุลนี้ใช้เวลาเพียง 3 การวนซ้ำเพื่อให้ได้บันทึก K. HashMaps ทั้งสองนี้เก็บข้อมูลจำนวนเท่ากันและอาร์เรย์ภายในมีขนาดเท่ากัน ความแตกต่างเพียงอย่างเดียวคือฟังก์ชั่นแฮชของคีย์ซึ่งใช้เพื่อแจกจ่ายระเบียนไปยังถังที่แตกต่างกัน
นี่คือตัวอย่างสุดโต่งที่เขียนใน Java ซึ่งฉันใช้ฟังก์ชันแฮชเพื่อนำข้อมูลทั้งหมดลงในรายการที่เชื่อมโยง (ถัง) เดียวกันจากนั้นฉันเพิ่มข้อมูล 2,000,000 ชิ้น
การทดสอบระดับสาธารณะ {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {คลาส mykey {จำนวนเต็ม i; public mykey (จำนวนเต็ม i) {this.i = i;}@overridepublic int hashcode () {return 1; hashmap <> (2_500_000,1); สำหรับ (int i = 0; i <2_000_000; i ++) {mymap.put (ใหม่ mykey (i), "ทดสอบ"+i);} วันที่สิ้นสุด = วันที่ใหม่ ();การกำหนดค่าเครื่องของฉันคือ Core i5-2500K @ 3.6G และใช้เวลามากกว่า 45 นาทีในการทำงานภายใต้ Java 8U40 (ฉันหยุดกระบวนการหลังจาก 45 นาที) ถ้าฉันเรียกใช้รหัสเดียวกัน แต่ฉันใช้ฟังก์ชันแฮชแบบนี้:
@OverridePublic int hashCode () {int key = 2097152-1; Return Key+2097152*i;}ใช้เวลา 46 วินาทีในการเรียกใช้ซึ่งดีกว่าเดิมมาก! ฟังก์ชั่นแฮชใหม่มีความสมเหตุสมผลกว่าฟังก์ชั่นแฮชเก่าเมื่อประมวลผลพาร์ติชันแฮชดังนั้นการเรียกใช้วิธีการใส่ () เร็วกว่า หากคุณเรียกใช้รหัสเดียวกันตอนนี้ แต่ใช้ฟังก์ชั่นแฮชด้านล่างมันจะให้พาร์ติชันแฮชที่ดีกว่า:
@Overridepublic int hashCode () {return i;}ตอนนี้ใช้เวลาเพียง 2 วินาที!
ฉันหวังว่าคุณจะรู้ว่าฟังก์ชั่นแฮชมีความสำคัญเพียงใด หากคุณทำการทดสอบเดียวกันกับ Java 7 ครั้งที่หนึ่งและครั้งที่สองจะแย่ลง (เพราะวิธีการใส่ () ใน Java 7 มีความซับซ้อน O (n) ในขณะที่ความซับซ้อนใน Java 8 มี O (log (n))
เมื่อใช้ HashMap คุณต้องค้นหาฟังก์ชั่นแฮชสำหรับปุ่มที่สามารถกระจายปุ่มไปยังถังที่น่าจะเป็นไปได้มากที่สุด ในการทำเช่นนี้คุณต้องหลีกเลี่ยงความขัดแย้งแฮช วัตถุสตริงเป็นคีย์ที่ดีมากเพราะมีฟังก์ชั่นแฮชที่ดี จำนวนเต็มก็ดีเช่นกันเพราะแฮชเป็นค่าของตัวเอง
ปรับขนาดค่าใช้จ่าย
หากคุณต้องการจัดเก็บข้อมูลจำนวนมากคุณควรระบุความจุเริ่มต้นเมื่อสร้าง HashMap ซึ่งควรจะใกล้เคียงกับขนาดที่คุณต้องการ
หากคุณไม่ทำเช่นนี้แผนที่จะใช้ขนาดเริ่มต้นเช่น 16 และค่าของ factorload คือ 0.75 วิธีการโทร 11 ครั้งแรกที่จะใส่ () จะเร็วมาก แต่การโทรครั้งที่ 12 (16*0.75) จะสร้างอาร์เรย์ภายในใหม่ที่มีความยาว 32 (และรายการ/ต้นไม้ที่เชื่อมโยงที่สอดคล้องกัน) และการโทรครั้งที่ 13 ถึง 22 จะทำให้การโทร () มีความยาว 23 (32*0.75) จากนั้นการดำเนินการปรับขนาดภายในจะถูกเรียกใช้เมื่อวิธีการใส่ () เรียกว่า 48, 96, 192nd …. หากจำนวนข้อมูลไม่ใหญ่การดำเนินการสร้างอาร์เรย์ภายในจะใหม่จะเร็วมาก แต่เมื่อจำนวนข้อมูลมีขนาดใหญ่เวลาที่ใช้อาจอยู่ในช่วงไม่กี่วินาทีถึงนาที โดยการระบุขนาดที่ต้องการของแผนที่ในระหว่างการเริ่มต้นคุณสามารถหลีกเลี่ยงการบริโภคที่เกิดจากการปรับขนาดการดำเนินงาน
แต่ยังมีข้อเสียเปรียบที่นี่: หากคุณตั้งค่าอาร์เรย์ให้ใหญ่มากตัวอย่างเช่น 2^28 แต่คุณเพียงแค่ใช้ถัง 2^26 ในอาร์เรย์คุณจะเสียความทรงจำจำนวนมาก (ประมาณ 2^30 ไบต์ในตัวอย่างนี้)
สรุปแล้ว
สำหรับกรณีการใช้งานอย่างง่ายคุณไม่จำเป็นต้องรู้ว่า HASHMAP ทำงานอย่างไรเพราะคุณจะไม่เห็นความแตกต่างระหว่าง O (1), O (N) และ O (log (n)) แต่มันเป็นประโยชน์เสมอที่จะเข้าใจกลไกที่อยู่เบื้องหลังโครงสร้างข้อมูลที่ใช้บ่อยนี้ นอกจากนี้นี่เป็นคำถามสัมภาษณ์ทั่วไปสำหรับตำแหน่งนักพัฒนา Java
สำหรับปริมาณข้อมูลขนาดใหญ่มันเป็นสิ่งสำคัญมากที่จะต้องเข้าใจว่า HASHMAP ทำงานอย่างไรและเข้าใจความสำคัญของฟังก์ชั่นแฮชสำหรับคีย์
ฉันหวังว่าบทความนี้จะช่วยให้คุณมีความเข้าใจอย่างลึกซึ้งเกี่ยวกับการใช้ HashMap