How would you implement an LRU cache with expected constant-time get and put operations?

Combine a hash map from keys to nodes with a doubly linked list ordered by recent use. On a hit, move the node to the most-recent end; on an update, change its value and move it. On insertion at capacity, remove the least-recent node from both structures. These operations are expected O(1) with ordinary hash-map assumptions. Handle capacity zero, overwrites, and missing keys explicitly. In concurrent code, protect the map and list as one invariant; independently locking each structure can leave them inconsistent.