Java standard libraries for prefix search

For a new capability in OMERO.blitz I have a set of string prefix transformations where if a string starts with one then that prefix should be replaced by its partner. Abstractly, this seems easy to implement efficiently: for example, I can store the prefixes in a balanced search tree then, when I have a string whose prefix may need substituting, I can search for it in the tree and that largely gets me to its applicable prefix, if any.

I wondered if the Java standard libraries hand this to me on a plate but it took me some sleep to see how. Eventually I realized that I can roll my own Comparator that returns 0 (for is equal to) if startsWith and use it in a TreeMap that has from prefixes as keys with the same from and its to prefix together as each value. This approach violates equals but that is fine, it works nicely.