Map 内の要素からランダム抽出するには?

Map が持ってる要素の中からランダムに 1 要素を取り出すには keySet を Array に変換して、その中からランダムに選択するしかないのかな?

String[] keys = map.keySet().toArray(new String[map.size()]);
String value = map.get(keys[rnd.nextInt(keys.length)]);

Map.getIndex とかあったら一発なんだけど Map の意図するところとずれるか。