การแฮชด้วยการคูณในโครงสร้างข้อมูล

ในที่นี้เราจะพูดถึงเรื่องการแฮชด้วยวิธีคูณ สำหรับสิ่งนี้เราใช้ฟังก์ชันแฮช -

ℎ(𝑥) = ⌊𝑚𝑥𝐴⌋ 𝑚𝑜𝑑 𝑚

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

ตามความเห็นของ Knuth เราสามารถใช้อัตราส่วนทองคำสำหรับ A ได้ ดังนั้น A จะเป็น

$$A=\frac{\sqrt5-1}{2}=0.61803398$$

แน่นอน ไม่ว่าจะเลือกค่าใดสำหรับ A หลักการของรูพิราบบอกเป็นนัยว่าถ้าคุณ ≥ nm ก็จะมีค่าแฮชหนึ่งค่า i และ S ⊆ U ของขนาด n บางส่วน ดังนั้น h(x) =i สำหรับ x ทั้งหมด ในส.

ดังนั้นเราสามารถพูดได้ว่าการแฮชในกรณีที่เลวร้ายที่สุดด้วยการคูณนั้นแย่พอๆ กับการแฮชด้วยการหาร