Explained Code: Hashing with chaining in C++

okay so let's build a hash data structure that uses chaining as a collegiate resolution mechanism i have created a project already it's an empty project at this point i have main.cpp which is an empty name function and hash table dot hpp which is where i'm going to be creating my hashtable class now to do chaining i would have to use a list and i've got a number of choices to choose from for for a last implementation i could use uh the standard template library or stl list or vector or i could provide my own implementation of a list now for this particular exercise i'm going to use these stls list the standard template library list implementation and to do that i need to include list now let's uh create the class class hash table right now the class need to basically maintain a table of less or array of less right now to create a single list a single list element this is the syntax std list and then the type of each element in this list in this case let's just say integer okay and then you provide the name so this is actually going to create a single list now we actually need an array of less so i could use the array syntax to let's say create 10 lists or an array of 10 lists now the problem with this is that this is a fixed size array so if i later on needed to resize the hash table for whatever reason i wouldn't be able to do that okay so in order to overcome this problem i'm going to allocate the uh array dynamically in the heap in the constructor so here i'm going to simply have a pointer and then in the constructor i'm going to allocate the memory dynamically and since the size can vary let's just go ahead and maintain the size within the as a private data member as well now let's go ahead and create a default constructor so hash table default constructor doesn't take any arguments so let's assume that the initial size the default initial size is just 10 elements so this arrow size equal 10 elements and then i'd need to allocate the memory dynamically uh for the table so map equal new so the new operator is used to allocate memory dynamically in the heap right so new and then uh uh every element is just an std list of integers and then i need a size of these okay now to create a parameterized constructor where we get the size as a parameter the initial size is a parameter um i basically use the same thing so except that i have the size uh passed to me as a parameter so this arrow size equal size and the rest is just the same okay so now since we have a constructor let's just go ahead and create a destructor because we certainly need to uh free this memory once we're done right so hash table uh obviously the structure doesn't take any arguments and then this is basically an array so we delete it using the array syntax and then that's map okay so let with this we're supposed to be able to uh create an object of hash table so we just do hash well we need to include first hash table.hpp and now i should be able to create an object of type hash table it hash table for example okay i should be able to build successfully so yeah it built successfully now let's go ahead and add the insertion functionality to be able to insert an item within the list right so the function that inserts isn't supposed to return anything so return data type is void call it insert and this is supposed to take the data item that needs to be inserted as an argument now what's the process the process is that i would need first to hash the data item to locate the appropriate bucket and then i would need to insert it in that appropriate bucket okay so i would need to compute the hash first and since i will need the hash in many places and and the hash is uh is just helping other functions i'm going to create it as a private helper function so this is supposed to return integer call it hash and it takes a data integer data and all it does is just returns the data mod size okay so again for the insertion i'm going to uh find the bucket first or integer bucket equal hash of data so this is going to find uh the appropriate bucket and then the list at that appropriate bucket is basically map of bucket right in that list i would like to insert my element my data element data so uh map dot push front data so that's it that's how i insert data items within this hash table now in to do search let's support the search operation so let's say the search returns boolean either truefound or false not found search and then it accepts the data item that we would like to search for right so the first thing that we need to do is we need to find the bucket that this data item is supposed to go into so we calculate the hash so hash of data and then um the data item or the the list that this data item uh is supposed to be available at if it is if it exists is map of bucket right now i can uh uh you know uh search within this list i do my linear search uh myself or i could use uh the find function which is provided to us by c plus plus standard libraries uh and i need to include algorithms for that so i'll go with them right so uh the function find takes the uh an iterator which is you know very something that's very similar to pointers basically uh point to the first element in the list and then last element in the list and then the data item that we would like to search for okay so the first item in the list in my list so map of bucket so this is my list the list that i would like to search within the first item is referenced by calling the begin function so find starting from begin to end to the last item bucket dot end and the item that i'm looking for is data okay now um the return value from this function is an iterator to the item if it exists or uh you know the less dot end if it doesn't exist so i will use auto to allow c plus plus to create to basically infer the data type and i'll call the return value iterator right so now if the value exists iterator is going to be pointing to that value if the value doesn't exist then iterator is basically going to be map of bucket dot end so let's do that so f let's do this the check f iterator equals a map of bucket dot n that means the item was not found so we will return false otherwise that means the item exists so we are going to return return true so that's that's the search now let's just add a uh some some items uh in our hash table and search for these items let's do hash table dot insert that's insert let's say 10 hash table dot insert let's say 33 hash table dot insert let's say of 34 let's do insert or hash table dot insert uh 53 as well and now let's search for some of these items okay so let's search for an item that exists let's search for 33 for example and and the if it exists the function hash table dot search for 33 should actually return a true true and c plus plus is just non-zero value so i will do stdc out just to find out the value that returns from this function obviously i would need to include i o stream it's already included and now let's search for an item that doesn't exist so this one is supposed to return a non-zero value this one is supposed to return a zero value let's search for 55 this is going to return a0 right so let's build that and see there you go the first search return returns a non-zero value the second search returns a zero value now i think it might be appropriate to kind of provide a print function which basically visualizes the entire hash table so let's just do that let's just go ahead and create a function call it print so it returns nothing print takes nothing so what this is going to do is going to iterate over every list and then print that list okay so to iterate over the list so we do a for loop for i equals 0. i is less than size because the size of the list uh the size of the array is size i plus plus and then um at the beginning of every list let's just print the index so std c out uh i and let's just have a little column here okay obviously we need to include iostream here so let's just include that and now uh for every so basically map of i is a list now i need to iterate over the list and print its items the way i do that i use another for loop four so i need to uh use an iterator that starts at the beginning of the list stops at the end of the list and we keep incrementing this so again i will use allow c plus plus to uh infer the type right and i'll do uh iterator equal map of i so this is the list that i'm currently examining dot begin so that's an iterator to the first element in that list as long as this iterator does not equal a map of i dot end then simply increment that iterator and then what we're going to be doing inside is basically printing uh the value of that iterator so star iterator so this is basically going to print the value that is pointed to by this iterator okay so and let's have a little space afterward and then once we print the entire list let's print a a new line so each list would would go in its own line okay so um let's go ahead and print the list so hd dot print so this is going to print the entire list let's see how it looks like so we got a failure what's the problem uh is a missing semicolon somewhere oh this is this should be std right okay so let's try that yeah so now it succeeds so there you go obviously if you try to analyze this 10 uh so 10 mod 10 that is zero so 10 goes to less number zero bucket number zero uh 53 and 33 are all you know mod 10 that's basically three so they go to uh less number three and so on okay all right so next let's go ahead and build a remove function which is going to remove an item from the list so um it returns nothing called remove and it takes a data item so um you know just just like we did with uh insert and search we need to first find out the bucket so bucket dot bucket equals uh hash of uh data and now we need you know just pretty much like uh the search we need to find the uh item right so we need to find the item and obviously we can use the find function and if the item doesn't exist then there is nothing to do so this is basically finding the item if the item doesn't exist then it's going to return iterator is going to be map of bucket dot end so in this case there's nothing that we need to do just just return otherwise uh we need to remove it right so map dot so now iterator is pointing to the uh element that we would like to remove so we can just say map of bucket dot uh erase so these are again functions provided to us by the uh list implementation and then we all just need to do is just uh pass the iterator to the item that we would like to delete so now let's go ahead and try to delete some items and print afterwards so h dot remove and then i will let's remove 33 okay and let's print afterwards dot print and let's just build this again so there you go now 33 is removed so this is the first table before deleting and this is the table after deleting so 33 is gone now there is one additional functionality that i'd like to do to demonstrate which is basically resizing and i will come back to this in a different video

Channel: CSExplained

Views: 1,471

Rating: 5 out of 5

Keywords: hashing, chaining, c++, hash table, hash function

Id: 6deoJqbsv3E

Length: 17min 42sec (1062 seconds)

Published: Sun Sep 06 2020