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.
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])]
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