Only if your keys adhere to a pattern that you can take advantage of in the data structure.
A good example would be a TrieMap
. See Wikipedia for a description and here for a discussion containing references to implementations.
I posted a Trie implementation here some time ago. Not sure how efficient it is but it works. I have certainly improved it since that post.