A multi-threaded key-value cache that only has thread contention while querying for same key simultaneously
I'm working on similar thing at the moment. So my thoughts are that you might use most popular EhCache in order to keep something you already have. 
  ehCache.get(key) -> if its there, you return, if it's not there, we call provider.
  When we call provider - we need to wait for response, so I'm thinking about something like 
 Question about your data provider - can you have parallel calls? Do you have some throttling there? If so, you could have some concurrent map for calls to store responses for keys. Once API is done you might store response in Ehcache so you have that for future. 
 I think EhCache is better than just concurrent map for "caching" because you might define amount of entities, eliminate them, have a disk-backed cache, etc.