Hash Algorithms


Notations:

    Hash table size: m
    Key of an element x: key[x]
    Hash function: h; an element with key k hashes to h(k)
    Slots of a hash table: T[0 .. m-1]
    For Open Addressing: if a slot has value
        NIL: indicating that the slot has never been occuppied
        DELETED: indicating that the slot was occupied by some key.
 

Chaining Hash Algorithm

Insert (T, x)
    insert x at the tail of list T[h(key[x])]

Search (T, k)
    search for an element with key k in list T[h(k)]

Delete (T, x)
    delete x from the list T[h(key[x])]
 

Open Adressing Hash Algorithm

Insert (T, k)
    i := 0
    repeat  j := h (k, i)
            if  T[j] = NIL  or T[j] = DELETED
                then  T[j] := k
            else  i := i + 1
        until  i = m
    error  "Hash Table is Full"

Search (T, k)
    i := 0
    repeat  j := h (k, i)
            if  T[j] = k
                then  return j
            i := i + 1
        until  T[j] = NIL  or  i = m
    return NIL

Delete (T, k)
    j := Search (T, k)
    if (not (j = NIL))
        then  T[j] = DELETED


Back to the Applet Page
How to use this Applet