เกี่ยวกับฟังก์ชันแฮชที่ป้องกันการชนกัน ใน Introduction to Modern Cryptography ของ Katz
6.1 คำจำกัดความ
ฟังก์ชันแฮชเป็นเพียงฟังก์ชันที่รับอินพุตที่มีความยาวและ
บีบอัดให้เป็นเอาต์พุตสั้นและยาวคงที่การใช้แบบคลาสสิกของ (ไม่ใช่
cryptographic) ฟังก์ชันแฮชอยู่ในโครงสร้างข้อมูลที่สามารถใช้
สร้างตารางแฮชที่เปิดใช้งาน O(1) เวลาในการค้นหาเมื่อจัดเก็บชุดองค์ประกอบ
โดยเฉพาะอย่างยิ่ง ถ้าช่วงของฟังก์ชันแฮช H มีขนาดเท่ากับ N ดังนั้นองค์ประกอบ x
ถูกจัดเก็บไว้ในแถว H(x) ของตารางขนาด N หากต้องการดึงข้อมูล x ก็แค่คำนวณ H(x) และตรวจสอบแถวนั้นของตารางเพื่อหาองค์ประกอบที่เก็บไว้ที่นั่น ฟังก์ชันแฮชที่ดีสำหรับจุดประสงค์นี้คือฟังก์ชันที่ทำให้เกิดการชนกันเพียงเล็กน้อย โดยที่
การชนกันคือคู่ขององค์ประกอบที่แตกต่างกัน x และ x0
โดยที่ H(x) = H(x0);
ในกรณีนี้ เราก็บอกว่า x และ x0
ชนกัน (เมื่อเกิดการชนสอง
องค์ประกอบจะถูกจัดเก็บไว้ในเซลล์เดียวกัน ทำให้เวลาในการค้นหาเพิ่มขึ้น)
ฟังก์ชันแฮชที่ทนต่อการชนกันนั้นมีความคล้ายคลึงกันในด้านจิตวิญญาณ อีกครั้งเป้าหมายคือ
เพื่อหลีกเลี่ยงการชนกัน อย่างไรก็ตาม มีความแตกต่างพื้นฐาน ประการหนึ่ง
ความปรารถนาที่จะลดการชนกันในการตั้งค่าโครงสร้างข้อมูลกลายเป็น
ข้อกำหนดเพื่อหลีกเลี่ยงการชนกันในการตั้งค่าการเข้ารหัส อนึ่ง ใน
บริบทของโครงสร้างข้อมูล เราถือว่าชุดขององค์ประกอบที่ถูกแฮช
ถูกเลือกโดยไม่ขึ้นกับ H และไม่มีเจตนาที่จะทำให้เกิดการชนกัน ใน
บริบทของการเข้ารหัส ตรงกันข้าม เราต้องเผชิญกับศัตรูที่
อาจเลือกองค์ประกอบที่มีเป้าหมายที่ชัดเจนในการทำให้เกิดการชนกัน นี่หมายความว่า
ฟังก์ชันแฮชที่ป้องกันการชนนั้นออกแบบได้ยากกว่ามาก
เกี่ยวกับแนวคิดของการแฮชที่สมบูรณ์แบบในบทนำของอัลกอริทึมของ CLRS:
11.5 การแฮชที่สมบูรณ์แบบ
เราเรียกเทคนิคการแฮชว่าการแฮชที่สมบูรณ์แบบ ถ้าจำเป็นต้องใช้การเข้าถึงหน่วยความจำ O(1) เพื่อทำการค้นหาในกรณีที่เลวร้ายที่สุด
เพื่อสร้างแผนการแฮชที่สมบูรณ์แบบ เราใช้การแฮชสองระดับ โดยมีการแฮชสากลในแต่ละระดับ
โดยพื้นฐานแล้วระดับแรกจะเหมือนกับการแฮชด้วยการผูกมัด: เราแฮชคีย์ n ลงในช่อง m โดยใช้ฟังก์ชันแฮช h ที่คัดสรรมาอย่างดีจากตระกูลของ
ฟังก์ชันแฮชสากล
แทนที่จะสร้างรายการลิงก์ของคีย์ที่แฮชกับช่อง j อย่างไรก็ตาม เราใช้ตารางแฮชรองขนาดเล็ก S j ที่มีฟังก์ชันแฮชที่เกี่ยวข้อง h j โดยการเลือก
ฟังก์ชันแฮช h j อย่างระมัดระวัง เราสามารถรับประกันได้ว่าไม่มีการชนกันในระดับมัธยมศึกษา
และใน https://en.wikipedia.org/wiki/Perfect_hash_function
ในวิทยาการคอมพิวเตอร์ ฟังก์ชันแฮชที่สมบูรณ์แบบ h สำหรับเซต S คือฟังก์ชันแฮชที่จับคู่องค์ประกอบที่แตกต่างกันใน S กับเซตของจำนวนเต็ม m โดยไม่มีการชนกัน. ในทางคณิตศาสตร์ มันคือฟังก์ชันอินเจกทีฟ
ถูกต้องหรือไม่ที่ในหนังสือของ Katz ฟังก์ชันแฮชที่ป้องกันการชนกันหมายถึงฟังก์ชันแฮชที่ไม่มีการชนกัน (ฉันคิดอย่างนั้น.)
ฟังก์ชันแฮชที่สมบูรณ์แบบใน Wikipedia เหมือนกับฟังก์ชันแฮชที่ป้องกันการชนกันในหนังสือของ Katz หรือไม่ (ฉันคิดอย่างนั้น.)
ฟังก์ชันแฮชที่สมบูรณ์แบบในหนังสือของ CLRS เหมือนกับฟังก์ชันแฮชที่ป้องกันการชนกันในหนังสือของ Katz หรือไม่ (CLRS กำหนดฟังก์ชันแฮชที่สมบูรณ์แบบในแง่ของความซับซ้อนของการเข้าถึงหน่วยความจำที่เป็น O(1) และใช้ฟังก์ชันแฮชที่สมบูรณ์แบบเป็นฟังก์ชันแฮชที่ป้องกันการชนกัน ดังนั้นฉันจึงคิดว่าฟังก์ชันแฮชที่ป้องกันการชนกันก็เป็นแฮชที่สมบูรณ์แบบเช่นกัน ฟังก์ชัน แต่ไม่แน่ใจว่าฟังก์ชันแฮชที่สมบูรณ์แบบจำเป็นต้องป้องกันการชนกันหรือไม่)
ฟังก์ชันแฮชที่สมบูรณ์แบบในหนังสือของ CLRS เหมือนกับฟังก์ชันแฮชที่สมบูรณ์แบบใน Wikipedia หรือไม่
ขอบคุณ.