ฟังก์ชันแฮชที่สมบูรณ์แบบเป็นแนวคิดเดียวกับฟังก์ชันแฮชที่ป้องกันการชนกันหรือไม่

เกี่ยวกับฟังก์ชันแฮชที่ป้องกันการชนกัน ใน 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 หรือไม่

ขอบคุณ.

ถูกต้องหรือไม่ที่ในหนังสือของ Katz ฟังก์ชันแฮชที่ป้องกันการชนกันหมายถึงฟังก์ชันแฮชที่ไม่มีการชนกัน

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

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

ในทางคณิตศาสตร์ มันคือฟังก์ชันอินเจกทีฟ

ฟังก์ชันแฮชในการเข้ารหัสไม่ใช่แบบฉีดเนื่องจากดังที่กล่าวไว้ข้างต้น พื้นที่เอาต์พุตมีขนาดเล็กกว่าพื้นที่อินพุตมาก ดังนั้นจึงไม่เหมือนกับฟังก์ชันแฮชที่สมบูรณ์แบบอย่างแน่นอน

ฟังก์ชันแฮชที่สมบูรณ์แบบในหนังสือของ CLRS เหมือนกับฟังก์ชันแฮชที่สมบูรณ์แบบใน Wikipedia หรือไม่

ใช่ ในทั้งสองกรณีนี้ ฟังก์ชันแฮชจะไม่มีการชนกัน (ไม่มีการชนกัน)