How to limit the maximum size of a Map by removing oldest entries when limit reached

I want an implementation of Map that has a maximum size. I want to use this as a cache and so oldest entries are removed once limit has been reached.

I also don't want to introduce a dependency on any 3rd party libraries.