Hash table separate chaining source code

Key Takeaways

all right it's time to have a look at some separate chaining source code for the hash table so here I am on my github repository will empty data fast data structures and you can find the source code here under the hash table folder I have multiple implementations of the hash table today we're going to be looking at the hash table with separate chaining and in the later videos probably one of these three I haven't forgot which one yet so let's dive into the code I have it here on my computer so let's get going alright so first things first I have two classes one of them called entry the other one just separate chaining hash table so let's have a look at the entry class first and these entries represent individual items or key value pairs you would want to be inserting into the hash table so in Java we have generics so a generic key which has to be hashable and some value so when I create an entry I give it the key value pairs and I also compute the hash code so there's a built in method in Java to compute the hash code for a particular object and you can override it to specified hash code for your particular object which is really convenient so compute the hash code and cache it you absolutely want to cache it so you don't have to recompute this thing multiple times it should be cheap to compute but for something I guess string of hash code can take linear time to compute which is not good so here I have an equals method which doesn't override the object equals method because I don't want to have to do any casting first it checks if the hashes are not equal if the hash is not equal we know from the first video that they are not equal so we can return false otherwise I compare the keys to each other and that's about it for the entry class very very simple very basic now let's get into the meat of the thing so the hash table itself okay so my default hash table capacity is gonna be three so it holds three three items and the load factor by default if the user doesn't specify one's or be 0.75 so that's the maximum capacity I'm willing to tolerate then I have a few important instance variables when you go over so the maximum load factor so once the load factor goes above this value then I resize with table sort of the capacity so the actual maximum number of items like could or how big the table sizes rather so the threshold so this is computed to be a capacity times the max load factor so it tells us hey you're above the threshold to resize time to resize size how many items are currently in the table and this is the table itself so it's in a right of linked list which themselves have entries pretty simple so there's a few constructors so you can construct a hash table just using the default settings with the initial capacity or the capacity and a max load factor so this is decimated constructor let's have a look so just say but the max load factor is compute default capacity and make sure you take the max of say default capacity and capacity just so that I know you don't want to capacity be too low there may be weird things happening if the capacity is set to 1 or something that they calculate threshold and then finally initialize the table really simple all right let's have a look at all these methods right here so size you retain some of realm inside hash table empty is a hash table empty okay so this is the first really interesting method so normalize index and it's used when you want to convert a hash value into index answers in the comments here essentially the strip's the negative sign and place the hash value in a domain 0 to capacity because the hash values are integers they could be anywhere in the domain of an integer which is about minus 32 to the 31 sorry to positive to the 31 or not so what this does is a mask it strips off the negative sign from the hash value and then mod it by the capacity so bring it into this domain so we can actually use it as a lookup index next type is clear so it just won't clear everything on the table let's straight forward contains key and hash here the same thing so what we're going to do is compute give it a key so we want to find out does this key exists within a hash table all right so what we're going to do is compute the keys hash normalize it and then now give us the bucket index so which bucket should this key appear should it be in a hash table now I'm just going to seek to see if I'm going to seek to find the entry if the entry is not equal to null and it exists so it's equal to null it doesn't exist simple okay foot added insert are all common names for just putting something into the hash table or updating a value inside the hash table too so we don't want to allow null Keys so that's something we absolutely don't want so just throw an exception there otherwise we're going to create a new entry find the bucket it belongs to and then insert it using this method we'll get to okay get so given a key I want to find the value associated with that key again don't allow null keys and this going to be pretty routine all the time always want to find which bucket this particular key belongs to give the bucket index okay find the entry assuming it's not null then this is the entry you want and return its value if it is no well the key doesn't exist so return null okay suppose we want to remove a key now from the hash table so he's not null find the bucket index and we recall yes private remove entry method which is just down here so given the bucket index so which which bucket does this key belong to what we're going to do is we're going to seek for the entry inside the linked list structure and if the entry is not null then we're going to extract the actual linked list and remove it so this is a built-in a data types in Java so so it's removed from that length of state structure decrement the size and return the entry value that's all we have to do otherwise it's not there so return null so insert a bucket insert entry so given a particular bucket we want to place this entry inside of it okay so first we're since we have the bucket index we can go in our table and automatically get the length of structure checkout bucket so bucket is null well we have to create a new linked list so we're essentially lazily allocating these linked list data structures which is good because we don't want to use more memory than we need to so next up I find the entry that already exists so this is in case we want to do an update for instance so if the existence entry is no this means that we need to add a new entry to the end of the linked list so add it to the end of the linked list increment the size and check if we're about the threshold and so resize the table and yeah use an L to indicate that there was no previous entry otherwise need to update that entry so then just update the value in the existing entry and return value all right so secant resistant method we've been using pretty much everywhere and it finds the returns a particular entry a given bucket index it fits this otherwise just return null it probably know it's going on by now so extract the length list at the particular bucket index otherwise return null it doesn't exist yet although I seek through each of the entries in the linked list and compare the keys to the key we're after and if there's a match return that entry otherwise return melt okay here's the last really complicated method called a resize table so this resizes of the initial table doubling the capacity of the table first we're double the capacity we recompute the new threshold because now we have a higher threshold because we've increased capacity now create a new table with this new capacity so this new table is bigger than the current table then go through the current table look for linked list based structures which would not know if you find one will loop through all its entries calculate the bucket index find the bucket and essentially insert it into this new table and after that completely removed the old data that was in the old table at the end set the table to be equal to the new table okay and then these last two methods they just returned of the keys and other values within the hash table fairly simple and then these last two methods are it's razors and to string which we don't need to go over so that's essentially separate chaining a nutshell fairly simple to implement with the linked list much more difficult to implement with say a balanced binary tree or something like that so guys thanks for watching I hope you learned something if you did hit the subscribe button hit the like button and leave me a comment awesome see you later