A hash map finds a key’s node in O(1), and a doubly linked list keeps the nodes in order of use, so get, put and evicting the least recently used entry are all O(1).
This interactive visualization needs JavaScript.