HashMap เป็นการใช้งานอินเทอร์เฟซแผนที่ตามตารางแฮชให้การดำเนินการแมปแบบเลือกทั้งหมดและอนุญาตให้ค่า NULL และการก่อสร้างโมฆะออกจากการซิงโครไนซ์และไม่มีการรับประกันลำดับการแมป มาบันทึกหลักการดำเนินการของ HashMap
ที่เก็บข้อมูลภายใน hashmap
ใน HashMap ความสัมพันธ์คู่คีย์-ค่าทั้งหมดจะถูกเก็บไว้โดยการรักษาอาร์เรย์ของตารางตัวแปรทันที (หรือที่เรียกว่า Bucket) ถังเป็นอาร์เรย์ของวัตถุรายการ ขนาดของถังสามารถปรับขนาดได้ตามต้องการและความยาวจะต้องเป็นพลังของ 2 รหัสต่อไปนี้:
/ *** อาร์เรย์รายการว่างเปล่าค่าเริ่มต้นของที่เก็บข้อมูล*/ รายการสุดท้ายคงที่ <?,?> [] empty_table = {}; / *** ถังปรับขนาดตามต้องการ แต่ต้องเป็นพลังของ 2*/ รายการชั่วคราว <k, v> [] table = (รายการ <k, v> []) emport_table;ความจุเริ่มต้นและปัจจัยโหลด
HashMap มีพารามิเตอร์สองตัวที่มีผลต่อประสิทธิภาพความจุเริ่มต้นและปัจจัยโหลด กำลังการผลิตคือจำนวนถังในตารางแฮชความจุเริ่มต้นเป็นเพียงความจุของตารางแฮชเมื่อสร้างขึ้นและปัจจัยโหลดเป็นสเกลที่ตารางแฮชสามารถเข้าถึงได้อย่างไรก่อนที่ความจุจะเพิ่มขึ้นโดยอัตโนมัติ เมื่อจำนวนรายการในตารางแฮชเกินกว่าผลิตภัณฑ์ของปัจจัยโหลดและกำลังการผลิตปัจจุบันตารางแฮชจะต้องได้รับการปรับปรุงใหม่ (เช่นสร้างโครงสร้างข้อมูลภายในใหม่) และการสร้างใหม่จะถูกสร้างขึ้นที่สองเท่าของจำนวนกำลังการผลิตปัจจุบัน ความจุเริ่มต้นและปัจจัยโหลดสามารถตั้งค่าผ่านตัวสร้าง ความจุเริ่มต้นเริ่มต้นคือ 16 รายการความจุสูงสุดคือ 2^30 รายการและปัจจัยโหลดเริ่มต้นคือ 0.75
ถังเป็นเหมือนถังที่เก็บน้ำ ความจุเริ่มต้นเริ่มต้นคือ 16 หน่วยของน้ำ เมื่อน้ำถูกเทถึง 16*0.75 ความจุจะถูกขยายก่อนเป็น 32 หน่วยเมื่อเพิ่มข้อมูลในครั้งต่อไป 0.75 เป็นปัจจัยโหลดและสามารถตั้งค่าความจุและปัจจัยการโหลดเริ่มต้นเมื่อสร้างถัง ความจุสูงสุดของถังคือ 2 หน่วยของน้ำถึงกำลังของ 30 เมื่อจำนวนการตั้งค่าความจุเริ่มต้นมากกว่าความจุสูงสุดความจุสูงสุดจะเหนือกว่า เมื่อขยายตัวจะถูกส่งคืนโดยตรงหากมากกว่าหรือเท่ากับความจุสูงสุด
ต่อไปนี้เป็นส่วนหนึ่งของซอร์สโค้ดของ HASHMAP ซึ่งกำหนดความจุเริ่มต้นเริ่มต้นปัจจัยโหลดและค่าคงที่อื่น ๆ :
/ ** * ความจุเริ่มต้นเริ่มต้นจะต้องเป็นกำลังของ 2. */ int สุดท้าย int default_initial_capacity = 1 << 4; // aka 16/ *** ความจุสูงสุดหากความจุเริ่มต้นสูงกว่าความจุสูงสุดผ่านพารามิเตอร์ตัวสร้างความจุจะถูกใช้เป็นความจุเริ่มต้น* จะต้องเป็นกำลังของ 2 และน้อยกว่าหรือเท่ากับ 30th ของ 2*/ int สุดท้าย int สุดท้าย _capacity = 1 << 30; / *** ปัจจัยการโหลดเริ่มต้นสามารถระบุได้โดยตัวสร้าง*/ คงที่ float float default_load_factor = 0.75f; / *** ตารางอาร์เรย์ที่ว่างเปล่าเมื่อถังไม่ได้เริ่มต้น*/ รายการสุดท้ายคงที่ <?,?> [] emport_table = {}; / *** ถังเก็บรายการคู่คีย์-ค่าทั้งหมดและสามารถปรับขนาดได้ตามต้องการและความยาวจะต้องเป็นพลังของ 2*/ รายการชั่วคราว <k, v> [] table = (รายการ <k, v> []) empty_table; /*** จำนวนคู่คีย์ -ค่าในแผนที่ขนาดจะเป็นการดำเนินการ +1 หรือ -1 ทุกครั้งที่มีการเพิ่มหรือลบ */ ขนาด int ชั่วคราว; /** * ค่าวิกฤตของค่าโหลดซึ่งจำเป็นต้องปรับขนาดคือ: (ความจุ * ปัจจัยโหลด) หลังจากปรับขนาดแต่ละตัวกำลังการผลิตใหม่จะถูกคำนวณโดยใช้กำลังการผลิตใหม่ * @Serial */ // ถ้าตาราง == empty_table แล้วนี่คือความจุเริ่มต้นที่ // ตารางจะถูกสร้างขึ้นเมื่อพองตัว เกณฑ์ int; / ** * ปัจจัยโหลดหากไม่ได้ระบุไว้ในตัวสร้างจะใช้ปัจจัยการโหลดเริ่มต้น * * @Serial */ Final Float LoadFactor; /** * จำนวนครั้งการปรับเปลี่ยนโครงสร้าง HASHMAP เปลี่ยนจำนวนแผนที่ใน HASHMAP หรือปรับเปลี่ยนโครงสร้างภายในเมื่อโครงสร้างถูกแก้ไข (ตัวอย่างเช่นวิธีการ rehash * สร้างโครงสร้างข้อมูลภายในใหม่) ฟิลด์นี้ใช้ใน * ตัววนซ้ำที่สร้างขึ้นในมุมมองคอลเลกชัน HashMap จะถูกประมวลผลเป็น Fast Failed */Transient Int Modcount;ความจุเริ่มต้นและการปรับประสิทธิภาพการโหลดปัจจัย
โดยทั่วไปแล้วปัจจัยการโหลดเริ่มต้น (0.75) จะพยายามลดค่าใช้จ่ายในเวลาและค่าใช้จ่าย แม้ว่าปัจจัยการโหลดจะสูงเกินไป แต่ก็เพิ่มต้นทุนการสืบค้น (ซึ่งสะท้อนให้เห็นในการดำเนินงาน HASHMAP ส่วนใหญ่รวมถึงการดำเนินการรับและการดำเนินการ) เมื่อตั้งค่าความจุเริ่มต้นจำนวนรายการที่ต้องการในแผนที่และปัจจัยโหลดควรนำมาพิจารณาเพื่อลดจำนวนการดำเนินการฟื้นฟู หากความจุเริ่มต้นมากกว่าจำนวนสูงสุดของรายการหารด้วยปัจจัยโหลดการดำเนินการ rehash จะไม่เกิดขึ้น
หากการทำแผนที่ความสัมพันธ์จำนวนมากถูกเก็บไว้ในอินสแตนซ์ HashMap การสร้างความจุเริ่มต้นที่มีขนาดใหญ่พอจะทำให้ความสัมพันธ์การทำแผนที่จัดเก็บได้อย่างมีประสิทธิภาพมากขึ้นเมื่อเทียบกับการดำเนินการฟื้นฟูอัตโนมัติตามความต้องการเพื่อเพิ่มความสามารถของตาราง
ต่อไปนี้เป็นรหัสเพื่อสร้างโครงสร้างข้อมูล HASHMAP:
โมฆะปรับขนาด (int newCapacity) {entry [] oldTable = ตาราง; int oldcapacity = oldTable.length; ถ้า (oldCapacity == maximum_capacity) {// ถ้าความจุถึงขีด จำกัด สูงสุดจากนั้นตั้งค่าโหลดและกลับไปที่ threshold = integer.max_value; กลับ; } // สร้างตารางใหม่เพื่อจัดเก็บการป้อนข้อมูล [] newTable = รายการใหม่ [newCapacity]; // ถ่ายโอนข้อมูลจากตารางเก่าไปยังตารางใหม่ขั้นตอนนี้จะใช้เวลามากในการถ่ายโอน (newtable, inithseedasneeded (newcapacity)); ตาราง = newTable; // ในที่สุดตั้งค่าค่าโหลดของเกณฑ์การปรับขนาดถัดไป = (int) math.min (newCapacity * loadfactor, maximum_capacity + 1);}วิธีการก่อสร้าง HashMap
วิธีการก่อสร้างครั้งที่สี่คือการสร้าง HashMap ใหม่ด้วยแผนที่ที่มีอยู่ มาพูดถึงเรื่องนี้ในภายหลัง ในความเป็นจริงวิธีการก่อสร้างสามวิธีแรกถูกเรียกในวิธีที่สามสุดท้ายด้วยพารามิเตอร์สองตัว หากไม่มีการส่งพารามิเตอร์ค่าเริ่มต้นจะถูกใช้ รหัสมีดังนี้:
/** * สร้าง <tt> HashMap ที่ว่างเปล่า </tt> ด้วยความจุเริ่มต้นเริ่มต้น * (16) และปัจจัยการโหลดเริ่มต้น (0.75) */ public hashmap () {this (default_initial_capacity, default_load_factor); } /** * สร้าง <tt> hashmap ที่ว่างเปล่า < /tt> ด้วยความจุเริ่มต้น * เริ่มต้นที่ระบุและปัจจัยการโหลดเริ่มต้น (0.75) * * @param การเริ่มต้นความจุเริ่มต้น * @THROWS unglemalargumentException หากความสามารถเริ่มต้นเป็นลบ */ public hashmap (int initialcapacity) {this (initialcapacity, default_load_factor); } /** * สร้าง <tt> HashMap ที่ว่างเปล่า < /tt> ด้วยความจุเริ่มต้น * เริ่มต้นที่ระบุและปัจจัยโหลด * * @param การเริ่มต้นความจุเริ่มต้น * @param loadfactor ตัวประกอบโหลด * @throws ungloralargumentException หากความจุเริ่มต้นเป็นลบ * หรือปัจจัยโหลดเป็น nonpositive */ hashmap สาธารณะ if (initialCapacity> maximum_capacity) การเริ่มต้นการเริ่มต้น = maximum_capacity; if (loadfactor <= 0 || float.isnan (loadfactor)) โยน unlegalargumentException ใหม่ ("ปัจจัยโหลดที่ผิดกฎหมาย:" +loadfactor); this.loadfactor = loadfactor; threshold = initialCapacity; init (); -ดังที่เห็นได้จากด้านบนในคอนสตรัคเตอร์หากกำลังการผลิตเริ่มต้นสูงกว่าความจุสูงสุดความจุสูงสุดจะถูกแทนที่โดยตรง
ใส่วิธีการ
จากนั้นมาดูส่วนที่สำคัญกว่าของ hashmap
/*** ในแผนที่นี้ค่าที่ระบุและการสร้างที่ระบุจะเชื่อมโยง หากแผนที่ก่อนหน้านี้มีความสัมพันธ์การแมปของคีย์ค่าเก่าจะถูกแทนที่** @param ระบุคีย์ที่จะเชื่อมโยง* @param ระบุค่าที่จะเชื่อมโยง* @return ค่าเก่าที่เกี่ยวข้องกับคีย์ถ้าคีย์ไม่มีความสัมพันธ์การแมป {พองได้ (เกณฑ์); } if (key == null) return putfornullkey (ค่า); int hash = hash (คีย์); int i = indexfor (แฮช, table.length); สำหรับ (รายการ <k, v> e = ตาราง [i]; e! = null; e = e.next) {วัตถุ k; if (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.value; e.value = ค่า; E.RecordAccess (นี่); กลับ OldValue; }} ModCount ++; Addentry (แฮช, คีย์, ค่า, i); คืนค่า null; -1. ก่อนอื่นในวิธีการก่อนกำหนดว่าจะมีที่เก็บข้อมูลอยู่ในสถานะที่ไม่ได้กำหนดค่าเริ่มต้นหรือไม่ หากไม่ได้เริ่มต้นให้เรียกใช้วิธีการพองตัวเพื่อเริ่มต้นและจากนั้นพิจารณาว่าคีย์พารามิเตอร์นั้นเป็นโมฆะหรือไม่ หากเป็นโมฆะให้โทร PutforNullkey โดยเฉพาะเพื่อวางข้อมูลด้วยคีย์เป็น NULL วิธีการ PutforNullkey นั้นเหมือนกันกับขั้นตอนที่ 3 ต่อไปนี้ยกเว้นว่าตำแหน่งที่เก็บข้อมูลเริ่มต้นของข้อมูลที่มีคีย์เป็น null เป็นครั้งแรกนั่นคือตัวห้อยเริ่มต้นคือ 0
2. หากคีย์ไม่เป็นโมฆะให้เรียกใช้วิธีแฮช () เพื่อรับค่าแฮชของคีย์ คุณสามารถคำนวณตำแหน่งที่สามารถวางคีย์ในถังตามค่าแฮชและความยาวของถัง
3. มีแอตทริบิวต์ถัดไปในวัตถุรายการซึ่งสามารถสร้างรายการที่เชื่อมโยงทางเดียวเพื่อจัดเก็บองค์ประกอบที่มีค่าแฮชเดียวกัน ดังนั้นเมื่อคำนวณค่าแฮชของคีย์สถานที่จัดเก็บจะถูกทำซ้ำ เพียงตัดสินว่าองค์ประกอบของตำแหน่งที่เก็บข้อมูลและรายการแอตทริบิวต์ถัดไปขององค์ประกอบนั้นเหมือนกับค่าแฮชของคีย์และคีย์ที่กำหนด หากมีค่าที่สอดคล้องกันอย่างสมบูรณ์ก็หมายความว่ามีอยู่แล้วให้แทนที่ค่าเก่าและส่งคืนค่าเก่าโดยตรงเป็นค่าส่งคืน
4. เพิ่มจำนวนการปรับเปลี่ยนโครงสร้างโดย 1
5. เรียกใช้วิธี Addentry เพื่อเพิ่มคู่คีย์ค่าใหม่ลงใน HashMap วิธีการติดแสงก่อนกำหนดว่าข้อมูลรายการปัจจุบันมีค่ามากกว่าหรือเท่ากับค่าโหลด (ความจุของตัวประกอบภาระ *) และตำแหน่งที่ระบุของถังไม่ได้เป็นโมฆะ หากมีมากกว่าและตำแหน่งที่ระบุไม่ได้เป็นโมฆะความสามารถของถังปรับจะเป็นสองเท่าของความจุปัจจุบัน ความจุของถังปรับจะอ้างอิงถึง ความจุเริ่มต้นและไดเรกทอรีการปรับประสิทธิภาพการโหลดปัจจัย ด้านบน คำนวณค่าแฮชใหม่และคำนวณตำแหน่งที่เก็บข้อมูล โทรหาวิธี CreateEntry เพื่อเก็บไว้ในถัง
โมฆะ Addentry (int hash, k key, v ค่า V, int bucketindex) {ถ้า ((ขนาด> = threshold) && (null! = ตาราง [bucketindex])) {resize (2 * table.length); hash = (null! = key)? แฮช (กุญแจ): 0; BucketIndex = indexfor (แฮช, table.length); } createentry (แฮชคีย์ค่า bucketindex); } เป็นโมฆะ createentry (int hash, k key, v ค่า V, int bucketindex) {entry <k, v> e = ตาราง [bucketindex]; ตาราง [BucketIndex] = รายการใหม่ <> (แฮช, คีย์, ค่า, e); ขนาด ++; } /*** วิธีการสร้างรายการเพื่อสร้างรายการใหม่ */ entry (int h, k k, v v, รายการ <k, v> n) {value = v; ถัดไป = n; key = k; แฮช = h; -6. ในวิธี CreateEntry ก่อนอื่นรับรายการที่ตำแหน่งที่ระบุจากนั้นสร้างรายการใหม่ เมื่อสร้างรายการให้จัดเก็บรายการต้นฉบับลงในคุณสมบัติถัดไปของรายการที่สร้างขึ้นใหม่ (ดูวิธีการก่อสร้างรายการ) และแทนที่รายการที่ตำแหน่งที่ระบุด้วยรายการที่สร้างขึ้นใหม่
เนื่องจากเมื่อเพิ่มรายการใหม่ค่าแฮชจะต้องคำนวณและเมื่อความยาวไม่เพียงพอความยาวจะต้องปรับ เมื่อมีองค์ประกอบในตำแหน่งที่เก็บข้อมูลที่คำนวณได้รายการที่เชื่อมโยงจะต้องจัดเก็บดังนั้นประสิทธิภาพของการใช้ HASHMAP เพื่อเพิ่มการดำเนินการใหม่จึงไม่สูงเกินไป
รับวิธีการ
ก่อนอื่นมาดูซอร์สโค้ดของวิธีการ:
/*** ส่งคืนค่าที่แมปโดยคีย์ที่ระบุ; หากแผนที่นี้ไม่มีความสัมพันธ์การแมปใด ๆ สำหรับคีย์นี้มันจะส่งคืนค่า NULL * การส่งคืนค่า NULL ไม่ได้หมายความว่าแผนที่จะไม่มีการแมปของคีย์และอาจเปลี่ยนการแมปเป็น NULL คุณสามารถใช้การดำเนินการ containskey เพื่อแยกความแตกต่างระหว่างสองสถานการณ์นี้ * @see #put (วัตถุวัตถุ) */ สาธารณะ v รับ (คีย์วัตถุ) {ถ้า (key == null) ส่งคืน getForNullKey (); รายการ <k, v> entry = getentry (คีย์); ส่งคืน null == รายการ? null: entry.getValue (); } รายการสุดท้าย <k, v> getentry (คีย์วัตถุ) {ถ้า (ขนาด == 0) {return null; } int hash = (key == null)? 0: แฮช (กุญแจ); สำหรับ (รายการ <k, v> e = ตาราง [indexfor (แฮช, table.length)]; e! = null; e = e.next) {object k; if (e.hash == hash && ((k = e.key) == key || (key! = null && key.equals (k)))) กลับ e; } return null;}วิธี GET นั้นง่ายต่อการใช้งานและต่อไปนี้เป็นเพียงไม่กี่ขั้นตอน:
โดยการดูที่ซอร์สโค้ดของ GET เราจะพบว่าวิธี GET จะคำนวณตำแหน่งที่เก็บข้อมูลผ่านค่าแฮชของคีย์และความยาวของถัง โดยทั่วไปคุณสามารถค้นหาองค์ประกอบที่คุณกำลังมองหา แม้ว่าคุณจะสำรวจคีย์สองสามตัวด้วยค่าแฮชซ้ำ ๆ มันก็เร็วมาก เนื่องจากค่าแฮชค่อนข้างไม่ซ้ำกัน HashMap จึงรวดเร็วมากสำหรับการค้นหา
วัตถุที่กำหนดเองเป็นกุญแจสำคัญในการ hashmap
ผู้ใช้ในชั้นเรียน {// หมายเลข id ได้รับการป้องกัน int iDnumber; ผู้ใช้สาธารณะ (ID int) {idnumber = id; }} ผู้ทดสอบคลาสสาธารณะ {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {แผนที่ <ผู้ใช้, สตริง> แผนที่ = ใหม่ hashmap <ผู้ใช้, สตริง> (); สำหรับ (int i = 0; i <5; i ++) {map.put (ผู้ใช้ใหม่ (i), "ชื่อ:"+i); } system.out.println ("ชื่อผู้ใช้ 3:" + map.get (ผู้ใช้ใหม่ (3))); }} เอาต์พุต: ผู้ใช้ 3 ชื่อ: nullดังที่ได้กล่าวไว้ข้างต้นเมื่อใช้อินสแตนซ์คลาสผู้ใช้ที่กำหนดเองเป็นวัตถุ HashMap ชื่อของผู้ใช้ 3 ไม่สามารถพบได้เมื่อพิมพ์เนื่องจากคลาสผู้ใช้จะสืบทอดวัตถุคลาสพื้นฐานโดยอัตโนมัติดังนั้นวิธีการ HashCode ของวัตถุจะถูกใช้โดยอัตโนมัติเพื่อสร้างค่าแฮชและใช้ที่อยู่ของวัตถุเพื่อคำนวณค่าแฮชโดยค่าเริ่มต้น ดังนั้นค่าแฮชของอินสแตนซ์แรกที่สร้างโดยผู้ใช้ใหม่ (3) จึงแตกต่างจากค่าแฮชของอินสแตนซ์ที่สองที่สร้างขึ้น อย่างไรก็ตามหากคุณต้องการเพียงแค่แทนที่วิธี HashCode มันจะไม่ทำงานอย่างถูกต้องเว้นแต่คุณจะแทนที่วิธี Equals ในเวลาเดียวกันมันก็เป็นส่วนหนึ่งของวัตถุ HashMap ใช้ Equals () เพื่อตรวจสอบว่าคีย์ปัจจุบันเหมือนกับคีย์ที่มีอยู่ในตารางหรือไม่ คุณสามารถอ้างถึงวิธีการรับหรือใส่ด้านบน
วิธีการที่ถูกต้อง Equals () จะต้องเป็นไปตามเงื่อนไข 5 ข้อต่อไปนี้ :- อ้างถึง "ความคิดการเขียนโปรแกรม Java" -หน้า 489
อีกครั้ง : วัตถุเริ่มต้น equals () เป็นเพียงที่อยู่ของวัตถุเปรียบเทียบดังนั้นผู้ใช้ใหม่หนึ่งคน (3) ไม่เท่ากับผู้ใช้ใหม่รายอื่น (3) ดังนั้นหากคุณต้องการใช้คลาสของคุณเองเป็นกุญแจสู่ HashMap คุณจะต้องโอเวอร์โหลดทั้ง HashCode () และ Equals ()
รหัสต่อไปนี้ใช้งานได้ตามปกติ:
ผู้ใช้ในชั้นเรียน {// หมายเลข id ได้รับการป้องกัน int iDnumber; ผู้ใช้สาธารณะ (ID int) {idnumber = id; } @Override public int hashCode () {return idnumber; } @Override บูลีนสาธารณะเท่ากับ (Object obj) {return obj instanceof user && (idnumber == ((ผู้ใช้) obj) .idnumber); }} ผู้ทดสอบคลาสสาธารณะ {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {แผนที่ <ผู้ใช้, สตริง> แผนที่ = ใหม่ hashmap <ผู้ใช้, สตริง> (); สำหรับ (int i = 0; i <5; i ++) {map.put (ผู้ใช้ใหม่ (i), "ชื่อ:"+i); } system.out.println ("ชื่อผู้ใช้ 3:" + map.get (ผู้ใช้ใหม่ (3))); }} เอาต์พุต: ชื่อของผู้ใช้ 3 ชื่อ: 3 ชื่อ: 3ข้างต้นเพียงส่งคืน Idnumber เป็นเพียงการเลือกปฏิบัติใน HashCode และผู้ใช้ยังสามารถใช้วิธีการของตนเองตามธุรกิจของตนเอง ในวิธี Equals อินสแตนซ์ของจะตรวจสอบอย่างเงียบ ๆ ว่าวัตถุนั้นเป็นโมฆะหรือไม่ หากพารามิเตอร์ทางด้านซ้ายของอินสแตนซ์เป็นโมฆะเท็จจะถูกส่งคืน หากพารามิเตอร์ของ Equals () ไม่เป็นโมฆะและประเภทนั้นถูกต้องการเปรียบเทียบจะขึ้นอยู่กับ iDnumber จริงในแต่ละวัตถุ ดังที่เห็นได้จากเอาต์พุตวิธีการปัจจุบันถูกต้อง
อ้างถึง:
"ความคิดการเขียนโปรแกรม Java"
JDK 1.6 คู่มือช่วยเหลือจีน
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่าเนื้อหาของบทความนี้จะช่วยในการศึกษาหรือทำงานของทุกคน ฉันหวังว่าจะสนับสนุน Wulin.com เพิ่มเติม!