How do dictionaries (hashmaps) actually work?
ฝัง
- เผยแพร่เมื่อ 4 มิ.ย. 2022
- The hashmap (aka dictionary or associative array) is a data format where keys are associated to values, but using a clever algorithm which works in O(1) time. But how do these actually work?
- วิทยาศาสตร์และเทคโนโลยี
i know quite a bit abt hashmaps, and i have to say, you did a very good job explaining it.
except the part abt dealing with hash collisions, which it seems you made it look like that's the only way, when in reality it's only one way of dealing with the problem. for starters, it can be a tree or even not any structure at all: whenever a hash collision occurs, it puts the value in the next free slot, or it can do some moving items around before putting the value.
in fact, there are many algorithms to decide how to move stuff around and even how to get a free slot to put the value in. see for example, Robin hood hashing.
Very true, I guess I kind of tunnel visionned into just one possibility in order to finish the video as soon as possible. I'm really gonna need to improve my fact checking, the only video of mine I i think doesn't have holes is the flask one :|
I'll pin this so others can see the nuance.
@@AByteofCode i don't think the "tunnel visioning" is a problem as long as you make it clear that this is just one possibility.
This is really helpful! Very reminiscent of Fireship's 100 seconds videos, I can totally see you becoming big like that. Also the animation is great.
Thanks man! Yeah I'd started this channel after watching his second channel video on how he made content, and I wanted to give that style a shot (omg the ctrl-z trick is hot as f*ck tho).
and i'll see you in the next one 😄😄
These videos are great. Keep them coming.
Shall do! Also thanks for the kind words!
What can I do to make my future videos better? Any feedback (even negative) is greatly appreciated!
_Blazingly Fast_
@@THEROOT1111 Yep, sorted that one out lol. Monad and future will be at least not "whispering and reading an erotic novel at the same time" (some other commenter)
@@AByteofCode perhaps increase the sound levels. Reducible might be a good reference (speaking for myself, dunno abt others)
@@zyansheep yeah im not sure its actually _that_ fast in practice
@@proloycodes I was speaking pretty quietly in those videos, from monads on I'm gonna be nearly shouting at my mic, it sounds a lot better!
these videos are so high quality, im genuinely surprised you dont have more
clout
Considering my sub count of two weeks ago (30), I'd say that's getting resolved right now :)
ah yes, smoking hash to do fast coding
Hashmaps and Dictionaries are not the same thing. Yes a hashmap is a dictionary but a dictionary is not a hashmap. You can implement a dictionary with just about any data structure that lets you insert and remove data. e.g. an array of key-value structs. You can simply traverse using linear searching find the key you're looking for. It's not efficient but it works and is a dictionary.
A hashmap on the other hand uses a hash function with the key is a parameter to compute a hashcode. The code is used to decided where to store the data in your chosen data structure.
That is an excellent point! I had cut the difference out of my script but I should have left it in
thank you that was so helpful
I had normally imagined they were done with trees and therefore O(log n) for both reading and writing. That allows for scaling up without reorganising as it grow bigger.
The next question then is what size is used when creating the new object? Too large and creating a lot of them uses lots of memory. Too small and it has to rejig itself a few times if more and more elements are added.
I assume the size used would go up by powers of 2 or 4, putting a limit on the proportion of 'wasted' space. Although that extra space makes collisions less frequent.
What is the most efficient algo may depend on the ratio of reads & writes, not to mention knowledge of how many elements there are going to be.
I'm actually not too sure about specific implementations but I do know python does the rejigging with different sizes thing
I remember learning that prime numbers are specifically good at being the size of a hash map, their lack of factors helps avoid collisions, so it's probably not as simple as powers of 2.
Wow I actually understand it!!!
If you have to iterate through all of the keys that collided at the mod of the hash, then isn't accessing still linear time (albeit with a nice small leading constant)? IIRC when I implemented hashmap for my data structures class I had to use a tree at each index of the internal array for logarithmic time, but that's still not the constant time you mentioned.
I guess he meant to say that the average complexity is O(1). The case you are describing is the worst case scenario O(n) which shouldn't happen very often if the hashing algorithm is decent and even if its happens the lists wouldn't be that long and that's why is usually considered as O(1)
Ah, I hadn't accounted for, the internal array will usually have more spaces than the number of total items stored.
If your hash map is going at O(1) time you're doing something seriously wrong. Most languages either force you to say how big it is or automatically readjust for you when it grows. Needing to loop through the end array is just a contingency plan that even when needed, as Shai Léger said, isn't much overhead.
From my understanding, most practical implementation of hash maps, append additional colliding key-value pairs, as nodes of a linked list...? This has the advantage of not requiring any costly reallocations when inserting a value under a colliding key, whilst still managing to provide a close to `O(1)` time complexity, even with the random memory access...
Good point! I didn't do as much research as I should have for this video so I definitively missed a fair amount of details...
Thanks Bro, I'm trying for the n+1 time to get into APL
0:12 lmao, I got the meme references (except Mike, who's Mike?)
0:19 to anyone at this part, please note that he said "interpreters". Compiled langs (like Rust and C) don't need hashmaps to lookup vars, because all the variables that will ever be used are known and declared statically at compile-time, so the compiler can replace vars with raw pointers to memory addresses, completely invalidating the need for a "middle-man".
Dynamic langs like Py and JS usually require hashmaps, because the halting-problem prevents the bytecode-compiler from predicting assignments and declarations
FINALLY! Out of 8k+ views you're the first person to comment about the meme names! Let's just say Mike's last name is "Oxlong" :)
Also second point very good and true.
@@AByteofCode thanks lol
Just food for thought on your next video: "dictionary vs inline cache"
Whens next video, one tip it sounds like you're whispering from behind me lol
Definitively this week, I've nearly finished the editing for it! And yes, Im whispering a bit less in this one :p
Can we deal with hash collisions using a hashmap? Like hashmaps within a hashmap
Generally most hash collisions come from just rounding the hash result, so the solution is to have a bigger table. The odds of two different objects with actually colliding hashes is so low that you're better off with a regular list. However, using a different hash function for subtables is a very fun idea :)
Still have no idea what hashmap is, but very interesting 🧐
nice
I'm a bit tired of hearing hashmaps are "O(1)" when any implementation I've seen is dependent on the hash function as well as the collision handling. To my understanding, those two cannot possibly be implemented in O(1) unless you have an internal array large enough to uniquely cover every possible hash value thus avoiding collisions.
You are absolutely correct! Then again, our computers and all are turing complete, even though they do not have enough memory to actually satisfy the definition. These classifications are mathematical estimates assuming the algorithm is executed perfectly, but the list thing is just to overcome technical limitations.
Yeah I stumbled over that one too. It's weird, the computation time is not directly dependent on n but kind of stochastically, although a scenario is possible where it is stochastically 1. I guess one limitation of hash maps is knowing the best size of the internal array beforehand. Too big and you waste space, too small and you decrease runtime. How collisions are handled also play a major role in this.
The Next Fireship channel
keep up ❤❤
Thank you!
Yeah the 'blazingly fast' comment made me alert and then the presentation style and memes put me off watching it seeing it's pretty much a direct rip of Fireship. Be unique. Make your own style. Don't blatently rip it off someone else.
It also makes you to subscribe subliminally
Shhhh don't let the others know :)
Good content. Only improvement I suggest is mic quality. It sounds a bit like you are way too close to the microphone
Yeah I figured out a bit about how to use the mic I have so should be better in future videos (and the monad one)
Love the ethereal sounding voice
I mean, if my array is the exact size of the largest prime number known to man, it may take up way more storage than necessary, but I think I can avoid most collisions. On another note, doing that might be catastrophic if hackers can find the array size trivially, but at least it’s free of most collisions, right?
I don't immediately see the danger of hackers knowing the size of your hash map, but I'd be interested to know if you don't mind sharing :)
I just mean that is they know the size then they have a clue as to what the key will be since the key is usually related to taking the remainder of any value with the given prime number value, and if the size is the same as the key so that there are’t any sizing issues, if you can somehow find the array allocation size then you also know a big chunk of the key.
@@blazingazong Worst case scenario, the hacker could know a chunk of the key, which is a hash. Already, if you know a hash, unless the key is tiny or you have a lot of computing power, you won't get anything out of it. So if you only know a chunk of the hash, its pretty much worthless. And that's assuming knowing a key is useful. If you have a password dictionary, the actual password hash would be in the value, not the key, and if you have access to the file anyways, you have all the keys already :)
@@AByteofCode I see what you’re saying on both of those fronts. I suppose you’d have to run the hash code on the client side in order to see any of the code, and at that point you would be able to see the entire hashing algorithm anyways- and also you’d have the entire array of passwords sent to your client which would be hilarious- but even if you did know the key, you still wouldn’t have access to the array behind the hash map anyways. Thanks for the learning!
@@blazingazong Absolutely no problem! That's why im here :)
A dictionary doesn't have to be a hash map. Red-black tree can also be used, for example, as in Java's TreeMap (as opposed to HashMap). Yeah, in Java they call Dictionary a Map - because it's shorter I guess.
While C#, Python, Objective-C and Swift call Dictionary a Dictionary - some more limited languages like Perl and Ruby just call it hash, because hashtable is the only kind of Dictionary they have built in (and I don't even know what do you call it in those languages when it's a hash function like SHA1 or MD5). But truly special is PHP which calls a Dictionary just Array. That's it, Array. I mean Dictionary is also not a proper term - proper one is Associative Array. But calling Associative Array just Array is like calling JavaScript Java.
PHP always finding a way to make a non sensical decision smh. But yeah you are right that dictionary != hashmap, although the most efficient dictionary algorithm is the hash map
@@AByteofCode Well, I guess we expect too much from a technology called PERSONAL Home Page :-)
@@ArchonLicht i thought it stood for pile of hot poop 🤔
@@AByteofCode Yeah, that sounds about right :D
Hold on I'm a bit confused with the collision aspect of it:
So you could have like a class Cheese, then have an inherited class called Cheddar, then put it into a hashmap which shows its popularity and maybe with whom it is popular idk. But if Brie and Cheddar collide, idk how to find out which is the correct popularity of each Cheese.
I tried Googling but as you might've guessed, I can't find anything answering about Cheese-related Hashmaps 😂
I don't understand your question but basically if two keys get the same hash, their values are stored together as a list of tuples, meaning you can look through and every value will be written next to its original key.
so if Chedder and Brie both get the location 4, you'd have 4: [(Chedder, 78), (Brie, 52)]
@@AByteofCode Ohh ok thank you that mostly makes sense, do tuples only store 2 of the same datatype though or could it store a class and an int? Wait could you not store the whole array as a list of tuples or is that what a dictionary is? Wait nvm that would be O(n) wouldn't it ok thank you 😂.
@@TomtheMagician21 Tuples (in python at least) can store whatever the f**k you want. Other languages may require certain type consistencies, but considering that classes have their own type, you could have (Class, Int) tuples (im guessing, not too sure)
@@AByteofCode Oh that's cool then, is a tuple basically an array that you can't change?
@@TomtheMagician21 Exactly!
Good video. Only critique is that you skipped the part about how it actually finds the element by its hash value.
If the problem is I didn't explain the hash function, tbh I don't understand it yet but when I figure it out I'll make a video about that. If the problem is how it turns a hash into an index, note that a hash is just binary and can be read as a number, which can be modulo'd with the length of the list. That gives an index in the list and it uses the native array[index] method. Would it have helped if the video contained a re-write of dictionaries?
@@AByteofCode Thanks for the reply. Yeah I was referring to how the actual lookup happens. How you find the hash without just looping through until you find a match
@@kelton5020 Oh the hash is basically just a fancy mathematical function that takes a binary input and turns it into a semi random output of fixed length. I don't know much more for now (will be researching it soon) but its just a ton of modulos and bit magic.
@@kelton5020 I believe you would just plug the result of the (hash % num_of_indices) into the array index and then search the actual id or hash linearly in the inner array/linkedlist.
Although, I wish the video also explains the possibility of changing the array size.
Did an exam on hashmap while on hash this afternoon
Thematically consistent :)
Try speaking a bit louder please, it will help
Yep, did that with my monad video and I am very happy with the result so will be doing that in the future!
more videos on DSA
In the works ;)
hey but here how you've came with the length 0:56, why you've set it to 5
1. i thought that it's the current lenght + 1, but you have an empty map.
2. i thought it's just a huge number => lead to collisions maybe, and then we can solve them with the table
3. i thought that the element just appears out of thin air! 🤣
I'm getting NoMagic vibes with this channel
Idk who that is so I'll watch some of his stuff and get back to you about it
@@AByteofCode haha. That's awesome that you replied. Great channel! I'm looking forward to new content
@@MaxPicAxe I'm looking forward to making new content! Ngl thats a good combo. And thanks for the kind words!
brb fixing my multiple (lots of) ui elements highlight & select code now
wdym?
@@AByteofCode If I could select elements with a selection box and update their positions when dragging them by looking at a hashmap of their positions rather than looping through an array of all the positions finding the i-th index to update it would probably be faster when dragging a lot of elements at the same time right?
@@sanjaux I'm starting to see it, but wouldn't a position be an (x,y) coordinate amongst a large number of coordinates, so I'm not sure going through a hash table of every coord in your selection area is faster than checking every object, unless you have an absolutely insane number of objects per pixel. (or maybe I didn't see it)
@@AByteofCode I meant a hash table that stores the coordinates of each object's position and its name/ID *after* the selection was made, not specifically during the selection surrounding it by the selection's coordinates. I'd store the position of the objects afterward so when I need to access them for a position update it would have lower time complexity, at least that was my thought process 🤔
@@sanjaux I see, but what key would you use for the hash table?
Great video, low voice volume
Sorry about that. I fixed it for monads and future though, so shouldn't be an issue anymore!
Great job 👍🏽. Just advice but maybe it's me, you may try to articulate and speak a little louder cause it sounds like you're mumbling
twink femboy
Try using innovate...
god damn
Why you don't have ANY punctuation marks in your script. So tiring to listen to.
I had edited the spaces out but yeah won't be doing that any more lol