Design Hashmap - Leetcode 706 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem design hashmap basically we want to implement the main operations of a hashmap which includes putting or inserting a value using some key we can map it to some value also we should be able to retrieve elements that are already stored so given a key we should be able to retrieve that element and lastly we should be able to remove elements based on some key value now of course we can't just use a built-in hash map so we have to implement our own there's a restriction that we're going to be using which is that on this hash map we will have at most a thousand operations that are done that's just based off like the test cases so we probably won't need to store more than a thousand elements but other than that we'll still be implementing the main operations from scratch so what is a hash map well generally we want to be able to map any any arbitrary key in this case the key value is just going to be an integer so that simplifies things for us even more but usually we want to map a key to some value and we want to do it as quickly as we can on average most hash Maps will implement this in constant time and we also want to be able to retrieve elements doing the same thing the easiest way to implement hashmaps and most of the time this is how they're implemented with an array and we know arrays just generally have an index and a value but we will be using the index instead as the key value now normally what you want to do with that key value is map it to some index within our array in our array we're going to have about a thousand elements so the valid indices are going to be starting at zero and probably going up until nine nine nine so how can we take a key value in this case the key value is an integer and then map it to an integer between 0 and 9 99 well the easiest way is to take that key value let's say it's a hundred and mod it by a thousand so modding by a thousand will always give us a value between zero and nine nine nine because with a hundred modded by a thousand we'll just get a hundred so any value less than a thousand will just get that value but what happens when we start getting up until that value well a thousand modded by a thousand is just going to be zero a Thousand and One modded by a thousand is going to be one and so on and so on so every value is guaranteed to be between 0 and 999 so we'll have a way to map the key somewhere here now another issue that can happen with hashmaps is this concept of collisions so what happens if multiple values are mapped to the same index like we talked about we had a hundred modding it by a thousand will give us a hundred what about 11 100 modded by a thousand that will also give us 100 so multiple values will be stored at the same key location let's say the key is a hundred so multiple values could be here how are we going to handle that well there's multiple ways one is open addressing which we won't talk about right now because it's a bit more complicated than the one I'm going to show you which is called chaining chaining is pretty straightforward because just as the name implies if we have multiple values here let's just say the first value we were inserting was a one and now we want another value with a different key is going to be a value too we would just take those values and add them into a chain so we can store multiple values with a single key I guess it's misleading to say we have multiple values stored with the same key it's just that those multiple keys will map to the same index they will be different keys so I guess a better way to illustrate this would be that let's say these are the two two insertions that we did so a key value of 100 will be mapped to one key value with 1100 will be mapped to two we know both of these Keys when we mod them by a thousand we are going to get the same index so over here they'll both be mapped to index 100. now when we actually store the value we will store them in that linked list that we were showing earlier so we'll store the key value 100 and we'll store the value itself which is one so both of those will be stored in that linked list node that we were talking about and if we inserted another value here and we saw that well there's already a node stored here doesn't matter we just insert a new node and connect them via like a pointer just like you would with linked lists the value in this case or the key is going to be 1100 in this case and the value is going to be 2. so we store the keys in the nodes because we don't want to lose any information sure the 100 here matches the 100 over here but the index here doesn't necessarily mean it's going to be the same as the key like in this case we have an 1100 stored over here so we don't want to lose like the original key that we were using that's why we add that to the node we don't just rely on the index so we just showed the put operation so far but I bet you can tell how the get and remove operations are going to go so with get it's also going to be similar we're going to take whatever key that we're given so maybe it's 1100 we're going to mod it by a thousand so we're going to get the index which is a hundred then we're gonna go through that linked list until we find the key that we were looking for if it exists at all so we're looking for Eleven Hundred so we're going to keep going through this linked list until we find a node that has the key of 1100 which is this node over here so then we would return its value which is two now if we don't find a linked list node with the key that we're looking for then I believe we just return a fault value of negative one and lastly how would we remove a node well just some pointer manipulation which would mean we would go up until we reached the node so maybe this is the node that we want to remove so we'd go up until we reach the previous node and then we'd take its pointer and then set it to the next node so maybe we have three nodes in this case in that case we'd remove this pointer and then set it to the next node or maybe there's nothing over here in which case we'd set the next pointer equal to null and this node would basically be removed we could delete the memory that stores this node or we could not usually encoding interviews you don't really need to but that's how this would work now one last thing I want to mention notice how there's kind of an edge case here what if we were removing the first node well there's no previous pointer in front of that so it would be a little awkward we need additional conditions to be able to handle this case so an easy work around is to initialize every linked list here with like a dummy node so we'd have a dummy node that's starting here even though there's no nodes here we'd still have a dummy node here and we'd have a dummy node here that's pointing to this first real node that we have so if we wanted to remove this we'd just take the dummy node and set its next pointer equal to the next node which is over here so that's mainly it now technically the way we've written this hash map it's not going to be constant time in every case we could have a bunch of values that are inserted at the same index it is possible but on average chaining is pretty efficient and we know we're not going to have more than a thousand elements in our data structure so assuming that they're evenly distributed these operations should be pretty efficient so now let's code it up so the first thing I have here is my list node we know we're going to have a key value a real value and a next pointer to now get started on our hash map we know we're going to have an array I'm going to call it our map but it's technically an array and I'm going to just initialize it to be size of a thousand so for I in range a thousand we're going to initialize every index with a dummy node as I kind of mentioned earlier so we're going to create a list node for a thousand times and then that's what the array is going to be initialized with and that is pretty much it now for the put operation there's actually two cases we have to handle one is if we're inserting this key for the first time in that case we would create a new list node but if we're not then that means this key already exists and all we want to do is update the value of that key first what we want to do though is take the key and map it to the index so we decided that we were just going to take the key and mod it by a thousand aka the length of our hash map so this will give us the index and we're going to be needing this a few times actually so I think it's worth putting it in its own helper function so let's define one where we can hash some key value then we will return the hash of that key and we'll be needing it pretty much in all of these because this will tell us what index we should go to and once we have this index we want to start at the head of that linked list because we know it's going to map to some linked list so we're going to say in this map at this Index this is going to be the start of the linked list so I'm going to call it Cur we're going to take our current pointer and while it's non-null we are going to continue to Traverse this linked list so we're going to set the current pointer equal to current dot next but there's two cases remember one is that we find a node so if current dot key is equal to the key that we were given that means this node already exists this key already exists so we just want to update its value so current.val would be set to the new value that we were passed in and then we want to return immediately the second case is where we will reach the end of the linked list and at that point we want to insert a new linked list node at the end now the way our current Loop is coded up by the time we reach the end of the loop our current pointer will be equal to null but that's not where we want to end we want current to be pointing at the last node so instead of saying while current we say while current dot next remember that our current will start at the first node in the linked list which is going to be a dummy node so when we actually check these values we shouldn't say current dot key we should say current dot next dot key is equal to the key that we were passing then we would update current dot next dot value so now if we never find that key in our linked list and we reach the end of this then we know we can now insert a new list node so I'd create a new list node with the key that we were given and the value that we were given just like our Constructor is defined up above and we take this node and we'd say current dot next is null now because current.next is null that's why the loop terminated so we want to set current.next equal to this new list node and then we don't really need to return anything but now we can get started on our get method which will be pretty similar to this we just want to get the head of the linked list that this key maps to so we'll just go ahead and copy and paste this and what we'll be doing this time is while our current pointer is not null we're going to check if current dot key is equal to the key that we were passed in then we return current dot value otherwise we just take the pointer and set it to the next pointer now if we ever reach the end that means we didn't find the key that we were looking for in which case we can just return negative one that's the default value that we want to return and one minor change here we probably can go ahead and take this and set it equal to dot next because we don't need to start at the dummy node in this case we don't need to check the dummy nodes value so it makes sense to just start at the second node of that linked list lastly we have our remove method we're going to do the same thing that we did up here but we probably do need to start at the dummy node in this case because we're going to need to do some pointer manipulation so now we want to check if current is non-null and current dot next is non-null then we want to check if current dot next the next node's value or rather its key is equal to the key that we were given if it is that means this is the node that we're going to remove and then after we remove we can probably just go ahead and return how do we remove it and more importantly the reason I'm using current.next in this case is because we want our current pointer to stop at the node right before we delete a node so we want to stop at the node prior to the one that we're deleting so then we can say current dot next is going to be equal to current dot next dot next so we're just setting its next pointer and skipping a node the node that we're skipping is the one that we want to delete and this is basically us performing that deletion we don't really need to delete the memory it doesn't really make a difference most of the time it doesn't make a difference on leak code and it usually doesn't make a difference in coding interviews so I won't do that but lastly here we need to set our current pointer equal to current dot next so either will reach the end of the loop in which case we won't remove anything or we will remove the node and then immediately return so this is pretty much the entire code it's not too bad luckily we didn't need to handle the resize method usually hash maps are growing and as they grow we need to double the capacity every time they exceed the current capacity or exceed some threshold but in this case we don't really need to do that so I'll go ahead and run the code to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neatcode.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon