Thanks you very much. I recently failed an interview for a good position at a large corporation. I've had big problems with the HashSet topic and this motivated me to study the topic better. I'm happy that I found such a useful video.
I had a few very specific questions regarding HashSet implementation and your video answered them all. Thank you very much for such a great explanation!
Hello! First of all, thank you for this video! This is great! At 5:10, I'm not sure how the math behind that works? By multiplying the base with hashCode itself, will it raise 31 to the power of the base? First time hashCode is 0, so that's correct, but the next value of hashCode depends on obj, so I'm not sure how that works. Thanks!
If characters (from right to left) are c0, c1, ... , cn, and if int could accommodate the whole result, then the result would be cn*31^n + cn-1*31^(n-1) + ... + c2*31^2 + c1*31^1 + c0*31^0. Due to overflows, the unchecked block will end up with whatever has remained in the 32-bit int, making the whole process approximate, but fast. If you read current source code of the string class, you will note that its GetHashCode is shifting left by 5 bits (i.e. multiplying by 32) and then adding a correction (I guess, to move it closer to factor 31). It is another layer of approximation which makes implementation even faster than that based on full multiplication. github.com/microsoft/referencesource/blob/master/mscorlib/system/string.cs
First of all, thank you very much Zoran. Very useful video. I too had the same question which Dan has asked. After reading your answer and trying to understand it a bit more, I came up with the below note. Sharing it here, in case if it helps anyone else having the same question. Let us say, the string is "abcd"
Note that when we assign a character to an int, the character's ASCII value is assigned. In the explanation below, when we assign 'a' to an int, 'a's ASCII value is assigned.
The foreach loops through each character in the string.
Hi Zoran Horvat you did well for explanation. as a entry level developer. suggest can u use little bit less technical words. i hard to get the meaning. ;)
@@Ram-hv8xo Technically yes, but in reality an impossible task for me, personally... I do understand what you are saying, though. I might change over time.
Ram, with all due respect. It is my experience in interview for you to raise the bar. Usually devs do not lower their expectations on candidates, it is usually quite the opposite.
Oh I don't! If you really want to know, I write a coding script in my own scripting language and then run it on VS Code. The result is the video as you see it.
I recently was told a way to produce combined hash using ValueTuple like this : var vt = (this.State, this.MoreState); var hash = vt.GetHashCode(); It calls HashCode.Combine under the hood.
That should be the same as calling HashCode.Combine on your own, with an important distinction that ValueTuple will not aggregates hash codes if a component is a collection.
Become a patron and get access to source code and exclusive live streams: www.patreon.com/posts/here-is-why-is-81380423
Thanks you very much. I recently failed an interview for a good position at a large corporation. I've had big problems with the HashSet topic and this motivated me to study the topic better. I'm happy that I found such a useful video.
I had a few very specific questions regarding HashSet implementation and your video answered them all. Thank you very much for such a great explanation!
A clear and thorough explanation - very impressive!
Extreamly good explanation !❤ Thanks!
Top level of explanation! Bravo! And great example!
Super great video makes excited to learn more and get started! Love the "stay organized" motto !!
About the GetHashCode of strings - Some of the strings seems to have produced negative numbers. This is because the int overflows ?
@@tore28 No, it's because it is signed :)
Negative hash code is a regular, valid result.
Hello!
First of all, thank you for this video! This is great!
At 5:10, I'm not sure how the math behind that works? By multiplying the base with hashCode itself, will it raise 31 to the power of the base? First time hashCode is 0, so that's correct, but the next value of hashCode depends on obj, so I'm not sure how that works. Thanks!
If characters (from right to left) are c0, c1, ... , cn, and if int could accommodate the whole result, then the result would be cn*31^n + cn-1*31^(n-1) + ... + c2*31^2 + c1*31^1 + c0*31^0. Due to overflows, the unchecked block will end up with whatever has remained in the 32-bit int, making the whole process approximate, but fast.
If you read current source code of the string class, you will note that its GetHashCode is shifting left by 5 bits (i.e. multiplying by 32) and then adding a correction (I guess, to move it closer to factor 31). It is another layer of approximation which makes implementation even faster than that based on full multiplication.
github.com/microsoft/referencesource/blob/master/mscorlib/system/string.cs
First of all, thank you very much Zoran. Very useful video. I too had the same question which Dan has asked. After reading your answer and trying to understand it a bit more, I came up with the below note. Sharing it here, in case if it helps anyone else having the same question.
Let us say, the string is "abcd"
Note that when we assign a character to an int, the character's ASCII value is assigned.
In the explanation below, when we assign 'a' to an int, 'a's ASCII value is assigned.
The foreach loops through each character in the string.
before 1st iteration
hashCode = 0
1st iteration
hashCode = 31 * 0 + 'a' = 'a' = 31^0 * 'a'
2nd iteration
hashCode = 31 * (31^0 * 'a') + 'b' = 31^1 * 'a' + 31^0 * 'b'
3rd iteration
hashCode = 31 * (31^1 * 'a' + 31^0 * 'b') + 'c' = 31^2 * 'a' + 31^1 * 'b' + 31^0 * 'c'
4th iteration
hashCode = 31 * (31^2 * 'a' + 31^1 * 'b' + 31^0 * 'c') + 'd' = 31^3 * 'a' + 31^2 * 'b' + 31^1* 'c' + 31^0* 'd'
@@vinayv3160 I was about to ask a similar question. I see it has not been answered yet, though
Hi Zoran Horvat you did well for explanation. as a entry level developer. suggest can u use little bit less technical words. i hard to get the meaning. ;)
@@Ram-hv8xo Technically yes, but in reality an impossible task for me, personally... I do understand what you are saying, though. I might change over time.
Ram, with all due respect. It is my experience in interview for you to raise the bar. Usually devs do not lower their expectations on candidates, it is usually quite the opposite.
How do you type so fast?
Oh I don't! If you really want to know, I write a coding script in my own scripting language and then run it on VS Code. The result is the video as you see it.
Sa . It's hard when you look at the software
I tNice tutorialnk i'm gonna stick to gaming...
I recently was told a way to produce combined hash using ValueTuple like this : var vt = (this.State, this.MoreState); var hash = vt.GetHashCode(); It calls HashCode.Combine under the hood.
That should be the same as calling HashCode.Combine on your own, with an important distinction that ValueTuple will not aggregates hash codes if a component is a collection.