Evict the least frequently used key, the least recently used of them on a tie, in O(1): a map from key to node, a doubly linked list per frequency, and the smallest frequency in use. Against scanning every key for the fewest uses.
This interactive visualization needs JavaScript.