Register

GO Classes DPP | GATE CS, DA | Algorithms | Hash Collision Handling

84 views
0 0 votes

When hashing is used for table addressing, a collision-resolution method is generally required.

Why?

  1. Collision handling is required only when the table is completely full.
     
  2. Collision handling is required to calculate the initial hash address of every key.
     
  3. Collision handling is required when the table is empty.
     
  4. Collision handling is required whenever the inserted key is not already present.
     
  5. Different keys may hash to the same table address.

1 Answer

0 0 votes

A hash function maps a potentially large key space into a limited number of table positions.

For ex,

$h(k)=k\bmod10$

Then,

$h(17)=7$ and $h(27)=7$

Two different keys produce the same address.

This is a collision.

Therefore, a hash table requires some method for resolving such situations, such as:

  • separate chaining
     
  • linear probing
     
  • quadratic probing
     
  • double hashing
     

Hence,

Answer : E

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes GATE DA |...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

1 1 vote
1 1 answer
98
98 views
GO Classes asked Aug 25
98 views
GO Classes DPP | GATE CS, DA | Algorithms | Minimum Spanning Tree
Let $G=(V,E)$ be a connected weighted undirected graph in which all edge weights are distinct.Let, $e=(u,v)$ be an edge of weight $w(e)$.Construct a graph $G'$ containing...
0 0 votes
1 1 answer
75
75 views
GO Classes asked Aug 25
75 views
GO Classes DPP | GATE CS, DA | Algorithms | Sorting Complexity
Let $P$ be the problem of sorting $n\geq1$ elements using only comparisons.Consider the class of all comparison-based algorithms that correctly solve $P$.What is the asym...
0 0 votes
1 1 answer
96
96 views
GO Classes asked Aug 25
96 views
GO Classes DPP | GATE CS, DA | Algorithms | Asymptotic Analysis
Let $T_A(n)$ and $T_B(n)$ denote the worst-case running times of two algorithms $A$ and $B$ that solve the same problem.We say that $A$ is asymptotically more efficient t...
0 0 votes
1 1 answer
55
55 views
GO Classes asked Aug 25
55 views
GO Classes DPP | GATE CS, DA | Algorithms | Dijkstra's Algorithm
Suppose every edge weight of a graph is either:a positive integer, or exactly $-1$.Consider the statement:Dijkstra's algorithm will always compute the correct shortest-pa...