New FLASH SALE Dhamaka - Flat 60% Off on All Courses

    Question

    Which of the following collision resolution techniques

    involves storing all elements that hash to the same value in a linked list?
    A Open Addressing Correct Answer Incorrect Answer
    B Chaining Correct Answer Incorrect Answer
    C Quadratic Probing Correct Answer Incorrect Answer
    D Rehashing Correct Answer Incorrect Answer
    E Double Hashing Correct Answer Incorrect Answer

    Solution

    Chaining is a collision resolution strategy where each index in the hash table is associated with a linked list. If multiple keys hash to the same index, they are added to the linked list at that index. This method allows the hash table to handle an unlimited number of collisions at a single index by dynamically growing the linked list. Advantages of chaining include:

    • Simplifies handling collisions, especially in cases with high load factors.
    • Reduces clustering compared to open addressing.
    • Efficient for insertions and deletions as they occur in linked lists.
    Why Other Options Are Incorrect: ·         Option A (Open Addressing): In open addressing, all elements are stored within the array itself. Collisions are resolved by probing (linear, quadratic, or double hashing) to find the next empty slot, not through linked lists. ·         Option C (Quadratic Probing): A type of open addressing, quadratic probing resolves collisions by checking slots at intervals determined by a quadratic function. It does not use linked lists. ·         Option D (Rehashing): Rehashing involves recalculating the hash index using a second hash function or resizing the table when collisions occur. It is an entirely different approach compared to chaining. ·         Option E (Double Hashing): Another form of open addressing, double hashing uses two hash functions to calculate index positions. It does not use linked lists.

    Practice Next