title: How to randomly select a key based on its Integer value in a Map with respect to the other values in O(n) time?
body: <p>If we have a <code>Map&lt;T, Integer&gt;</code>, let's say the Integer value represents "how many" Ts there are. Thus, I want to uniformly select a T based on its Integer value. If the map contains Strings with "a"=4 and "b"=6, then I want it so that 40% of the time "a" is selected and 60% of the time "b" is selected.</p>
  
  <p>Most importantly, I'd like this in O(n), n being <strong>two</strong> (not ten) in my previous example. I originally made an ArrayList containing the keys by how many values it had (and simply returning any random index), but this process is not only very slow, but completely counterintuitive for what the <code>Map&lt;T, Integer&gt;</code> represents.</p>