To get a benefit out of the HashMaps quick access to keys you you'd need an exact match between your search date and a key date.
Can you cluster your Map-Content? eg.: do you always serch for a complete month?
Then you could change your Map from Map<Date,Object> to Map<Date,List<Object>> where Date is "normalised" to the first Day in month 00:00 o clock (UTC or local...).
You could also consider an additional map (Map<Date,List<Date>>) where you group the actual keys of the original Map by the expected search clusters.