Insert / Delete / GetRandom in O(1) (with duplicates)

Design a data structure that supports insert, delete, and getRandom, all in average O(1):

put(key, value) — insert/associate value with key (duplicate values across keys allowed) delete(key) — remove the entry for key get(key) — return the value for key getRandom() — return a value chosen uniformly at random

Requirement: getRandom() must run in O(1) and account correctly for duplicate values — a value held by k keys is k times as likely to be returned.

Simpler variant also asked: the same structure over a plain set of strings (the string is both key and value) with insert(s) / remove(s) / getRandom() and no duplicate handling. Reported in both the online assessment and the technical phone screen.