หลักการทำงานของ HashMap เป็นคำถามสัมภาษณ์ Java ทั่วไปในช่วงไม่กี่ปีที่ผ่านมา เกือบทุกโปรแกรมโปรแกรมเมอร์ Java รู้ว่า HashMap รู้ว่าจะใช้ HashMap ที่ไหนและรู้ถึงความแตกต่างระหว่างแฮชและ HashMap เหตุใดคำถามการสัมภาษณ์นี้จึงพิเศษ? นี่เป็นเพราะคำถามนี้ลึกมาก คำถามนี้มักจะปรากฏในการสัมภาษณ์ระดับสูงหรือระดับกลาง ธนาคารเพื่อการลงทุนต้องการถามคำถามนี้และอาจขอให้คุณใช้ HashMap เพื่อตรวจสอบทักษะการเขียนโปรแกรมของคุณ การแนะนำของชุดพร้อมกันและชุดซิงโครนัสอื่น ๆ ทำให้ปัญหานี้ซับซ้อนมากขึ้น มาเริ่มการเดินทางของการสำรวจกันเถอะ!
มามีคำถามง่ายๆก่อน
"คุณเคยใช้ HashMap หรือไม่" "Hashmap คืออะไรทำไมคุณถึงใช้มัน"
เกือบทุกคนจะตอบว่า "ใช่" จากนั้นตอบคุณลักษณะบางอย่างของ HashMap เช่น HASHMAP สามารถยอมรับค่าและค่าคีย์ NULL ในขณะที่ Hashtable ไม่สามารถ; HashMap ไม่ได้ซิงโครไนซ์ HashMap เร็ว และ HashMap เก็บคู่คีย์-ค่า ฯลฯ สิ่งนี้แสดงให้เห็นว่าคุณเคยใช้ HashMap และค่อนข้างคุ้นเคยกับมัน แต่ผู้สัมภาษณ์หันมาอย่างรวดเร็วและเริ่มถามคำถามที่ยุ่งยากจากนี้ไปเกี่ยวกับรายละเอียดพื้นฐานเพิ่มเติมของ HashMap ผู้สัมภาษณ์อาจถามคำถามต่อไปนี้:
"คุณรู้หรือไม่ว่า HASHMAP ทำงานอย่างไร" "คุณรู้หรือไม่ว่าวิธีการของ HashMap Get () ทำงานอย่างไร"
คุณอาจตอบว่า“ ฉันไม่ได้ค้นหา Java API มาตรฐานในรายละเอียดคุณสามารถดูซอร์สโค้ด Java หรือเปิด JDK ได้” “ ฉันสามารถหาคำตอบกับ Google ได้”
แต่ผู้สัมภาษณ์บางคนอาจสามารถให้คำตอบได้ "HashMap ขึ้นอยู่กับหลักการของการแฮชเราใช้ (คีย์, ค่า) เพื่อจัดเก็บวัตถุลงในแฮชแมปและใช้ Get (กุญแจ) เพื่อรับวัตถุจาก HashMap เมื่อเราผ่านการใช้งาน จุดสำคัญที่นี่คือการชี้ให้เห็นว่า hashmap เก็บวัตถุคีย์และวัตถุค่าในถังเป็น map.entry สิ่งนี้ช่วยให้เข้าใจตรรกะของการได้รับวัตถุ หากคุณไม่ได้ตระหนักถึงสิ่งนี้หรือคิดผิดว่าคุณเพียงแค่เก็บค่าในถังคุณจะไม่ตอบตรรกะของวิธีการรับวัตถุจาก HashMap คำตอบนี้ค่อนข้างถูกต้องและยังแสดงให้เห็นว่าผู้สัมภาษณ์รู้จักการแฮชและวิธีการทำงานของ HASHMAP แต่นี่เป็นเพียงจุดเริ่มต้นของเรื่อง เมื่อผู้สัมภาษณ์เข้าร่วมฉากจริงบางฉากที่โปรแกรมเมอร์ Java ต้องพบทุกวันคำตอบที่ผิดจะปรากฏขึ้นบ่อยครั้ง คำถามต่อไปอาจเกี่ยวกับการตรวจจับการชนใน HashMap และการแก้ปัญหาการชน:
"จะเกิดอะไรขึ้นเมื่อแฮชโค้ดของวัตถุสองชิ้นเหมือนกัน" จากที่นี่ความสับสนที่แท้จริงเริ่มต้นขึ้นและผู้สัมภาษณ์บางคนจะตอบว่าเนื่องจาก hashcode เหมือนกันวัตถุทั้งสองมีค่าเท่ากันและ HashMap จะโยนข้อยกเว้นหรือพวกเขาจะไม่ถูกเก็บไว้ จากนั้นผู้สัมภาษณ์อาจเตือนพวกเขาว่ามีสองวิธี: Equals () และ HashCode () และบอกพวกเขาว่าแม้ว่า hashcode จะเหมือนกันพวกเขาอาจไม่เท่ากัน ผู้สัมภาษณ์บางคนอาจยอมแพ้ในขณะที่คนอื่นสามารถก้าวต่อไปได้ พวกเขาตอบว่า "เนื่องจาก hashcode เหมือนกันตำแหน่งถังของพวกเขาเหมือนกันและ 'การชนกัน' จะเกิดขึ้นเนื่องจาก HashMap ใช้รายการที่เชื่อมโยงเพื่อจัดเก็บวัตถุรายการนี้ (วัตถุ Map.entry ที่มีคู่คีย์-ค่า) จะถูกเก็บไว้ในรายการที่เชื่อมโยง" คำตอบนี้สมเหตุสมผลมาก แม้ว่าจะมีหลายวิธีในการจัดการกับการชน แต่วิธีนี้เป็นวิธีที่ง่ายที่สุดและเป็นวิธีการประมวลผลของ Hashmap แต่เรื่องราวยังไม่เสร็จและผู้สัมภาษณ์จะถามต่อไป:
"ถ้าแฮชโฟนของปุ่มทั้งสองเหมือนกันคุณจะได้รับวัตถุค่าได้อย่างไร" ผู้สัมภาษณ์จะตอบ: เมื่อเราเรียกเมธอด Get () HashMap จะใช้ HashCode ของวัตถุคีย์เพื่อค้นหาตำแหน่งที่เก็บข้อมูลจากนั้นรับวัตถุค่า ผู้สัมภาษณ์เตือนเขาว่าหากมีการเก็บวัตถุมูลค่าสองรายการไว้ในถังเดียวกันเขาจะให้คำตอบ: รายการที่เชื่อมโยงจะถูกข้ามจนกว่าจะพบวัตถุค่า ผู้สัมภาษณ์จะถามเพราะคุณไม่มีวัตถุที่มีค่าที่จะเปรียบเทียบคุณระบุว่าจะค้นหาวัตถุที่มีค่าได้อย่างไร? เว้นแต่ผู้สัมภาษณ์จะเก็บคู่คีย์-ค่าในรายการที่เชื่อมโยงจนกระทั่ง HashMap เก็บไว้ในรายการที่เชื่อมโยงพวกเขาจะไม่สามารถตอบคำถามนี้ได้
ผู้สัมภาษณ์บางคนที่จำจุดความรู้ที่สำคัญนี้จะบอกว่าหลังจากค้นหาตำแหน่งที่เก็บข้อมูลพวกเขาจะเรียกวิธีการ keys.equals () เพื่อค้นหาโหนดที่ถูกต้องในรายการที่เชื่อมโยงและในที่สุดก็พบวัตถุค่าที่จะพบ คำตอบที่สมบูรณ์แบบ!
ในหลายกรณีผู้สัมภาษณ์จะทำผิดพลาดในลิงค์นี้เพราะพวกเขาสับสนวิธีการ HashCode () และเท่ากับ () เพราะก่อนหน้านี้ HashCode () จะปรากฏซ้ำ ๆ และวิธี Equals () จะปรากฏขึ้นเมื่อได้รับวัตถุค่าเท่านั้น นักพัฒนาที่ยอดเยี่ยมบางคนจะชี้ให้เห็นว่าการใช้วัตถุที่ไม่เปลี่ยนแปลงประกาศเป็นขั้นสุดท้ายและการใช้วิธีการที่เหมาะสม () และวิธีการ HashCode () จะช่วยลดการเกิดการชนและปรับปรุงประสิทธิภาพ ความไม่สามารถเปลี่ยนแปลงได้ช่วยให้แฮชโค้ดของคีย์ต่าง ๆ ถูกแคชซึ่งจะเพิ่มความเร็วในการรับวัตถุทั้งหมด การใช้คลาส wrapper เช่นสตริงและ interger เป็นคีย์เป็นตัวเลือกที่ดีมาก
หากคุณคิดว่ามันอยู่ที่นี่คุณจะประหลาดใจเมื่อได้ยินคำถามต่อไปนี้ "จะเกิดอะไรขึ้นถ้าขนาดของ HashMap เกินความสามารถที่กำหนดโดยปัจจัยโหลด?" หากคุณไม่ทราบว่า HASHMAP ทำงานอย่างไรคุณจะไม่ตอบคำถามนี้ ขนาดปัจจัยโหลดเริ่มต้นคือ 0.75 กล่าวคือเมื่อแผนที่เติมถัง 75% เช่นเดียวกับคลาสคอลเลกชันอื่น ๆ (เช่น ArrayList ฯลฯ ) อาร์เรย์ถังที่มีขนาดเท่ากันสองเท่าของ HashMap ดั้งเดิมจะถูกสร้างขึ้นเพื่อปรับขนาดแผนที่และใส่วัตถุดั้งเดิมลงในอาร์เรย์ถังใหม่ กระบวนการนี้เรียกว่าการฟื้นฟูเนื่องจากวิธีการแฮชเพื่อค้นหาตำแหน่งถังใหม่
หากคุณสามารถตอบคำถามนี้ได้คำถามต่อไปนี้มา: "คุณเข้าใจไหมว่ามีปัญหาอะไรบ้างในการปรับขนาด HASHMAP" คุณอาจไม่สามารถตอบได้ ในเวลานี้ผู้สัมภาษณ์จะเตือนคุณว่าเมื่อมัลติเธรดอาจมีเงื่อนไขการแข่งขัน
เมื่อปรับขนาด HashMap มีการแข่งขันแบบมีเงื่อนไขอย่างแท้จริงเพราะหากทั้งสองเธรดพบว่าต้องมีการปรับขนาด HashMap พวกเขาจะพยายามปรับขนาดในเวลาเดียวกัน ในระหว่างกระบวนการปรับขนาดลำดับขององค์ประกอบที่เก็บไว้ในรายการที่เชื่อมโยงจะถูกย้อนกลับเพราะเมื่อย้ายไปยังตำแหน่งถังใหม่ HashMap ไม่ได้วางองค์ประกอบในตอนท้ายของรายการที่เชื่อมโยง แต่ที่หัวซึ่งจะหลีกเลี่ยงการข้ามหาง หากการแข่งขันแบบมีเงื่อนไขเกิดขึ้นจะมีวงจรอุบาทว์ ในเวลานี้คุณสามารถถามผู้สัมภาษณ์ว่าทำไมมันแปลกที่คุณต้องใช้ HashMap ในสภาพแวดล้อมแบบมัลติเธรด -
ผู้อ่านที่กระตือรือร้นสนับสนุนคำถามเพิ่มเติมเกี่ยวกับ HashMap:
1. เหตุใดคลาส wrapper จึงชอบสตริงและ Interger เหมาะกับปุ่ม? คลาส wrapper เช่น String และ Interger นั้นเหมาะสมที่สุดในฐานะคีย์ HashMap และสตริงเป็นที่ใช้กันมากที่สุด เนื่องจากสตริงไม่เปลี่ยนรูปและสุดท้ายและวิธีการ Equals () และ HashCode () ได้รับการเขียนใหม่ คลาส wrapper อื่น ๆ ยังมีคุณสมบัตินี้ ความไม่สามารถเปลี่ยนแปลงได้เป็นสิ่งจำเป็นเนื่องจากเพื่อคำนวณ HashCode () คุณต้องป้องกันไม่ให้ค่าคีย์เปลี่ยน หากค่าคีย์ส่งคืนแฮชโค้ดที่แตกต่างกันเมื่อใส่และรับคุณไม่พบวัตถุที่คุณต้องการจากแฮชแมป ความไม่สามารถเปลี่ยนแปลงได้มีข้อได้เปรียบอื่น ๆ เช่นความปลอดภัยของด้าย หากคุณสามารถรับประกันได้ว่า hashcode ไม่เปลี่ยนแปลงเพียงแค่ประกาศฟิลด์เป็นขั้นสุดท้ายโปรดทำเช่นนั้น เนื่องจากวิธี Equals () และ hashCode () ถูกใช้เมื่อได้รับวัตถุจึงเป็นสิ่งสำคัญมากที่จะเขียนทั้งสองวิธีนี้ใหม่อย่างถูกต้อง หากวัตถุที่ไม่เท่ากันสองรายการส่งคืนแฮชโค้ดที่แตกต่างกันโอกาสในการชนจะเล็กลงซึ่งสามารถปรับปรุงประสิทธิภาพของ HashMap
2. เราสามารถใช้วัตถุที่กำหนดเองเป็นปุ่มได้หรือไม่? นี่คือส่วนขยายของคำถามก่อนหน้า แน่นอนว่าคุณอาจใช้วัตถุใด ๆ เป็นคีย์ตราบใดที่มันเป็นไปตามกฎการกำหนดของเท่ากับ () และวิธีการ hashcode () และจะไม่เปลี่ยนแปลงอีกครั้งหลังจากที่วัตถุถูกแทรกลงในแผนที่ หากวัตถุที่กำหนดเองนี้ไม่เปลี่ยนรูปนั้นจะเป็นไปตามเงื่อนไขเป็นคีย์แล้วเพราะไม่สามารถเปลี่ยนแปลงได้หลังจากสร้างขึ้น
3. เราสามารถใช้ cocurrenthashmap เพื่อแทนที่แฮชแต้มได้หรือไม่? นี่เป็นคำถามสัมภาษณ์ที่ได้รับความนิยมอย่างมากเพราะผู้คนจำนวนมากขึ้นใช้งานพร้อมกัน เรารู้ว่าการเชื่อมต่อแบบแฮชนั้นมีการซิงโครไนซ์ แต่การซิงโครไนซ์พร้อมกันนั้นดีกว่าเพราะมันล็อคส่วนหนึ่งของแผนที่ตามระดับการซิงโครไนซ์ ConcurrentHashMap สามารถแทนที่ Hashtable ได้อย่างแน่นอน แต่ Hashtable ให้ความปลอดภัยของด้ายที่แข็งแกร่งขึ้น ตรวจสอบบล็อกนี้เพื่อดูความแตกต่างระหว่าง Hashtable และพร้อมกัน
โดยส่วนตัวแล้วฉันชอบคำถามนี้มากเพราะความลึกและความกว้างของคำถามนี้ไม่ได้เกี่ยวข้องกับแนวคิดที่แตกต่างโดยตรง มาดูกันว่าจุดความรู้เกี่ยวกับการออกแบบคำถามเหล่านี้:
สรุป
HASHMAP ทำงานได้อย่างไร
HashMap ขึ้นอยู่กับหลักการแฮชและเราจัดเก็บและรับวัตถุผ่านวิธีการใส่ () และรับ () เมื่อเราผ่านคู่คีย์-ค่าไปยังเมธอด put () จะเรียกวิธี HashCode () ของวัตถุคีย์เพื่อคำนวณ hashCode จากนั้นค้นหาตำแหน่งที่เก็บข้อมูลเพื่อเก็บวัตถุค่า เมื่อได้รับวัตถุจะพบคู่คีย์-ค่าที่ถูกต้องผ่านวิธี Equals () ของวัตถุคีย์และจากนั้นวัตถุค่าจะถูกส่งคืน HashMap ใช้รายการที่เชื่อมโยงเพื่อแก้ปัญหาการชน เมื่อมีการชนกันวัตถุจะถูกเก็บไว้ในโหนดถัดไปของรายการที่เชื่อมโยง HashMap จัดเก็บวัตถุคู่คีย์-ค่าในแต่ละรายการรายการที่เชื่อมโยง
จะเกิดอะไรขึ้นเมื่อแฮชโค้ดของวัตถุคีย์สองวัตถุที่แตกต่างกันเหมือนกัน? พวกเขาจะถูกเก็บไว้ในรายการที่เชื่อมโยงในตำแหน่งที่เก็บข้อมูลเดียวกัน วิธี Equals () ของวัตถุคีย์ใช้เพื่อค้นหาคู่คีย์-ค่า
เนื่องจาก HASHMAP มีประโยชน์มากมายฉันจึงใช้ HASHMAP เป็นแคชในแอปพลิเคชันอีคอมเมิร์ซ เนื่องจาก Java ถูกใช้มากในด้านการเงินและสำหรับการพิจารณาประสิทธิภาพเราจึงใช้ HashMap และพร้อมกัน คุณสามารถดูบทความเพิ่มเติมเกี่ยวกับ HashMap:
ความแตกต่างระหว่าง HashMap และ Hashtable
ความแตกต่างระหว่าง hashmap และ hashset
ลิงค์ต้นฉบับ: Javarevisited Translation: importNew.com - Tang Xiaojuan Translation Link: http://www.importnew.com/7099.html