[Evans] I hope everyone understands the main idea behind the hash table now. Our goal is to map a keyword and the number of buckets using a hashstring function to a particular bucket,and that bucket will contain all of the keywords that map to that location. So now what we’re going to do is try to actually write the code to do this. We’re going to start from our index that we wrote for the previous unit but try to figure out how to implement that with a hash table instead. The first question is, how is this going to change our data structure? This was what we had before. If you remember, we had our index was a list of keywords. We had a list of entries, and each entry was a pair, which was a keyword, and the second element of the pair was a list of the URLs where that word appears. And we would have each word in the index as its own entry with its own list of URLs. So this was the data structure that we used last class. Now we want to change things to implement a hash table. I want you to think about what data structure I’ll use, and we’ll make that a quiz to decide a good data structure to use to implement the hash table. The question is, which of these data structures would make most sense to implement the hash table index? The first choice is a list where the elements in the list are a list where the first element is a word and the second element is a list of URLs where that word appears. The second choice is a list where each element in the list is a list itself where the first element is a word and the second element is a list of lists where each element in that list is a list of URLs. The third choice is a list where each element is a list where the element lists themselves contain lists where the element lists of the element lists are a list of a word followed by a list of all the URLs where that word appears. So we have 3 nested lists for choice 3. For choice 4 we have a list where each element of the list is a list where within the element list there’s another list which is a list of words followed by a list of URLs. And for the final choice we also have 3 nested lists where each element list is a list where the elements of that list are lists that are a word followed by a list where each element in that list is a list of URLs. So which one of these would be the best structure to use to implement a hash table?