But the point of interning is that you're reducing the strings to atoms (perhaps represented as machine words such as pointers).

Whereas a prefix search says, no, the items are not atoms, they have a structure which we can divide into a prefix and as suffix, which are independently significant in some way that we need to search for one or the other.

If this is for the identifiers in a programming language which has some hacky reflection features (like iterate over all class methods that begin with "Get"---some aspect-oriented programming systems come to mind here) then it could help to have a fast prefix search (assuming the performance of that even matters).

Yeah that's definitely the case. This test was for string interning though, so I assume the prefix checking wasn't really necessary so the trie doesn't gain any advantage from having that capability (though I admit I wasn't familiar with the concept of string interning before reading this post so I could be missing something).

It seems to be that you've hit the nail on the head:

Hash Tables are faster than Tries when your only requirement is that you don't duplicate storage.

That is the perfect use case for tries. For reference (and an excellent writeup):

http://blog.vulcanproxy.com/trie-based-http-requests-routing...

I had actually never even heard of Tries until today. Fast prefix searching makes a lot of sense; are there any other clear use cases for Tries?

Large dictionaries (set of words) can compactly be represented with tries.

For words with similar prefixes and suffixes directed acyclic word graph is a much better option (reuses prefixes and suffixes, not just the prefix as in trie), it's a little bit slower to build but fast to traverse if done right.

Any problem where there's a lot of suffix/prefix reusage benefits from a proper trie implementation (or suffix array/tree as alternative) - ex. lempel-ziv compression.

Ahh that makes a ton of sense, thanks!

more of a niche case, but i once achieved easy concurrent writes to an rbtree by converting it into a bunch of rbtrees hanging off a two-level trie. the point was that you only need to lock the subtree you're actually editing, because since tries are never rebalanced, edits cannot propagate upwards.