Combine two data structures: a hash map and a doubly linked list.
The hash map maps keys to nodes in the linked list, giving you access. The doubly linked list maintains usage order. The most recently used node sits at the head. The least recently used sits at the tail.
On get: find the node via the hash map, move it to the head (it was just accessed), return the value.
On put: if the key exists, update its value and move it to the head. If it doesn't exist, create a new node at the head. If you're over capacity, remove the tail node and delete its key from the hash map.
Moving a node to the head and removing the tail are both with a doubly linked list. Use dummy head and tail sentinels to avoid null checks.