Getting Values From a Hashmap Randomly

Question

So I have a hashmap of the the type <T,Integer>. T being a generic type.

T is the any object and integer is the amount of that object we current have in the map.

For example, a string "shirt" and has a value mapping to it of 3.

I would like to build a method called random that would return a random object from the map according to the current distribution of the objects.

Meaning, if I have 2 keys in my map.."Shirt" and "Pants". There are 3 "Shirts" in my map and 7 "Pants". The distribution should be 30% of the time it will be a shirt that gets returned and 70% of the time "Pants" will be returned.

How would I go about doing something like this with a random generator?

Answer 1

That map data type is making it quite hard to implement your requirements. A better data structure will make it a lot easier. There are various possible data structures that optimise different things.

Solution for few distinct values / value counts

Here's a solution that works very well if you need to pick random values very often, and if you don't have too many distinct values / value counts:

How about a simple List<T> instead?

// Calculate this in advance
List<T> values = 
map.entrySet()
   .stream()
   .flatMap(entry -> Stream.generate(() -> entry.getKey())
                           .limit(entry.getValue()))
   .collect(Collectors.toList());

As per your example, this array will now contain 3 copies of "Shirts" and 7 copies of "Pants"

It's now very easy to pick a value at random with your desired probability distribution:

SecureRandom random = new SecureRandom();
T randomValue = values.get(random.nextInt(values.length));

Proof:

Map<String, Integer> result = new HashMap<>();
for (int i = 0; i < 100000; i++)
    result.compute(values.get(random.nextInt(values.length)), 
                  (s, j) -> j == null ? 1 : j + 1);

System.out.println(result);

... yields:

{Shirts=29955, Pants=70045}