Advanced Data Structures: Double Hashing

CORRECTIONS/NOTES:
6:46: h_1(k) should be h_1(x)

[@MaliaCamille]

Video starts @ 5:30

[@reddistone]

What does this have to do with double hashing?

[@hhh1656]

If we use digit floding method as hash function,then hash key for 70 is 7(7+0).where we have to insert key 70 as the table size Is 5

[@beegyoshi9292]

Wouldn't you want your second hash function to always output a number coprime to the length of the table for this to work? Otherwise you end up wasting space as when doing the "probing" step you could easily miss empty slots.

[@yunoletmehaveaname]

You want to miss empty slots. You don't want clumping, like he says at the beginning.

[@kevinjosueraymundogarcia3029]

Well explained video, thank you!

[@johnmartin9294]

Pro tip : watch movies on KaldroStream. I've been using it for watching loads of movies these days.

[@coltenbraxton4326]

@John Martin Definitely, I have been watching on kaldrostream for years myself =)

[@bridgerhouston4131]

@John Martin Yup, I have been watching on kaldrostream for years myself :)

[@leroylevi7432]

@John Martin yup, I've been watching on kaldroStream for years myself =)

[@isaacdouglas1119]

Is the h1(k) supposed to be h1(x)?

[@niemasd]

Woops, thanks, good catch! Yes it is

[@yesyas5972]

All clear, thanks

[@channelname9468]

why talk about linear probing in a video about double hashing

[@pawmeowzing2906]

what if after double hash there is collision too??

[@niemasd]

You keep probing just as you would with Linear Probing. The only distinction between Double Hashing and Linear Probing is that, in Linear Probing, if you have a collision, you keep probing 1 slot over at a time until you find an open slot, whereas in Double Hashing, if you have a collision, you keep probing h2(k) slots over at a time until you find an open slot

[@pawmeowzing2906]

@@niemasd the question now is how about if we want to find back the key? Say first round it didn't find it, then how do it knows when to stop probing when searching?

[@jacobtrombley7650]

You gave hash_function1(x) = x%5. Therefore, your hash_function2(x) = 1 + (hash_function1(x)/m)%(m-1) for 70 would be hash_function2(x) = 1 + ((x%5)/m)%(m-1) = 1 + ((70%5)/5)%(5-1) = 1 + (0/5)%4 = 1. Therefore, your hash_function2 is giving a different value than the one you computed (1 instead of 3). Maybe you meant hash_function2(x) = 1 + (x/m)%(m-1)? This would give you 1 + (70/5)%(5-1) = 1 + 14%4 = 3.

[@niemasd]

h(x) = x, not x%5. The %5 comes from converting the hash value (x) into a valid index in the array (which has a length of 5)

[@jacobtrombley7650]

@@niemasd gotcha, I misunderstood for h(x) definition

[@bwbs7410]

you spent half the video talking about linear probing in a video titled double probing smh