Internal Structure of a Hash Table

System Design for SDE-2 and above: arpitbhayani.me/masterclass
System Design for Beginners: arpitbhayani.me/sys-design
Redis Internals: arpitbhayani.me/redis
Build Your Own Redis / DNS / BitTorrent / SQLite - with CodeCrafters.
Sign up and get 40% off - app.codecrafters.io/join?via=...
In the video, I discussed hash tables, a common data structure used in various programming languages. Hash tables store key-value pairs and support constant time operations like insertion, update, and deletion. The internal structure involves mapping application keys to hash keys through hashing functions. By mapping hash keys to a smaller range, hash tables become efficient and avoid excessive memory usage. Dynamic resizing of the array allows for accommodating varying numbers of keys. Understanding these concepts is vital for efficient hash table implementation in software development.
Recommended videos and playlists
If you liked this video, you will find the following videos and playlists helpful
System Design: • PostgreSQL connection ...
Designing Microservices: • Advantages of adopting...
Database Engineering: • How nested loop, hash,...
Concurrency In-depth: • How to write efficient...
Research paper dissections: • The Google File System...
Outage Dissections: • Dissecting GitHub Outa...
Hash Table Internals: • Internal Structure of ...
Bittorrent Internals: • Introduction to BitTor...
Things you will find amusing
Knowledge Base: arpitbhayani.me/knowledge-base
Bookshelf: arpitbhayani.me/bookshelf
Papershelf: arpitbhayani.me/papershelf
Other socials
I keep writing and sharing my practical experience and learnings every day, so if you resonate then follow along. I keep it no fluff.
LinkedIn: / arpitbhayani
Twitter: / arpit_bhayani
Weekly Newsletter: arpit.substack.com
Thank you for watching and supporting! it means a ton.
I am on a mission to bring out the best engineering stories from around the world and make you all fall in
love with engineering. If you resonate with this then follow along, I always keep it no-fluff.

[@shaileshgande3875]

Amazing playlist, can't find anything like this on the internet.

[@soumavabanerjee5925]

Now this is interesting stuff! Waiting for the rest of the videos !

[@shishirchaurasiya7374]

I am just in love with your concept explanation style

[@harshitanand7349]

Great explanation Arpit. It gave intuition why people thought of creating hash table data structure. Arrays are fast but only when we know the index. Hash table uses keys which are provided by the user that can be of any supported data type and converts it into an integer which is used as an index to store values in array.

[@AsliEngineering]

This is the right way to think ... building the right intuition and knowing the real "how" and the "why" is the best way to understand anything. Now you can apply this concept or draw parallels when you find something similar.

[@suchanachakrabarti6783]

You explain so amazing, kudos to you brother for bringing us such contents in super depth!!

[@barebears289]

Of course I'll watch a video from arpit bhayani

[@GodofStories]

Yo great video. Keep growing, subbed!

[@roshanmhatre8810]

Your content is so true to the channel name ❤️ I love this kind of indepth explanation.

[@AsliEngineering]

Thanks a ton Roshan 😁

[@mohitkumartoshniwal]

I think in Javascript, we can use Map instead of Object for the purpose of hash tables.

[@saptathirtachoudhury4158]

Suppose we have four keys like apple, banana, mango, and jackfruit then how can we allocate the number of memory blocks ?

[@d4devotion]

Apart from doubling the key space, some language may also support using the same location to store the value thus lead to the concept of key collision and techniques to tackle them, so that even large number of keys can be stored (but yes timecomplexity will be little bit high as compared to first way, but that is acceptable I guess )

[@AsliEngineering]

Yes. And we would touch upon handling collisions in coming videos.

[@d4devotion]

@@AsliEngineering great, BTW this is going to be great series on hash tables, as we have got an expert.

[@aishwaryadwani908]

I found Gold !

[@__VishalSharma]

In cpp why map have different insertion complexity than unordered map (O(1))

[@abhijithk7290]

If we are continuously putting values to a hash table and in between if a resize happens, will it effect the performance?

[@AsliEngineering]

Yes.

[@utkershgahoi7101]

just curious about one thing after the hashing of the key how map will decide that we will store this value in this particular index? and what about the collision?

[@AsliEngineering]

I have explained it in future videos. Have gone in-depth for all possible approaches and trade-offs.

[@utkershgahoi7101]

@@AsliEngineering okay,thanks.

[@abhilashmallikarjuna4277]

I got that we are converting the Application key -> INT32 -> smaller range. But why not convert the app key to the smaller range itself? Is it because of Int-int mapping will be easier?

[@AsliEngineering]

Because then your custom hash function would need to change. Check __hash__ of python or similar function in Java that lets you put native objects in a HashMap.

[@abhilashmallikarjuna4277]

@@AsliEngineering Got it..Thanks

[@rjarora8162]

I am confused. Don't we append the values at a particular index? (CHaining)?

[@AsliEngineering]

In case of collision yes. We have not yet touched upon handling collision yet.

[@rjarora8162]

@@AsliEngineering ah okay! I thought that you said we just increase the array size when collision happens

[@robinhoodmacha9085]

Tooo bad waynof teaching something, u shall write and explain, the hole video u hv been just floaating ur hands and explaining, it is same as speaking the concept loud without writing code, maybe u hv know the concept, but. when someone is trying to understand something u need to explain as ur explaining to a 12 yr old child. Writing and reading and fleekering ur words no sense. You are just wasting the time of the person who is trusting u to understand. PLease take it as a advice and request.

[@robinhoodmacha9085]

For more try to see feynman way of learning because learning is teaching , just replace the keys values with someone else from ur self. Hope u undertand.

[@robinhoodmacha9085]

More u need to walk me by the pen, or travel me to the journey of understanding, what ur doing is telling the map go travel, that doesn't get anything, anyone can can write and talk. Take me like a tour guide. if u cant stop teaching, u only waste and break the trust of the person who trusts u n comes.

[@surajpandey7533]

@@robinhoodmacha9085 He is not reading it, it's more than that. The way he teaches to clear the concept and lay the foundation. Videos available in this channel are not beginner-level.