A better hash table (in C)

today I thought we'd make a better hash table or at least a more General one [Music] welcome back everybody I've talked about hash tables in the past it's been I think the last time I did a hash table video was 2020 and that video is definitely still relevant it covers the basics of a hash table what hash tables are how they work the the basic idea why we use them when we use them but the hash table that I made in that video wasn't very general purpose it was just very specific to a particular type of data and so I thought we would take some time today to make things a little more General try to expand on that idea and look at how you can make data structures that you can package up into a library that then you can reuse in a lot of different projects as is the case with most of my videos this video will have source code and source code is available through patreon also you can get access to my monthly office hours so huge thanks to all of you who support the channel but of course the video will contain all the code so if you don't mind typing it's here for free but thanks for all of you that help make this channel possible and now without further Ado let's jump into the code okay so today I'm basically going to I wanted to start with the hash table example that I used back in 2020 this is the example using external chaining like I mentioned that one was very focused like we had a hash table that would store these person structs so a name and an age and we could have put other stuff in them but I thought today we would look at making this a little bit more General so that we have a little more flexibility basically try to create a software artifact a data structure that you could then just drop into any project and just use it without having to change the hash table code so this is the starting point uh if this is all brand new to you do check out the previous video and it'll help make everything make more sense but so I've created a couple of files that we're going to use here so hashtable.h will fill this out in hashtable.c so they're going in this better hash folder here which is hopefully going to be a better hash table I also have a make file in here this is how we're gonna build things so you've seen my make videos hopefully before hopefully this isn't anything too crazy check out those videos if it is but really what I'm gonna do is I've just got a couple rules in here that are going to take dot C files and compile them to dot o files I'm going to then create two different versions of this Library so I want to create a library called lib hash table and I'm going to make a shared object version and I'm going to make a static Library version I've talked a bit about these in previous videos as well I'll link to those videos down in the description so check them out if you're new to libraries as well but it's just a different way to package the code so that we can use it in different projects and so right here you'll also notice there's a rule for compiling what what's going to be my test programs so I also have this test.c we'll get to that in a minute but the idea is I want to be able to take a DOT C file and compile it with the static version of the library and then we can run tests on it and actually make sure that it works and then finally we're going to have a clean Target down here that's just going to clean up everything in our project so that's removing all of the dot a files.o files.so files the dsim files which are debug files that you see if I'm ever compiling this on Mac OS I'm working in Linux today but I tend to leave that in there because sometimes I want to compile on for my Mac but anyway let's take let's jump back into here and let's take a quick look at what our interface is going to look like so before I had a hash function sure we're going to need that but I'm going to try to make that a little more General I had an initialization function so this init hash table I also had a print table function down here I had a hash table insert a hash table lookup a hash table delete and yeah and then I had a test down here that just basically ran this whole thing through its Paces so let's try to replicate something like this these these basic functions let's put these into our hash table.h I'm going to start out with and hopefully I'll catch my errors I'm sure anytime I make an error you'll mention it down in the comments but let's put some if def cards here table dot h and then and if okay this is just going to help prevent issues with like double includes and things like that and then let's come down here and let's just add some of those same functions we had before but because I want to make this a little more generic I'm going to make let's just type def a new data type struct we'll do an underscore hash table and then we'll call it hash table now the idea here is that the user doesn't have to know what's actually stored inside of my hash table struct this is just what you're going to be using anytime you want to create a hashtag table you need something you can create so this is similar to like file pointers that are returned from F open same idea here also I mentioned before that I want to make hash functions more General so I'm going to also type def a type of function so this is going to be a un 64t which or I forget means I need to include standardint.h here and then what I'm going to do here is this is going to be a hash function is any function that takes a const character pointer and a size T so basically telling you here's a pointer to some bytes and here's the number of bytes that I want you to hash and then we're going to compute a hash and return a un64 underscore T now this should match up to close enough to this one so this one I was just assuming that it was a string so I wasn't passing in a size and I was doing an unsigned int instead of a un 64t but other than that basically the same thing so we can adjust that later on to make it fit but this is what I want to go with here and this is going to allow me to basically change out the hash function if I want this hash table doesn't have to be married to a particular hash function so now let's come down and make our functions so so let's say we want a function called hash table create and we're going to say what size we want it to be and let's pass in let's say you want a hash function pointer so pointer hash function we'll call it HF here and then let's return a hash table pointer okay so the idea here is this will create a new hash table with this many entries in the table and this is the hash function we're going to use and then it's going to return a handle basically a pointer to this opaque struct that we're going to Define insider.c file we'll get to that later then down here we also need a way to let's say hash table destroy in case you actually want to clean up this hash table and let's pass in a hash table pointer to that we'll call HT and then let's also make we had a print before so hash table print you notice I am trying to name things uniformly this is really common in libraries in C we often like to preface the name with the thing that it operates on makes it easier to see what belongs in what header file we're trying to get some of the benefits that you would get from an object-oriented language here just by using careful naming so this is going to take in a hash table now of course for really big hash tables printing is going to get a bit disastrous but that's okay this will be useful for debugging in the early stages we also want a hash table insert function and that's going to pass in a hash table HT just like all the rest of these and then we'll come in here and say we need a key right so we're going to call this a little bit of cons character key we'll assume that your key is a string and because we're doing this with our hash function I'm not going to assume that it's a string it could be but we'll assume nothing at this point and we'll pass in a key length and then we're also going to pass in a void object okay now why am I using void pointers avoid pointer basically I can point to anything so because I want to make this more general what I'm going to do is have my hash table elements B void pointers basically you just give me a pointer to something and I'll just put it in the hash table and the user can keep track of what it actually is and let's also have this return a Bool basically true if it was inserted and false if it was already there if that key already existed and then because I'm using Bool let's come up here and include standard bool.h okay so far looks okay now let's also because I mean the whole point of our hash table is to do fast lookup so let's make a hash table lookup function hash table HT so you notice all of these I'm basically passing in the object that we're operating on and let's pass in our key and the size T the key length so in this case we're going to be looking up by key what what we're looking for and then we're going to return a void pointer so this will grab the pointer that we stored in the hash table now there is sort of an implicit rule here that I'm going by and that is I'm assuming that you can't put a null pointer into the hash table because I'm going to return null if the lookup failed basically if it didn't find what we're looking for so we're gonna have to keep that in mind when we do a hash table insert is if a null gets passed in as this argument we're basically going to just return false and say now sorry we did not add that to the table now of course you could make different decisions you could pass back the void pointer through an argument and then you could have a Boolean that tells you whether it found it or not that would be totally fine as well this is just how I'm going to do it today and then let's Also let's copy this and make a hash table delete function that's going to take in again we're just going to take in a hash table and a key and a key length and so it's exactly the same as hash table lookup except because we are going to return what we found but if we did find something we're also going to remove that from the table and so this seems like a good place to start we might think of other functions that we might want to add here to operate on hash tables in the future but for now let's just start here this seems like this will work fairly well so let's take this over to our DOT C file let's include hash table dot h and then let's start implementing some of these different functions but before we do let's first come up here and oh yeah sorry this is needs to be quotes but let's come down here and let's define a few things so I the first thing I want to do is to create our structs remember we had some opaque data types up above so the first one I'm going to do is Hash table and let's give it a few things let's say it has a un32t size this is the number of elements the size of the table let's add our hash function pointer you should call that hash and then I need an array of elements so we're going to call this let's call this we'll we'll Define this in a minute but let's say they're entries and we'll do an array of Entry pointers okay so this is just a double pointer but it's an array of pointers if you're new to C and not clear on the relationship between arrays and pointers I do have a video on that that I made quite a while ago please check that out it'll make this a little bit clearer but I think that's a good place to start so we can get rid of that red line let's come up here and well actually one thing I forgot Ash table down here then let's come up and Define our entries we'll call this entry and then for each entry what I want to do is to keep track of its key I want to keep track of the the key length because we are passing in every every one of these keys we're keeping track of the length of the keys and then a void pointer to the actual object that we're storing and then I'm also going to add a pointer to another entry and that's going to be our next pointer because I'm using external chaining so each of these is going to be a node in a linked list now my size T that's just again I'm missing a header file so let's because I also use that up in here I'm not sure why it wasn't complaining at me but let's just include standard lib.h that should take care of that come down here yep okay so that took care of that right so we have our hash table struct and we have our entry struct which is the entries in the hash table now we should be ready to actually start implementing things so the first thing Let's do let's come down and let's start implementing our hash table create function so what's going to happen when we first say I want to create a hash table well what we can do let's actually we make a hash table and malloc the size of our hash table so that should allocate enough space for this table struct and then we'll come down here and set the size to be equal to size and set the hash function to be equal to HF as we passed in we're basically just saving this for use later when we actually need to Hash elements and then let's allocate space for our elements I'm going to use calc for this because it will Zero out my memory and so it will prevent me from needing a for Loop going through and setting all of those addresses all those pointers to null so here we'll just do size of Entry pointer and we're going to have the number of elements if I can type today so yeah it's important to remember that calic zeros out the memory that's one of the special things calic does for us so that's why I'm using it here and then let's just return our Ash table okay so that's going to allocate some space for all the different pointers that we want to store to objects and if we come down here to our init hash table well there's a few different things this one's a little simpler notice that it does have the for Loop that goes through and initializes everything to empty but back here we were actually using just a global hash table that I just allocated at the beginning so in this case we're trying to make it more General so we're going to allocate it on the Heap here and then we'll return a pointer to it so that you could have three or four or five hash tables however many you need Okay so let's also come down and Implement our destroy function here what we're going to do is well I'm going to come back to what to do about individual elements we will come back to that in just a minute but before we do that let's free so once we handle the elements then we're going to to free all of our array of elements so we're going to free all those pointers and then we will free our hash table struct okay so I'm going to come back to the freeing of the individual elements because I'm not really sure how I want to handle that let me think about that for just a minute now there are a few different ways we could handle that sorry this video is a little more organic than usual I haven't thought this all the way out but we'll figure it out by the end and hopefully not make too many mistakes along the way so let's for our hash table print let's go back and kind of do what we did before and that is have a say something like start table and then we'll have a for Loop of a an index that goes from zero to the hash table size and then in here if let's say if the elements if the ith element is null then maybe do we want to print out null entries I'm not really sure for now let's just do it and then as the table gets big this is going to get really annoying but for now that's okay so let's just put a tab character I think we did this this way before let me see really quick over here yeah so we did something like this so let's just keep that that could be we could just use the same thing here so we'll print out I and say hey there's nothing there so that one's empty and then otherwise if there is actually something here then what I'm going to want to do is we'll do this except now we need to go through this chain right we've got this external chain going on so now we're going to do something like make a pointer call it temp to our the head of this linked list to the ith element in our we know it's not null so we know we've got at least one thing there and then while temp is not null we are just going to go through this and print out now at this point I'm actually having some second thoughts about passing in the length of my keys so I think what I'm going to do yeah let's I'm going to call an audible here and we're going to change things up just a little bit but first let's just let's put quotes and then we're going to print out what the actual key is that we're going to use so I'm changing my mind I'm just going to treat I'm going to assume that all keys are just strings okay so I'm going to go up and remove the size in just a minute the key lengths because it's just going to make this I think a little cleaner so I'm going to print out the key and I'm going to print out the actual pointer that is stored in here since we don't have the other information then I'll put a hyphen here and yeah so let's just print out the key and let's print out the address of the object and then temp equals temp Arrow next to get the next note so this is going to go just March through and then once we're done we're just going to print f a new line okay and then one last thing we want to down here at the very end after our for loop we're going to print out end table okay now before I forget I just made a fairly significant change to my design sorry about that but what I'm going to do is come up here and say we are not storing key lengths instead I'm going to assume that everything is a null terminated string it's going to make my life just a little simpler this is going to force me to come up here and my hash function well maybe for now I'll leave the hash function as is but all these folks up here I'm going to remove the key length and we'll just pass in the pointer to our string so that'll simplify things a bit okay so now we can resume I think that's the only thing that we really changed so far I'm sure you'll call it out if I've messed something up let's close up our print let's look at how we actually add things to our hash table again let's remove the key lengths from here going to assume that we have null terminating strings for each of these so let's then come down here and while I'm at it I'm just going to add function bodies for these functions as well okay now for our insert what we're going to do here is we're going to come in here and say first of all I'm just going to check a couple of things so let's say if the key is null we're not going to allow that right so can't use a null key and you can't use a null object okay so either of these I'm just going to return false saying sorry couldn't add that to your table and then finally we actually need to do some hashing and say okay what is the index of this key in our table and so I could do this this is actually something that's going to happen in quite a few places so let's just make a function called hash table index and let's say hash table and we'll pass in the key and just get the index so let's come up here and Define one more function this is not a function that anybody else is going to be able to call it's just a private one static so it'll only be visible within this translation unit and so we'll come down here and now what I'm going to do is say size T result equals and let's take our hash table and we're going to call our hash function and I really need to Define these okay so we're going to call this hash function on our key our hash function does still require a length so we're going to do string length of key now remember that this is going to produce a uint 64 underscore T so I'm going to mod that to the size of our hash table so this should give us an index into the table it should fit from 0 to the size of the table minus 1 so it will always fit and then let's just return the result okay so this is just something that we'll be able to use over and over again we'll come back down here and we need to assign that so yeah so we're basically going to pass in the hash table and the key and this is going to give us the index into that table so now what I want to do is also make sure that I don't get duplicates in my table so what I'm going to do is say void pointer we'll call it test and I'm going to call my hash table lookup function which I haven't written yet but I'm assuming someday it will work so I'm going to pass in my hash table and I'm going to pass in my key and actually we don't even need to save it here we'll just say if hash table lookup key if that is not equal to null meaning that we actually did find something there it's already there then I'm going to return false okay so you can't use the same key twice if it's already in there you got to delete it and then reinsert it we could change this so that it overrides or whatever it doesn't really matter but for today this is what I'm going to do and then let's come down here and create a new entry for our node so if it we didn't find it basically then we're going to come down here and say entry E equals let's malloc size of thing that E points to and then let's set the object for this element equal to obj and it's key and we're here we're going to malloc space because I'm sort of taking the approach that I have custody over these elements in the hash table so once you give me the key I don't want to make any assumptions about what's going to happen to the memory that's holding that key so rather than just storing a pointer I'm actually going to Malik space for it and I'm going to get the string length of the key plus one remember key is a string so this will guarantee that I have enough space for that string on the Heap and then let's just string copy into our newly allocated space from the key that was passed in okay so now we have our entry object our entry struct and so then we can come down here and insert our entry and here we're just going to say we're going to set the next pointer of our entry to be equal to the ith element basically the head of the linked list corresponding to this hash table location that should be index so this is the index that we found up here so this is the index in the hash table that we found that's where we're going to put it and basically we're going to add it to the front of the list because that's just simpler it's going to be faster so we set this here and then we would say HT elements index equals e right so we're going to set this to be the new head of the list sorry e and then return true be because we did insert it into the list okay so that's pretty straightforward it won't work until we actually have hash table lookup implemented but otherwise this should be fine as long as I didn't mess anything up too bad okay now let's come down to look up so here what I want to do is well first of all we're going to do the exact same thing we did up top here we're going to add some checks and then we're going to get the index so we're going to say key can't be null and let's also say hash table can't be null I guess I didn't check that up here but I probably should have now of course in some cases you might want to treat the case where you passed in a null pointer as a just a program error like it's just a bug that should just crash in that case I could replace this with an assert I'll leave that up to you to sort of do what makes most sense for your program for today I'll just leave it here as a runtime check so now we have our index what I'm going to do is come down here and we're going to get a pointer to an entry we'll call that temp and that's going to start at the head so we'll go to our elements index so that's gonna that's what we're going to start looking for this node and then while temp is not equal to null and as long as the as long as let's use string compare to check or Keys as long as temps key is not the same as the key we're looking for so string compare will return zero if they're the same so as long as they're not the same then we're going to keep looking so keep looking means temp equals temp next and then if we get to the end and temp is null well then we know that we fail to find it so let's return null okay so that basically is our way of saying we couldn't find anything because we know we can't insert null into this object otherwise we're going to return temp we're going to return the void pointer to the object that 10 points to okay so that should work that looks good now let's come down here and do delete now if you remember before delete is almost the same as lookup we have to find as well but we're just going to remove it if we find it so we're going to change a couple of things we're going to start off same thing with this check basically making sure that we don't have no key don't have null hash table and we're going to get the index and then similarly we're going to come down here and we're going to get the beginning of the list we're going to be looking through this time we're basically hunting through looking for the node we want to delete let's there's a bunch of different ways we could do this but for Simplicity probably for beginning programmers let's start with a previous pointer and we'll start that out as null and then we're going to do this same search here we're going to look through basically we're looking as long as we don't run into a null pointer and as long as our keys don't match then what we're going to do is say a previous is assigned to attempt and I'm keeping track of the previous because I'm going to need it when it comes time to delete the node that I find right so other than that it's the same we're basically going to hunt one step at a time but just keeping track of what the node before the node that we're looking at is so similarly if we don't find it here you can just return null but then we can come down here and we can say if previous is null okay so if this case this basically means that we are deleting the head of the list right so in this in this case all we're going to do is set HT elements index equal to Temp next okay so this basically just moves the head pointer beyond the node that we're deleting and then otherwise it's somewhere in the middle so in this case then what you would say is the previous its next pointer needs to point to the temps next pointer okay so this is just basic deleting from the linked list from The Middle of course it could be the end but anyway deleting from somewhere that's not the head so and then at this point then what we would do is we would return the object once again so you know this is what we deleted from the list now of course it's not quite that simple because we just removed an object from the list so let's say something like result equals the object and then I'm actually going to free this temp object because we don't need it anymore so here we can come up here and then just return the result and this is basically going to give the pointer back to the user they can do with it what they want so if they delete it it comes back I'm going to assume that they will take care of freeing it or destroying it in whatever way makes sense for them okay and so now we should have a working-ish patch table that we can play with so let's just jump in here and see if we can compile it okay what do we have let's take a look at our warnings there are a lot of them so okay so it doesn't like that okay I use string length and I did not include string.h okay looks like I also missed out on on standard i o because we're going to use printf and so now it looks like okay we've got the hash table being compiled to its various forms right you can see my DOT a file and my DOT so file are being built just as I wanted the only issue we come into is when we get to this test.c and that's because if we look at test.c it's totally empty right there's nothing in it so that's fine as well so let's come in here and let's change that let's include our hash table.h and let's make a main function down here just make sure everything compiles okay so now we compile of course test doesn't actually test anything but we compile and maybe for this one let's actually come in here and add arguments yeah I think I think we might want to do that yeah the way that I think I want to run this is I think I want to actually run this so that we can pass in I have a couple of words lists here so we're going to add some words to our linked list so if ARG see let's let's do it like this if it's not equal to three oops then let's print out a usage string and let's pass in a word list file name right here and then let's also what we're going to do what I think I want to do is to have it just tried a whole bunch of guesses in the hash table guess a bunch of random words and then see what it can find that'll be a way for us to test things we could of course have a guest list or something like that but let's just do something like this it'll be interesting Maybe and then let's return exit failure because you didn't run it right so that's a failure okay now let's open that file so let's make file name equal to ARG V1 and un32t num guesses is gonna be uh it's gonna be a t o l or V2 yeah so that one should come next okay and then let's come down here and do constant table size okay we're just going to create a size for playing around with it and let's make this ah let's let's do something like this this should give us a good size to work with not so massive that we're running out of memory or anything but you know it gives us some room to run and then let's go ahead and create our hash table let's call it table and let's call Hash table create and pass in table size and then we need a hash function right so this is where our hash function comes in we need you know my hash function some thing like that to get passed in as a function pointer to this function so of course we haven't created one so let's come up and do that at this point actually what I think I'm going to do is we'll just come back here and grab the hash function that we used before we'll just basically snag that since the point of this video is not to create the world's best hash function in fact maybe we'll take a look at that in a future video but so over here in my test now notice this isn't part of my library I'm just coming in here and then we're going to say un 64 T because that's what we were returning and then I also needed a size T length and then let's change this to you and 64t we can remove this because we're passing it in as an argument and then yeah then the rest of this should work except this I don't need to monitor the table size because this function doesn't know about the table size anymore it doesn't know that there is a table or anything about the table we're just going to return a un64t and then we'll deal with the modding in the hash table itself okay so now we should have a okay so hash well we'll just leave the name as hash I'll come down here and change this to hash and that should make my red line go away okay because now we know it so now we're saying create a hash table with this many entries and using this hash function now let's come down here and open up that file and we'll pass in the file name and we'll open it for reading I'm also going to create a buffer we're going to read into and let's make it something like some kind of MAX Line let's come up here and Define that let's make it something big 4096 something way bigger than I'm ever going to need but that's okay let's also come in here and keep a count of the number of words we're looking at just so we make sure that everything worked the way we expected it and then we'll do something like while not feof well it's not the end of file oh forgot to actually Define actually name my file pointer so we're gonna have something called FP and we're going to say as long as FP it's not the end of file and as long as F gets buffer MAX Line FP so that's going to be like we're going to try to read in to this buffer up to this length from this file so as long as that did not return null then we're just going to keep reading now in this Loop I'm just going to read in all of the different lines in the file now each one when we get a line it's going to have a End of Line character on it so I want to take that off that's sort of the first thing I want to do so let's say I'm going to use a function that I really have come to love for this and that is strcspn that's string C span and we pass in buffer and then we're going to pass in a string that has a bunch of characters and if it finds one of those characters whichever the first one it finds it is going to basically give us the index of that character but if it doesn't find anything at all it will just give us the null terminating index so we can come in here and set that equal to zero so that's basically just going to if we see a slash n or r on that line it's going to change it to zero which that will become the new null Terminator so we'll just remove any unwanted line ending characters okay now at this point we could just say hash table insert we're going to add it into the table and we could here say let's just add the key being buffer right because remember we are going to malloc space for this new thing this new buffer that we've created now the problem with that though is that really what I want to do is just add this word to the hash table and so like I could try something like this unfortunately this is going to result in the same address the address of this local variable buffer being added to the hash table every time so that's probably not what I want that's going to result in basically every single entry in my whole hash table having the same address stored in that void pointer yeah I'm not really crazy about that so instead what I'm going to do is just let's make a new entry character pointer and we're going to Malik space and that's going to be the string length of buffer plus one and then we'll come down here and string copy into new entry and we will copy in buffer okay so now we can come down here and we'll just pass in new entry and new entry here now these don't have to be the same in this case I'm just making them the same because really all I want to use this hash table for is to store the keys themselves I want to store just a big list of words in a dictionary where I can look up whether something's in the dictionary or not very quickly because that's what hash tables are good for but of course this could be some other object that corresponds to this word just in this case that's not what I'm doing and then once we have inserted into the hash table then we can come down here and say num words plus plus we're basically just going to count how many words we've inserted into our table and it would be good to say number it's not an um word now we can come down here and close our file and let's print something out we're going to say something like loaded percent d words into the table and we'll print out num words oh no underscore now let's just see if this worked let's call Hash table print print out table and that should give us a good idea of whether or not we're on the right track so let's compile this I'm getting a warning because I'm still not using that num guesses variable that I used up above that's okay we will get to that so now we can come down and run it and we're going to say okay we're gonna use our words short dot txt file because otherwise it's going to be massive and let's put numb guesses 50 it doesn't really matter okay this is a bit of a problem as I mentioned before I had my doubts about whether we wanted to print out all of the empty entries so let's come in and actually remove that foreign it again and let's try this again okay this is actually looking pretty good you notice we've got all of my different words in their various rows we didn't have any collisions which is great and you notice that because we didn't pass in buffer here that each of these addresses is different so we have a different spot on the Heap for each of them so that's great that's what we were looking for now you notice that we don't have any collisions right now that's because we have a huge table and we only added 20 words to it and so yeah so if we add the whole file then we are going to naturally get many more collisions how many collisions is going to depend on the hash function and and we'll look at that maybe in a future video this one's getting a little long already but before we end let's come down here first in our test and let's actually make some of these guesses I said I was going to so I'm actually going to take out the print because as we get lots of things going on so we get lots of words in here that's going to get really obnoxious so now let's just make some guesses let's first just make a un32t I'm going to call it good guesses now start at zero okay and then we are going to have a constant that's going to be our shortest guess so we're gonna like the shortest word we're gonna guess is gonna be two and longest guess is going to be let's say 15. right so we're gonna we're gonna make random guesses anywhere from two letter guesses to 15 letter guesses and then let's just make a for Loop here really quick and we will just oh grab my parentheses and we'll start at zero and we'll go to num guesses and each time through the loop what I want to do here is basically just generate some random word and I'm going to use the buffer that we've been using before I've already got it laying around so let's just use it and then we will say like shortest guess now this Generate random word function is one that I'm going to need to implement but we'll start with shortest and let's just add so Rand mod longest guess and we probably want that to be longest guess minus shortest guess not that it's really critical that what the length is but just so it matches up to what I said I was going to do so this is going to generate a random word at some point once we're done and then we can just in here try to look it up so we can say if hash table look up and passing table and pass in this buffer that we have this random guess in so if that is not null so so if we found it then we're going to say good guesses plus plus and then down here after we're done then let's just do a print statement that just says something like percent U out of percent U guesses were in the table and we'll put in good guesses and numb guesses okay so this is great now let's just go up here and come up here to the top and let's actually go ahead and create this function this this uh Generate random word function and this we want to pass in something like a character pointer we'll call it buffer and let's pass in a size T length basically how long we want this thing to be it's important that the buffer is actually big enough to hold that length which we took care of by making it way bigger than we needed but now we'll just have a for Loop in here that will start with a size t i it's going to start at zero go from zero up to length minus one and then in this for Loop all I'm going to do is say buffer I so the ith character in buffer is going to be equal to lowercase a plus Rand mod 26 because there are 26 characters in the English alphabet so I'm basically just going to try to get random characters from A to Z and we'll see how many of those actually show up as words in our dictionary then here at the end very last let's just say buffer length minus one equals zero make sure it's null terminated it and then let's make this return void okay so now now we should have a working example so let's come down here let's compile it okay that looks okay our warning is gone which is nice now if we come in here and we rerun that well you notice we had 20 words and we made 50 guesses and not surprisingly none of them were actually guesses that were in the dictionary so that's fine let's try it with a larger example so if we go our full words file and let's say we're gonna guess something like 500 000. all right so this took a little bit longer you know as we loaded a lot more words into our table and over 18 000 of our guesses actually showed up in the table which is kind of cool now there is one thing so far that we still haven't addressed and that is now that we're all done we probably want to come in here I mean in this case this is the end of the program so it doesn't really matter but let's say that this wasn't the end of the program we were doing other things but we were done with this hash table then what about hash table destroy right wanna clean things up so we would call it like like this but you remember we didn't really finish hash table destroy right and one way that you can see we didn't finish it is if I compile this now and let's say I run this example but I run it through valgrind which is going to take a little bit longer just because well it's doing a lot and it's checking a lot of things but you notice that we've got a whole bunch of memory that is definitely lost and a whole bunch that's indirectly lost so we basically have megabytes of memory that we're just leaking so that's not a good idea to leave in our code so let's go back and look at the code this video has gone pretty long but the issue here is that we free our elements array but we don't free the individual elements okay and so I do need to come back and actually make sure I clean this all up and unfortunately I'm out of time for today so this is where I'm going to stop I hope this is useful I hope this gives you a sense for how we could make this a little more flexible I will follow this up with how we clean up this hash table as well as how we drop in different hash functions and we can compare their performance so that's coming up in a future video if you found this helpful make sure to like subscribe tell a friend click something on your way out and until next week I'll see you later

Channel: Jacob Sorber

Views: 27,255

Keywords: hash table in c, hash table, hash tables, hashtable in c, hash table in c program, hash table in c data structure, hash table in c data stucture, hash function, c hash table, hashtable example in c, hash table data structure, hashtable data structure, data structures, c tutorial hash table, c program hashtable

Id: KI_V91UdL1I

Length: 41min 20sec (2480 seconds)

Published: Tue Mar 21 2023