★ FEATURED ARTICLE ⑴Now, to make this clear, how do we translate this to something like code ?Well, here again is the struct we used last time for that of a person and a person had a name and a number.Here, for a hash table, we might do something a little bit differently. We might now have a node in a hash table storing the persons name, persons phone number, and a pointer to the next such person in that chain if needed. Hopefully this is going to be NULL most of the time, all of the time. But we need it just in case we do have that collision. Weve seen in our pictures the names, like Mario, Luigi, and so forth. We didnt see the numbers. But thats whats inside of those boxes on the picture. But that node would give us what we need to build up these linked lists. Meanwhile what is the hash table itself, that vertical strip along the left ?Well, its really just a variable. We could call it table for short of size 26. And each of the locations in that array that was on the side, here, at least in the simple, small version, was a pointer to a node. So its NULL if theres no one there or its a valid address of the first node in the linked list. So this then is a hash table. And each of those nodes, to be clear, would be defined as follows. So whats the takeaway then with a hash table ? Ideally, with a good hash function and with a good set of inputs where youre not presented with some perverse set of inputs thats like all of the friends whose names start with the same letter.Ideally what the hash function will be doing for you is this. The input is going to be someones name.The algorithm in the middle is going to be the hash function. And the output is the so-called hash value or location in this case.So, for instance, in the case of Mario, when we had just 26 buckets total, the input to the hash function would be Mario. That hash function would really just look at the first letter, M in that case, and would ideally output the number 12. I did the same thing.But in my head, whenever I pulled out a card like the five of diamonds here, I figured out, ok, thats location 0 out of my 0, 1, 2, 3, all four total buckets.Here were doing it instead alphabetically. And so someone like Luigi meanwhile would have a hash value of 11. These numbers would be bigger, of course, though, if were looking at 1, 2, 3 letters instead of just one. So with that said, if we were to implement this in actual code, a hash function ?I did it physically by acting out the cards. Here is how we might implement this in code using C. I could have a function called hash whose argument is a string, a.k.a, char star, a name of which is word, where the word is like the first word in their name. We want this function to return an int, which ideally in this case of 26 buckets would be a number from 0 to 26. And how do we achieve that ? Well, if we use our old friend ctype, which had a function like toupper from a couple of weeks back, we could pass in the first letter of that word, capitalize it, which is going to give us a number thats 65, 66, 67 on up for the 26 English letters. And if I subtract 65, a.k.a, quote, unquote - - single quotes because its a char - - thats going to mathematically give me a number between 0 and 25 inclusive. Theres a potential bug. If I pass in punctuation or anything thats not alphabetical, bad things will happen. So I should probably have some more error checking, but this is the simplest way in code that I could implement a hash function that looks only at the first letter of their name. Probably not ideal because I can think of friends in the real world who have the same first letter of their name. Whether this is better or worse than looking a 2 letters, 3 letters, 4 letters, its going to depend on how much memory you want to spend and how much time you want to ultimately save.Let me tweak this though a little bit. Its conventional in C, just so you know, that if youre passing in a string that is a char star to a function and you have no intention of letting that function change the string, you should probably declare the argument to the function as const. And that will tell the compiler to please dont let the human programmer actually change that actual word in this function. Its just not their place to do so. And we can actually do something else. In a hash function because youre using in this case, the output, the integer as a location in an array, it had better not be negative. You want it to be zero or positive.And so, technically, if you want to impose that in code, you can specify that the int thats being returned has to be unsigned, that is, its 0 on up through the positive numbers. It is not a negative value. So this is slightly better than the previous version where we didnt have these defenses in place. All right, so what does this actually mean in practice ? You dont get to necessarily pick the hash function based on the names of your friends. Presumably, Apple and Google and others already chose their hash function independent of what your friends names are. So ideally, they want to pick a hash function that generally is quite fast, big O of 1. But practically speaking, in a hash table unless you get really lucky with the inputs, which you generally wont, really its big O of n running time. Why ? Because in the worst possible scenario, you might have one long linked list. But in practice, ideally - - and this is a little naive - - but suppose that you have a uniform distribution of friends in the world where 126 of them have names starting with and then another 126 out of B and then dot, dot, dot, Z. That would be a nice uniform distribution of friends.Technically then, your running time of a hash table for searching it or deleting or inserting would technically be big O of n divided by k, where k is the number of buckets, a constant. So its technically big O of n divided by 26. Now, again, per our discussion of big O notation, thats still the same thing. You get rid of constant factors. So, yes, its 26 times faster. The chains are 126, the length.But asymptotically in terms of big O notation, its still big O of n. And heres where now we can start to veer away from what is theoretically right versus what is practically right. In reality, in the real world, if you work for Google, Microsoft, Apple, and others, 26 times faster is actually faster in the real world even though a mathematician might say, thats really the same thing. But its not.The real world wall clock time, if you watch the number of seconds passing on the clock, n over k is a much better running time than big O of n. So here too were getting to the point where the conversations need to become a little more sophisticated. Its not quite as simple as theory versus practice. It depends on what matters ultimately to you.But ideally and literally if somehow or other they picked an ideal hash function, big O of 1 would really be the ideal here, would really be the running time we achieve. And what youll generally find in the real world is that you dont use hash functions that are as simplistic as just look at the first letter. And, honestly, they wont generally look at the first and the second and the third letter. Theyll use some even fancier math to put real downward pressure on the probability of collisions, so that, yes, they will still happen. But most of the time a really good hash function, even if its not quite ideal, will be darn close to constant time, which makes hash tables and in turn dictionaries one of the most universally compelling data structures to use.⑵Now, with that said, we have time for just another data structure or so.And this is not a typo. This ones called and try. And a try is short for retrieval, which is weird because you say retrieval. But you say try. But thats the etymology of try. And a try is of the weirdest amalgamation of all of these things, whereby a try is a tree of arrays. So a hash table is an array of linked lists. A try is a tree of arrays. So at some point computer scientists just started mashing together all of these different inputs, and lets see what comes out of it. But a try is actually really interesting. And what youre about to see is a data structure that is literally big O of one time, constant time. But there is a downside.So in a try, every node is an array. And every location in that array generally represents a letter of the alphabet. But you could generalize this away from words too.In this case, if we have a root node, that root node is technically a big array with 26 locations.And if you want to insert names or words more generally into a try, what you do is this. You hash again and again and again creating one array for every letter in your word. So what do I mean by that ?If weve got 26 elements here, this would be representing A.This would be representing Z. And initially these are all NULL by default when you have just this root.But suppose I want to insert a few friends of mine, including Toad for instance, T-O-A-D is the name. So how would I do that ?I would first find the location for T based on its number 0 through 25. And if this is T, what would I then do ?I would change the NULL to actually be a pointer to another node, a.k.a. Another array. And then I would go into the second array and hash on the second letter of Toads name which is, of course, O.And then I would set a pointer to a third node in my tree, which would be represented here, so another 26 pointers.Then I would find the pointer representing A.And I could create finally a fourth node, another array representing the fourth letter of Toads name. But because Toads name ends with D and therefore I already have four nodes here, we need to specially color though we could probably use an actual variable here.I need to somehow indicate that Toads name stops here. So its not NULL per se, this actually means that T-O-A-D is in this data structure. But I did this deliberately because another friend of mine might be Toadette in the Nintendo World. And Toadette, of course, is a superstring of Toad. That is, its longer but it shares a common prefix.So Toadette would continue. And I could have another node for the E,another node for the T,another node for the second T,and another node for the last E. But I somehow have to mark that E as the end of her name as well.So even though they share a common prefix, the fact that theres two green boxes on the screen means that T-O-A-D is in this dictionary as a key as T-O-A-D-E-T-T-E is another key. And technically speaking, whats in these boxes, too - - its not just a pointer.Its probably Toad and Toadettes phone number and email address and the actual value of the dictionary, which is to say, this too is in fact a dictioanary. A dictionary is just an abstract data type, a collection of key value pairs, just like I claimed a stack and a queue was. And how you implement it can differ. You could implement it with a hash table, an array of linked lists as we just did, or you can implement a dictionary as a try, a tree of arrays.And let me add one more name to the mix, Tom, for instance, a valid name from the universe T-O-M just means that, ok, that name exists in this structure as well. Now, what is the implication of storing the names in this way, which is implicitly. Im effectively storing Toad and Toadette and Tom in this data structure without actually storing T or O or A or D or any of the other letters.Im just implicitly storing those letters by actually using valid pointers that lead to another node.And so whats the implication of this encode ? Well, encode it might look like this. Every node in a try is now redefined as being an array of size 26 - - and Ill call it chirldren just to borrow the family tree metaphor - - and that in each of these nodes there is room for the persons phone number, for instance, a.k.a, a string or char star.So what does this mean ? Well, if theres actually a non-null number there, thats equivalent to there being a green box. If you actually see plus 1, 617 dash whatever there, that means theres a green box because Toads number is right here. Or Toadettes numer is down here. Or Toms is over there. But if this is NULL, that just means that maybe this is the T or the D or the E, which are not actually ends of peoples names. So thats all these nodes actually are.And if we think back now to what this data structure looks like, this is in fact a data structure that can be navigated in constant time. Why ?Well, all we need to keep track of this data structure is literally one pointer called try thats a pointer to the first of these nodes, the so-called root of the try.And when it comes to now thinking about the running time of a try, well, what is it ? Well, if you got n friends in your contacts already or if theres n keys in that data structure, how many steps does it take to find anyone ? Well, whether I have three names, Toad, Toadette, or Tom or three million names in that data structure, how many steps will it take me to find Toad ever ? T-O-A-D. How many steps for Toadette ? T-O-A-D-E-T-T-E. Eight steps. How about for Tom ? 1, 2, 3. And frankly. Im sure if we looked it up, theres probably a limit on the number of characters in Nintendo characters name. Maybe its 20 characters total or maybe a little longer 30. Theres some fixed value. Its not unbounded. Theres not an infinite number of letters in any Nintendo characters name. So theres some constant value. Call it K. So no matter whose name youre looking for, its going to take you maximally K steps. But K is a constant. And we always said that big O of K is the same thing as big O of 1. So for all intents and purposes, even though were taking a bit of liberty here, searching a try, inserting into a try, deleting from a try is constant time. Because if you have a billion names in the dictionary already, its going to take up a huge amount of space. But it does not affect how many steps it takes to find Toad or Toadette or Tom. That depends only on the length of their names which effectively is a constant value. But there is a downside here. And its a big one. In practice, I daresay most computers, most systems would actually use hash tables, not tries, to implement dictionaries, collections of key value pairsWhats the downside of this here data structure might you think ? And this is just a representative picture for Toad, Tom and Toadette. All the space it takes up - - I mean, even for these three names, look at how many empty pointers there are. So theyre NULL to be sure.But theres 25 unused spaces here, another 25 unused spaces here, 24 unused spaces here. And whats not pictured is if Ive got more and more names, this things just going to blow up with more and more and more and more and more arrays even though theres not going to be someone whose name starts with like Laa or Lba or Lbb. Theres going to be so many combinations of letters where its just going to be NULL pointers instead. So it takes up a huge amount of space. But it does give us constant time. And that then is this here trade off. So I would encourage you here on out as we exit the world of C and so much of todays code in the past several weeks code will soon be reduced in a weeks time to just on line of code, two lines of code. Because Python and the authors of Python will have implemented all of this weeks and last weeks and prior weeks ideas for us, well be able to operate at a higher level of abstraction. And just think about what problems we want to solve and how we want to do so algorithmically and with data structures. And data structures in conclusion are everywhere.Has anyone recognized this spot in Harvard Square. So this is Sweetgreen, a popular salad place. And this is actually a dictionary or really a hash table of sorts. Why ? Well, if you buy a very expensive salad at Sweetgreen, they put it on the shelf for you if youve ordered via the app or online in advance.And if I, for instance, were to order a salad, it would probably go under the D heading. If Carter were to order a salad, it would go under C, Julia under J. And so they hash the salads based on your first time to a particular location on the shelf. Why is that a good thing ? Well, if it were just one long shelf that wasnt even alphabetical, it would be big O of n for me to find my salad and for Carter and Julia to find theirs. Because theyve got 26 letters here, its big O of 1. Its one step for any of us to find our salads. Except, again, in perverse situations, where to might this system devolve at like 12:30 PM in the afternoon for instance ? What could go wrong ? Yeah, a lot of people with the same first letters of their names might order a salad. So theres lots of like D, D, D. Where do we put the next person ? Ok, well, maybe we overflow to E. What if theres a lot of E people ? It overflows too. F, what if it overflows ? Then we go to G. And it devolves anyway into a linked list or really multiple arrays that you have to search in big O of n time ? Ive even been to Sweetgreen at non-popular times. And sometimes the staff just dont even choose to use the dictionaries. They just put whats closest to them. So you have to search the same thing anywhere. But youll start to see now that youve seen some of these building blocks that data structures are everywhere, algorithms are everywhere. And among the goals of CS50 now are to harness these ideas most efficiently.
阅读完成 · 觉得有帮助？
