Robin-Hood Hashing
เป็นเทคนิค Open Addressing พยายามทำให้ Search Time เท่าเทียมด้วย Collision Resolution ที่เป็นธรรม เมื่อแทรก x ที่ตำแหน่ง xᵢ ถ้ามี y อยู่แล้ว (yⱼ = xᵢ) ตัวที่ "อายุน้อยกว่า" (Younger) ต้องไปต่อ i ≤ j แล้วลอง xᵢ₊₁, xᵢ₊₂... มิฉะนั้น ใส่ x ที่ xᵢ ย้าย y ไป yⱼ₊₁, yⱼ₊₂...
ผลการวิเคราะห์ (Devroye et al.)
หลังแทรก n ครั้งในตารางว่างขนาด m = αn โดย Robin-Hood Insertion Expected Worst-case Search Time:
$$E[W] = \Theta(\log \log n)$$
Bound นี้ Tight (แน่นอน) ดังนั้น Robin-Hood เป็น Open Addressing ที่มี Worst-case Search Time แบบ Doubly Logarithmic
