⑴Now, what about other combinations of arrays and linked lists ? We can really start to mash these things up and see what comes out of them.Dictionaries are another abstract data type similar in spirit to stacks and queues in that you can implement them in different ways. A dictionary is a data structure that stores keys and values. And those are technical terms, keys and values. The analog in the human world would be literally a dictionary that you’d have in a classroom, a dictionary with words and definitions, more generally known as keys and values words. So that’s all a dictionary is. It associates keys with values.So, for instance, you could think of it almost as like two columns in a spreadsheet, where on the left you put the key, on the right you put the value. Or, specifically, you put the world in a dictionary and the definition thereafter. And that’s roughly how the printed pages in a dictionary are laid out.So dictionaries associate words with definitions or more generally keys with values. But it’s an abstract data type in that we could implement this in a bunch of ways. We could use maybe two arrays, one array for the keys, one array for the definitions. And you just hope that they line up. Bracket i in this one maps to bracket i in this one. But an array is not going to give us the dynamism that we want. You might run out of space when Merriam-Webster or whoever comes up and adds new words to the English language. You might not want to be using an array. You might want to use a linked list. But, again, linked lists then devolve into big O of n. And that’s not good for dictionaries and spell checking. If you have to check every possible word to find something, getting something that’s a little faster than that is compelling.So let’s consider how maybe Apple, maybe Google, maybe others are actually implementing contacts. Because even though I implied in week 0 and maybe outright said, it’s an array - - it’s a big list of all of your names of contacts maybe of some fixed size - - they probably better be using some variant of a linked list, otherwise you could never add more friends potentially. You’d max out. And they’d say you have to unfriend someone just to fit it. As an aside, this is sort of true in the social media world. Once you have 5000 friends on Facebook, you can’t have 5001. Once you have some number on Linkedln you can’t have more connections. That’s not necessarily that they’re using arrays. But it is the same implication that they’ve chosen some finite size for memory. So how might we consider implementing a dictionary specifically for your address book or your contacts.So you can store the names of everyone ideally alphabetically but also their phone numbers and maybe anything else ?Well, ultimately, we want to be able to get at someone’s name and lead to their number. So the keys and values for our discussion here will be names are the keys and phone numbers are the values. But the values themselves could also include email address and a mailing address and all of that. But we’ll keep it simple, names and phone numbers.So heres how you might think about this or draw it. On a chalkboard, two columns or in a spreadsheet, left and right. But how could we actually implement this in memory ?Because, ideally we dont want it to devolve into something linear. We dont want to have to look through all of my friends and family and colleagues to find someone whose name starts with z, for instance, or anything else. It would be nice to have something logarithmic with binary search. But with binary search again, we have to maybe use a tree instead. But now we have to use two pointers instead of one theres a lot of trade offs here. But lets see how else we could solve this same problem.Because wouldnt it be nice - - and weve not really talked about this before - - if we instead aspire to this Holy Grail of algorithms ? The best algorithm out there is surely one thats big O of 1, like constant time, because what that means is it doesnt matter if you have 1 friend, 10 friends, 100, 1000, a million, a billion friends - - it doesnt matter how big n is, your searches will always take you the same amount of time. It is independent of n. And thats why its sort of the ultimate goal for performance.So can we get to this aspiration ?Well, a couple of building blocks. Theres this notion in computing known as harshing. And hashing is a technique, literally a function in math or in code that actually takes any number of inputs and maps them to a finite number of outputs. So if you think back to high school math, domains and ranges, you can take an infinite domain with any values in the world. But it reduces them, a hash function to a finite range of specific values.So, for instance, its no accident that we have these four buckets on the stage, now, each of which has a suit from a deck of cards.We got for visibilitys sake the biggest card we can. These are the super jumbo playing cards. And in this box are a bunch of randomly ordered playing cards. And, typically, if you were to ever play some game or you wanted to these for some reason, how would you go about sorting them by suit and also by number ? Odds are if youre like me, youd probably take some shortcuts and maybe pull out all of the hearts, pull out all of the spades, pull out all of the clubs, or you bucketize it into categories. And that term is actually technical.Here are four buckets to make this clear.And, for instance, if the first card I find is the five of hearts, you know what ?Just to make my life easier, Im going to put that into the hearts bucket.Or here we have 4.Here we have 5.Here we have 6. And notice that Im putting these cards into the appropriate buckets. Why ? Because, ultimately, then Im going to have four problems but of smaller size, a 13 size problem, 13, 13, 13. And frankly, its just going to be easier cognitively, daresay algorithmically, to then sort each of the 13 cards in these buckets rather than deal with four suits somehow combined all together. So if youve ever in life made piles - - if youve ever literally used buckets like this, you are harshing. Im taking some number of inputs, 52 in this case. And Im mapping it to a finite number of outputs, 4 in this case. So harshing, again, just takes in inputs and harshes them to output values in this way. So beyond that terminology, lets consider what we can now do with hash functions thats a little more germane to storing things like our friends and family and colleagues in dictionaries.A hash function is just one that does that I as the human was just implementing or behaving like a hash function. But technically a hash function is actually a math function or a function in C or Scratch or soon Python or other languages that takes as input some value, be it a physical card or a name or a number or something else, and outputs some value.And we can use harshing as an operation to implement what well call hash tables. And thats what that dictionary was if you think about how I drew it on the screen as two columns, its like a table of information keys on the left, values on the right. So what is a hash table.The simplest way to think about it is that this is an amalgam, a combination of arrays and linked lists right. We borrowed some ideas of linked lists a moment ago to give us trees in two dimensions. What if we stick with this idea of having two-dimensional worlds but now use an array initially ? So we get the speed benefits of arrays because everythings contiguous. We can do simple arithmetic and jump to the middle or the middle or the middle or the first or the last very easily. And then you know what ? Lets use the horizontal part of the screen to give us linked lists as needed.So, for instance, if the goal at hand is to implement the contracts in my cell phone or my Mac or PC, let me propose that we start at least in English with an array of size 26.Of course, its 0 index. So its really location 0 through 25. And for the sake of discussion, let me propose that location 0 represents A, location 25 represents Z. And then everything else in between. Why We know from C that we can convert thanks to ASCII and Unicode from letters to numbers and back and forth.So in constant time, we can find location A.In constant time, we can find location Z. Why ? Because were using an array just like in week 2.All right, well, suppose that I want to think about these more as letters of the alphabet, the English alphabet rather than numbers. So its equivalent to label them A through Z. And suppose now I want to start adding friends and family and contacts to my address book. How might this book ?Well, if the first one I want to add is Mario - - Marios name starts with an M. And so thats A, B, C, D, E, F - - Ok, M goes there.So Im going to put Mario at that location in the array.After that, I add a second person, for instance, how about Luigi ? Well, L comes just before M. So it stands to reason that it goes there in the array.Meanwhile, if I go and add another character like Peach, shes going to go there a few spots away because her name starts with P.Meanwhile, heres a whole bunch of other Nintendo characters that happen to have unique letters of their first names. And theres room for everyone, room for everyone on the board A through Z with some blanks in the middle. But you can perhaps see where this is going. When and where might a problem arise with this array-based approach ? Yeah, so when we add someone else whos name colides with one of these existing characters, just because by accident, they have a name that starts with the same letter.So, for instance, theres Lakitu here who colides with Luigi potentially.Here is link who colides with both of them. But Ive drawn a solution to this along the way. I could if I was Kronion just remove Luigi from the data structure and put Lakitu in or remove and then put Link in there instead. But thats stupid if you can only have one friend whose name starts with L. Thats just bad design. But what if we now on the off chance I have two friends whose names start with the same letter, well, Ill just string them together, link them together, no pun intended, using pointers of sorts.So my vertical here is an array. And this is just an artists rendition. Theres no actual notion of up, down, left, right in the computers memory. But this is my array always of size 26. And each of the elements in this array are now not a simple number. But its a pointer to a linked list.And if theres nothing there, its just NULL, NULL, NULL, NULL.But, otherwise, its a valid address that points to the first node. And you know what ?If we have multiple names with the same letters, we can just string these nodes together, together, using pointers as well. So a hash table then as implemented here is an array of linked lists. And that allows us to, one, get some speed benefit because look how fast we inserted or found Mario, Luigi and Peach.But it still covers the scenario where, ok, some people can have the same first letters. Some of these names will colide. So collisions are an expected problem with a hash table, whereby two values from some domain happen to map to the same value.And frankly, youll see this here too. So these buckets are technically a finite size. Theyre definitely big enough for 13 cards each. But you could, imagine a world where if Im using 2 decks, 3 decks, or 4 decks, Im going to run out of space. And then my data structure cant fit any more information.But were not going to have this problem here, because the linked lists, as weve seen, can grow and even shrink, as much as they want.In the world of Nintendo theres actually lots of collisions. And these arent even all of the characters. So thats then a hash table. So with a hash table in mind, how fast is it ? Did we achieve that Holy Grail of constant time ?Well, for some of these names if I back up, yeah, its kind of constant time. Yoshi and zelda, boom, constant time, location 24, location 25. Some of then, though, like Luigi, Link, its not quite constant time because I first have to get to Luigis location. And then I have to follow this linked list. So technically then whats the running time of searching a hash table ?Sometimes youll get lucky. But sometimes you wont consider the worst case. Big O is often used to describle worst case. So what would be the worst case in your own context ? And so to summarize in some weird scenario like all of your friends and family and contacts could have names that start with the same letter. And then it doesnt matter that this is a hash table with an array of linked lists. For all intents and purposes, if your friends names only start with the same letter, all you have is a linked lists. Much like with a tree, if you dont keep it balanced, all you have really is a linked lists. So technically speaking, yes, hash tables are big O of n, in the worst case, hash tables are big O of n. Why ? Because it can devolve into this perverse scenario where you just have lots and lots of collisions all at the same values. But theres got to be a way to fix this. How could we chip away at the length of these chains so to speak ? Could I decrease the length of these linked lists. So that with much higher probability theres no collisions ?Well, maybe, the problem is that I started with just 26 buckets.I mean, 4 buckets here, 26 buckets here. Maybe the problem is the size of my array.So what if I instead just give myself a bigger array, and its too big to fit on the screen - - but what if I instead have a dollar for names that start with Laa and Lab, and Lac, Lad, do, dot, dot, all the way down ?Now, when I hash these names into my hash table, Lakitu is going to end up at their own location here. And so now I dont have linked lists. I really just have an array of names. So now Im actually back to constant time. Why ? Because so long as every letter of the alphabet has an ASCII value I can get that in constant time. And we did that as far back as week one. And so I can figure out what the arithmetic location is of each of these buckets just by looking at 1, 2, 3 characters or the total number of letters that I care about, which is just 3 in this case. So this feels like a solution. Even though I havent drawn all the names, it feels like weve solved the problem. But whats the downside or trade off of what weve just done ? Memory.So not pictured here is the dot, dot, dot, and everything above and everything below. This just exploded in terms of the number of locations in this array. Why ? Because if Im taking into account not just the first letter but the first, the second, and third, thats 26 to the third power, 26 times 26 times 26. And even though theres going to be a crazy number of names that just dont exist - - I cant think of a Nintendo character whose name starts with Laa - - you still need that bucket. Why ? Because otherwise, you dont have contiguousness. You cant just arbitrarily label these buckets. If you want to be able to use a function that looks at first, second, third letter and then arithmetically figures out where to go, whether its 0 to 25 or 0 to 26 to the third power minus 1 being the number of buckets there - - So theres a trade off there. Youre wasting a huge amount of memory just to give yourself that time. But that would then give us constant time. So in that sense, if we have an ideal hash function whereby the function ensures that no values colide, we do actually obtain that that Grail of big O of 1 because it only takes one or maybe three steps to find that names location.
CS50 x 2024 Notes Data structures - 07
⑴Now, what about other combinations of arrays and linked lists ? We can really start to mash these things up and see what comes out of them.Dictionaries are another abstract data type similar in spirit to stacks and queues in that you can implement them in different ways. A dictionary is a data structure that stores keys and values. And those are technical terms, keys and values. The analog in the human world would be literally a dictionary that you’d have in a classroom, a dictionary with words and definitions, more generally known as keys and values words. So that’s all a dictionary is. It associates keys with values.So, for instance, you could think of it almost as like two columns in a spreadsheet, where on the left you put the key, on the right you put the value. Or, specifically, you put the world in a dictionary and the definition thereafter. And that’s roughly how the printed pages in a dictionary are laid out.So dictionaries associate words with definitions or more generally keys with values. But it’s an abstract data type in that we could implement this in a bunch of ways. We could use maybe two arrays, one array for the keys, one array for the definitions. And you just hope that they line up. Bracket i in this one maps to bracket i in this one. But an array is not going to give us the dynamism that we want. You might run out of space when Merriam-Webster or whoever comes up and adds new words to the English language. You might not want to be using an array. You might want to use a linked list. But, again, linked lists then devolve into big O of n. And that’s not good for dictionaries and spell checking. If you have to check every possible word to find something, getting something that’s a little faster than that is compelling.So let’s consider how maybe Apple, maybe Google, maybe others are actually implementing contacts. Because even though I implied in week 0 and maybe outright said, it’s an array - - it’s a big list of all of your names of contacts maybe of some fixed size - - they probably better be using some variant of a linked list, otherwise you could never add more friends potentially. You’d max out. And they’d say you have to unfriend someone just to fit it. As an aside, this is sort of true in the social media world. Once you have 5000 friends on Facebook, you can’t have 5001. Once you have some number on Linkedln you can’t have more connections. That’s not necessarily that they’re using arrays. But it is the same implication that they’ve chosen some finite size for memory. So how might we consider implementing a dictionary specifically for your address book or your contacts.So you can store the names of everyone ideally alphabetically but also their phone numbers and maybe anything else ?Well, ultimately, we want to be able to get at someone’s name and lead to their number. So the keys and values for our discussion here will be names are the keys and phone numbers are the values. But the values themselves could also include email address and a mailing address and all of that. But we’ll keep it simple, names and phone numbers.So heres how you might think about this or draw it. On a chalkboard, two columns or in a spreadsheet, left and right. But how could we actually implement this in memory ?Because, ideally we dont want it to devolve into something linear. We dont want to have to look through all of my friends and family and colleagues to find someone whose name starts with z, for instance, or anything else. It would be nice to have something logarithmic with binary search. But with binary search again, we have to maybe use a tree instead. But now we have to use two pointers instead of one theres a lot of trade offs here. But lets see how else we could solve this same problem.Because wouldnt it be nice - - and weve not really talked about this before - - if we instead aspire to this Holy Grail of algorithms ? The best algorithm out there is surely one thats big O of 1, like constant time, because what that means is it doesnt matter if you have 1 friend, 10 friends, 100, 1000, a million, a billion friends - - it doesnt matter how big n is, your searches will always take you the same amount of time. It is independent of n. And thats why its sort of the ultimate goal for performance.So can we get to this aspiration ?Well, a couple of building blocks. Theres this notion in computing known as harshing. And hashing is a technique, literally a function in math or in code that actually takes any number of inputs and maps them to a finite number of outputs. So if you think back to high school math, domains and ranges, you can take an infinite domain with any values in the world. But it reduces them, a hash function to a finite range of specific values.So, for instance, its no accident that we have these four buckets on the stage, now, each of which has a suit from a deck of cards.We got for visibilitys sake the biggest card we can. These are the super jumbo playing cards. And in this box are a bunch of randomly ordered playing cards. And, typically, if you were to ever play some game or you wanted to these for some reason, how would you go about sorting them by suit and also by number ? Odds are if youre like me, youd probably take some shortcuts and maybe pull out all of the hearts, pull out all of the spades, pull out all of the clubs, or you bucketize it into categories. And that term is actually technical.Here are four buckets to make this clear.And, for instance, if the first card I find is the five of hearts, you know what ?Just to make my life easier, Im going to put that into the hearts bucket.Or here we have 4.Here we have 5.Here we have 6. And notice that Im putting these cards into the appropriate buckets. Why ? Because, ultimately, then Im going to have four problems but of smaller size, a 13 size problem, 13, 13, 13. And frankly, its just going to be easier cognitively, daresay algorithmically, to then sort each of the 13 cards in these buckets rather than deal with four suits somehow combined all together. So if youve ever in life made piles - - if youve ever literally used buckets like this, you are harshing. Im taking some number of inputs, 52 in this case. And Im mapping it to a finite number of outputs, 4 in this case. So harshing, again, just takes in inputs and harshes them to output values in this way. So beyond that terminology, lets consider what we can now do with hash functions thats a little more germane to storing things like our friends and family and colleagues in dictionaries.A hash function is just one that does that I as the human was just implementing or behaving like a hash function. But technically a hash function is actually a math function or a function in C or Scratch or soon Python or other languages that takes as input some value, be it a physical card or a name or a number or something else, and outputs some value.And we can use harshing as an operation to implement what well call hash tables. And thats what that dictionary was if you think about how I drew it on the screen as two columns, its like a table of information keys on the left, values on the right. So what is a hash table.The simplest way to think about it is that this is an amalgam, a combination of arrays and linked lists right. We borrowed some ideas of linked lists a moment ago to give us trees in two dimensions. What if we stick with this idea of having two-dimensional worlds but now use an array initially ? So we get the speed benefits of arrays because everythings contiguous. We can do simple arithmetic and jump to the middle or the middle or the middle or the first or the last very easily. And then you know what ? Lets use the horizontal part of the screen to give us linked lists as needed.So, for instance, if the goal at hand is to implement the contracts in my cell phone or my Mac or PC, let me propose that we start at least in English with an array of size 26.Of course, its 0 index. So its really location 0 through 25. And for the sake of discussion, let me propose that location 0 represents A, location 25 represents Z. And then everything else in between. Why We know from C that we can convert thanks to ASCII and Unicode from letters to numbers and back and forth.So in constant time, we can find location A.In constant time, we can find location Z. Why ? Because were using an array just like in week 2.All right, well, suppose that I want to think about these more as letters of the alphabet, the English alphabet rather than numbers. So its equivalent to label them A through Z. And suppose now I want to start adding friends and family and contacts to my address book. How might this book ?Well, if the first one I want to add is Mario - - Marios name starts with an M. And so thats A, B, C, D, E, F - - Ok, M goes there.So Im going to put Mario at that location in the array.After that, I add a second person, for instance, how about Luigi ? Well, L comes just before M. So it stands to reason that it goes there in the array.Meanwhile, if I go and add another character like Peach, shes going to go there a few spots away because her name starts with P.Meanwhile, heres a whole bunch of other Nintendo characters that happen to have unique letters of their first names. And theres room for everyone, room for everyone on the board A through Z with some blanks in the middle. But you can perhaps see where this is going. When and where might a problem arise with this array-based approach ? Yeah, so when we add someone else whos name colides with one of these existing characters, just because by accident, they have a name that starts with the same letter.So, for instance, theres Lakitu here who colides with Luigi potentially.Here is link who colides with both of them. But Ive drawn a solution to this along the way. I could if I was Kronion just remove Luigi from the data structure and put Lakitu in or remove and then put Link in there instead. But thats stupid if you can only have one friend whose name starts with L. Thats just bad design. But what if we now on the off chance I have two friends whose names start with the same letter, well, Ill just string them together, link them together, no pun intended, using pointers of sorts.So my vertical here is an array. And this is just an artists rendition. Theres no actual notion of up, down, left, right in the computers memory. But this is my array always of size 26. And each of the elements in this array are now not a simple number. But its a pointer to a linked list.And if theres nothing there, its just NULL, NULL, NULL, NULL.But, otherwise, its a valid address that points to the first node. And you know what ?If we have multiple names with the same letters, we can just string these nodes together, together, using pointers as well. So a hash table then as implemented here is an array of linked lists. And that allows us to, one, get some speed benefit because look how fast we inserted or found Mario, Luigi and Peach.But it still covers the scenario where, ok, some people can have the same first letters. Some of these names will colide. So collisions are an expected problem with a hash table, whereby two values from some domain happen to map to the same value.And frankly, youll see this here too. So these buckets are technically a finite size. Theyre definitely big enough for 13 cards each. But you could, imagine a world where if Im using 2 decks, 3 decks, or 4 decks, Im going to run out of space. And then my data structure cant fit any more information.But were not going to have this problem here, because the linked lists, as weve seen, can grow and even shrink, as much as they want.In the world of Nintendo theres actually lots of collisions. And these arent even all of the characters. So thats then a hash table. So with a hash table in mind, how fast is it ? Did we achieve that Holy Grail of constant time ?Well, for some of these names if I back up, yeah, its kind of constant time. Yoshi and zelda, boom, constant time, location 24, location 25. Some of then, though, like Luigi, Link, its not quite constant time because I first have to get to Luigis location. And then I have to follow this linked list. So technically then whats the running time of searching a hash table ?Sometimes youll get lucky. But sometimes you wont consider the worst case. Big O is often used to describle worst case. So what would be the worst case in your own context ? And so to summarize in some weird scenario like all of your friends and family and contacts could have names that start with the same letter. And then it doesnt matter that this is a hash table with an array of linked lists. For all intents and purposes, if your friends names only start with the same letter, all you have is a linked lists. Much like with a tree, if you dont keep it balanced, all you have really is a linked lists. So technically speaking, yes, hash tables are big O of n, in the worst case, hash tables are big O of n. Why ? Because it can devolve into this perverse scenario where you just have lots and lots of collisions all at the same values. But theres got to be a way to fix this. How could we chip away at the length of these chains so to speak ? Could I decrease the length of these linked lists. So that with much higher probability theres no collisions ?Well, maybe, the problem is that I started with just 26 buckets.I mean, 4 buckets here, 26 buckets here. Maybe the problem is the size of my array.So what if I instead just give myself a bigger array, and its too big to fit on the screen - - but what if I instead have a dollar for names that start with Laa and Lab, and Lac, Lad, do, dot, dot, all the way down ?Now, when I hash these names into my hash table, Lakitu is going to end up at their own location here. And so now I dont have linked lists. I really just have an array of names. So now Im actually back to constant time. Why ? Because so long as every letter of the alphabet has an ASCII value I can get that in constant time. And we did that as far back as week one. And so I can figure out what the arithmetic location is of each of these buckets just by looking at 1, 2, 3 characters or the total number of letters that I care about, which is just 3 in this case. So this feels like a solution. Even though I havent drawn all the names, it feels like weve solved the problem. But whats the downside or trade off of what weve just done ? Memory.So not pictured here is the dot, dot, dot, and everything above and everything below. This just exploded in terms of the number of locations in this array. Why ? Because if Im taking into account not just the first letter but the first, the second, and third, thats 26 to the third power, 26 times 26 times 26. And even though theres going to be a crazy number of names that just dont exist - - I cant think of a Nintendo character whose name starts with Laa - - you still need that bucket. Why ? Because otherwise, you dont have contiguousness. You cant just arbitrarily label these buckets. If you want to be able to use a function that looks at first, second, third letter and then arithmetically figures out where to go, whether its 0 to 25 or 0 to 26 to the third power minus 1 being the number of buckets there - - So theres a trade off there. Youre wasting a huge amount of memory just to give yourself that time. But that would then give us constant time. So in that sense, if we have an ideal hash function whereby the function ensures that no values colide, we do actually obtain that that Grail of big O of 1 because it only takes one or maybe three steps to find that names location.