หมายเลขถังแฮชเชิลมักจะทำการวิเคราะห์จำนวนที่สำคัญ

เหตุใดถังแฮชแต้มจึงใช้หมายเลขที่สำคัญ?

มีฟังก์ชั่นแฮช

h (c) = c % n;

เมื่อ n ใช้หมายเลขคอมโพสิตตัวอย่างที่ง่ายที่สุดคือใช้ 2^n ตัวอย่างเช่นใช้ 2^3 = 8 ในเวลานี้

H (11100 (ไบนารี)) = H (28) = 4
H (10100 (ไบนารี)) = H (20) = 4

ในเวลานี้บิตที่ 4 ของไบนารี (จากขวาไปซ้าย) ของ C จะ "ล้มเหลว" ซึ่งหมายความว่าไม่ว่าจะมีค่าใดในบิตที่ 4 ของ C มันจะนำไปสู่ค่าเดียวกันของ H (C) ในเวลานี้บิตที่สี่ของ C ไม่ได้มีส่วนร่วมในการดำเนินงานของ H (c) เลยดังนั้น H (c) จึงไม่สามารถสะท้อนลักษณะของ C ได้อย่างเต็มที่เพิ่มโอกาสของความขัดแย้ง

เมื่อใช้หมายเลขคอมโพสิตอื่น ๆ บิตบางตัวของ C จะ "ล้มเหลว" ถึงองศาที่แตกต่างกันส่งผลให้เกิดความขัดแย้งในแอปพลิเคชันทั่วไปบางอย่าง

อย่างไรก็ตามการใช้ตัวเลขที่สำคัญสามารถตรวจสอบให้แน่ใจว่าแต่ละบิตมีส่วนร่วมในการดำเนินงานของ H (c) ซึ่งจะช่วยลดโอกาสของความขัดแย้งในแอปพลิเคชันทั่วไป -

(ความเห็นส่วนตัว: บางครั้งประสิทธิภาพของการไม่ใช้ตัวเลขที่สำคัญก็ไม่ได้เลวร้ายเกินไป ... แต่มันปลอดภัยกว่าที่จะต้องใช้ตัวเลขที่สำคัญยิ่งขึ้น ... )

ข้างต้นคือความเข้าใจของฉัน

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

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

สิ่งที่คุณพูดเป็นสถานการณ์พิเศษเพราะเมื่อเลือกหมายเลขเฉพาะที่ค่อนข้างเล็กเมื่อเลือกหมายเลขสำคัญขนาดใหญ่ N จะล้มเหลวในระบบ N-Digit เพียงบิต เมื่อรวมกับคุณสมบัติของระบบคอมพิวเตอร์การเป็นตัวแทน N-Digit มักจะไม่สำคัญในขณะที่ระบบ 2^n-Digit ที่ใช้กันทั่วไปนั้นมีความสำคัญมากขึ้นดังนั้นจึงสามารถหลีกเลี่ยงความขัดแย้งได้

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

คุณอาจทำการทดลองของคุณเองไม่เลือกจำนวนเต็มแบบสุ่ม แต่พิจารณาแอปพลิเคชันทั่วไปบางอย่างใช้ตัวเลขที่สำคัญและหมายเลขคอมโพสิตเพื่อทดสอบส่วนใหญ่ตรวจสอบปัจจัยการโหลดโดยเฉลี่ยและข้อสรุปที่คุณได้รับอาจเป็นของฉัน: ตัวเลขคอมโพสิตก็ดีที่สุด

โดยส่วนตัวแล้วฉันคิดว่าโดยทั่วไปถ้าคุณไม่ได้ใช้ตัวเลขที่สำคัญจะมีอันตรายบางอย่าง อันตรายเกิดขึ้นเมื่อหมายเลขที่ไม่ใช่ครั้งแรก m = x*y ถูกเลือกให้เลือกและหากกุญแจของแฮชเกิดขึ้นที่เกี่ยวข้องกับตัวหารนี้ X มันจะน่าสังเวช ในกรณีที่เลวร้ายที่สุดทุกคนคิดว่ามันเป็นทวีคูณของ x จากนั้นคุณสามารถจินตนาการได้ว่าผลลัพธ์ของแฮชคือ: 1 ~ y ไม่ใช่ 1 ~ m อย่างไรก็ตามหากขนาดของถังถูกเลือกเป็นหมายเลขเฉพาะจะไม่มีปัญหา

ขอบคุณสำหรับการอ่านฉันหวังว่ามันจะช่วยคุณได้ ขอบคุณสำหรับการสนับสนุนเว็บไซต์นี้!