Open addressing

Open addressing :

               In open addressing all the record entries are stored in the bucket arrays.The locations of the hash table are turned as buckets. Each bucket is portioned in to slots.The buckets are examined whenever a new entry has to be inserted,starting with hashed-to-slot using some probe sequence until an empty slot is found

                      [0]    [1]    [2]…………[s-1]

Ø  To search for a entry all buckets are scanned in the same sequence until the entry is found or an empty slot is found which indicates that there is no such entry in table.

Ø  The loacation or address of an item is not determined by the hash value with open addressing.Each location in an array will be in EMPTY,DELETED or OCCUPIED state.

Ø  If the state of locatin is OCCUPIED then it contains key and data otherwise it does not have any value.

Ø  Initially all the locations in the array are in EMPTY state.

Ø  When an item at a particular location is deleted then its state will be DELETED,not EMPTY.

Ø  The need of these three states is explained by an algorithm which inserts an item in to a table.

Algorithm:

1.Find  the location  at  which  item  is to be  stored  L=H(key(ITEM))

2.If  the  location  L  IS  NOT  occupied  then  insert  ITEM.

3.If   location  L is  OCCUPIED  find  another  location  using  some  probe 

4  .End.

Collision resolution techniques

Dictionaries