Hash Tables, Associative Arrays, and Dictionaries (Data Structures and Optimization)
Вставка
- Опубліковано 13 чер 2024
- An introduction to the hash table data structures, how that relates to associative arrays and dictionaries, and how to use them.
Support me on:
Patreon: / simondevyt
Follow me on:
Twitter: / iced_coffee_dev
Instagram: / beer_and_code
Github: github.com/simondevyoutube/
Covering a bit more ground with data structures, algorithms, and optimizations, we're looking at hash tables now. These are amazing, general purpose data structures that are a good fit in a lot of cases. We'll explore the different collision resolution schemes like chaining and open addressing. We'll touch on abstract data structures and the difference between an associative array (or dictionary) and a hash table. Finally, we'll do a dive through existing code to show some examples of where I've used them in a lot of the games I've built in JavaScript.
Misc Links:
scottmeyers.blogspot.com/2015/...
en.wikipedia.org/wiki/Hash_table
en.wikipedia.org/wiki/Associa...
en.wikipedia.org/wiki/Abstrac...
en.wikipedia.org/wiki/Birthda...
en.wikipedia.org/wiki/Open_ad...
en.wikipedia.org/wiki/Linear_...
en.wikipedia.org/wiki/Quadrat...
en.wikipedia.org/wiki/Double_...
en.wikipedia.org/wiki/Compari...) - Наука та технологія
I found the nihilistic voice tone a perfect match to learn IT stuff.
i love it
"This is objective truth. Watcha gonna do?"
These were 13 relaxing minutes of listening to you talk about hash tables (Y), enjoyed, thanks!
Probably also worth mentioning the case of *no* collision resolution, and just doing an unconditional overwrite, basically a "lossy hash table", which gives guaranteed constant-time lookups. This approach is commonly used in chess engines, where it's used to cache position evaluations to spare the search from having to recurse further down the game tree. Of course, collisions happen and you lose the evaluation previously held in that slot, but that just means you have to search the position, which you'd have to do anyway if you weren't using the hash table to begin with, so it's a huge win overall.
9:19 that's why small objects in javascript (v8) are internally represented as two arrays, one for the keys and another for the values instead of a hash tables
pretty cool
Although being a motion designer by trade, I have a strong interest in programming and data analysis. After discovering your channel a few days ago, I have been binge watching. I’m one third done with your shaders course. Learning from you is like shopping at Home Depot for my graphics/programming self improvements. Sarcasm is the icing on the cake! Thanks Simon.
The timing of this video couldn't be more perfect, Just had a class lesson about hash tables today!
I am addicted to this channel. your way of explaining stuff really kills it.
This is very nit-pikcy but "Hermes" is most definitely 6 letters
Great video haha
Omg how did i not notice that hah
Quite playa hatin' on the world's best hashing function.
I'd not noticed that too :D
I was wondering if there was a prize for being the thousandth person to point that out!
Maybe it happened because Hermes was the messenger of the gods and he delivered an extra letter?
OK, I was leaving anyway ...
@@T0NYD1CK I think I had the second comment on this video lol
Whatever helps you man
Thank you for all your videos!!
As someone who is in its early university years and has a job a software developer, I can learn a lot with all of your content!
Again, thank you so much and great work!
Please support future vids: www.patreon.com/simondevyt
The energetic funny text makes for a good contrast with the calm, almost sleepy voice. I don't know when I might need to handcraft an artisanal data structure but this is neat!
This video was beautiful and very relevant to a discussion I was having recently about how Big O notation is often misused and can be misleading, because people try to optimize for handling numbers of items they won't ever be handling.
Yeah, a weird number of devs like to make believe their systems are going to be used by 18 trillion people, so better prepare now. I prefer to just go with something reasonable, and have an API surface that can swap out the underlying implementation later if need be.
Okay so I've literally never understood these damned things before, mainly because I'd never been able to get over how they're different than arrays, and you just cleared up months worth of confusion in a few minutes. You're my new favorite.
Yay!
new vid by the king! I can't wait until this series reaches the wierdest types of trees.
I guess sometimes it is best to keep it simple, but I am really pumped to hear some stories about custom datatypes you've seen in your life. useage, flaws, or brilliant solutions by you or your coworkers. I bet youve encountered some.
Yeah I have some interesting stories that I'd like to tell, unsure what format suits those best.
thank you for using those names it made my day
😉
Great explanations with slang sauce. They make hard chunks of information tender and more digest. Bravo
Great video as always Simon, keep them coming, it's a privilege to learn from you
This channel is my best discovery in 2022
Even as an experienced developer, i find your videos are very entertaining and informative. 😘
Great stuff man, knew it from my studies but great refresher on the basics. Subed!.
UA-cam algorithm -> awesome channel. Profit!!
Great video as always. The animations were fun, please keep them in future videos too.
Just discovered your channel and totally charmed, great, funny, clear and instructive.
la la la, I can see this
Beautiful presentation
Great compilation, thank you. 👍
Informative and entertaining. How I handled it with one of my earliest attempts at implementing hash tables was to store the non-normalized key with the data, I had an array of all the data as a power of two so lookups were by key&(p2-1) and I had an array of dynamic arrays for the buckets storing an index into the main array of data. For deletions I would swap the element to be deleted to the end of the array and repoint the element that was there to the place where the old element was and decrement. Since each bucket array merely stored an index into the main data array when I resized or sorted, I could just rebuild the bucket arrays using the stored hash and not have to query the hashing function. On my old 533mhz celery it could handle millions of strings quite fast. So I've been iterating many designs for hash tables since.
Very good videos. Great presentation. Thanks!
I wrote a puppeteer script to like all your youtube videos. Next goal: Using a corn-job to check for new videos and like it as soon as they come.
hah
the peppering of dry sarcasm is everything ive ever wanted in programming info videos. You have a new dedicated viewer. Now I just need to find a sweary programming channel.
"I just need to find a sweary programming channel"
Now I find myself imagining Gordon Ramsay if he were a C++ programmer, roasting bad or inefficient code.
Thks. I envy your computer expertise & your fluency in teenager speak.
@@MuhammadHosny0 ?Could you spell that out for everyone?
@@MuhammadHosny0 I apologize I wasn't clear. I'm a retired military physicist & my wife despises hard-science jargon (for-good-reason).
Besides the typical geek physics, most of my career has been explaining the impact of hard-science on/to those outside my geek discipline.
I've learned the hard-way that until you can tailor your discipline to synergetically fit your audience you haven't really mastered it. SimonDev seems to have mastered this sort-of-thing & so I envy him (in a good way).
For example Einstein said until you can explain it clearly to a 6 year you don't really understand it ; ua-cam.com/video/EjUaXQbMAeA/v-deo.html
Don't worry, grokked the comment, love the compliment :) Does take me a little while to work through to an explanation that I like and feel is as accessible as I can make it.
saw Futurama references and immediately subscribed
Excellent video!
That. Was. Beautiful.
I love this freaking videos
3:10 nearly choked on my coffee there.
my mind was absolutely blown when I learned about hash tables in m data structures class in 2015/6. They're still my favorite data structure (yes, im weird. i have a favorite data structure lol)
Nothing wrong with playing favourites! I'm partial to dynamic arrays myself.
@@simondev758 they _are_ pretty awesome! abstract data structures are super cool!
Simon, your javascript contents are golden, please make more of thses! Also your Making game videos are entertaining!
Woah, Batman watches my videos
Couldn't resist clicking on the Cuckoo Hashing couldn't you Simon? XD
Now, that sounds like some wise old man giving me essential life lessons 😂😂.
Thanks a lot though... ❤️
Aww man, I'm in old man territory.
That was awesome 😎😎😎😎😎
"holding a bunch of crap" hahahaha 🤣
"pedantic != skilled" hahahahahah ❤
Im trying to implement your spatial hash grids to form a good basis for calculating road network connections in a tile based system, getting there with it but wonder if you have thought of doing a video on it? Love the content btw!
Kinda guessing that you could represent the road network as a graph, would be easier. Spatial hash is great for speeding up queries, so if you end up needing that you simply bolt that over top.
Love your videos! Could you do one discussing design patterns?
Absolutely, any particular direction you want?
@@simondev758 say I got a GUI application showing data from a health watch. Here, data has to be loaded into some structure, and shared between a chart plotter, a value display, and maybe a playback feature. In order to create maintainable code, proper use of design patterns is essential
If anyone enjoyed this video, I would highly recommend looking up Raymond Hettinger's talk on how new dictionaries are implemented in Python. It's a fantastic distillation of many topics such as learning from history, software project politics, and (of course) data algorithms.
Oooh very interesting, I'm going to check that out.
@@simondev758 Not sure if I can post links here without getting spam filtered, so the title is "Modern Dictionaries by Raymond Hettinger" from Dec16 2016.
I love thinking about data structures. I hope I don't get crucified for this, but one thing that I found myself adding is a sort-of Frankenstein's monster between arrays and linked lists, in the form of a linked list that stores an array in each node. An example of a use case: I work in game development and the framework that I use specializes in parallel processing. But having multiple threads write to the same output without taking proper precautions is a recipe for disaster.
An array-backed list could be used, but then if the list runs out of space, all threads would have to wait while one thread allocates a larger array and copies over the current contents. A linked list would have the same problem: creating new space has to be synchronized (as far as I'm aware at least), and new space would have to be created for each element, meaning that linked lists do not (easily) support parallel writing (again, as far as I'm aware).
By using 'blocks' of memory I was able to reduce the probability of memory having to be expanded. The remaining problem was implementing parallel writing. Given that the framework I am using does not allow me to use most C# features in a multithreaded context, such as the lock-keyword or mutexes, this was also a bit of a trick. I ended up implementing everything through Interlocked-Increment. Since the blocks would each need a variable that keeps track of how many items it currently holds, and since this would then also be the index of the next unused slot, I could use interlocked increment to essentially 'claim' a slot in the array.
The remaining problem, of course, is detecting when a block is full, and resolving how to allocate a new chunk, given that there may be multiple threads trying to do so at the same time. The solution I ended up going for is that only one of the threads will attempt to write to the slot that is just out of bounds, or in other words, is looking to write to index 0 of the next block's array. That thread will be tasked with allocating a new block while the others wait for the block to become available by essentially busy-waiting. This is not ideal, but then this situation of busy-waiting can only be reached once another thread is already in the process of creating a new block.
This does mean that operations like inserting and deleting cannot be implemented in parallel, but that's alright for my particular use case.
Reading and writing to a particular index does run into the same problem as a linked list, namely that it requires looping over the blocks. If the blocks are all a constant size though, it is possible to calculate the index of the block that contains the value that is being requested or overwritten: divide by the chunk size to get the chunk index, and do modulo chunk size to get the index within the chunk. If the chunks are reasonably large then hopefully only a handful of loop iterations are necessary to reach the desired chunk.
Currently my implementation maintains a head and a tail pointer, and every chunk only contains a pointer to the next chunk. If necessary I suppose I could double-link the chunks. For reading and writing to a given index, one could then traverse from the head or the tail, depending on which is faster. With a large enough chunk size, the overhead of these additional pointers shouldn't be _too_ bad.
I've yet to investigate if this approach makes good usage of CPU cache. At face value I hope that the repeated parallel accesses to successive indices of one chunk (which, given that the chunk itself is just an array, would be successive memory addresses) may cause the CPU to load (part of) a particular chunk into the cache, but I've yet to have a closer look.
You’re funny as fuck and that makes learning from you great. Cheers from Seattle
Thx
I followed the first three minutes but then he went back into his usual God mode 😃
Hah, where did I go off the rails?
@@simondev758 its not you,its me 😃.I admire your level of understanding and knowledge...even if most of it I cannot grasp...I hope to one day!
Informative as usual. I just recently started using structs on top of your standard arrays and linked lists of various dimensions, maybe I should look into hash tables next? I'm not really sure where I'd use them though...
Hash tables are CRAZY useful. After basic dynamic arrays, hash tables are a strong 2nd place in terms of usefulness. There's a good reason that higher level languages basically expose an "array or list" and a "dictionary" object.
Anytime you know in advance that you need to be able to look up things with a specific key, hash tables and their ilk are your friends.
The main data structure in PHP is based on 'Hash Tables' (HashMap). It can have some of the issues mentioned. However, it is surprisingly flexible and quite fast. It can be a bit of a 'memory hog'. That isn't such an issue these days.
Some languages seem to use hash tables AS arrays. They just use integer keys when it’s an array. Or perhaps even just strings representing integers.
The only data structure Lua has is associative arrays which it calls tables. Even an ordered collection (alternatively called both an array and a list as far as I can tell) is achieved by having the keys just count "up" from 1 (yes, 1)
If you think about it though, 1 indexing almost makes sense in this context since we are no longer talking about actual arrays and offsetting some memory address by a certain amount. Might as well start counting at one since its the first thing in the list.
Yeah I've used Lua before, the 1 based indexing drove me nuts.
Hash tables and arrays are generally what you should use. If something is performance critical, different data structures can be worth investigating.
A lot of performance optimization is premature.
Hash tables and arrays covers the overwhelming majority of what I use.
Yes, I can see it. La la la to you too.
No collisions is O(1). Java's HashMap implementation uses a linked list for each bucket, until the bucket gets big enough, at which point it switches to a Red-Black Tree, ensuring that a lookup never exceeds O(log n). Really nice for a builtin data structure.
Python's dict on the other hand uses Open Addressing with a fancy math equation optimized to come up with indices that aren't likely to have collisions when used with consecutive hashes. (See the source code for details. There's a comment explaining it.)
In java we use hashmap for storing data what would be used in php .Please tell me.
too good. like, sub
1:59 Early PHP used strlen() to hash function names, if you don't believe me, see php.internals (#70691), or the PHP 1.99 source code
Wow, that is awful. I love it.
❤❤❤❤
Hey, I always had one concern about hash tables:
If my ids are ints that can go really big, will it take a lot of memory, like allocating a very big array so that it can have an entity with an index corresponding to my hash ?
It's pretty normal for hash functions to apply a modulo to bring the range within the size of the table.
index = hashed_value % table_size
Interesting!
Could this work to sort collitions on a physics engine?
I've never made a physics engine, but a lot of people commented on the spatial hash grids video that they use that as part of their broadphase step
This tutorial makes Lurr happy..
Ndnd doesn't know I'm on the computer...
Also.. trying to delete "human horn" from search history.. any ideas?
Prepare to harvest the lower horn!
futurama!
Hey man, I want you to know, may make you feel happy, may make you feel sad, but I know most of these characters and where they're from.
Gotta add, I'm 18.
Also sleep deprived and coming down
Whoever is paying your salary ought to give you a raise.
5:47
you make me study more C and ++, goddamnt...
Hah, great to know! Although technically, the understanding of these data structures transcends language. Understanding how they work is separate from any particular language implementation.
thank you for sharing this
Could some kind of "virtual geometry" like Ninite in ue5, be written in JS?
Hier I found some source: Karis_Nanite_SIGGRAPH_Advances_2021_final.pdf
Oooh didn't know there was a paper on this, I'll check it out, thanks!
For chaining, why not use another hash table with a different hash function?
You can do whatever you want. There's some common ways to do it that are well known, but there's nothing preventing you from coming up with something, as long as you profile it and understand the advantages/disadvantages compared to other methods.
Hi .. good explication ... but in 12:44 "Hermes" word .. are 6 letters ... not 5 ... is a typeout .??
Apparently I can't count
Zero dislikes
Nice
Yes, I could see that the video was over.
hey can you please revisit the 3D rpg game i really am interested in that!! many people seem to be. man it was awesome
Ya I'm thinking about doing another version sometime in the next couple projects.
Yes! I have seen all the sneaky comments: "pedantic =/= skiled", "Lisa needs braces"... LOL!
02:51 how do you know about the fancy pants data structures I've been working on
I'll be there when you finally crack the pants theorem
Problem with collusion resolution by using alternate addressing is that lookups slow down even if there are no collisions as just because you didn't find anything at the first location possible doesn't mean it's not in the table, it could still be at an alternate address. So you *always* must check *all* alternate addresses first before you can conclude the key is not there. This is a horrible idea IMHO considering that the main goal is to keep the number of collisions small to none in the first place. It's okay if adding or removing items is a bit slowish at times but slow lookups defeat the entire purpose of using hashtables in the first place IMO.
A way better approach is to solve collisions by using linked lists and keeping collisions very rare (even if three items end up in on spot, traversing three linked lists nodes is not horribly slow and if you have large linked lists, you have way too many collisions to begin with, rather use a better hash and a bigger table) or use arrays and keep them sorted, as then you can do a binary search in the array and your O(1) will only degrade to O(log2 n) in the very worst case possible, yet O(log2 n) is still very good performance and a sorted array can easily beat a hashtable in performance when small., since people tend do forget that hashing is not for free and can be quite expensive for a good hash value. If I can only check on 8 array items in the time required to calculate a hash, I can check sorted array with 256 items in that time.
What’s ur favorite show?
I generally watch pretty mindless stuff, Family Guy, Rick & Morty, The Boys come to mind.
Is Hermes = 5 letters also part of the super stupid concept? Haha jokes aside, I love how you explain these concepts :)
Thanks!
It is my appalling lack of attention to detail
HA HA!
EAT SHI-
jokes aside this video was super helpful
Bobs burgers and IT instruction
This is what you become after 10 years of programming
Bob? From Bobs burger? 😅
oh no somebody beat me to the 420th like
im gonna get revenge by liking
haha 421 likes go brr
New Matrix movie is not like what you expect...
HERMES is 6 letters tho
Hah yeah apparently I can't count properly
bob's burger
WHERE IS SHEEEEE?!?
Why do you sound kinda like Bob from Bob's Burgers
Data ❌ Crap ✅
👎
Informative video but can you have some respect to your God (Allah), your Creator.
In the video, you named yourself as a "God", You can't just call yourself or anything else but him a God even if you are joking.
A God doesn't die, get sick, have a spouse, have kids nor need any body rather we are the ones who are in need of Him.
Be careful next time you joke.
May Allah the All-Merciful guide you.
God is an idea, not a person. People deserve respect. Ideas don't.
@@spartanatreyu
I agree with you that people deserve respect, but
How did the people come to existence?
Why are they on this earth?
What happens to them after they die?
I highly recommend that you sincerely think about the answers to these questions.
and after you find the answers to it I will be glad to hear from you again.
@@hazema.6150 People came to existence through random chance. Abiogenesis then evolution gave rise to all forms of life. There is no purpose to life, thinking otherwise is naivety at best and narcissism at worst. We are an otherwise insignificant speck in a chaotic universe, on its excursion from enthalpy to entropy.
@@spartanatreyu
Alright, I appreciate that you thought about it and concluded that there is no God based on presented premises not just from utter negligence nor blind faith.
I assume that you are an open-minded person and seek the truth based on evidences
So, I would highly recommend to you to watch the "Journey of certainty" playlist from Dr. Eyad Qunaibi channel on UA-cam, where he critiques and dissects the atheistic arguments in a scientific and scholarly manner and you be the judge yourself afterwards, does atheism with all its arguments really stand or not.
@@hazema.6150 48 videos, a decent sized playlist. Let's see how long it takes before I find something objectionable...
I'm typing this as I watch.
Okay, it's not in English, but I'm assuming the translations are correct.
It didn't take long...
Video 1, 1:57 in. "We might still have questions, but out faith can withstand them".
It seems that he is literally trying to teach people to ignore doubts. That is completely opposite to what you called a "scientific and scholarly manner" as you put it.
As Tim Minchin so aptly stated: “Science adjusts its views based on what's observed. Faith is the denial of observation so that belief can be preserved.”
That appears to be exactly what is happening here, the literal denial of reality, a cop-out to avoid cognative dissonance, lest the viewer take up critical thinking.
This is reason enough to discard anything else he's saying.
Let me see what else I come across in this video alone.
"If we do not, we will bring these issues under the umbrella of submisison", I'm assuming this might be a mistranslation (or at the very least some meaning might be getting lost), but if it's not then he appears to be advocating to disguard reason all together.
Anything that is claimed without reason, can be disguarded without reason.
I don't think I need to watch the rest of the video now, since he's literally being unreasonable.
"A submission that stems from reason-based faith", yeah that's an oxymoron. I only made it 2:14 in. There's isn't any point continuing, sorry.
*Edit:* Spelling mistakes fixed
I really don't get the usage of “crap”, “wtf” and so on? Is that the best way you could find to make yourself sound cool?
That's just sad
Good for you buddu