Hashtable คืออะไร?

ในวิทยาการคอมพิวเตอร์ Hashtable เป็นโครงสร้างข้อมูลสำหรับการจัดเก็บข้อมูลที่ประกอบด้วยรายการค่าที่เรียกว่าคีย์ซึ่งได้รับการจับคู่กับรายการค่าที่สอดคล้องกันเรียกว่าอาร์เรย์ตัวอย่างเช่นชื่อธุรกิจอาจถูกจับคู่กับที่อยู่โดยทั่วไปค่าแต่ละค่าในอาร์เรย์จะมีหมายเลขตำแหน่งที่เรียกว่าแฮชฟังก์ชั่นแฮชโดยทั่วไปเป็นชุดของคำแนะนำหรืออัลกอริทึมที่แมปแต่ละค่าคีย์กับแฮช mdash;การเชื่อมต่อชื่อธุรกิจกับที่อยู่หมายเลขโทรศัพท์และหมวดหมู่ธุรกิจวัตถุประสงค์ของฟังก์ชั่นแฮชคือการกำหนดแต่ละคีย์ให้กับค่าที่สอดคล้องกันที่ไม่ซ้ำกันในอาร์เรย์นี่มักจะเรียกว่าการแฮชฟังก์ชั่นแฮชจะต้องจัดรูปแบบอย่างเหมาะสมสำหรับแฮชช์เพื่อทำงานอย่างถูกต้อง

ประสิทธิภาพของแฮชช์ในชุดข้อมูลขึ้นอยู่กับประสิทธิภาพของฟังก์ชันแฮชฟังก์ชั่นแฮชที่ดีมักจะให้การค้นหาที่สม่ำเสมอของคีย์และการแจกแจงการแมปอย่างสม่ำเสมอในอาร์เรย์ที่เกี่ยวข้องการชนกันของแฮชเกิดขึ้นเมื่อมีการกำหนดปุ่มสองปุ่มให้กับค่าที่สอดคล้องกันเดียวกันเมื่อการชนกันของแฮชเกิดขึ้นฟังก์ชันแฮชมักจะดำเนินการอีกครั้งจนกว่าจะพบค่าที่สอดคล้องกันที่ไม่ซ้ำกันสิ่งนี้ส่งผลให้เกิดการแฮชนานขึ้นแม้ว่าจำนวนคีย์ในแฮชแต้มจะได้รับการแก้ไข แต่บางครั้งอาจมีคีย์ซ้ำถึงกระนั้นแฮชแฮชที่ออกแบบมาอย่างดีก็มีฟังก์ชั่นแฮชที่มีประสิทธิภาพที่แมปคีย์แต่ละอันกับค่าที่สอดคล้องกันในอาร์เรย์

บางครั้งฟังก์ชั่นแฮชที่ไม่มีประสิทธิภาพในแฮชช์อาจสร้างกลุ่มของการแมปหากฟังก์ชั่นแฮชสร้างคลัสเตอร์ของการแมปสำหรับคีย์ที่มีอยู่สิ่งนี้สามารถเพิ่มระยะเวลาที่ใช้ในการค้นหาค่าที่เกี่ยวข้องสิ่งนี้สามารถชะลอการแฮชสำหรับคีย์ในอนาคตเนื่องจากฟังก์ชั่นแฮชส่วนใหญ่โดยทั่วไปจะมองหาตำแหน่งที่มีอยู่ในอาร์เรย์หากมีการกำหนดค่ากลุ่มจำนวนมากไปแล้วโดยทั่วไปแล้วจะใช้เวลานานกว่านี้ในการค้นหาค่าที่ไม่ได้กำหนดสำหรับคีย์ใหม่

ปัจจัยโหลดเป็นอีกแนวคิดหนึ่งที่เกี่ยวข้องกับประสิทธิภาพของฟังก์ชันแฮช;ปัจจัยโหลดคือปริมาณของแฮชชิงที่มีอยู่แล้วซึ่งสัมพันธ์กับขนาดโดยรวมของอาร์เรย์ที่เกี่ยวข้องในแฮชมันมักจะถูกกำหนดโดยการหารจำนวนคีย์ที่กำหนดแล้วด้วยขนาดของอาร์เรย์ที่เกี่ยวข้องเมื่อปัจจัยการโหลดเพิ่มขึ้นฟังก์ชั่นแฮชที่ดีมักจะยังคงรักษาจำนวนการชนและกลุ่มจนถึงจุดหนึ่งบ่อยครั้งที่เกณฑ์นี้สามารถใช้เพื่อกำหนดว่าฟังก์ชั่นแฮชที่มีประสิทธิภาพมีจำนวนคีย์ที่กำหนดและเมื่อต้องการฟังก์ชั่นแฮชใหม่

นักวิจัยวิทยาศาสตร์คอมพิวเตอร์จำนวนมากพยายามสร้างฟังก์ชั่นแฮชที่สมบูรณ์แบบ mdash;สิ่งหนึ่งที่ไม่ก่อให้เกิดการชนหรือกลุ่มเนื่องจากปัจจัยโหลดที่เพิ่มขึ้นในทางทฤษฎีกุญแจสำคัญในการผลิตแฮชช์ที่สมบูรณ์แบบคือการสร้างฟังก์ชั่นแฮชที่สมบูรณ์แบบโดยทั่วไปนักวิจัยเชื่อว่าฟังก์ชั่นแฮชที่สมบูรณ์แบบควรมีประสิทธิภาพอย่างต่อเนื่อง mdash;จำนวนการชนและกลุ่ม mdash;ด้วยปัจจัยโหลดที่เพิ่มขึ้นในสถานการณ์กรณีที่เลวร้ายที่สุดฟังก์ชั่นแฮชที่สมบูรณ์แบบจะยังคงอนุญาตให้แฮชคงที่โดยไม่ถึงธรณีประตู