[go: up one dir, main page]
Scribd
Upload
130 views10 pages

Collision Resolution Techniques

The document discusses collision resolution techniques in hashing, specifically Separate Chaining and Open Addressing, highlighting their differences in key storage, deletion ease, space requirements, and cache performance. It details operations for both methods, including insertion, searching, and deletion, and compares various open addressing techniques such as Linear Probing, Quadratic Probing, and Double Hashing. The document concludes with a practice problem demonstrating the insertion of keys using linear probing.

Uploaded by

dgpguru
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
130 views10 pages

Collision Resolution Techniques

The document discusses collision resolution techniques in hashing, specifically Separate Chaining and Open Addressing, highlighting their differences in key storage, deletion ease, space requirements, and cache performance. It details operations for both methods, including insertion, searching, and deletion, and compares various open addressing techniques such as Linear Probing, Quadratic Probing, and Double Hashing. The document concludes with a practice problem demonstrating the insertion of keys using linear probing.

Uploaded by

dgpguru
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 10

Collision Resolution Techniques-

In Hashing, collision resolution techniques are classified as-

1. Separate Chaining
2. Open Addressing

Separate Chaining Vs Open Addressing-


Separate Chaining Open Addressing
All the keys are stored only inside the hash table.
Keys are stored inside the hash table as well as
outside the hash table. No key is present outside the hash table.

The number of keys to be stored in the hash The number of keys to be stored in the hash
table can even exceed the size of the hash table. table can never exceed the size of the hash table.

Deletion is easier. Deletion is difficult.

Extra space is required for the pointers to store


No extra space is required.
the keys outside the hash table.

Cache performance is poor.


Cache performance is better.
This is because of linked lists which store the
This is because here no linked lists are used.
keys outside the hash table.

Some buckets of the hash table are never used Buckets may be used even if no key maps to
which leads to wastage of space. those particular buckets.
Which is the Preferred Technique?
The performance of both the techniques depend on the kind of operations that are required to
be performed on the keys stored in the hash table-

Separate Chaining-
Separate Chaining is advantageous when it is required to perform all the following operations
on the keys stored in the hash table-

 Insertion Operation
 Deletion Operation
 Searching Operation

Open Addressing-
Open addressing is advantageous when it is required to perform only the following operations on
the keys stored in the hash table-

 Insertion Operation
 Searching Operation

Collision Resolution Techniques-

Before you go through this article, make sure that you have gone through the previous article
on Collision Resolution Techniques.

We have discussed-

 Hashing is a well-known searching technique.


 Collision occurs when hash value of the new key maps to an occupied bucket of the hash
table.
 Collision resolution techniques are classified as-

Operations in Open Addressing-


Insert Operation-
Hash function is used to compute the hash value for a key to be inserted.

 Hash value is then used as an index to store the key in the hash table.
In case of collision,

 Probing is performed until an empty bucket is found.


 Once an empty bucket is found, the key is inserted.
 Probing is performed in accordance with the technique used for open addressing.

Search Operation-

To search any particular key,

 Its hash value is obtained using the hash function used.


 Using the hash value, that bucket of the hash table is checked.
 If the required key is found, the key is searched.
 Otherwise, the subsequent buckets are checked until the required key or an empty bucket is
found.
 The empty bucket indicates that the key is not present in the hash table.

Delete Operation-
The key is first searched and then deleted.

 After deleting the key, that particular bucket is marked as “deleted”.

Operations in Open Addressing-

Insert Operation-

 Hash function is used to compute the hash value for a key to be inserted.
 Hash value is then used as an index to store the key in the hash table.
In case of collision,

 Probing is performed until an empty bucket is found.


 Once an empty bucket is found, the key is inserted.
 Probing is performed in accordance with the technique used for open addressing.

Search Operation-

To search any particular key,

 Its hash value is obtained using the hash function used.


 Using the hash value, that bucket of the hash table is checked.
 If the required key is found, the key is searched.
 Otherwise, the subsequent buckets are checked until the required key or an empty bucket is
found.
 The empty bucket indicates that the key is not present in the hash table.

Delete Operation-

 The key is first searched and then deleted.


 After deleting the key, that particular bucket is marked as “deleted”.

Open Addressing Techniques-

Techniques used for open addressing are-

1. Linear Probing-

In linear probing,

 When collision occurs, we linearly probe for the next bucket.


 We keep probing until an empty bucket is found.

Advantage-

 It is easy to compute.

Disadvantage-

 The main problem with linear probing is clustering.


 Many consecutive elements form groups.
 Then, it takes time to search an element or to find an empty bucket.

Time Complexity-

Worst time to search an element in linear probing is O (table size).

This is because-

 Even if there is only one element present and all other elements are deleted.
 Then, “deleted” markers present in the hash table makes search the entire table.

2. Quadratic Probing-

In quadratic probing,

 When collision occurs, we probe for i2‘th bucket in ith iteration.


 We keep probing until an empty bucket is found.

3. Double Hashing-

In double hashing,

 We use another hash function hash2(x) and look for i * hash2(x) bucket in ith iteration.
 It requires more computation time as two hash functions need to be computed.

Comparison of Open Addressing Techniques-

Linear Probing Quadratic Probing Double Hashing


Primary Clustering Yes No No

Secondary Clustering Yes Yes No

Number of Probe
Sequence m m m2
(m = size of table)

Cache performance Best Lies between the two Poor

Conclusions-

 Linear Probing has the best cache performance but suffers from clustering.
 Quadratic probing lies between the two in terms of cache performance and clustering.
 Double caching has poor cache performance but no clustering.

Load Factor (α)-


Load factor (α) is defined as-

In open addressing, the value of load factor always lie between 0 and 1.

This is because-

 In open addressing, all the keys are stored inside the hash table.
 So, size of the table is always greater or at least equal to the number of keys stored in the
table.

PRACTICE PROBLEM BASED ON OPEN


ADDRESSING-

Problem-

Using the hash function ‘key mod 7’, insert the following sequence of keys in the hash table-

50, 700, 76, 85, 92, 73 and 101

Use linear probing technique for collision resolution.


Solution-

The given sequence of keys will be inserted in the hash table as-

Step-01:

 Draw an empty hash table.


 For the given hash function, the possible range of hash values is [0, 6].
 So, draw an empty hash table consisting of 7 buckets as-

Step-02:

 Insert the given keys in the hash table one by one.


 The first key to be inserted in the hash table = 50.
 Bucket of the hash table to which key 50 maps = 50 mod 7 = 1.
 So, key 50 will be inserted in bucket-1 of the hash table as-

Step-03:
 The next key to be inserted in the hash table = 700.
 Bucket of the hash table to which key 700 maps = 700 mod 7 = 0.
 So, key 700 will be inserted in bucket-0 of the hash table as-

Step-04:

 The next key to be inserted in the hash table = 76.


 Bucket of the hash table to which key 76 maps = 76 mod 7 = 6.
 So, key 76 will be inserted in bucket-6 of the hash table as-

Step-05:

 The next key to be inserted in the hash table = 85.


 Bucket of the hash table to which key 85 maps = 85 mod 7 = 1.
 Since bucket-1 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket
is found.
 The first empty bucket is bucket-2.
 So, key 85 will be inserted in bucket-2 of the hash table as-
Step-06:
The next key to be inserted in the hash table = 92.

 Bucket of the hash table to which key 92 maps = 92 mod 7 = 1.


 Since bucket-1 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket
is found.
 The first empty bucket is bucket-3.
 So, key 92 will be inserted in bucket-3 of the hash table as-

Step-07:
The next key to be inserted in the hash table = 73.

 Bucket of the hash table to which key 73 maps = 73 mod 7 = 3.


 Since bucket-3 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket
is found.
 The first empty bucket is bucket-4.
 So, key 73 will be inserted in bucket-4 of the hash table as-
Step-08:

 The next key to be inserted in the hash table = 101.


 Bucket of the hash table to which key 101 maps = 101 mod 7 = 3.
 Since bucket-3 is already occupied, so collision occurs.
 To handle the collision, linear probing technique keeps probing linearly until an empty bucket
is found.
 The first empty bucket is bucket-5.
 So, key 101 will be inserted in bucket-5 of the hash table as-

You might also like