HASH TABLE : ADVANCE ALGORITHM

A hash table is an unordered collection of key-value pairs, where each key is unique.

 for each key value, hash function will generate the unique index then that key value will stored in that unique index as look like storing in normal array.

so next what is Direct-address tables

We shall assume that no two elements have the same key , to represent the dynamic set, we use an array, or direct-address table

 here T is the hash table k is the key value
DIRECT -ADDRESS -SEARCH (T, k)
             return T [k]

DIRECT -ADDRESS -INSERT (T, x)
            T [key[x]] ← x

DIRECT -ADDRESS -DELETE (T, x)
            T [key[x]] ← NIL

Each of these operations is fast: only O(1) time is required.

Let have a look in HASH TABLE Collision resolution by chaining

       if two elements have the same key  we put all the elements that hash to the same slot in a linked list

CHAINED -HASH -INSERT (T, x)
        insert x at the head of list T [h(key[x])]

CHAINED -HASH -SEARCH (T, k)
        search for an element with key k in list T [h(k)]

CHAINED -HASH -DELETE (T, x)
        delete x from the list T [h(key[x])] 

Let check Hash functions, in which are the methods to Interpreting keys as natural numbers

k is the key

• The division method : h(k) = k mod m 
• The multiplication method : h(k) = m (k A mod 1)  
• Universal hashing

short description about hash table have a look

Open addressing 
 all elements are stored in the hash table itself. That is, each table entry contains either an element of the dynamic set or NIL . When searching for an element, we systematically examine table slots until the desired element is found or it is clear that the element is not in the table. There are no lists and no elements stored outside the table, as there are in chaining. Thus, in open addressing, the hash table can “fill up” so that no further insertions can be made

HASH -INSERT (T, k)
i ← 0
 repeat j ← h(k, i)
     if T [ j ] = NIL
         then T [ j ] ← k
             return j
         else i ← i + 1
    until i = m
error “hash table overflow”

HASH -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