Design a HashMap with char keys and int values

Design a HashMap with char keys and int values, plus a getRandom() that returns a value chosen with probability proportional to how many keys currently hold that value (weighted by value frequency).

putItem('a', 5); putItem('b', 6); putItem('c', 5);
// 'a':5, 'b':6, 'c':5  =>  getRandom() returns 5 w.p. 2/3, 6 w.p. 1/3

putItem('c', 6);  // updates 'c' from 5 -> 6
// 'a':5, 'b':6, 'c':6  =>  getRandom() returns 6 w.p. 2/3, 5 w.p. 1/3

Constraints: putItem() must be O(1) (it may replace an existing key's value, which changes the distribution); delete() may be O(n).