8.1 Hashing Techniques to Resolve Collision| Separate Chaining and Linear Probing | Data structure

Summary

This educational video delves into the concept of hashing, a technique for efficient data retrieval with constant time complexity. It introduces hashing methods, including division, folding, mid-square, and modulo multiplication, and discusses collision resolution strategies like chaining and open vs. closed addressing. The script provides a detailed example using division and closed addressing with a hash function (h(k) = 2k + 3) mod (M), illustrating how to handle collisions through chaining and linear probing. It also explains the process of linear probing for collision minimization and hints at upcoming coverage of quadratic probing and double hashing.

Takeaways

• 🔑 Hashing is a searching technique that provides constant time complexity, O(1), for data retrieval.
• 📚 Data structures like arrays, linked lists, and trees can be used for storing data in hashing.
• 🔍 Two common searching techniques are linear search, which has a time complexity of O(n), and binary search, with O(log n).
• 🚪 Collision occurs in hashing when two keys hash to the same index in the hash table.
• 🔄 There are various methods to calculate hash functions, including division, folding, mid-square, and modulo multiplication methods.
• 🔄‍🔧 Collision resolution techniques include open hashing (closed addressing) and closed hashing (open addressing).
• 🔗 Open hashing uses the chaining method, where a linked list is used to store multiple items at the same index.
• 🔍 Closed hashing involves linear probing, quadratic probing, and double hashing to find the next available slot in case of a collision.
• 🔄 Linear probing is a closed hashing technique that searches for the next free slot in a linear sequence after a collision.
• 📈 The total number of probes can be calculated to measure the efficiency of the hashing process.
• 🔢 The order of elements in the hash table after all insertions can be determined using the hashing and collision resolution methods described.

Q & A

What is hashing in the context of data structures?

Hashing is a searching technique used to store and retrieve data in constant time, typically using a hash table and a hash function to compute the address where data is stored.

Why is hashing preferred over other searching techniques like linear or binary search?

Hashing is preferred because it offers constant time complexity for search operations, regardless of the number of keys, unlike linear or binary search which have time complexities of O(n) and O(log n) respectively.

What are the common data structures used for storing data?

Common data structures used for storing data include arrays, linked lists, and trees.

What is a hash table?

A hash table is a data structure that implements an associative array, a structure that can map keys to values, using a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

What is a hash function and why is it important?

A hash function is a function used to map data of arbitrary size to fixed-size values, which are used as keys or addresses in a hash table. It is important because it determines the efficiency of the hash table by minimizing collisions.

What is a collision in hashing?

A collision occurs when two different keys hash to the same index in the hash table, which is a problem because only one value can be stored at a given index.

What are the different methods to resolve collisions in hashing?

Common methods to resolve collisions include chaining (using linked lists), open addressing (including linear probing, quadratic probing, and double hashing), and the modulo multiplication method.

What is chaining in the context of resolving hash collisions?

Chaining is a collision resolution technique where each cell of the hash table contains a linked list of all the items that hash to the same index.

What is linear probing and how does it work?

Linear probing is an open addressing technique used to resolve collisions. When a collision occurs, the algorithm searches for the next available slot in the hash table by moving linearly through the table.

What is the difference between open addressing and closed addressing in hashing?

Open addressing is a method of collision resolution where an alternative address is found within the hash table itself. Closed addressing, on the other hand, refers to the use of a hash table and a hash function without explicitly stating the collision resolution technique, often implying chaining.

How is the division method used to calculate a hash function in hashing?

The division method involves taking the key value, multiplying it by a constant (often 2), adding a constant, and then taking the modulus of the hash table size to determine the index in the hash table.

Can you provide an example of how to store keys in a hash table using the division method and linear probing?

Sure. Given a hash function h(k) = 2k + 3 mod 10 for a hash table of size 10, to store the key value 3, you would calculate h(3) = (2*3 + 3) mod 10 = 9, so the key 3 would be stored at index 9. If there's a collision, linear probing would be used to find the next free slot.

Outlines

00:00

🔐 Introduction to Hashing and Collision Resolution Techniques

This paragraph introduces the concept of hashing as a search technique that allows for constant time data retrieval. It explains the basic idea of using a hash table and a hash function to store and retrieve data efficiently. The paragraph also discusses the potential for collisions when two keys hash to the same index and introduces various collision resolution methods, including open addressing and closed hashing, with specific focus on the division method for hash function calculation.

05:02

🔄 Collision Resolution through Chaining in Closed Hashing

The second paragraph delves into the chaining method for resolving collisions within closed hashing. It provides an example using a hash table of size N and a hash function h(k) = 2k + 3, explaining how to calculate hash values for given key values and how to store them in the hash table using the division method. The paragraph illustrates the process of handling collisions by creating linked lists at indices where collisions occur.

10:09

🔍 Implementing Linear Probing in Open Addressing

This paragraph explains the concept of linear probing as a default collision resolution technique in open addressing. It uses the same hash function and set of key values to demonstrate how to store them in a hash table of size 10. The process involves calculating the hash value for each key and then linearly searching for the next free slot in the hash table in case of a collision, thus ensuring that each key is stored in the first available position after the hashed index.

15:10

📝 Calculating Total Probes and Element Order in Linear Probing

The fourth paragraph focuses on calculating the total number of probes required to store all elements in a hash table using linear probing. It also discusses how to determine the order of elements in the hash table after all insertions are complete. The explanation includes a step-by-step process for each key value, showing how to handle collisions by probing sequentially until an empty slot is found.

20:15

🔢 Detailed Process of Linear Probing with Key Insertion

This paragraph provides a detailed explanation of how linear probing works, including the formula used to calculate the index for key insertion. It walks through the process of inserting keys into the hash table, showing how to handle collisions by incrementing the index and using modulo operation to wrap around the table until an empty slot is located. The paragraph also emphasizes the importance of maintaining the order of elements for potential examination questions.

25:16

👋 Conclusion and Preview of Upcoming Collision Resolution Techniques

The final paragraph wraps up the discussion on linear probing and teases the next video, which will cover quadratic probing as another method for resolving collisions in hash tables. It summarizes the basic idea of linear probing and sets the stage for further exploration of collision resolution strategies in hashing.

Keywords

💡Hashing

Hashing is a technique used to map data of arbitrary size to fixed-size values. In the context of the video, it is used for efficient data retrieval with a time complexity of O(1), meaning constant time. The script discusses hashing as a method to store and retrieve data using a hash table and a hash function, which is central to the video's theme of data processing and optimization.

💡Hash Table

A hash table is a data structure that implements an associative array, a structure that can map keys to values. The video script describes the hash table as a tool for storing data using the hashing technique, where the keys are mapped to specific indices or addresses within the table, which is crucial for the performance of the hashing method.

💡Hash Function

A hash function is a function that takes an input (or 'key') and returns a fixed-size string of bytes. The script explains that the hash function is used to calculate a hash value or address for storing data in a hash table. It's a fundamental component of the hashing technique discussed in the video.

💡Collision

Collision in hashing occurs when two different keys hash to the same index in the hash table. The script uses the example of keys 6 and 26 both hashing to index 6 in a table of size 10 to illustrate this concept. Collision resolution is a key topic in the video, as it impacts the efficiency of the hashing technique.

💡Division Method

The division method is a specific way to calculate the hash value in a hash function, as mentioned in the script. It involves taking the key, multiplying it by a constant, adding another constant, and then modulo-ing by the size of the hash table. This method is used to distribute keys evenly across the hash table to minimize collisions.

💡Open Addressing

Open addressing is a collision resolution technique where all elements are stored in the hash table itself. The script contrasts open addressing with separate chaining and explains that it involves methods like linear probing, quadratic probing, and double hashing to find the next available slot in case of a collision.

💡Chaining Method

Chaining is a collision resolution method where each slot of the hash table points to a linked list of entries that have the same hash. The script describes chaining as a way to handle collisions by creating a separate linked list at each index of the hash table to store colliding elements.

💡Linear Probing

Linear probing is an open addressing technique used to resolve collisions. The script explains that when a collision occurs, linear probing searches for the next free slot in the hash table by moving linearly through the table. It is the default method used when open addressing is specified.

💡Quadratic Probing

Quadratic probing is another open addressing technique mentioned in the script. Unlike linear probing, it moves quadratically through the hash table when searching for an empty slot after a collision, thus reducing clustering and improving distribution of entries.

💡Double Hashing

Double hashing is a more complex open addressing technique that uses a second hash function to determine the step size for probing. The script does not go into detail about this method, but it is listed as a technique for resolving collisions in a hash table.

Highlights

Hashing is a searching technique that provides constant time complexity for data retrieval.

Data structures like arrays, linked lists, and trees can be used for data storage in hashing.

Linear search and binary search are common data retrieval techniques with varying time complexities.

Hashing uses hash tables and hash functions to store and retrieve data in constant time.

Collision occurs when two keys hash to the same index in the hash table.

Different methods to calculate hash functions include division, folding, mid square, and modulo multiplication.

Division method for hash function is demonstrated with an example using modulo operation.

Open hashing and closed hashing are two types of hashing with different collision resolution techniques.

Chaining method is used in open hashing to resolve collisions by using linked lists.

Closed hashing uses techniques like linear probing, quadratic probing, and double hashing to minimize collisions.

Linear probing is a method of open addressing that searches for the next free location linearly.

Quadratic probing and double hashing are alternative methods to linear probing for collision resolution.

A detailed example demonstrates storing key values in a hash table using division method and closed addressing.

Chaining method creates a linked list to handle collisions when the same hash index is calculated for different keys.

Linear probing is explained with an example, showing how to find the next free location in case of collision.

The concept of total probes is introduced to measure the number of searches performed during the insertion process in hashing.

The order of elements in the hash table after all insertions is discussed, highlighting the sequence of stored keys.

The definition and process of linear probing are explained in detail, including the formula used for collision resolution.

Quadratic probing will be discussed in the next video as another method for collision resolution in hashing.

Transcripts

welcome back today's topic is type of

types of hashing okay so let me tell you

something about hashing hashing is

basically what it is a searching

technique okay and in searching of some

data if you use it this hashing

technique then the time taken is that is

a constant time but you can say order of

one time taken is order of one see for

storing some data obviously some data

structure would be used may be array may

be linked list may be tree okay and the

main thing is in data processing is the

main or the common paradigm is to store

the data and after that to retrieve that

data okay a post or we can now rock or a

tree with a knife or some processing

okay so for searching some date our for

retrieving the data two types of

searching technique I guess a possible

path other one is linear search and one

is binary search in linear search time

taken is in the worst case the time

taken is order of and and is that number

of keys stored in that array or some

data structure and in binary search if

you use then order of log n time taken

is order of log n so this time depends

on the value of n means how many keys or

how many you know a number of data you

are supposed to you have inserted and

you're supposed to retrieve from that

data structure okay but we want some

technique where the searching is you

know searching takes takes constant time

it does not depend on this number of

keys and that technique is hashing

technique okay the main concept is in

this hashing technique we use some hash

table and hash function using some hash

function for storing some data we will

calculate some hash value or you can say

that address and that address we can

store that key okay or that data in that

hash table okay fine now suppose some

policing occurs collision means if you

see let us take an example we have six

and twenty six these two keys we have

and

have their table of sorry the size of

hash table is 10 we can store 10 values

in that hash table and the hash function

you are given is this you are supposed

to use that division method three

methods are there to calculate the hash

function hash function that is division

method one is folding method and one is

mid square method and also another one

is that modulo multiplication method

also there okay so you are asked to use

that division method division method

McKevitt aapke hash function will be

like this key whatever the key mode mm

is size of hash table okay whether it is

eight whether it is ten or eleven or

fifteen whatever it is here in this

example i am taking the size of hash

table is ten now if you calculate the

address to store this key value six

using the hash function okay then what

should be the value C K value is now six

then six mod M value is in this example

am value I am taking and it is just an

example then the value would be six you

can store the six where at six location

or you can say the index should be six

like this here we will have one hash

table and from zero to nine because the

size of hash table is what n so at some

point we will have this index X and we

can store this X at this place but

suppose we have 26 another case 26 and

the using the same method you are

supposed to calculate the hash function

or you can say the address for this 26

now this address for 26 would be 26 mode

mm value is 10 and this is also 6 okay

but at sixth place we cannot store this

26 because already 6 is there so this is

known as policing when you know when you

calculate some hash function or the

location or you can say address for 2

keys and using that same hash from

that hash function will give you the

same result same index but we cannot

store two values at this place like 6

and 26 this is the collision so to

resolve these collision we have some

techniques today I am going to discuss

with you those techniques see and you

can see types of hashing one is open

hashing and one is closed hashing open

hashing is also known as closed

addressing and this closed hashing is

also known as open addressing okay so in

this method in first one this open

hashing the method to resolve these type

of collision okay is what that is

chaining method but you can see separate

chaining okay in this case the method

would be to resolve the collision that

is chaining method fine and in closed

hashing three methods are there to

resolve the collision see you cannot

remove the collision you can only

minimize the collision okay so three

techniques are one is linear probing one

is quadratic probing and the third one

is double hashing technique right I'll

discuss all these techniques with the

help of example so in this video I am

going to discuss with you this chaining

method how to use this chaining method

to resolve the collision okay through

let us take one example now let us take

one question suppose you are given these

key values this one is suppose any and

these key values are there three two

nine six eleven thirteen seven twelve

and you are supposed to store these key

values and put into the hash table the

size of hash table is given is N and the

hash function vs. which is given is h

case 2 k plus 3 in

this question and you are asked to use

division method and closed addressing

technique to store these values now

before you know solving these this

question you must have the idea what is

this division method and what is closed

addressing do is in method we have

already discussed how this method is to

be used how the hash function hash

values would be calculated the key and

mod of a mode of size of hash table and

what is closed addressing this is also

known as open hashing and in this case

what method is used to resolve the

collision that is chaining method okay

okay now let us we have one hash table

this hash table and this hash table is

of size 10

zero two one two three four five six

seven eight nine

okay this is up to zero to nine okay

this is our hash table of size and hash

function is 2k plus three and you are

supposed to use this division method now

calculate the location proper position

or you can say the address for these key

values here we'll write down the

location first key value is three find

out the proper place to store this three

in this hash table and how you will

calculate that using hash function and

hash function is given plus a which

method you will use the division method

or folding mat method or mid square

method you are asked to use division

method okay now calculate H for a method

obviously you know ko5 mode M this is

the method okay but here function has

from a hash function is given to k plus

3 so we cannot directly calculate that

three more 10 and the value is 3 no we

cannot directly put if this is not given

to you then you can directly use this

one okay if you are asked to use

division method but here you are given

this HK value 2 k plus 3 then how will

calculate this value this would be like

this 2 into the what is value of K here

we have 3 okay plus 3 and then mod 10

fine

now here that a K is this one because

hash function is given to k plus 3 now

what is the value 6 plus 3 is 9 9 mod 10

years 9 only because the result would be

the remainder only so the location is 9

at 9th index you can store this 3

okay now find out the position for value

to 2 into 2 plus 3 and now mod 10 4 plus

3 7 & 7 more 10 is 7 only the where you

can store this too at 7th place here we

can store this too

now find out this 1 4 9 have you'll find

out the same method 2 into 9 plus 3 and

then mode then what is the value 9 18 18

plus 3 is 21 21 more 10 is 1 here at one

position at one index you can store this

9 now for 6 say method 2 into 6 plus 3

more 10 what is the value 12 plus 3 is

15 15 more 10 is 5 at fifth place you

can store this value given you six now

for 11 2 into 11 plus 3 mod 10 see for

this one is 11 to 22 22 plus 3 is 25 25

mod 10 is 5 now check what is the

position for to store this 11 is 5 go to

5 but here we have already the 6 this is

the case of keynesian now in question

you are given use closed addressing

technique and enclosed addressing what

is the technique you will use chaining

method separate chaining method in

chaining method what is there go to the

fifth place already 6 is there then a

linked list will be used like this fine

and here 11 would be stored a chain

would be created like this okay

this is you can say linked list would be

used to store

the values in case of collision okay now

for 13 what is the value two into 13

plus 3 mod n 13 into 2 is 26 26 plus 3

is 27 28 29 29 mode 10 is 9 now here

also we have one collision go to the

ninth place but we have already three at

the space you cannot store 13 what

method you use chaining method and

chaining method making of the separate

linked list would be used and here we

will store what 30 now next is 7 2 into

7 plus 3 mode and what is the value 1414

plus 3 is 17 17 mode 10 is 7 he rolls

will happily then go to the seventh

place but here we have already what is

stored that is 2 we cannot store the 7

what is the method chaining method the

chaining method making our separate link

list will be created and the 7 would be

stored at this place this is linked list

link lachemann basically 1 node is

having two part one is that information

part and one is that address part that

this link will or this pointer will

contain the address of next node ok you

can denote like this only now next is 12

2 into 12 plus 3 mod 10 and what does

this value 12 into 2 is 24 24 plus 3 is

27 27 mod 10 is again 7 now go to

seventh place find out this is not free

you cannot store here go to the linked

list part here also you cannot store we

have 1 linked list

now again 1 linked list or one node

would be created fine

and 12 would be stored at this place and

this this you know this one this link or

this pointer will contain the address of

this node and this pointer would contain

now this is also not this is not also

not fine so this is the chaining method

how the staining method can be used to

resolve the collision the next video I'm

going to discuss with you what does that

how the linear probing method will be

used to resolve the or to minimize the

collision

okay now let's kiss the linear probing

method with the help of same question

the same question is there these are the

keys same hash function is there to k

plus 3 same you have to use division

method only the changes you're supposed

to use open addressing fine to store

these elements okay and size of hash

table is 10 now whenever you are asked

to use open addressing then by default

you will use linear probing to resolve

the or to minimize the collision okay

then that is the tool if you are because

this the open addressing few techniques

are there linear probing quadratic

probing and double hashing but by

default you will use linear probing in

case of say Putrajaya use quadratic

probing in that case when you lose that

one in case you're asked to use double

hashing then you will use double hashing

but by default you will use what linear

probing okay now check the only changes

the hair is we have open addressing same

question is there okay for this three

you have calculated the value that is

nine okay I'm just going to write these

values at ninth place we will use will

store this three now what is the place

for this key second this key value two

here is seventh here you can store this

to nine co-op can store Ikaruga here at

one occasion here you can store nine six

Co you can store at index fifth or fifth

location here you can store six now

problem comes in the case of eleven same

hash

hash value is being generated using this

hash function okay that is five when you

go to five but it is already there six

is already there so collision is there

now use linear probing what is C probing

means what in simple English term

probing means you know a synonymous

searching or a coach karna so it will

search the free place now where you can

it can store the value okay now at fifth

place we cannot store because already

six is their Pelini linear probing

linearly hamaji building it at the next

place this is a simple technique okay

next place

check out this is free yes this is free

throw you can store 11 at this place

fine and sometime in question you are

asked if we at last to store these

elements using open addressing total

props of kupatana how many total probes

was there okay so such SATA maybe

discuss contain four key to store this

key three how many props are there

obviously one probe is there now

ix big they have omni search here ninth

who searched or Nikki Anaya bar then one

probe is there for two also one probe

for nine also one province for six also

one prom but to store this 11 how many

probes you required one probe is encase

them up to five Milla search five but

this is already filled one probe is

already there now again search the next

location this is free yes this is free

fine so two probes are there one is for

this fifth one original one and next is

for the next one so here two props for

13 go to 9th but this is already filled

then what you will do find out linearly

the next place and next place would be

this one zero okay because we have

already say the size of this hash table

is 0 to 9 then go backward and this one

is 0 now where you can store this 13

here we can store this 13 next is how

many prompts for 32 probes 1 9 p ji apne

search here 9 who then happening next

place search here 13 then two proms are

there for storing the seven go to the

seventh place but this is already filled

then the next place yes this is free we

can store seven at this place and total

number of probes are due for storing

this 12 go to the seventh place this one

is already filled we cannot store go to

the next place this is already filled we

cannot store go to the next place this

is already filled we cannot cannot store

the next place is this 1 0 0 this

location but this was already filled the

next go to the next place that isn't one

that index 1 that is already filled we

cannot store go to the next yes say

linearly we are we are searching the

free place linearly one by one we are

not jumping like this I got a free Nieto

will jump towards three locations no

linearly up Azam canal that is why it is

known as linear probing here we can

store this to L okay now how many props

for this - L 1 is we go to 7 7 company

search here one probe one is for this

one - one is for this 3 4 5 and finally

6 6 problems now total Pro for this - LS

6 pro now total Pro bhai hope calculate

cursor go in case if you are asked to

total prop give me way sometimes in net

exam they are also asked he just find

out just tell the order of the elements

in the hash table after inserting all

the elements what is the order of

elements you are supposed to give the

for multiple you know that choices the

order of element is this this this or

this this this now in this case what is

the order of element in the hash table

if you are asked then the order of

element would be you has applicant start

over from 0

zero - please 13 then 9 then 12 then you

will not write the sex directly one in

two places are free one and two these

are blank then six then 11 then two then

seven and then three this is the order

of element okay so in linear this was a

shortcut

yup just look out the hash table and

finally next by next by search for

Karenia if you write the proper you know

definition of that linear probing then

what is that that one is this is what

happens in linear problem throbbing

properly if you'll write insert ki like

k1 k2 k3 these are keys at the first

free location from you plus I both mode

M where I will range from 0 to M minus 1

now here is a path I bogan 0 to M minus

1 M question media Haga that is 10 then

that I would be 0 to 9

what is this you you is what this

address so you can say this location

whatever whatever you have calculated

this 9 7 1 using this hash function that

would be the you now check out see if

directly a poisoning knife you use this

method or this definition and then check

out for 11 will check out okay 11 Kelly

in case of collision you will use this

one insert kind of a pokey I acquired

the very at the first free location from

this one fine for 11 what is the value

of U u plus I more 10 what is value of U

for 11 what is value of u whatever what

you have calculated that is 5 then 5

plus I I will range from 0 to M minus 1

of starting my Q value is 0 0 fine

more mm value is

ten and this would be five more ten that

is five but this is not free place okay

now increase value of Phi I is now 1

then 5 plus 1 mod n 6 more and that is 6

find out sixth place how many insert

copy our key copy ksi 6 3 because sixth

was free so here we have inserted this

11 so this is the same definition insert

key I add the first free location from

this one first free location yeha say

the very first free location was this

one sixth okay in case of this 12 check

out sea fort well what is when you of

you the value of you is 7 calculate 7

plus in starting value of I is 0 mod n 7

would 10 is 7 7 this one is not free ok

now 7 plus 1 mod 10 8 plus 8 more tennis

8 more pen that is 8 this one is also

not free because 7 is already there now

7 plus increase IQ value 0 to M minus 1

that is 0 to 9 7 plus 2 mode and that is

nine nine more 10 is 9 this is also not

free 7 then now I Q value is 3 7 plus 3

mode 10 that is 10 more 10 10 more 10 is

0 remainder would be 0 go to the zeroth

place but this one is also not free

because 13 is also there again check out

the next location 7 plus 4 more 10 11

more 10 that is 1 but 1 is also note

free now 7 plus 5 more 10 that is 12

mode n is 2 now go to the index - this

one was free okay and here we have we

can insert this 12 okay so using this

formula formula also you can calculate

these indexes or well you are same

linear probing me up cohosh deviled egg

nyan simply just look over the next

place is free and free then insert it

other nail top next Nick Nick Nick said

y'all grab circle together so this is

the basic idea of linear probing and

next video I'll discuss how to use

quadratic probing to find out that or

you can see the to dissolve the

collision till then bye bye

take care