Selecting random key and value sets from a Map in Java

Question

I want to get random keys and their respective values from a Map. The idea is that a random generator would pick a key and display that value. The tricky part is that both key and value will be strings, for example myMap.put("Geddy", "Lee").

Transcribe

What are your performance criteria? There's an O(n) solution to pick a random element from an arbitrary sequence, but if you're going to be picking random elements a lot from the same map, you might want to create a list of the keys so you can just pick a random number and go from that. – Trometer

I have two ways that I envision this: a key is called randomly and displayed, the user enters a value, the value entered is checked against the value stored with the key. From my example above, let's say the user is asked "What is Geddy's last name?" (where "Geddy" would be taken as a string from the key), the user enters "Smith". "Smith" is then checked against the value "Lee", etc... – Transcribe

Answer 1

HashMap<String, String> x;

Random       random    = new Random();
List<String> keys      = new ArrayList<String>(x.keySet());
String       randomKey = keys.get( random.nextInt(keys.size()) );
String       value     = x.get(randomKey);

Marrowbone

I would place the entrySet() into the List. – Anesthesiology

I should add that I didn't reveal that I had to implement this in Android. Ultimately I ended up using SharedPreferences -> Map and Map -> ArrayList. – Transcribe

Worked like a charm – Peculiar

Answer 2

This question should be of help to you Is there a way to get the value of a HashMap randomly in Java? and this one also Picking a random element from a set because HashMap is backed by a HashSet. It would be either O(n) time and constant space or it would be O(n) extra space and constant time.

Trolly

Answer 3

If you don't mind the wasted space, one approach would be to separately keep a List of all keys that are in the Map. For best performance, you'll want a List that has good random-access performance (like an ArrayList). Then, just get a random number between 0 (inclusive) and list.size() (exclusive), pull out the key at that index, and look that key up.

Random rand = something
int randIndex = rand.nextInt(list.size());
K key = list.get(randIndex);
V value = map.get(key);

This approach also means that adding a key-value pair is a good deal cheaper than removing one. To add the key-value pair, you would test to see if the key is already in the map (if your values can be null, you'll have to separately call map.containsKey; if not, you can just add the key-value pair and see if the "old value" it returns is null). If the key is already in the map, the list is unchanged, but if not, you add the key to the list (an O(1) operation for most lists). Removing a key-value pair, though, involves an O(N) operation to remove the key from the list.

If space is a big concern, but performance is less so, you could also get an Iterator over the map's entry set (Map.entrySet()), and skip randIndex entries before returning the one you want. But that would be an O(N) operation, which kinda defeats the whole point of a map.

Finally, you can just get the entry set's toArray() and randomly index into that. That's simpler, though less efficient.

Beaverbrook

Answer 4

if your keys are integer, or something comparable, you can use TreeMap to do that.

TreeMap<Integer, Integer> treeMap = new TreeMap<>();
int key = RandomUtils.ranInt(treeMap.lastKey());
int value = treeMap.ceilingKey(key);

Plucky

Answer 5

I would copy the Map into an array and select the entry you want at random. This avoid the need to also lookup the value from the key.

Map<String, String> x = new HashMap<String, String>();
Map.Entry<String,String>[] entries = x.entrySet().toArray(new Map.Entry[0]);
Random rand = new Random();

// call repeatedly
Map.Entry<String, String> keyValue = entries[rand.nextInt(entries.length)];

---

If you want to avoid duplication, you can randomize the order of the entries

Map<String, String> x = new HashMap<String, String>();
List<Map.Entry<String,String>> entries = new ArrayList<Map.Entry<String, String>> (x.entrySet());
Collections.shuffle(entries);
for (Map.Entry<String, String> entry : entries) {
    System.out.println(entry);
}

Anesthesiology

Answer 6

Use reservoir sampling to select a list of random keys, then insert them into a map (along with their corresponding values in the source map.)

This way you do not need to copy the whole keySet into an array, only the selected keys.

public static <K, V>Map<K, V> sampleFromMap(Map<? extends K, ? extends V> source, int n, Random rnd) {
    List<K> chosenKeys = new ArrayList<K>();
    int count = 0;
    for (K k: source.keySet()) {
        if (count++ < n) {
            chosenKeys.add(k);
            if (count == n) {
                Collections.shuffle(chosenKeys, rnd);
            }
        } else {
            int pos = rnd.nextInt(count);
            if (pos < n) {
                chosenKeys.set(pos, k);
            }
        }
    }
    Map<K, V> result = new HashMap<K, V>();
    for (K k: chosenKeys) {
        result.put(k, source.get(k));
    }
    return Collections.unmodifiableMap(result);
}

Outlay

Although this is sound in theory, doesn't keySet() already allocate into a – Cutaneous

Answer 7

In some cases you might want to preserve an order you put the elements in the Set,
In such scenario you can use, This 

Set<Integer> alldocsId = new HashSet<>();
            for (int i=0;i<normalized.length;i++)
            {
                String sql = "SELECT DISTINCT movieID FROM postingtbl WHERE term=?";
                PreparedStatement prepstm = conn.prepareStatement(sql);
                prepstm.setString(1,normalized[i]);
                ResultSet rs = prepstm.executeQuery();
                while (rs.next())
                {
                    alldocsId.add(rs.getInt("MovieID"));
                }
                prepstm.close();
            }

        List<Integer> alldocIDlst = new ArrayList<>();
        Iterator it = alldocsId.iterator();
        while (it.hasNext())
        {
            alldocIDlst.add(Integer.valueOf(it.next().toString()));
        }

Jennette

Answer 8

Been a while since a played with java, but doesn't keySet() give you a list that you can select from using a numerical index? I think you could pick a random number and select that from the keySet of myMap, then select the corresponding value from myMap. Can't test this right now, but it seems to strike me as possible!

Numbersnumbfish

No, as the name suggests that returns a Set and not a List. So yes, you can pick a random key from a Set but not as straightforward (nor as fast) as from a List – Vishinsky