Trong phần này, chúng ta sẽ xem Phương pháp Brent’s liên quan đến băm theo địa chỉ mở là gì. Phương pháp này là một phương pháp heuristic. Điều này cố gắng giảm thiểu thời gian trung bình để tìm kiếm thành công trong bảng băm.
Phương pháp này ban đầu được áp dụng trên kỹ thuật băm kép, nhưng điều này có thể được sử dụng trên bất kỳ kỹ thuật định địa chỉ mở nào như thăm dò tuyến tính và bậc hai. Tuổi của một phần tử x, được lưu trữ trong một bảng băm địa chỉ mở, là giá trị nhỏ nhất i, sao cho x được đặt tại A [x i ]
Phương pháp Brent cố gắng giảm thiểu tổng số tuổi của tất cả các phần tử. Nếu chúng ta chèn một phần tử x, thì nó sẽ thực hiện theo một số bước - Chúng ta sẽ tìm giá trị nhỏ nhất của i, sao cho A [x i ] trống, đây là nơi địa chỉ mở tiêu chuẩn sẽ chèn x. Bây giờ hãy xem xét một phần tử y, được lưu trữ tại A [x i-2 ]. Phần tử này được lưu trữ ở đó vì yj =x i-2 , với giá trị nào đó của j ≥ 0. Chúng tôi kiểm tra xem vị trí mảng A [y j + 1 ] trống, sau đó chúng tôi chuyển y đến vị trí A [y j + 1 ], và lưu trữ x tại vị trí A [x i-2 ].
So với cách định địa chỉ mở thông thường, điều này làm giảm tổng độ tuổi đi 1. Nói chung Phương pháp Brent kiểm tra từng 2 ≤ k ≤ i, mục nhập mảng A [x i-k ] để xem, nếu phần tử y được lưu trữ, ở đó, có thể được chuyển đến bất kỳ phần tử nào trong A [y j + 1 ], A [y j + 2 ],. . ., A [y j + k-1 ], để nhường chỗ cho x.