Create: Caching data-structure

[DavidRaab]

I need a data-structure for caching. It should have the following behaviour.

• Adding/Selecting something efficently by a key (very important).
• Restricted by a maximum amount.
• When something new is created that should be cached and there is not enough room, the oldest least requested element should be removed.
• Whenever something is requested it's expire time should refresh.

How to build such a structure? Which algorithms to use?

[DavidRaab]

Current approach i would maybe pick.

• Use a Hash for Storage.
• Keep extra variable that stores the current count.
• somehow save an expire-time / creation time or whatever for every key/value that is created.
• Whenever something is requested that expire-time/creation-time needs to be updated.
• Oldest must be deleted. So need a way to fast detect "oldest". (Maybe a Heap is useful here?)