The environment of my application is as mentioned below :

The application is a Router/Accounter library used to identify an appropriate Route (and also the price for that) when a destination for a Mobile number is queried through the API. The Route to be used for sending an SMS message depends on two things the, one the destination prefix and the two the user/client sending the SMS message.

To explain the environment in more detail, lets say an External application queries my library with details of a mobile number say 919833XXXXXX, and user say smssender. Now the route to be used for sending this message will be identified by checking if the user is have a mapping for any of the prefixes in the destination say 91 or 919833. This is where my problem lies. Given a destination I want to find out all the prefixes for the destination and then check if the user has a mapping for any of these. I am currently using a HashMap to store the Prefixes (from the Prefix master) as Keys and their details as the Values. So to find a prefix I simply run a method with a substring of the destination which gives me the prefix.

I want to know whether is there any faster more optimized way to do this search, maybe some data structure which is more suitable to such lookups than the HashMap or anything else that would possibly optimize my looking up further.

Currently the typical times for the lookups are ~30msecs for 10K lookups.

This application is written in Core Java and mostly called by a plugin Servlet.

Note : I have already considered the possibility of using a Constant Database such as the CDB with the SG-CDB interface for Java, but since this uses hash tables internally, which I am already using through the use of a HashMap, I guess it won't be much of performance booster, if it would be pls note so how.

Thanks for your help already.