Video 54 of a series explaining the basic concepts of Data Structures and Algorithms. This video explains the concept of Double Hashing. This video is meant for educational purposes only.
This channel is a godsend for all who are taking the course Data Structures and Algorithms (and similar) and suffer, like so many others, from lecturers who can't teach. Myself included. I would fail and drop out if videos like these didn't exist.
there's an issue with this, you can get out of bounds. let's try to hash key 12, supposing index 12 is already occupied. hash1(12) = 12, hash2(12) = 2 you'd need to add key 12 at position 14, which doesn't exist. fix: position should be given by (hash1(key) + j * hash2(key)) mod size.
Thanks for the forecast! I need some advice: My OKX wallet holds some USDT, and I have the seed phrase. (alarm fetch churn bridge exercise tape speak race clerk couch crater letter). How can I transfer them to Binance?
I think the first thing you should say is that double hashing only works for a prime length array. The second thing you should fix is: I think the formula should not d be hash(k) + jhash2(k), the reason being that I tried it using a while loop in java and it enters an infinite loop . By your approach if the j is zero then the code would keep on repeating itself(do keep in mind that the second function cannot have the value of 0 in double hashing). So it should always start with hash(k) + hash2(k). So it should look like this hash(k)=hash(k)+hash2(k). This way we would always reach the intended way purpose of double hashing which is to increment hash(k) with the value of hash2(k). Like many beginners, I think those 2 points would make it easier for us to grasp and comprehend the material. Thank you, otherwise great content and delivery
I think that starting with j = 0 is fine, there doesn't seem to be any reason why you'd need to start with j = 1. Also, double hashing can work on non-prime length tables, if the hash2(k) always outputs a number that is not a factor of the size of the table.
It can happen that hash1(k) + j * hash2(k) > 13 I think its possible, despite that 7 and 13 are prime. In your example you had "Lucky numbers" :D Otherwise you end up with index out of bounds.
thank you very much for your videos. I have a question , what will we do if the collision occur at the final key when using linear probing and quadratic probing ?
Anyone here know what m in this statement could be? H2(k) = 1 + (k mod (m - 1) I get that it's the hash2 taking the key as input, but what would m represent here? A value incrementing if the spot it taken perhaps?
The m represents the size of the array so if you have got an array of [1, 2, 3, 4, 5, 6] then the m is 6. AAU gang here to save you (skal selv op i ALG)
This channel is a godsend for all who are taking the course Data Structures and Algorithms (and similar) and suffer, like so many others, from lecturers who can't teach. Myself included. I would fail and drop out if videos like these didn't exist.
This saved me from failing out of my intro to data structures course (during COVID). Life saver.
Why madam takes 7 there
@@BhargavPuri-ki7hm I think question gives us
literally the most underrated hashing legend
thank you for saving me
Short and crisp explanation with example. Saved my lots of time. Thanks a lot
Thank the gods this video exist!
Thank you so much this saved me from today's discussion of data structures
Τhank you sooooooo much ... I was looking for this for 6 hours and it was a five min solution... hate my life -_-
BUT YOU ARE GREAT:)
I love the way you break down the concepts!! Thank you so much for sharing !
Your voice is amazing ,it made fall to sleep .
thank u ,u saved my life ,keep the good work
😂😂
You are an excellent teacher! Did great on my quiz because of this video ❤️
Thank you so much, you're doing a great job ❤️
great explanation and neat handwriting!
Thank you so much for your videos! You are just the best!
A simple example was taken. Hope you expand to a bigger example with multiple collisions.
Very nice
Clearly understand
Your voice is awesome ❤️❤️
WHAT A LIFESAVER, THANKS AND LOVE YOU SO MUCH, HOPE YOU HAVE A NICE DAY
You are a fantastic explainer. Much love from Texas :) and pray I pass this exam!
Very nice courses! Thank you madam!
this is life saver. thank you
Thank you so much! The explanation is really clear
that was too simple..Thank u mam
Great job explaining!
18mod7 =4 k= 4 , hash2 7-4=3 and so on for other numbers
Pro trick : watch movies at Flixzone. Been using them for watching a lot of movies during the lockdown.
@Christian Oliver definitely, I've been using flixzone} for years myself =)
How to calculate mod..18%7 is 1.26 naa ❓
Reply plz
@@Mammajiprincess 18/7 --> remainder = 4 so 18%7=4.
there's an issue with this, you can get out of bounds.
let's try to hash key 12, supposing index 12 is already occupied.
hash1(12) = 12, hash2(12) = 2
you'd need to add key 12 at position 14, which doesn't exist.
fix: position should be given by (hash1(key) + j * hash2(key)) mod size.
This is the correct method
πολύυυυυυ μάγκας respect
Saved my day
Beautifully explained
amazing explanation, thank you
Thank you sister helped a lot
Great explanation, thank you very much!
Nice explaination
Beautiful handwriting and cute voice ♥
Very nice.continue like this
Wowee great vid, helped a lot thx so muhc tee hee
Really helpful!! very clear
Amazing explanation, thank you so much
Short and concise :) please make more videos like this 👍
Short and sweet
Thanks, From TURKEY
wow, me encanta que excelente explicación, muchas gracias.
thank u friend.. just for this video i can clear my concept
very much helpful thank you
mam why don't you upload new videos .your videos are far more better then university professors !
It would have been nice if you showed how you got the hash 2 values
Great !!
And what happens if we get a larger value than our index limit?
Normally you would do (hash1 + i + hash2) modulo array.length. This way the value can't exceed the index limit.
love your hand writing :D
Excellent job madam 🤩🤩🤩🤩🤩
Thanks for the forecast! I need some advice: My OKX wallet holds some USDT, and I have the seed phrase. (alarm fetch churn bridge exercise tape speak race clerk couch crater letter). How can I transfer them to Binance?
I think the first thing you should say is that double hashing only works for a prime length array.
The second thing you should fix is:
I think the formula should not d be hash(k) + jhash2(k), the reason being that I tried it using a while loop in java and it enters an infinite loop . By your approach if the j is zero then the code would keep on repeating itself(do keep in mind that the second function cannot have the value of 0 in double hashing). So it should always start with hash(k) + hash2(k). So it should look like this hash(k)=hash(k)+hash2(k). This way we would always reach the intended way purpose of double hashing which is to increment hash(k) with the value of hash2(k).
Like many beginners, I think those 2 points would make it easier for us to grasp and comprehend the material. Thank you, otherwise great content and delivery
I think that starting with j = 0 is fine, there doesn't seem to be any reason why you'd need to start with j = 1. Also, double hashing can work on non-prime length tables, if the hash2(k) always outputs a number that is not a factor of the size of the table.
cool, thanks
y u have taking in hash2 (K)=7- kmod7??
18's key hash 2 is 4 not 3???
second hash function is k(mod)7 so putting the values in (7-k(mod)7) it comes out to be 3
THank you very much
Thank you sooo much ❤
Maam , when addition --- h1(k)+ j*h2(k) ,,,, greater than 13 , then what to do?
amazing
why 7?? is it an upper bound of 13/2?
thank you kind woman
what do you mean ... 5 + 0 in to 3, then 2 + 0 in to 1? I thought it was supposed to be hash1 + hash2 ??
Yessss
Even I dint get that part
in to = multiply = "j" state in the formula
for this example if 44 hash 1 was 5 and hash 2 was 6. Would we go in position 6? or would we do location of 5+(6*2)mod 13?
Thanks tomorrow I'll have a ds exam
ERROR IS THERE (hash1(k) +j*hash2(k))modN will be there you have missed modN
Thanks! But how do SEARCH (not insertion) works? For example, how to find 44, if 18(at index 5) was removed an is EMPTY?
perfect teacher :o))
It can happen that hash1(k) + j * hash2(k) > 13
I think its possible, despite that 7 and 13 are prime. In your example you had "Lucky numbers" :D
Otherwise you end up with index out of bounds.
doesn't matter if index is out of bounds
@@StoicLife-7 so if it becomes out of bounds then what happens?
@@StoicLife-7 it does
thank you very much for your videos. I have a question , what will we do if the collision occur at the final key when using linear probing and quadratic probing ?
thanks you so much
what would happen if sum of two hashes is more than the table size?
maam,
are you doing MS in AI ?
Why u chose hash2 a particular function. Plz, elaborate the reason for choosing that function. Thanks
she used an arbitrary function
Where did you get the 7?
nice!!!!
I don't know how you manufactured the 7 in the first four lines and you didn't explain that. Had to use other resources to figure that out.
Nice voice❤
why did u take 7 while calculating v alue of h2?
r-k mod r is the formula and r should be a prime number less than the size of hash table
Its given in question and changes according to question.
Why didn't you modularized the double hashing function by the table size
Yeah she made that mistake she has to take modulus of the whole h1 plus h2
Thank You
dought free lecture :)
Ye hash 1 nd hash 2 kha se aaya
How can u take that mod 13. If they given we taken.... right...and for hash 2 also how can u randomly take 7 and for the mod also take 7
Why madam takes 7 there
really ,u dont think its important to tell hwo to take second hash function ?
Are you from CMU?
Vo 11-kmode11 ku nhi hua?
Anyone here know what m in this statement could be?
H2(k) = 1 + (k mod (m - 1)
I get that it's the hash2 taking the key as input, but what would m represent here? A value incrementing if the spot it taken perhaps?
The m represents the size of the array so if you have got an array of [1, 2, 3, 4, 5, 6] then the m is 6. AAU gang here to save you (skal selv op i ALG)
@@J2KJonas King, gir en øl i gaden.
😇😇😇😇
Thanks!!!!
I lub u😻
How to get hash1 and hash2 values
How did you calculate H1 and H2?
taking mod values, like we do for other hashing functions
@@AshutoshSingh-qj1gm not exactly there's sth about prime numbers for H2.
@@fisayoojo9331 it has to be of q - (k mod q) where q is smaller or equal the size of the array
saolasın hintli bacı
11 mod 7 is 4
you have taken easy example
take some complex example
I want extendable hashing
HELLO im from poland, im young programmer, im have algoritmos kolokwium, thx for help.
The hash 2 value of key 44 is 1 not 5.
h2(K) i didn't understand
mam wiTh face cam pdao
eyy ooru madam meddhi
mee number pettandi please
Explain me the calculation of
" hash2 "