LCFS Hashing คืออะไร
LCFS (Last Come First Served) เป็นกลยุทธ์ Open Addressing ที่เปลี่ยนวิธีการแก้ไข Collision ใน Open Addressing แบบปกติเป็น FCFS (First Come First Served) คือถ้าชนกัน ตัวที่มี Priority สูงกว่า (มาก่อน) จะอยู่ในตาราง ตัวหลังต้องไปหาที่ว่าง
หลักการ LCFS
ทำงานตรงข้ามกับ FCFS: เมื่อแทรกองค์ประกอบ x ที่ตำแหน่ง x₀ ถ้าที่นั่นมี y อยู่แล้ว (yⱼ = x₀) จะย้าย y ไปที่ yⱼ₊₁ อาจขยับ z ต่อไป...
Expected Search Time (Poblete & Munro)
หลังแทรก n องค์ประกอบในตารางว่าง เวลาค้นหาคาดหมาย:
$$E[W]=1+\Gamma^{-1}(\alpha n)\left(1+\frac{\ln\ln\frac{1}{1+\alpha}}{\ln\Gamma^{-1}(\alpha n)}+O\left(\frac{1}{\ln^{2}\Gamma^{2}(\alpha n)}\right)\right)$$
โดย Γ คือ Gamma Function และ
$$\Gamma^{-1}(\alpha n)=\frac{\ln n}{\ln\ln n}\left(1+\frac{\ln\ln\ln n}{\ln\ln n}+O\left(\frac{1}{\ln\ln n}\right)\right)$$
