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.
You can also consider putting the data in a database table (which I prefer) as Date objects and querying what you want with SQL, something like the following pseudo code, where '?' is today's date.
select ItemName from Stock where ?>=EffectiveDate and ?<=ExpireDate order by ItemName