# 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 t11.’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