Really refreshed my memories on these concepts. How about doing some analysis on real minecraft classes’ codes sometime? That will certainly makes the purpose of using hashset in minecraft even clearer.
Great video! Just wanna add a little bit more details as I'm bored. Haha.
In most cases, hashtables/hashmaps are initialized with the number of slots being a prime. Using composite numbers as slot count is commonly avoided, and I've read books that recommend avoiding powers of 2 at all cost unless certain special algorithm is required and implemented. Doing so is usually the best way to minimize the probability of collisions since modulo is used as array indices. Since traversing through a linked list requires extra computational time, it's crucial to keep the collision rate as low as possible. (Chaining is often the best collision resolving method as others, especially probe sequencing, require some extra codes to deal with collided items even after one of them already being removed.)
Thanks, I finally know what hashing and a Hashset is. You have shown me the start of a VERY deep Rabbit hole.
I think this was a good explanation for me and others, which came on contact with programming, bit I think it is not a good video for People who never Programmed befor. The examples where you computed the index for the Hashset manually was a little exhausting, bit nevertheless, Thanks, I learned something new
22:31 Usually it's bottom left, middle left, top left, the right one below that, then the root node and the same order on the other half. If you insert ascending numbers in that order into it, you can always go left for lower numbers and right for higher numbers. For example, if you insert 123456789 and then search for a 6, then you first see the root node 5, go right, you see 8, go left, 7, go left, 6.
That is true for sorted sets, however in hash sets there is no particular requirement on the iteration order, so they went for this weird linked structure for the iteration order, and the linking order is different depending on whether a node was added via treeification or added after the tree was formed, and differently again once nodes are removed. All that is a very long way of saying that I judged that order to be too complicated for this video, and in tech mc we don't tend to rely on treeified ordering anyway because of how volatile it is.
4:20 Actually actually, your original statement was correct. For example in Java, you can iterate over all the entries in the map, which are these pairs of key+value. So a map is indeed a set of pairs.
12:14 places it in square? #2. Starting from 1, it gets put in the third box. However, the box's counting starts from 0. Some people might assume it starts from one and be confused
It may be more confusing if you're not used to 0-indexing, but the modulus operator outputs a value from 0 to (n-1), not from 1 to n, so it makes more sense this way.
Set elements "hash" to a specific index in a collection. It's said that the elements are "null" because they don't actually exist in the collection, they're just "marked" as existing or not. It's useful to NOT store them since it SAVES memory. The purpose of a set is not to keep track of values, but to keep track of a value's existence in a collection.
To answer your second question, Java has their own implementation of a HashSet that Minecraft uses, so it it's really about the Java maintainers' decision, not the devs. Not really lazy or smart, just the most common way to do it
Maybe, but the next video will be more in depth and I dont think there are any computer science vidoes that go that in depth on the java data structures in particular
Really refreshed my memories on these concepts. How about doing some analysis on real minecraft classes’ codes sometime? That will certainly makes the purpose of using hashset in minecraft even clearer.
5 likesPacked full of great info, well done!
26 likesReplies (2)
Rays Works I see you on every minecraft video
3 likes@Li3 he watches them but he doesnt seem to learn anything. or at least clicks on the video and comments
4 likesVery clear explanation! I'm interested to see the next videos to see how it influences minecraft stuff!
4 likesWow, great explanation! Thank you very much for doing this video!
1 likeGreat video! Just wanna add a little bit more details as I'm bored. Haha.
2 likesIn most cases, hashtables/hashmaps are initialized with the number of slots being a prime. Using composite numbers as slot count is commonly avoided, and I've read books that recommend avoiding powers of 2 at all cost unless certain special algorithm is required and implemented. Doing so is usually the best way to minimize the probability of collisions since modulo is used as array indices. Since traversing through a linked list requires extra computational time, it's crucial to keep the collision rate as low as possible. (Chaining is often the best collision resolving method as others, especially probe sequencing, require some extra codes to deal with collided items even after one of them already being removed.)
BTW your works are amazing! I just subbed. c:
Thanks, I finally know what hashing and a Hashset is. You have shown me the start of a VERY deep Rabbit hole.
1 likeI think this was a good explanation for me and others, which came on contact with programming, bit I think it is not a good video for People who never Programmed befor. The examples where you computed the index for the Hashset manually was a little exhausting, bit nevertheless, Thanks, I learned something new
Data structure lessons in a Minecraft channel!
23 likesBeautiful explanation. Thanks.
0 likes22:31 Usually it's bottom left, middle left, top left, the right one below that, then the root node and the same order on the other half. If you insert ascending numbers in that order into it, you can always go left for lower numbers and right for higher numbers. For example, if you insert 123456789 and then search for a 6, then you first see the root node 5, go right, you see 8, go left, 7, go left, 6.
0 likesReplies (1)
That is true for sorted sets, however in hash sets there is no particular requirement on the iteration order, so they went for this weird linked structure for the iteration order, and the linking order is different depending on whether a node was added via treeification or added after the tree was formed, and differently again once nodes are removed. All that is a very long way of saying that I judged that order to be too complicated for this video, and in tech mc we don't tend to rely on treeified ordering anyway because of how volatile it is.
1 like4:20 Actually actually, your original statement was correct. For example in Java, you can iterate over all the entries in the map, which are these pairs of key+value. So a map is indeed a set of pairs.
0 likesReplies (2)
Internally it's the other way around, the public API misleads ;)
0 likes@Earthcomputer That's weird. Wouldn't it be more efficient to not have tons of null values?
0 likesGreat video but I think you should've included some of the big Os
0 likes12:14 places it in square? #2. Starting from 1, it gets put in the third box. However, the box's counting starts from 0. Some people might assume it starts from one and be confused
0 likesReplies (1)
It may be more confusing if you're not used to 0-indexing, but the modulus operator outputs a value from 0 to (n-1), not from 1 to n, so it makes more sense this way.
1 likeVery interesting video thanks!
1 like"Sets are maps with null values"
2 likesThis seems weird to me. Why waste the memory? Is there a reason or was it just easier to implement this way (i.e. lazy/smart devs)?
Replies (1)
Set elements "hash" to a specific index in a collection. It's said that the elements are "null" because they don't actually exist in the collection, they're just "marked" as existing or not. It's useful to NOT store them since it SAVES memory. The purpose of a set is not to keep track of values, but to keep track of a value's existence in a collection.
5 likesTo answer your second question, Java has their own implementation of a HashSet that Minecraft uses, so it it's really about the Java maintainers' decision, not the devs. Not really lazy or smart, just the most common way to do it
Congratulations! You deserve it! :D
14 likesVery interesting video!
no really, it was good video xd
Cool i'm the 2000th subscriber
0 likesYou're to redstone engineers what redstone engineers are to the rest of us ! Best mind that ever played Minecraft !
how do you only have 2k subs? O_O you're pretty much legendary on 2b2t. Great videos!
1 likeReplies (3)
Why is he legendary on 2b2t?
0 likes@TheDutchisGaming he leaked the book dupe glitch, well he was the first source of the program.
1 likealso, the "unbreakable'' items scourge we are currently in, we can thank him for ;)
0 likesI heard that you invented the hashset
11 likesReplies (1)
Lol
0 likes"EA, you owe I"
3 likesOrf EA shill confirmed
This duplication glitch is very complicated and confusing
0 likesReplies (2)
It's not and go comment on that video, not this
0 likes@ahgqw bassdd its a joke go take your salt elsewhere
0 likesyou could have probably just linked to some computer science channels video on hash sets and maps, couldnt you? xD
1 likeReplies (1)
Maybe, but the next video will be more in depth and I dont think there are any computer science vidoes that go that in depth on the java data structures in particular
5 likeshElP dTtS brOKe MY moBsWITch
7 likeslen(hello) is 5 not 4 so *****86%5 == 1 right?
0 likesVery technical and useful for bedrock speedrun
3 likesReplies (1)
Xd
0 likes\o/
4 likesLinux! Nice...
3 likeshello ilmumbo!
1 likeWtf is this shit. Where is LongOpenHashSet. xd
2 likesHello allo
2 likes