Find a prefix of a query string in the values of a Map
Trie

A trie would solve this problem perfectly.  With a trie, you could search all your prefixes in \$O(n)\$ time, where \$n\$ is the length of the input string.  You current implementation requires \$O(m*n)\$ time, where \$m\$ in the number of prefixes and \$n\$ is the length of the input string.

Of course, the trie solution will be much more complex than your existing solution, so you will need to weigh the performance benefits of using a trie versus the simplicity of using a HashMap.