Implemention of the hash table with the open adressing

hash_table.py

"""
Implemention of the hash table with the open adressing
"""
NIL = 'NIL'
DELETED = 'deleted'

C1 = 2
C2 = 3


def aux_func(key):
    """
    Auxiliary hash function
    """
    return key


def aux_func2(key, m):
    return 1 + (key % (m - 1))


def hash_func(key, i, m, probe='double_hashing'):
    if probe == 'linear':
        func = linear_probe
    elif probe == "quadro":
        func = quadro_probe
    elif probe == "double_hashing":
        func = double_hashing
    else:
        raise ValueError("Invalid Probe")

    h = func(key, i, m)
    return h


def linear_probe(key, i, m):
    return (aux_func(key) + i) % m


def quadro_probe(key, i, m):
    return (aux_func(key) + C1 * i + C2 * i ** 2) % m


def double_hashing(key, i, m):
    return (aux_func(key) + i * aux_func2(key, m)) % m


def hash_insert(T, k):
    i = 0
    m = len(T)
    while i <= m:
        j = hash_func(k, i, m)
        if T[j] == NIL:
            T[j] = [k, True]
            return j
        else:
            i += 1
    raise ValueError("Hash table is full")


def hash_search(T, k):
    i = 0
    m = len(T)
    while i <= m:
        j = hash_func(k, i, m)
        if isinstance(T[j], list) and T[j][0] == k and T[j][1]:
            return j
        elif T[j] == NIL:
            break
        i += 1
    raise ValueError("{} not found".format(k))


def hash_delete(T, k):
    j = hash_search(T, k)
    T[j][1] = False


def hash_print(T):
    """
    Helper func for the user-friendly printing without bool flags
    """
    result = []
    for item in T:
        if isinstance(item, list):
            if item[1]:
                result.append(item[0])
            else:
                result.append(NIL)
        else:
            result.append(item)
    print(result)


def main():
    keys = [10, 22, 31, 4, 15, 28, 17, 88, 59]
    print("keys={}".format(keys))
    m = 11  # Table size
    T = [NIL for i in range(m)]
    print("source hash table={}".format(T))
    for key in keys:
        hash_insert(T, key)
        hash_print(T)


if __name__ == "__main__":
    main()