7

我有一个 HashMap，我想在每次获得迭代器时以不同的随机顺序迭代它们的键值对。从概念上讲，我想在调用迭代器之前“洗牌”地图（或者如果你愿意，“洗牌”迭代器）。

我有两个选择：

1）使用 LinkedHashMap 的方法并在内部保留条目列表，将其就地打乱并在调用迭代器时返回该视图。
2) 取 map.entrySet()，构造一个 ArrayList 并在其上使用 shuffle()。

虽然这两种方法看起来和我很相似，但我期待非常大的 HashMap，所以我真的很关心细节和内部结构，因为我真的不能浪费内存或计算。

4

3 回答 3

11

重新洗牌大量收藏总是很昂贵的。每个条目至少需要一个参考。例如，对于 100 万个条目，您将需要大约 4 MB。

笔记; 洗牌操作是O(N)

我会用

Map<K,V> map = 
List<Map.Entry<K,V>> list = new ArrayList<Map.Entry<K,V>>(map.entrySet());

// each time you want a different order.
Collections.shuffle(list);
for(Map.Entry<K, V> entry: list) { /* ... */ }
于 2012-10-10T09:08:47.490 回答
0

实际上，您根本不需要洗牌：
只需在键数组中绘制一个随机索引并通过覆盖最后一个键来删除键：

public class RandomMapIterator<K,V> implements Iterator<V> {

private final Map<K,V> map;
private final K[] keys;

private int keysCount;

@SuppressWarnings("unchecked")
public RandomMapIterator(Map<K,V> map) {
    this.map = map;
    this.keys = (K[]) map.keySet().toArray();
    this.keysCount = keys.length;
}

@Override
public boolean hasNext() {
    return keysCount!=0;
}

@Override
public V next() {
    int index = nextIndex();
    K key = keys[index];
    keys[index] = keys[--keysCount];
    return map.get(key);
}

protected int nextIndex() {
    return (int)(Math.random() * keysCount);
}

@Override
public void remove() {
    throw new UnsupportedOperationException();
}

}

于 2012-10-10T10:53:39.843 回答
-2

尝试使用并发哈希映射并在迭代周期之前随机获取密钥

Map<String, String> map = Maps.newConcurrentMap();

        map.put("1", "1");
        map.put("2", "2");
        Iterator<String> iterator = map.keySet().iterator();
        while (iterator.hasNext()) {
            map.remove("2");// add random key values
            map.put("2", "2");
            String next = iterator.next();
            System.out.println("next" + next);
        }

随机删除/放置值可以“打乱”您的地图

于 2012-10-10T09:05:24.260 回答