Collision in Design and Analysis of Algorithm Study Notes with Example

 Collision

No matter what the hash function, there is the Possibility that two different keys could resolve to the same hash address. This situation is known as a collision

.When this situation occur, there are two simple methods to t1^–1.’s problem solve.

chaining

A chain is simply a linked list of all the elements with the same hash key. The hash table slots will no longer hold a table element (key). They will now hold the address of a table element

h(K)= key% table slots e.g., The following keys to be hashed

36, 18, 72, 43, 6, 10 , 5, 15

There are 8 slots in the hash table. So, first of all we have to calculate the hash index of each key.

            36 % 8 = 4   

            18 % 8 = 2

            72 % 8 = 0

            43 % 8 = 3

            6   % 8 = 6

            10 % 8 = 2

            5   % 8 = 5

            15 % 8 = 7

Hashing with Linear Probing

When using a linear probing method the will  be stored in the next available slot in the table, assuming that the is not already full. This is implemented via a linear searching for an empty slot, from the point of collision. If the end of table is reached during the linear search, the search will wrap around to the beginning of the table and continue from there.

Key Points

• If an empty slot is not found before reaching the point of collision, the table is full.

• In chaining, we put all the elements, which to the same slot, in a linked list.

e.g.,                                      suppose the keys to be inserted or hashed are as follows

                                                   36,18, 72, /13, 6,    10, 5,15

and there are 8 slots in hash table.

Now, we have to find out the hash address of keys.

36 %8 =                       4           inserted

18 % 8 =                      2           inserted

72 % 8 =                       0           inserted

43 % 8 =                       3           inserted

6 % 8 =                         6            inserted

10 % 8 =               2           problem is here because 2nd place is

already full

5 % 8 =                  5

15 % 8 =        7          <—

So, when the hash index, what we get through the hash function is already full, then search the next empty slot. So, for key 10, 2nd index is already full, then search the 3rd, it is also full, then search the 4th, it is also full, the search 5th index it is empty, then fill with key 10.

---

Sorting in Design and Analysis of Algorithm Study Notes with Example

Follow Us on Social Platforms to get Updated : twiter,  facebook, Google Plus

Learn Sorting in Handbook Series:  Click here