Assignment: Hashing | DSA in C++ - Software Development PDF Download

Instructions

• Attempt all the questions.
• For MCQs, HOTS, Fill in the blanks, and True/False questions, choose the most appropriate option or provide the correct answer.
• For Hands-On Questions, write the code or explain the concept as required.
• The difficulty level of questions varies from easy to hard.

Multiple Choice Questions (MCQs)

Q.1. What is hashing?
(a) It is a technique for searching data in a sorted array.
(b) It is a technique to transform data into a fixed-size array.
(c) It is a technique to sort data in ascending order.
(d) It is a technique to convert data into binary representation.

Ans. (b)

Q.2. Which of the following collision handling techniques is used in hashing to resolve collisions by storing elements in linked lists?

(a) Separate chaining
(b) Open addressing
(c) Linear probing
(d) Quadratic probing

Ans. (a)

Q.3. In hashing, which of the following collision handling techniques is used to resolve collisions by searching for the next available slot in the hash table?
(a) Separate chaining
(b) Linear probing
(c) Quadratic probing
(d) Double hashing

Ans. (b)

Q.4. In hashing, the load factor is defined as:
(a) The number of elements in the hash table.
(b) The number of collisions occurred during hashing.
(c) The ratio of occupied slots to total slots in the hash table.
(d) The average time complexity of searching in the hash table.

Ans. (c)

Q.5. Which of the following is a disadvantage of separate chaining collision handling technique in hashing?
(a) It requires a large amount of memory.
(b) It leads to clustering of elements in the hash table.
(c) It has a higher time complexity for searching.
(d) It cannot handle collisions efficiently.

Ans. (b)

HOTS (Higher Order Thinking Questions)

Q.1. Explain the concept of indexing mapping with negatives allowed in hashing.

Index mapping with negatives allowed in hashing involves mapping both positive and negative values into non-negative array indices by using an offset value.

Q.2. Discuss the advantages and disadvantages of open addressing collision handling technique in hashing.

Advantages of open addressing:

• No additional memory overhead for storing linked lists.
• Better cache performance as elements are stored compactly.
• Disadvantages of open addressing:
• Difficulty in handling deletions efficiently.

• Increased chances of clustering and performance degradation.

Q.3. How does double hashing resolve collisions in hashing? Provide an example to illustrate the process.

Double hashing resolves collisions by using a second hash function to calculate the number of steps to jump when a collision occurs. The second hash function is used to determine the displacement value, and it provides a different step size for each collision. Example: When a collision occurs at index 4, and the displacement value is 3, the next probe will be at index (4 + 3) % table_size.

Q.4. Explain the concept of load factor and its significance in hashing.

Load factor is the ratio of the number of elements stored in the hash table to the total number of slots. It indicates how full the hash table is and affects the performance of hashing operations. A higher load factor leads to increased chances of collisions and longer search times.

Q.5. Compare and contrast separate chaining and open addressing collision handling techniques in hashing.

Separate chaining:

• Collisions are resolved by storing elements in linked lists or other data structures.
• Requires additional memory for storing pointers or references to linked lists.
• Open addressing:
• Collisions are resolved by finding the next available slot in the hash table.
• Does not require additional memory for storing linked lists, resulting in better cache performance.

Fill in the Blanks

1. The _________ of a hash table refers to the number of occupied slots divided by the total number of slots.

The load factor of a hash table refers to the number of occupied slots divided by the total number of slots.

2. In separate chaining, collisions are handled by storing elements in _________.

In separate chaining, collisions are handled by storing elements in linked lists.

3. In open addressing, collisions are handled by searching for the _________ available slot in the hash table.

In open addressing, collisions are handled by searching for the next available slot in the hash table.

4. Double hashing uses _________ hash functions to resolve collisions in hashing.

Double hashing uses two hash functions to resolve collisions in hashing.

5. Hashing is often used for _________ and efficient retrieval of data.

Hashing is often used for fast and efficient retrieval of data.

True or False

1. Hashing guarantees unique mapping of data elements to array indices.

False

2. In separate chaining, each element is stored in its respective hash table slot.

True

3. The load factor of a hash table is always less than or equal to 1.

True

4. Linear probing is an example of open addressing collision handling technique.

True

5. Double hashing can lead to an infinite loop if the hash table is full.

True

Hands-On Questions

Q.1. Implement a hash function in C++ that takes an integer input and returns the hash value.

Example implementation of a hash function:

unsigned int hashFunction(int key) {

    return abs(key) % tableSize;

}

Q.2. Write a C++ program to demonstrate the separate chaining collision handling technique in hashing.

Example program demonstrating separate chaining collision handling technique:

#include <iostream>

#include <list>

using namespace std;

class HashTable {

    int tableSize;

    list<int>* hashTable;

public:

    HashTable(int size) {

        tableSize = size;

        hashTable = new list<int>[tableSize];

    }

    void insert(int key) {

        int index = hashFunction(key);

        hashTable[index].push_back(key);

    }

    void search(int key) {

        int index = hashFunction(key);

        for (auto it = hashTable[index].begin(); it != hashTable[index].end(); ++it) {

            if (*it == key) {

                cout << "Element " << key << " found at index " << index << endl;

                return;

            }

        }

        cout << "Element " << key << " not found!" << endl;

    }

    void display() {

        for (int i = 0; i < tableSize; ++i) {

            cout << "Index " << i << ": ";

            for (auto it = hashTable[i].begin(); it != hashTable[i].end(); ++it) {

                cout << *it << " ";

            }

            cout << endl;

        }

    }

    unsigned int hashFunction(int key) {

        return abs(key) % tableSize;

    }

};

int main() {

    HashTable ht(10);

    ht.insert(12);

    ht.insert(25);

    ht.insert(35);

    ht.insert(45);

    ht.insert(52);

    ht.display();

    ht.search(25);

    ht.search(42);

    return 0;

}

Q.3. Implement a hash table class in C++ using open addressing collision handling technique.

Example implementation of a hash table class using open addressing:

#include <iostream>

using namespace std;

class HashTable {

    int* hashTable;

    int tableSize;

public:

    HashTable(int size) {

        tableSize = size;

        hashTable = new int[tableSize];

        for (int i = 0; i < tableSize; ++i) {

            hashTable[i] = -1;  // Initialize all slots as unoccupied

        }

    }

    void insert(int key) {

        int index = hashFunction(key);

        int i = 0;

        while (hashTable[(index + i) % tableSize] != -1) {

            i++;

        }

        hashTable[(index + i) % tableSize] = key;

    }

    void search(int key) {

        int index = hashFunction(key);

        int i = 0;

        while (hashTable[(index + i) % tableSize] != key && hashTable[(index + i) % tableSize] != -1) {

            i++;

        }

        if (hashTable[(index + i) % tableSize] == key) {

            cout << "Element " << key << " found at index " << (index + i) % tableSize << endl;

        } else {

            cout << "Element " << key << " not found!" << endl;

        }

    }

    void display() {

        for (int i = 0; i < tableSize; ++i) {

            cout << "Index " << i << ": ";

            if (hashTable[i] != -1) {

                cout << hashTable[i];

            }

            cout << endl;

        }

    }

    unsigned int hashFunction(int key) {

        return abs(key) % tableSize;

    }

};

int main() {

    HashTable ht(10);

    ht.insert(12);

    ht.insert(25);

    ht.insert(35);

    ht.insert(45);

    ht.insert(52);

    ht.display();

    ht.search(25);

    ht.search(42);

    return 0;

}

Q.4. Explain the process of rehashing in hashing and its significance. Provide a code example in C++.

Rehashing in hashing is the process of increasing the size of the hash table and reinserting all the elements from the existing table into the new table. It is performed when the load factor exceeds a certain threshold or when the number of collisions becomes significant. Rehashing helps maintain a low load factor and reduces the chances of collisions. Example code for rehashing in C++:

void rehash() {

    int newSize = tableSize * 2;

    int* newHashTable = new int[newSize];

    for (int i = 0; i < newSize; ++i) {

        newHashTable[i] = -1;

    }

    for (int i = 0; i < tableSize; ++i) {

        if (hashTable[i] != -1) {

            int key = hashTable[i];

            int index = key % newSize;

            int j = 0;

            while (newHashTable[(index + j) % newSize] != -1) {

                j++;

            }

            newHashTable[(index + j) % newSize] = key;

        }

    }

    delete[] hashTable;

    hashTable = newHashTable;

    tableSize = newSize;

}

Q.5. Write a C++ program to calculate the load factor of a hash table.

Example program to calculate the load factor of a hash table:

#include <iostream>

using namespace std;

class HashTable {

    int* hashTable;

    int size;

    int count;

public:

    HashTable(int tableSize) {

        size = tableSize;

        count = 0;

        hashTable = new int[size];

        for (int i = 0; i < size; ++i) {

            hashTable[i] = -1;  // Initialize all slots as unoccupied

        }

    }

    void insert(int key) {

        if (count == size) {

            cout << "Hash table is full! Rehashing required." << endl;

            return;

        }

        int index = hashFunction(key);

        int i = 0;

        while (hashTable[(index + i) % size] != -1) {

            i++;

        }

        hashTable[(index + i) % size] = key;

        count++;

    }

    double calculateLoadFactor() {

        return static_cast<double>(count) / size;

    }

};

int main() {

    HashTable ht(10);

    ht.insert(12);

    ht.insert(25);

    ht.insert(35);

    ht.insert(45);

    ht.insert(52);

    double loadFactor = ht.calculateLoadFactor();

    cout << "Load factor: " << loadFactor << endl;

    return 0;

}