Brent's Method สำหรับ Open Addressed Hashing
เป็น Heuristic พยายามลดเวลาเฉลี่ยสำหรับ Successful Search ใน Hash Table
หลักการทำงาน
เดิมทีใช้กับ Double Hashing แต่ใช้กับ Linear/Quadratic Probing ได้ "อายุ" (Age) ขององค์ประกอบ x ใน Open Addressing Hash Table คือค่า i น้อยที่สุด ที่ x วางอยู่ที่ A[xᵢ]
Brent's Method พยายามลด Total Age ของทุกองค์ประกอบ เมื่อแทรก x:
- หา i น้อยที่สุดที่ A[xᵢ] ว่าง (ตำแหน่งมาตรฐาน)
- พิจารณา y ที่เก็บอยู่ที่ A[xᵢ₋₂] y อยู่ที่นั่นเพราะ yⱼ = xᵢ₋₂ สำหรับ j ≥ 0
- ถ้า A[yⱼ₊₁] ว่าง ย้าย y ไป A[yⱼ₊₁] วาง x ที่ A[xᵢ₋₂]
ลด Total Age ลง 1 เทียบกับ Open Addressing ปกติ โดยทั่วไปตรวจสอบสำหรับ 2 ≤ k ≤ i ว่า A[xᵢ₋ₖ] มี y ที่สามารถย้ายไป A[yⱼ₊₁]...A[yⱼ₊ₖ₋₁] ให้ที่ว่างแก x หรือไม่
