Python hash collision resolution

gistfile1.py

# Find an entry for the given key, probing to a free location if the default is
# taken
#
# table - set object
# key - the item we are looking for
# hash_val - the hash of key
def lookup_entry(table, key, hash_val):
    index = hash_val & table.mask

    entry = table[index]
    if entry.key == key:
        return entry
    # some other random checks here

    perturb = hash_val
    while True:
        index = (index << 2) + index + perturb + 1
        perturb = perturb >> PERTURB_SHIFT
        entry = table[index & table.mask)

        # pretend available() exists
        if entry is available():
            break

        if entry.key == key:
            break

        if entry.hash == hash_val:
            break

    return entry