I have just started with speller and wanna know that though I have to keep my runtime short how may I use hash tables for that because they have a constant runtime (in search) for every node to be hashed in a bucket or to a particular linked list but they also have the linear runningtime for the linked lists.In insertion hash tables have O(1) running time to keep unsorted and O(n) for sorted.Whereas with tries the runtime seems to be O(1) as it only depends on the length of the word to search or delete rather than the amount of whole words in the trie. I am more comfortable with hash tables and so am asking this question that is it ok if go for hash tables?Any suggestions will be apppreciated!


I know the pset mentions keeping time as short as possible such as this:

But therein lies the challenge, if not the fun, of this problem. This problem is your chance to design. Although we invite you to minimize space, your ultimate enemy is time.

But honestly I wouldn't worry so much about that as actually being able to complete the problem correctly. Considering that the walk through spends at least as much time discussing hash tables as tries, it seems that either one is just as good as the other. If you feel most comfortable with hash tables, then by all means go for it. If the staff really wanted to make time a serious part of this problem they would have some time limit in check50, but they don't. It is more of a personal challenge if you want to minimize wasted code, or implement faster algorithms (with different data structures. With that in mind I would say it is definitely fine to opt for a hash-table.

Remember that you can always go back and (re)implement this problem in a trie or some other structure if you wish, so my advice would be do any structure you feel comfortable with, and maybe if you come across a similar problem where a hash-table or trie could be used, see if you can challenge yourself to use a trie instead.

Have fun!


I got a runtime of 0.16 with a hash table, I certainly enjoy a lot more with a table hahs than with a trie, after solving the problem I could look for some optimizations, and I could implement my own hash function (if you are interested I can publish it, since it does not go against honor code), I definitely liked it a lot more, also the hash tables have a lot of applications. If you feel comfortable, I encourage you to try it whit a hash table.

You must log in to answer this question.

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