Select random without replacement according to a distribution

So, let's say I have a collection that maps colors to its number of balls:

colors = {"red": 1000, "green": 5000, "blue": 10000}

I want so select a random color without replacement:

For i in total number of colors:
    select random color according to distribution
    ...
    reduce the ball count for that color
    i = i - 1

or we could create the list: ["green", "green", "green", ... , "red"] and then use the shuffle method from the standard library. Once shuffled, we can then iterate over that list. However, I imagine this would have a greater space complexity (unless there is some kind of optimisation behind the scenes for the same elements in a list).

What is the most efficient way to implement this in Java?