Design a key-value store with O(1) get, put, delete, and getRandom

Problem Design a container supporting get, put (insert), delete (remove), and getRandom — each in average O(1) — where getRandom returns a key uniformly at random from the current elements.

Requirements

• get(key), put(key, value), delete(key): average O(1).
• getRandom(): a uniformly random current key, average O(1).

Areas to design

• Which two structures combine to give O(1) membership AND O(1) uniform sampling.
• How delete keeps the sampling structure free of gaps.
• Edge cases: deleting the only element, deleting the last element, get on a missing key, duplicate puts.