Hash Table Design

Opening scenario

Insert Delete GetRandom O(1) (LC 380). Design a structure supporting insert(val), remove(val), and getRandom() — each in average O(1), where getRandom returns an element with uniform probability. The interviewer will follow up: "Now allow duplicates." Then: "Now design the hash map itself with collision handling." With duplicates the same value may be stored many times, and getRandom must stay uniform over all copies.

LC numbers identify LeetCode problems.

In the base problem, values are unique: inserting an existing value returns False, and removing an absent one returns False. Successful insertions/removals return True. getRandom() is called only when the structure is nonempty. Which operations need a value lookup, and which need a position?

Question progression

Q1 — Why can't a single obvious structure give all three operations in O(1)?

Question: A set gives O(1) insert/remove and membership. A list gives O(1) random index. Why does neither alone satisfy LC 380, and what's the cost gap?