Know The Basics About Hash Tables To Excel During Your Interviews
Hash tables represent another data structure of the ones you should really know about. You should absolutely love them since they are very useful and used everywhere. It’s probably the most common interview question where you use a hash table to optimize something.
By using hash tables we can optimize a nested loop. There will undoubtedly be an interview related to using hash tables.
A few solid things to know is that hash tables have really fast lookups. But a good collision is needed. Usually we don’t need to worry about this because our language and computer underneath the hood take care of that for us.
The downside with hash tables is that it is unordered. It’s hard to really go through everything in order.
The other thing is it has slow key iteration. Also, to grab all the keys from a hash table, it’s necessary to go through an entire memory space.
If we look at a “Big O Cheatsheet”, we can see that hash tables has a search, insertion, deletion of O(1) but in worst case due to collision there are some O(n) operations that could happen. So with collisions, it’s also important to realize that we might want to use something like linked lists.
Hash tables, during interviews, are usually useful for improving time complexity, especially of nested loops. In this case, however, the tradeoff is we can have fast access but more memory.
There will definitely be times when you want to use a hash table over an array.
Also, remember we want to avoid nested loops if we can because they are O(n2) and two separate loops are better than 2 nested loops.
Remember, has tables are usually the answer to improve time complexity. They are some of the best ways to optimize your code. Looking at time vs space tradeoff, when using hash tables, sometimes storing extra state in memory can help the runtime. Finally with space time tradeoffs, hash tables usually solve this a lot of the time. You use more space, but you can get a time optimization in the process.
As always, I highly recommend the Zero to Mastery Academy to improve your own personal skills as a programmer as this is where all this information was drawn from and Andrei Neagoie, the founder and lead instructor, has been a true mentor to me.