You need lookup by key and eviction of the oldest entry. No single data structure does both. Combine structures:
A hash map maps keys to linked list nodes. This gives lookup.
A doubly linked list maintains usage order. The head is most recent, the tail is least recent. Moving a node to the head or removing the tail node is .
On get: look up the node, move it to the head, return its value. On put: if the key exists, update and move to head. If new and at capacity, remove the tail node and its map entry, then insert at head.