I see your point about early detection. While a trie will have precise early failure detection a hash will have 2 ways to fail early. One would be the hash is

I see your point about early detection. While a trie will have precise early failure detection a hash will have 2 ways to fail early. One would be the hash is simply not found. But at that point you had to at least look at the entire input word, compute the hash and check for the hash. I have not done any actual analysis on this but just for thought let us look at the hypothetical case that words would fail near halfway through the testing process. In a hash we would have needed to at least read the full word while in a trie comparison of at least half the word with half the letters in the trie path would have needed to be processed. So conceptually (at least in my head) both the hash and trie would need to have done something with about the same number of letters. The question there is is computing and checking the hash more efficient than traversing the trie. The second way the hash would fail early is when we have a hash match and comparing the resulting words the hash entry held. Now if the collision rate was low then we might only have to check one word, if it is high then many words. So I would hope the hash was tuned for a low collision rate. But when comparing two words there is also early detection (this is the point I was getting at). The entire word does not need to be compared, it would likely be compared word at a time (word as in 4 or 8 bytes at a time). If I have time this weekend I think I want to implement both of these to benchmark. All that being said, the more I think about it I think a trie would be the best for a spell checker in general. Simply checking if this is a word or not is nice, but what is nicer is the ability to suggest alternatives to the misspelled word and a trie would be mucher nicer to work with with building that list.