HashMap：随机顺序遍历键值对

Question

我有一个HashMap, 我想每次获取迭代器时按不同的随机顺序遍历键值对。从概念上讲，我想在调用迭代器之前 "洗牌" 映射表(或者如果您愿意，可以 "洗牌" 迭代器)。

我有两个选项： 1) 使用LinkedHashMap的方法，在内部保留条目列表，在调用迭代器时进行原地洗牌并返回视图。 2) 获取 map.entrySet()，构造ArrayList并使用shuffle()函数。

虽然这两种方法在我看来非常相似，但我期望有非常大的HashMap，因此我真的很关心细节和内部实现，因为我不能浪费内存或计算能力。

- marcorossi

---

你可能不知道具体的实现细节，但是你可以随时查看Java源代码...如果你熟悉计算时间复杂度，你应该能够自己推断出一些东西，至少对于计算部分来说 :) - Less

Answer 1

重新洗牌一个大集合总是会很耗费资源。您需要至少为每个条目保留一个引用。例如，对于1百万个条目，您将需要约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) { /* ... */ }

- Peter Lawrey

---

洗牌算法为什么是O(n lg n)的时间复杂度？Fisher-Yates洗牌算法只需要线性时间，Collections.shuffle也是如此。 - Fred Foo

正确的，一个糟糕的排序洗牌是O(N * log N)，而Java使用的洗牌确实是O(N)。 - Peter Lawrey

这基本上是我的（2）个建议方法。你依赖于额外开销每个条目4字节的事实？为什么？ - marcorossi

最近版本的JVM支持32位引用。对于大型集合，列表中的大部分空间将是对“Map.Entry”的引用。如果您反复重新洗牌相同的列表，则会有轻微的优化。 - Peter Lawrey

在Java 1.7中，当创建一个ArrayList时，你可以省略显式类型参数Map.Entry<K,V>。因此，你可以这样输入：= new ArrayList<>(map.entrySet()); - Alaa M.

Answer 2

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

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();
}

}

- Laurent

---

在arrayList上执行remove()操作并不是一项廉价的操作，因为它需要移动数据。此外，这需要通过get()对数据结构进行随机访问，虽然时间复杂度为O(1)，但仍比内部迭代数据结构更昂贵。 - marcorossi

@marcorossi 谢谢，同意使用 remove() 但我的主要观点仍然是：随机选择与洗牌实现相同的目的，成本却只有一小部分。 ArrayList 不是最佳的结构选择，因为我们不需要维护键的顺序。我已经用一个简单的数组修改了我的解决方案。这个决定在于你更愿意一次性承担 O(N) 的成本还是每个 next() 承担 O(1) 的成本。 - Laurent

Answer 3

尝试使用并发哈希映射，在迭代循环之前随机获取键

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);
        }

随机删除/插入数值可以“洗牌”你的地图

- Yahor10

---

put 可以打乱你的条目，但这种可能性非常小。remove/put 不会有任何作用。 - Peter Lawrey