Definition
Brent's Hashing Algorithm
Brent’s hashing algorithm is an optimisation for hash tables that allows the hash table to move previously placed slots that collide with current ones.
See pseudocode.
Pseudocode
def insert_brent(table: HashTable, k: int) -> None:
m = table.size
j = h1(k) # initial "guess"
while not table.is_free(j):
l = table.get(at=j) # existing key at position j
j1 = (j + h2(k)) % m # alternative pos. for key k
j2 = (j + h2(l)) % m # alternative pos. for key l
if table.is_empty(at=j1): # alternative pos. for key k is empty
j = j1
elif table.is_empty(at=j2): # alternative pos. for l
table.set(at=j, key=k)
k = l
j = j2
else:
j = j1
table.set(at=j, key=k)