Hash Tables, Associative Arrays, and Dictionaries (Data Structures and Optimization)

An introduction to the hash table data structures, how that relates to associative arrays and dictionaries, and how to use them.

Support me on:

Follow me on:

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:

[VforVanish]

I found the nihilistic voice tone a perfect match to learn IT stuff.

[TetrisMaster]

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.

[mukaschultze]

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

[Rssks]

These were 13 relaxing minutes of listening to you talk about hash tables (Y), enjoyed, thanks!

[javasquid]

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.

[Metradime]

This is very nit-pikcy but "Hermes" is most definitely 6 letters

Great video haha

[jean-pierrevermeulen]

The timing of this video couldn't be more perfect, Just had a class lesson about hash tables today!

[guard]

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.

[..]

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!

[lucasfarias]

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!

[felleg]

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.

[matthewhawkins]

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.

[oah]

I am addicted to this channel. your way of explaining stuff really kills it.

[chopov]

thank you for using those names it made my day

[anon_y_mousse]

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.

[pranjalagnihotri]

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.

[frddyfrsh]

Even as an experienced developer, i find your videos are very entertaining and informative. 😘

[tarikb.]

Great explanations with slang sauce. They make hard chunks of information tender and more digest. Bravo

[tombouie]

Thks. I envy your computer expertise & your fluency in teenager speak.

[pvic]

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)