In week 9 lecture, David said:

An associative array is one in which you can store key value pairs where the key is not necessarily a number. It could in fact be a string, a word. And so this can be implemented, underneath the hood, it turns out, using a data structure known as a? Thought something dramatic was about to happen — hash table. So a hash table, recall, those of you who did it for pset6, or even recall it, at least even if you did a try, a hash table, in our usage, was used to just store words. But really, you were storing keys and values. If you implemented a hash table for pset6 dictionary, the keys were the words themselves, and the values were effectively true or false. Yes, here, or implicitly, no, not here. Well, we can generalize that idea. And we could use a very similar data structure to store not the string itself alone in your hash table, but suppose that in every one of your hash table's nodes. And you could even do this in a try rather than just have a bool. You could have something else. What if the key was not maxwell, for instance, but quote unquote "name," or quote unquote "captain." And inside of your C data structure, you put a value, not just a Boolean, but of value like quote unquote "David," or "M," or "Matthews," and so forth. So those same data structures we used apparently exist in other languages. And I'd argue they're actually much, much simpler to access here.

Can some explain this? I don't understand why the key is the word and the value is a bool.

1 Answer 1


A hash-table basically maps keys to values (it basically consists of these two parts — the keys part and the values part). If you used a hash-table in pset6, you'd probably know that you had to implement a function, namely check, that takes a word and returns true if this word is in the dictionary or false otherwise. This is implicitly the same thing as mapping words to bool values.

Actually, the hash-table mapped numbers (the hash values) to words though, but this was just to serve the main goal (i.e., checking the dictionary for words).

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .