All O`one Data Structure

Use a doubly linked list of buckets ordered by frequency, with sentinels at both ends. Each bucket stores one count and a hash set of keys; a separate map points every key to its bucket. On increment, move the key into the adjacent count-plus-one bucket, creating it when absent. On decrement, move it into count-minus-one or remove it completely at count one. After each move, delete a bucket that becomes empty. The key invariant is that neighboring buckets differ by increasing count and every key appears in exactly one bucket. Then getMaxKey reads any key from tail.previous and getMinKey reads any key from head.next; return empty when only sentinels remain. Hash-map and hash-set operations are O(1) expected, so all operations are O(1) expected time with O(number of keys) space.