I have a HashMap that stores <city, state> pairs where city is key and
state is value. Now city names may be multiple words long, like "New Delhi". Now there are
many sentences that may or may not contain the city name. I want to check that for each of them.

 One approach is go on scanning the HashMap and check for each of the key whether it is present in sentence. But if the HashMap is of millions of entries it is going to be an
very inefficient approach.

So I am looking for if there is any efficient approach to do the same. Thank you.