HashMap ยังเป็นคอลเลกชันที่เราใช้มาก เป็นการใช้งานอินเทอร์เฟซแผนที่ตามตารางแฮชและมีอยู่ในรูปแบบของคีย์-ค่า ใน HashMap ค่าคีย์จะถูกประมวลผลโดยรวมเสมอ ระบบจะคำนวณตำแหน่งที่เก็บข้อมูลของคีย์-ค่าตามอัลกอริทึมแฮช เราสามารถจัดเก็บและดึงค่าผ่านคีย์ได้อย่างรวดเร็ว มาวิเคราะห์การเข้าถึง HashMap
1. คำจำกัดความ
HashMap ใช้อินเทอร์เฟซแผนที่และสืบทอด AbstractMap อินเตอร์เฟส MAP กำหนดกฎสำหรับการแมปคีย์กับค่าและคลาส AbstractMap ให้การใช้งานแบ็คโบนของอินเตอร์เฟส MAP เพื่อลดงานที่จำเป็นในการใช้งานอินเทอร์เฟซนี้ ในความเป็นจริงคลาส AbstractMap ได้ใช้แผนที่ ฉันคิดว่ามันควรจะชัดเจนกว่าที่จะทำเครื่องหมายแผนที่ lz ที่นี่!
คลาสสาธารณะ hashmap <k, v> ขยาย AbstractMap <k, v> ใช้แผนที่ <k, v>, cloneable, serializable
2. ฟังก์ชั่นตัวสร้าง
HashMap จัดเตรียมผู้สร้างสามคน:
HashMap (): สร้าง HASHMAP ที่ว่างเปล่าด้วยความจุเริ่มต้นเริ่มต้น (16) และปัจจัยการโหลดเริ่มต้น (0.75)
HASHMAP (Int InitialCapacity): สร้าง HASHMAP ที่ว่างเปล่าด้วยความจุเริ่มต้นที่ระบุและปัจจัยการโหลดเริ่มต้น (0.75)
hashmap (int initialcapacity, float loadfactor): สร้าง hashmap ว่างที่มีความจุเริ่มต้นและปัจจัยการโหลดที่ระบุ
มีการกล่าวถึงพารามิเตอร์สองพารามิเตอร์ที่นี่: ความจุเริ่มต้นปัจจัยการโหลด พารามิเตอร์ทั้งสองนี้เป็นพารามิเตอร์สำคัญที่มีผลต่อประสิทธิภาพของ HashMap ความจุแสดงถึงจำนวนถังในตารางแฮช ความจุเริ่มต้นคือความจุเมื่อสร้างตารางแฮช ปัจจัยการโหลดเป็นสเกลที่ตารางแฮชสามารถเข้าถึงได้ก่อนที่ความจุจะเพิ่มขึ้นโดยอัตโนมัติ มันวัดระดับการใช้พื้นที่ตารางแฮช ยิ่งปัจจัยการโหลดมากขึ้นบ่งชี้ว่าระดับการโหลดของตารางแฮชที่สูงขึ้นและในทางกลับกัน สำหรับตารางแฮชที่ใช้วิธีการที่เชื่อมโยงเวลาเฉลี่ยในการค้นหาองค์ประกอบคือ O (1+A) ดังนั้นหากปัจจัยโหลดมีขนาดใหญ่ขึ้นพื้นที่จะถูกใช้อย่างเต็มที่มากขึ้น แต่ผลที่ตามมาคือการลดประสิทธิภาพการค้นหา หากปัจจัยการโหลดมีขนาดเล็กเกินไปข้อมูลของตารางแฮชจะกระจัดกระจายเกินไปทำให้เกิดของเสียร้ายแรงต่อพื้นที่ ปัจจัยโหลดเริ่มต้นของระบบคือ 0.75 และโดยทั่วไปเราไม่จำเป็นต้องแก้ไข
HashMap เป็นโครงสร้างข้อมูลที่รองรับการเข้าถึงที่รวดเร็ว เพื่อให้เข้าใจถึงประสิทธิภาพของมันคุณต้องเข้าใจโครงสร้างข้อมูล
iii. โครงสร้างข้อมูล
เรารู้ว่าทั้งสองโครงสร้างที่ใช้กันมากที่สุดใน Java คืออาร์เรย์และพอยน์เตอร์จำลอง (อ้างอิง) โครงสร้างข้อมูลเกือบทั้งหมดสามารถนำไปใช้ร่วมกับทั้งสองนี้และสิ่งเดียวกันนี้เป็นจริงสำหรับ HashMap ในความเป็นจริง HashMap เป็น "รายการแฮชที่เชื่อมโยง" ดังนี้โครงสร้างข้อมูล:
จากรูปด้านบนเราสามารถดูได้ว่าการใช้ HashMap เป็นพื้นฐานหรืออาร์เรย์ แต่ทุกรายการในอาร์เรย์เป็นโซ่ พารามิเตอร์เริ่มต้นความจุแสดงถึงความยาวของอาร์เรย์ ต่อไปนี้เป็นซอร์สโค้ดของตัวสร้าง HashMap:
public hashmap (int initialcapacity, float loadfactor) {// ความจุเริ่มต้นไม่สามารถ <0 ถ้า (initialcapacity <0) โยน unlegalargumentException ใหม่ ("ความจุเริ่มต้นที่ผิดกฎหมาย:" + การเริ่มต้น); // ความจุเริ่มต้นไม่สามารถ> ค่าความจุสูงสุดความจุสูงสุดของ HASHMAP คือ 2^30 ถ้า (การเริ่มต้นความจุ> maximum_capacity) การเริ่มต้นการเริ่มต้น = maximum_capacity; // ปัจจัยโหลดไม่สามารถ <0 ถ้า (loadfactor <= 0 || float.isnan (loadfactor)) โยน unlegalargumentException ใหม่ ("ปัจจัยโหลดที่ผิดกฎหมาย:" + loadfactor); // คำนวณค่า N-POWER ของค่าที่เล็กที่สุด 2 ที่มากกว่าการเริ่มต้น ความจุ int = 1; ในขณะที่ (ความจุ <เริ่มต้นความจุ) ความจุ << = 1; this.loadfactor = loadfactor; // ตั้งค่าขีด จำกัด กำลังการผลิตของ HashMap เมื่อความสามารถของ HashMap ถึงขีด จำกัด นี้การดำเนินการขยายกำลังการผลิตจะดำเนินการเกณฑ์ = (int) (ความจุ * loadfactor); // เริ่มต้นตารางอาร์เรย์ตาราง = รายการใหม่ [ความจุ]; init (); - ดังที่เห็นได้จากซอร์สโค้ดอาร์เรย์ตารางจะเริ่มต้นทุกครั้งที่สร้าง HASHMAP ใหม่ องค์ประกอบของอาร์เรย์ตารางเป็นโหนดรายการ
รายการคลาสคงที่ <k, v> ใช้ map.entry <k, v> {คีย์สุดท้าย k; ค่า V; รายการ <k, v> ถัดไป; แฮช int สุดท้าย; /*** สร้างรายการใหม่ */ entry (int h, k k, v v, รายการ <k, v> n) {value = v; ถัดไป = n; key = k; แฮช = h; -ในหมู่พวกเขารายการคือคลาสภายในของ HashMap ซึ่งมีคีย์คีย์ค่าค่าค่าโหนดถัดไปและค่าแฮช สิ่งนี้สำคัญมาก มันเป็นเพราะรายการแบบฟอร์มรายการของตารางตารางเป็นรายการที่เชื่อมโยง
การวิเคราะห์โครงสร้างข้อมูลของ HashMap สั้น ๆ ข้างต้นและด้านล่างจะสำรวจว่า HASHMAP ใช้การเข้าถึงอย่างรวดเร็วอย่างไร
4. การใช้งานที่เก็บข้อมูล: ใส่ (คีย์, vlaue)
ก่อนอื่นมาดูซอร์สโค้ด
Public V Put (k key, v value) {// เมื่อคีย์เป็น null วิธีการ putfornullkey วิธีการบันทึกตำแหน่งแรกของ null และตาราง นี่คือเหตุผลที่ HASHMAP อนุญาตให้ null ถ้า (key == null) return putfornullkey (ค่า); // คำนวณค่าแฮชของคีย์ int hash = hash (key.hashcode ()); ----- (1) // คำนวณตำแหน่งของค่าแฮชคีย์ในตารางอาร์เรย์ int i = indexfor (แฮช, table.length); ----- (2) // ซ้ำจาก i และค้นหาตำแหน่งที่คีย์ถูกบันทึกไว้สำหรับ (รายการ <k, v> e = ตาราง [i]; e! = null; e = e.next) {วัตถุ K; // ตัดสินว่ามีค่าแฮชเดียวกันในห่วงโซ่ (คีย์เหมือนกัน) // ถ้ามีอยู่เดียวกันจะเขียนทับค่าโดยตรงและส่งคืนค่าเก่าถ้า (e.hash == hash && ((k = e.key) == key || key.equals (k))) {v oldValue = e.value; // ค่าเก่า = ค่าใหม่ e.value = ค่า; E.RecordAccess (นี่); กลับ OldValue; // ส่งคืนค่าเก่า}} // เพิ่มจำนวนการแก้ไขโดย 1 modcount ++; // เพิ่มคีย์และค่าให้กับ Identry ตำแหน่ง I (แฮช, คีย์, ค่า, i); คืนค่า null; -ผ่านซอร์สโค้ดเราสามารถเห็นได้อย่างชัดเจนว่ากระบวนการของข้อมูลการบันทึก hashmap คือ: ก่อนอื่นกำหนดว่าคีย์นั้นเป็นโมฆะหรือไม่ หากเป็นโมฆะให้เรียกใช้วิธี putfornullkey โดยตรง หากไม่ว่างเปล่าให้คำนวณค่าแฮชของคีย์ก่อนจากนั้นค้นหาตำแหน่งดัชนีในอาร์เรย์ตารางตามค่าแฮช หากมีองค์ประกอบที่ตำแหน่งนี้ให้เปรียบเทียบว่ามีคีย์เดียวกันอยู่หรือไม่ หากมีอยู่ให้เขียนทับค่าของคีย์ดั้งเดิมมิฉะนั้นบันทึกองค์ประกอบที่หัวของห่วงโซ่ (องค์ประกอบแรกที่บันทึกไว้จะถูกวางไว้ที่ส่วนท้ายของห่วงโซ่) หากตารางไม่มีองค์ประกอบที่นั่นจะถูกบันทึกโดยตรง กระบวนการนี้ดูง่าย แต่จริงๆแล้วมันมีข้อมูลภายในลึก มีหลายจุดดังนี้:
1. มาดูการทำซ้ำก่อน เหตุผลของการทำซ้ำที่นี่คือการป้องกันการมีอยู่ของค่าคีย์เดียวกัน หากพบว่าค่าแฮชสองค่า (คีย์) เหมือนกันวิธีการประมวลผลของ HASHMAP คือการแทนที่ค่าเก่าด้วยค่าใหม่ คีย์ไม่ได้ประมวลผลที่นี่ซึ่งอธิบายว่าไม่มีปุ่มที่เหมือนกันสองปุ่มใน HashMap
2. ในมุมมอง (1) และ (2) นี่คือสาระสำคัญของ HashMap ก่อนอื่นมีวิธีแฮชซึ่งเป็นการคำนวณทางคณิตศาสตร์ที่บริสุทธิ์ซึ่งคือการคำนวณค่าแฮชของ H
hash int คงที่ (int h) {h ^ = (h >>> 20) ^ (h >>> 12); กลับ h ^ (h >>> 7) ^ (h >>> 4); -เรารู้ว่าสำหรับตาราง HASHMAP การกระจายข้อมูลจะต้องมีแม้กระทั่ง (เป็นการดีที่สุดที่จะมีองค์ประกอบเดียวสำหรับแต่ละรายการเพื่อให้สามารถพบได้โดยตรง) ไม่สามารถแน่นเกินไปหรือหลวมเกินไป แน่นเกินไปจะนำไปสู่ความเร็วในการสืบค้นช้าและหลวมเกินไปจะเสียพื้นที่ หลังจากคำนวณค่าแฮชเราจะมั่นใจได้อย่างไรว่าองค์ประกอบของตารางมีการกระจายอย่างเท่าเทียมกัน? เราจะนึกถึงการได้มาซึ่งแม่พิมพ์ แต่เนื่องจากการได้มาของแม่พิมพ์นั้นใช้จำนวนมาก HashMap จึงจัดการกับสิ่งนี้: เรียกวิธีการทำดัชนี
INTED INDET แบบคงที่ (int H, ความยาว int) {return H & (length-1); -ความยาวของอาร์เรย์พื้นฐานของ HashMap อยู่ที่ N-Power ของ 2 เสมอและมีอยู่ในตัวสร้าง: ความจุ << = 1; การทำเช่นนั้นสามารถตรวจสอบให้แน่ใจว่าความยาวของอาร์เรย์พื้นฐานของ HashMap อยู่ที่ N -Power ของ 2 เมื่อความยาวถึง N กำลัง 2, H & (ความยาว - 1) เทียบเท่ากับการใช้โมดูลัสของความยาวและความเร็วเร็วกว่าการใช้โมดูลัสโดยตรง นี่คือการเพิ่มประสิทธิภาพของ HashMap ในแง่ของความเร็ว สำหรับสาเหตุที่ 2 ถึงพลังที่ n คำอธิบายต่อไปนี้คือ
กลับไปที่เมธอดสำหรับดัชนีซึ่งมีเพียงคำสั่งเดียวเท่านั้น: H & (ความยาว - 1) นอกเหนือจากการดำเนินการโมดูลัสข้างต้นประโยคนี้ยังมีความรับผิดชอบที่สำคัญมาก: แจกจ่ายข้อมูลตารางอย่างสม่ำเสมอและใช้พื้นที่อย่างเต็มที่
ที่นี่เราคิดว่าความยาวคือ 16 (2^n) และ 15 และ H คือ 5, 6 และ 7
เมื่อ n = 15 ผลลัพธ์ของ 6 และ 7 จะเหมือนกันซึ่งหมายความว่าตำแหน่งของพวกเขาที่เก็บไว้ในตารางจะเหมือนกันนั่นคือการชนเกิดขึ้นและ 6 และ 7 จะสร้างรายการที่เชื่อมโยงในที่เดียวซึ่งจะนำไปสู่การลดลงของความเร็วในการสืบค้น มันเป็นความจริงที่มีการวิเคราะห์ตัวเลขเพียงสามตัวที่นี่ แต่ไม่มากนักดังนั้นลองดูที่ 0-15
จากแผนภูมิด้านบนเราเห็นการชนทั้งหมด 8 ครั้งและในเวลาเดียวกันเราพบว่าพื้นที่ที่สูญเปล่ามีขนาดใหญ่มากโดยไม่มีบันทึกใน 1, 3, 5, 7, 9, 11, 13, และ 15 สถานที่นั่นคือไม่มีการเก็บข้อมูล นี่เป็นเพราะเมื่อพวกเขาดำเนินการและดำเนินการด้วย 14 บิตสุดท้ายของผลลัพธ์ที่พวกเขาได้รับคือ 0 นั่นคือมันเป็นไปไม่ได้ที่จะเก็บข้อมูลที่ตำแหน่งของ 0001, 0011, 0101, 0111, 1001, 1011, 1101, 1111 และ 1111 เมื่อความยาว = 16, ความยาว 1 = 15 คือ 1111 จากนั้นเมื่อทำการดำเนินการต่ำและการดำเนินการค่ามักจะเหมือนกับค่าแฮชดั้งเดิมเสมอและเมื่อทำการดำเนินการบิตสูงค่าของมันจะเท่ากับค่าบิตต่ำ ดังนั้นเมื่อความยาว = 2^n ความน่าจะเป็นของการชนระหว่างค่าแฮชที่แตกต่างกันนั้นค่อนข้างเล็กซึ่งจะทำให้ข้อมูลกระจายอย่างสม่ำเสมอในอาร์เรย์ตารางและความเร็วในการสืบค้นจะเร็วขึ้น
ที่นี่เราตรวจสอบกระบวนการที่วางไว้: เมื่อเราต้องการเพิ่มค่าคีย์คู่ลงในแฮชแมประบบจะคำนวณค่าแฮชของคีย์ก่อนจากนั้นยืนยันตำแหน่งที่เก็บไว้ในตารางตามค่าแฮช หากไม่มีองค์ประกอบที่ตำแหน่งนี้ให้แทรกโดยตรง มิฉะนั้นจะวนซ้ำรายการองค์ประกอบ ณ จุดนั้นและเปรียบเทียบค่าแฮชของคีย์ตามนั้น หากค่าแฮชทั้งสองเท่ากันและค่าคีย์เท่ากัน (e.hash == hash && ((k = ekey) == คีย์ || key.equals (k))) ค่าของโหนดดั้งเดิมจะถูกเขียนทับด้วยค่าของรายการใหม่ หากค่าแฮชทั้งสองเท่ากัน แต่ค่าคีย์ไม่เท่ากันให้แทรกโหนดลงในส่วนหัวของรายการที่เชื่อมโยง สำหรับกระบวนการใช้งานเฉพาะให้ดูวิธีการเสริมดังต่อไปนี้:
โมฆะ Addentry (int hash, k key, v ค่า V, int bucketindex) {// รับรายการรายการ <k, v> e = ตาราง [bucketindex]; // ใส่รายการที่สร้างขึ้นใหม่ลงในดัชนี BucketIndex และปล่อยให้จุดเริ่มต้นใหม่ไปยังตารางรายการต้นฉบับ [BucketIndex] = รายการใหม่ <k, v> (แฮช, คีย์, ค่า, e); // หากจำนวนองค์ประกอบใน HashMap เกินขีด จำกัด ความจุจะมีขนาดใหญ่เป็นสองเท่าถ้า (ขนาด ++> = เกณฑ์) ปรับขนาด (2 * table.length); -มีสองจุดที่ควรทราบในวิธีนี้:
หนึ่งคือรุ่นของโซ่ นี่คือการออกแบบที่หรูหรามาก ระบบจะเพิ่มวัตถุรายการใหม่ให้กับ BucketIndex เสมอ หากมีวัตถุที่ BucketIndex วัตถุรายการที่เพิ่มขึ้นใหม่จะชี้ไปที่วัตถุรายการต้นฉบับสร้างห่วงโซ่รายการ อย่างไรก็ตามหากไม่มีวัตถุรายการที่ BucketIndex นั่นคือ E == NULL ดังนั้นจุดเข้าที่เพิ่มขึ้นใหม่จะเป็น NULL และจะไม่มีการสร้างห่วงโซ่รายการ
2. การขยายกำลังการผลิต
เมื่อจำนวนองค์ประกอบใน HASHMAP เพิ่มขึ้นความน่าจะเป็นของการชนจะยิ่งใหญ่ขึ้นเรื่อย ๆ และความยาวของรายการลิงก์ที่สร้างขึ้นจะนานขึ้นเรื่อย ๆ สิ่งนี้จะส่งผลกระทบต่อความเร็วของ HashMap อย่างหลีกเลี่ยงไม่ได้ เพื่อให้แน่ใจว่าประสิทธิภาพของ HASHMAP ระบบจะต้องขยายกำลังการผลิตในจุดวิกฤติที่แน่นอน จุดวิกฤตินี้คือเมื่อจำนวนองค์ประกอบใน HASHMAP เท่ากับความยาวของอาร์เรย์ตาราง* ปัจจัยโหลด แต่การปรับขนาดเป็นกระบวนการที่ใช้เวลานานมากเนื่องจากต้องคำนวณตำแหน่งของข้อมูลนี้ในอาร์เรย์ตารางใหม่และคัดลอก ดังนั้นหากเราคาดการณ์จำนวนองค์ประกอบใน HASHMAP จำนวนองค์ประกอบที่ตั้งไว้ล่วงหน้าสามารถปรับปรุงประสิทธิภาพของ HASHMAP ได้อย่างมีประสิทธิภาพ
5. การอ่านการใช้งาน: รับ (คีย์)
เมื่อเทียบกับการจัดเก็บ HashMap การถอนตัวค่อนข้างง่าย ค้นหารายการที่ดัชนีในอาร์เรย์ตารางผ่านค่าแฮชของคีย์จากนั้นส่งคืนค่าที่สอดคล้องกับคีย์
สาธารณะ v รับ (คีย์วัตถุ) {// ถ้า null ให้โทรหาวิธี getForNullkey เพื่อส่งคืนค่าที่สอดคล้องกันถ้า (key == null) ส่งคืน getForNullKey (); // คำนวณรหัสแฮชตามค่า hashcode ของคีย์ int hash = hash (key.hashcode ()); // นำค่าออกที่ดัชนีที่ระบุในตารางตารางสำหรับ (รายการ <k, v> e = ตาราง [indexfor (แฮช, ตารางความยาว)]; e! = null; e = e.next) {วัตถุ K; // หากคีย์ค้นหาเหมือนกับคีย์ค้นหาให้ส่งคืนค่าที่สอดคล้องกันถ้า (e.hash == hash && ((k = e.key) == key || key.equals (k))) ส่งคืน e.value; } return null; - ที่นี่ค่าที่สามารถเรียกคืนได้อย่างรวดเร็วตามคีย์ไม่เพียงแยกกันออกจากโครงสร้างข้อมูลของ HashMap แต่ยังมีส่วนเกี่ยวข้องกับการเข้า ดังที่ได้กล่าวไว้ก่อนหน้านี้ HashMap ไม่ได้จัดเก็บคีย์และค่าแยกต่างหากในขั้นตอนที่เก็บไว้ แต่ถูกประมวลผลเป็นค่าคีย์ทั้งหมดซึ่งเป็นวัตถุรายการ ในเวลาเดียวกันค่าจะเทียบเท่ากับไฟล์แนบของคีย์เท่านั้น ในระหว่างกระบวนการจัดเก็บข้อมูลระบบจะกำหนดตำแหน่งการจัดเก็บของรายการในอาร์เรย์ตารางตาม hashcode ของคีย์และในกระบวนการดึงข้อมูลวัตถุรายการที่สอดคล้องกันจะถูกนำออกไปตาม hashcode ของคีย์
ลิงค์ดั้งเดิม: http://www.cnblogs.com/chenssy/p/3521565.html
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ ฉันหวังว่ามันจะเป็นประโยชน์ต่อการเรียนรู้ของทุกคนและฉันหวังว่าทุกคนจะสนับสนุน wulin.com มากขึ้น