Basic CS-Data Structures [3i Infotech Placement]: Sample Questions 20 - 20 of 52

Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

Question 20

Data Structures
Edit

Describe in Detail

Essay▾

What are the types of Collision Resolution Techniques and the methods used in each of the type?

Explanation

A collision or clash occurs when two different inputs to a function, typically one used to compress large data items into a smaller or fixed size, produce the same output, called a hash value, checksum, fingerprint, or digest.

Define Collision Resolution and Its Techniques

Open addressing (closed hashing)

  • All keys are stored in the hash table itself without the use of linked list.
  • We never leave the hash table; every object is stored directly an index in the internal array.
  • Only possible using sort open addressing strategy.

Used method for collusion: Overflow block.

  • Linked list for overflow block
The Overflow Block

Closed addressing (open hashing)

  • Keys are stored in linked lists attached to cell of a hash table.
  • Object is actually stored in the hash table.
  • Once an object is hashed, it is stored in a list which is separate from the hash internal array.
  • We leave the hash table, and use a separate list.

Used method for collusion: Linked list, Binary tree.

  • Overflow Linked list:
    • A linear collection of data elements, in which linear order is not their physical placement in memory.
    • The simplest and common data structures.
    • Used to implement several other common abstract data types.
    • A dynamic data structure, which can grow and pruned.
    • No need to define an initial size for a linked list.
  • Overflow Binary tree:
    • Instead of hanging the overflowed values form a linked list which has to be sequentially search they are hanging from the binary tree which can be searched more efficiently on the full hash.
    • A structure variable or an object with three types of member variable:
      • A data part:
        • One or more member variables appropriate to hold the data in the node.
      • A left part:
        • A pointer variable to hold the address of the left child node.
      • A right part:
        • A pointer variable to hold the address of the right child node.

Developed by: