Trong phần này, chúng ta sẽ xem sơ đồ băm Robin-Hood là gì. Phép băm này là một trong những kỹ thuật tạo địa chỉ mở. Điều này cố gắng cân bằng thời gian tìm kiếm của phần tử bằng cách sử dụng chiến lược giải quyết va chạm công bằng hơn. Trong khi chúng ta đang cố gắng chèn, nếu chúng ta muốn chèn phần tử x ở vị trí xi và đã có một phần tử y được đặt ở y j =x i , thì phần tử trẻ hơn của hai phần tử phải tiếp tục. Vì vậy, nếu tôi ≤ j, thì chúng tôi sẽ cố gắng chèn x ở vị trí x i + 1 , x i + 2 và như thế. Nếu không, chúng tôi sẽ lưu trữ x ở vị trí x i và cố gắng chèn y ở vị trí y j + 1 , y j + 2 và như vậy.
Theo Devroye và cộng sự. cho thấy rằng sau khi thực hiện n lần chèn trên một bảng trống ban đầu, có kích thước là 𝑚 =Α𝑛, sử dụng thuật toán chèn Robin-Hood, giá trị mong đợi của thời gian tìm kiếm trong trường hợp xấu nhất là -
$$ E [W] =\ Theta (log \:log \:n) $$
Và ràng buộc của nó rất chặt chẽ. Vì vậy, thuật toán này là một dạng địa chỉ mở, có thời gian tìm kiếm trong trường hợp xấu nhất theo lôgarit gấp đôi.