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 wellknown 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
In this article, we will discuss about Open Addressing.
Open Addressing
In open addressing,
 Unlike separate chaining, all the keys are stored inside the hash table.
 No key is stored outside the hash table.
Techniques used for open addressing are
 Linear Probing
 Quadratic Probing
 Double Hashing
Operations in Open Addressing
Let us discuss how operations are performed 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”.
NOTE
 During insertion, the buckets marked as “deleted” are treated like any other empty bucket.
 During searching, the search is not terminated on encountering the bucket marked as “deleted”.
 The search terminates only after the required key or an empty bucket is found.
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
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 i^{2}‘th bucket in i^{th} 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 i^{th} 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 = size of table)

m 
m 
m^{2} 
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
Step01:
 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
Step02:
 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 bucket1 of the hash table as
Step03:
 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 bucket0 of the hash table as
Step04:
 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 bucket6 of the hash table as
Step05:
 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 bucket1 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 bucket2.
 So, key 85 will be inserted in bucket2 of the hash table as
Step06:
 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 bucket1 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 bucket3.
 So, key 92 will be inserted in bucket3 of the hash table as
Step07:
 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 bucket3 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 bucket4.
 So, key 73 will be inserted in bucket4 of the hash table as
Step08:
 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 bucket3 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 bucket5.
 So, key 101 will be inserted in bucket5 of the hash table as
To gain better understanding about Open Addressing,
Watch this Video Lecture
Next Article Separate Chaining Vs Open Addressing
Get more notes and other study material of Data Structures.
Watch video lectures by visiting our YouTube channel LearnVidFun.