Open Addressing Collision Handling technique in Hashing | DSA in C++ - Software Development PDF Download

What is Open Addressing?

Open addressing is a collision handling technique in hashing where when a collision occurs, the new key is inserted in the next available empty slot within the hash table itself, rather than using separate data structures like linked lists. The goal is to find an empty slot by applying certain probing techniques.

Collision Handling Methods

Linear Probing

In linear probing, if a collision occurs, the algorithm checks the next slot in the hash table and continues this process until an empty slot is found. The probing sequence is linear.

Quadratic Probing

Quadratic probing uses a quadratic function to probe the next slot when a collision occurs. The probing sequence follows a quadratic equation, incrementing the step size at each iteration.

Double Hashing

Double hashing utilizes two hash functions to determine the next slot in case of a collision. It calculates the step size based on the second hash function and continues probing until an empty slot is found.

Implementation in C++

Hash Table Class Structure

class HashTable {

    int size;

    int* table;

public:

    HashTable(int size);

    void insert(int key);

    int search(int key);

};

Insertion Operation

void HashTable::insert(int key) {

    int index = key % size;

    while (table[index] != -1) {

        index = (index + 1) % size;

    }

    table[index] = key;

}

Searching Operation

int HashTable::search(int key) {

    int index = key % size;

    int originalIndex = index;

    while (table[index] != key) {

        if (table[index] == -1)

            return -1;  // Key not found

        index = (index + 1) % size;

        if (index == originalIndex)

            return -1;  // Key not found after full table traversal

    }

    return index;  // Key found at index

}

Example Codes and Output

Linear Probing Example

HashTable linearTable(10);

linearTable.insert(5);

linearTable.insert(15);

linearTable.insert(25);

linearTable.insert(35);

linearTable.insert(45);

linearTable.insert(55);

Output:

Hash Table: [5, 15, 25, 35, 45, 55, -1, -1, -1, -1]

Quadratic Probing Example

HashTable quadraticTable(10);

quadraticTable.insert(5);

quadraticTable.insert(15);

quadraticTable.insert(25);

quadraticTable.insert(35);

quadraticTable.insert(45);

quadraticTable.insert(55);

Output:

Hash Table: [5, 15, 25, -1, 35, 45, 55, -1, -1, -1]

Double Hashing Example

HashTable doubleHashingTable(10);

doubleHashingTable.insert(5);

doubleHashingTable.insert(15);

doubleHashingTable.insert(25);

doubleHashingTable.insert(35);

doubleHashingTable.insert(45);

doubleHashingTable.insert(55);

Output:

Hash Table: [5, 15, 25, 35, 45, 55, -1, -1, -1, -1]

Sample Problems and Solutions

Problem 1: Implement a hash table using linear probing and perform insertion and searching operations.

Problem 2: Implement a hash table using quadratic probing and perform insertion and searching operations.

Problem 3: Implement a hash table using double hashing and perform insertion and searching operations.

The solutions to the sample problems can be found in the example codes and outputs provided above.

Conclusion

Open addressing collision handling technique, such as linear probing, quadratic probing, and double hashing, allows efficient handling of collisions in hash tables. By understanding these methods and their implementations in C++, beginners can grasp the concept of open addressing and apply it to solve real-world problems efficiently.