Как случайным образом выбрать ключ на основе его целочисленного значения в Map по отношению к другим значениям за время O (n)?

Если у нас есть Map , допустим, целочисленное значение представляет «сколько» Ts существует. Таким образом, я хочу единообразно выбирать T на основе его целочисленного значения. Если карта содержит строки с «a» = 4 и «b» = 6, то я хочу, чтобы было выбрано 40% времени «a» и 60% времени «b».

Большинство что важно, я бы хотел, чтобы это было в O (n), где n было двумя (а не десятью) в моем предыдущем примере. Изначально я сделал список ArrayList, содержащий ключи по количеству значений, которые он имел (и просто возвращал любой случайный индекс), но этот процесс не только очень медленный, но и совершенно противоречивый для того, что Map представляет.