A search-as-you-type feature does `words.stream().filter(w -> w.startsWith(prefix))` over a `HashSet<String>` of two hundred thousand words, and it's slow enough on every keystroke to be noticeable. A teammate suggests switching to a trie. Is that the right fix, and is it the only option?

The HashSet is slow for exactly the reason a hash table can never fix: hashing tells you whether one specific key is present, and nothing about keys that merely start the same way, so startsWith has no choice but to check every single word — its cost is the size of the whole dictionary, two hundred thousand comparisons per keystroke regardless of how short the prefix is. A trie is built exactly for this: the path from the root to any node spells out a prefix, so looking up all words starting with a five-character prefix means walking five characters and then collecting matches — cost proportional to the prefix length and the number of matches, not the size of the dictionary. It's the right fix in principle, but it's not the only option: TreeMap.subMap(prefix, prefix + Character.MAX_VALUE) gets you the same prefix-range answer in O(log n) plus matches, using a structure already in the standard library, already tested, with no new class to write — which for most applications is the better trade, and a hand-rolled trie is worth its cost specifically when that's been measured and found insufficient.