Scribd
Upload
18 views

DSA Java Hashing (M 26)

Interview questions jagca

Uploaded by

Success Man
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
18 views

DSA Java Hashing (M 26)

Interview questions jagca

Uploaded by

Success Man
Copyright
© © All Rights Reserved
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 8

Hash Table

The Hash table data structure stores elements in key-value pairs where

•Key- unique integer that is used for indexing the values

•Value - data that are associated with keys.

This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Hash Table

Hashing (Hash
Function)
In a hash table, a new
index is processed using
the keys.
And, the element
corresponding to that key
is stored in the index.
This process is
called hashing.

Let k be a key
and h(x) be a hash
function.
Here, h(k) will Thisgive us a
video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Hash Collision

When the hash function generates the same index for multiple keys, there will be
a conflict (what value to be stored in that index). This is called a hash collision.

We can resolve the hash collision using one of the following techniques.

• Collision resolution by chaining

• Open Addressing: Linear/Quadratic Probing and Double Hashing

This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Hash Collision

1. Collision resolution by
chaining
In chaining, if a hash function
produces the same index for
multiple elements, these
elements are stored in the same
index by using a doubly-linked
list.

If j is the slot for multiple


elements, it contains a pointer to
the head of the list of elements.
If no element is present, j
contains NIL.
This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Hash Collision
2. Open Addressing
Unlike chaining, open addressing doesn't store multiple elements into the same slot. Here, each slot
is either filled with a single key or left NIL.

Different techniques used in open addressing are:


i. Linear Probing
In linear probing, collision is resolved by checking the next slot.

h(k, i) = (h′(k) + i) mod m

where
i = {0, 1, ….}
h'(k) is a new hash function
If a collision occurs at h(k, 0), then h(k, 1) is checked. In this way, the value of i is incremented
linearly.

This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Hash Collision

ii. Quadratic Probing

It works similar to linear probing but the spacing between the slots is increased
(greater than one) by using the following relation.

h(k, i) = (h′(k) + c1i + c2i2) mod m

where,

c1 and c2 are positive auxiliary constants,


i = {0, 1, ….}

This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Hash Collision

iii. Double hashing


If a collision occurs after applying a hash function h(k), then another hash function
is calculated for finding the next slot.

h(k, i) = (h1(k) + ih2(k)) mod m

This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video
Good Hash Function

A good hash function may not prevent the collisions completely however it
can reduce the number of collisions.

This video is sole property of Talent Battle Pvt. Ltd. Strict penal action will be taken against unauthorized piracy of this video

You might also like