5 ms·

I would argue a trie is not that good compared to a hash. Each letter is going to be a list (which you have to search), or have a fixed sized array pointing to

I would argue a trie is not that good compared to a hash. Each letter is going to be a list (which you have to search), or have a fixed sized array pointing to the next letter (could be problematic with languages that use more than a-zA-z). I just don't want to pretend that its trie or check all 235,887 words every time. This blog post could have been something much more, had it not stuck with the naive search every word method as the only alternative to a trie.

pjscott 10y ago
> I would argue a trie is not that good compared to a hash. It can be more memory efficient than a hash table if there are enough shared prefixes, and it supports prefix and range queries. As always, different data structures have different tradeoffs. > Each letter is going to be a list (which you have to search), or have a fixed sized array pointing to the next letter (could be problematic with languages that use more than a-zA-z). A common maneuver here is to encode strings as byte sequences in UTF-8 (or some such encoding), use 256-element arrays for nodes with enough children that the linear search would be inefficient, and possibly to use hash tables for nodes that are somewhere in the middle. See here for more discussion: https://en.wikipedia.org/wiki/HAT-trie https://en.wikipedia.org/wiki/HAT-trie