Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

การแฮชแบบอสมมาตรในโครงสร้างข้อมูล


ในส่วนนี้เราจะมาดูกันว่าเทคนิคการแฮชแบบอสมมาตรคืออะไร ในเทคนิคนี้ ตารางแฮชจะแบ่งออกเป็น d จำนวนบล็อก รอยแยกแต่ละอันมีความยาว n/d ค่าโพรบ xi, 0 ≤ i ≤ d, วาดแบบสม่ำเสมอจาก $$\lbrace\frac{i*n}{d},...,\frac{(i+1)*n}{d-1} \rbrace$$ เช่นเดียวกับการแฮชแบบหลายตัวเลือก ในการแทรก x อัลกอริทึมจะตรวจสอบความยาวของรายการ A[x0 ], A[x1 ], . . ., A[xd – 1 ]. จากนั้นผนวก x ต่อท้ายรายการที่สั้นที่สุดของรายการเหล่านี้ หากเสมอกัน ให้ใส่ x ลงในรายการด้วยดัชนีที่เล็กที่สุด

จากข้อมูลของ Vocking ความยาวที่คาดหวังของรายการที่ยาวที่สุดสำหรับการแฮชแบบอสมมาตรคือ −

$$E[W]\leq\frac{ln\:ln\:n}{d\:ln\:\phi_{2}}+O(1)$$

ฟังก์ชัน 𝜙𝑑 เป็นลักษณะทั่วไปของอัตราส่วนทองคำ ดังนั้น $$\phi_{2}=\frac{(1+\sqrt{5})}{2}$$