แฮชที่สมบูรณ์แบบแบบคงที่

นิยามของ Perfect Hashing

Perfect hashing ถูกกำหนดให้เป็นแบบจำลองของการ hash ซึ่งชุดขององค์ประกอบ n ใดๆ สามารถจัดเก็บในตารางแฮชที่มีขนาดเท่ากัน และสามารถดำเนินการค้นหาได้ในเวลาคงที่ มันถูกคิดค้นและอภิปรายโดยเฉพาะโดย Fredman, Komlos และ Szemeredi (1984) ดังนั้นจึงมีชื่อเล่นว่า "FKS Hashing"

นิยามของ Static Hashing

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

ใบสมัคร

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

การนำไปใช้

ในกรณีคงที่ เราจะได้รับชุดที่มีรายการ p ทั้งหมด โดยแต่ละรายการจะเชื่อมโยงกับคีย์ที่ไม่ซ้ำกันล่วงหน้า Fredman, Komlós และ Szemerédi เลือกตารางแฮชระดับแรกที่มีที่เก็บข้อมูลขนาด s =2(p-1) ในการสร้าง รายการ p จะถูกแยกออกเป็น q buckets โดยฟังก์ชัน hashing ระดับบนสุด โดยที่ q =2(p-1) จากนั้นสำหรับบัคเก็ตแต่ละรายการที่มีรายการ r ตารางระดับที่สองจะถูกจัดสรรด้วยสล็อต r2 และฟังก์ชันแฮชจะถูกเลือกแบบสุ่มจากชุดฟังก์ชันแฮชสากลเพื่อไม่ให้เกิดการชนกันและจัดเก็บไว้ข้างตารางแฮช หากสุ่มเลือกฟังก์ชันแฮชสร้างตารางที่มีการชนกัน ฟังก์ชันแฮชใหม่จะถูกสุ่มเลือกจนกว่าจะรับประกันตารางที่ไม่มีการชนกัน ในที่สุด ด้วยแฮชที่ไม่มีการชนกัน รายการ r จะถูกแฮชลงในตารางระดับที่สอง