如何在Java中从HashMap中随机选择一个键？

Question

我正在处理一个大型的 ArrayList<HashMap<A,B>>，我需要从随机 HashMap 中选择一个随机键（并对其进行一些处理）。选择随机 HashMap 很容易，但如何在这个 HashMap 内部选择一个随机键呢？

速度很重要（因为我需要执行此操作 10000 次且哈希表很大），所以仅仅在 [0,9999] 中选取一个随机数 k ，然后在迭代器上执行 k 次 .next()，真的不可行。同样，每次随机选择时将 HashMap 转换为数组或 ArrayList 也不可行。请在回复之前仔细阅读此内容。

从技术上讲，我认为这应该是可能的，因为 HashMap 在内部将其键存储在 Entry[] 中，并且从数组中随机选择很容易，但我无法弄清楚如何访问此 Entry[]。因此，欢迎任何访问内部 Entry[] 的想法。当然，其他解决方案（只要不消耗哈希表大小的线性时间）也是受欢迎的。

注意：启发式方法是可以的，因此，如果有一种方法可以排除 1％ 的元素（例如，由于多填充桶），那就没有问题。

- user1111929

---

当您在同一索引处有多个条目时，这些条目将被链接在一起，因此这并不是那么简单。 - Denys Séguret

如果将entrySet转换为List不够快（您进行了分析吗？），那么您需要另一种数据结构。 - Denys Séguret

@dystroy 伪随机是可以的，如果有1%的条目从未被选中，这并不是什么大问题。这是否提供了额外的选项？因此，如果一个元素被链接，那么只需选择另一个元素即可，不必担心。 - user1111929

Answer 1

从我的脑海顶端

List<A> keysAsArray = new ArrayList<A>(map.keySet())
Random r = new Random()

then just

map.get(keysAsArray.get(r.nextInt(keysAsArray.size()))

- user902383

---

这在keySet的大小上仍然具有线性复杂度，不是吗？ :/ - user1111929

@user1111929 这取决于你的键集是否经常更改。当地图中添加或删除某些内容时，您只需更新列表即可。然后获取本身将是恒定时间。 - Joeri Hendrickx

唉，每次随机选择都会修改其中一个哈希映射。如果我可以访问 Entry[]，当然可以在数组中进行简单的修改，但似乎这个 Entry[] 不可访问（除非我复制整个源代码）。 - user1111929

从某种意义上说，这更好，因为它不需要反射，并且即使剩下很少的条目，它也能有效地工作。 - Peter Lawrey

Answer 2

我成功找到了一种没有性能损失的解决方案。我会在这里发布它，因为它可能会帮助其他人，并且可能回答关于这个主题的几个未解决的问题（我稍后会搜索这些问题）。

你需要的是第二个类似于Set的自定义数据结构来存储键，而不是像一些人在这里建议的那样使用列表。像列表这样的数据结构从中删除项目太昂贵了。所需的操作是以恒定时间添加/删除元素（以使其与HashMap保持同步），以及选择随机元素的过程。以下类MySet正好做到这一点。

class MySet<A> {
     ArrayList<A> contents = new ArrayList();
     HashMap<A,Integer> indices = new HashMap<A,Integer>();
     Random R = new Random();

     //selects random element in constant time
     A randomKey() {
         return contents.get(R.nextInt(contents.size()));
     }

     //adds new element in constant time
     void add(A a) {
         indices.put(a,contents.size());
         contents.add(a);
     }

     //removes element in constant time
     void remove(A a) {
        int index = indices.get(a);
        contents.set(index,contents.get(contents.size()-1));
        indices.put(contents.get(index),index);
        contents.remove((int)(contents.size()-1));
        indices.remove(a);
     }
}

- user1111929

---

添加操作是O(n)，因为您正在使用ArrayList。 - Jakub Zaverka

为什么添加操作是O(n)？我将a附加到ArrayList的末尾，这是O(1)。 - user1111929

我不明白为什么你要使用另一个映射来存储整数索引。为什么不直接使用indexOf方法呢？ - Jakub Zaverka

由于indexOf方法的时间复杂度是线性的，而不是常数级别的。当删除索引为k的元素时，它的时间复杂度为O(size-k)，因此当每次只删除最后一个元素时，时间复杂度为O(1)。这就是ArrayList的工作原理。 - user1111929

不错的解决方案，但有点小问题：在remove方法中，您正在从contents中删除最后一个项目，然后使用（新的最后一个元素，放置前一个最后一个元素的索引）更新索引映射。您应该存储从contents中删除的最后一个元素，并将其用作索引键。 - Alberto Di Gioacchino

Answer 3

您需要访问底层的条目表。

// defined staticly
Field table = HashMap.class.getDeclaredField("table");
table.setAccessible(true);
Random rand = new Random();

public Entry randomEntry(HashMap map) {
    Entry[] entries = (Entry[]) table.get(map);
    int start = rand.nextInt(entries.length);
    for(int i=0;i<entries.length;i++) {
       int idx = (start + i) % entries.length;
       Entry entry = entries[idx];
       if (entry != null) return entry;
    }
    return null;
}

这仍然需要遍历条目以找到存在的一个，因此最坏情况是O(n)，但典型行为是O(1)。

- Peter Lawrey

---

HashMap.class.getDeclaredField("table");，太棒了，谢谢！现在我只剩下一个疑问，为什么他们没有默认将这个放在HashMap和HashSet中呢？ :-) - user1111929

@user1111929 在这种情况下使用泛型是不可靠的 - 如果实现发生变化，程序就会出错。应该针对接口进行编程，而不是实现。 - Jakub Zaverka

@JakubZaverka 我认为您的意思是使用反射有点不可靠和脆弱。我认为使用泛型没有问题。 ;) - Peter Lawrey

你觉得这个解决方案怎么样？https://dev59.com/Amct5IYBdhLWcg3wD5WU#12386664 - user1111929

Answer 4

听起来你应该考虑使用辅助的键列表或真正的对象，而不是Map来存储在你的列表中。

- duffymo

---

不幸的是，HashMap不能提供将键存储在简单列表中的功能，而且没有其他结构可以将任意对象映射到任意对象并具有常数时间的get()方法。 - user1111929

因此，这里使用了“辅助”的词语。它是一个单独的数据结构，您将与地图列表一起维护。您犯了低层次思考的错误。 - duffymo

这是真的，但考虑到我的HashMap的大小，任何辅助结构都会显著增加内存使用量（因为对象很小但数量很多）。我仍然希望以某种方式可以访问Entry[]。我可以将整个源代码复制粘贴到一个新文件中并在那里使用它，但那不是很好的编程风格。 :/ - user1111929

Answer 5

正如 @Alberto Di Gioacchino 指出的那样，接受解决方案中存在移除操作的错误。这是我修复它的方法。

class MySet<A> {
     ArrayList<A> contents = new ArrayList();
     HashMap<A,Integer> indices = new HashMap<A,Integer>();
     Random R = new Random();

     //selects random element in constant time
     A randomKey() {
         return contents.get(R.nextInt(contents.size()));
     }

     //adds new element in constant time
     void add(A item) {
         indices.put(item,contents.size());
         contents.add(item);
     }

     //removes element in constant time
     void remove(A item) {
        int index = indices.get(item);
        contents.set(index,contents.get(contents.size()-1));
        indices.put(contents.get(index),index);
        contents.remove(contents.size()-1);
        indices.remove(item);
     }
}

- DWD 3

---

啊，我本来以为我之前修复过了，看起来没有。但是代码确实正确！我现在也已经修复了我的代码。顺便说一下，你使用了 item 而不是 a，这样无法编译。 - user1111929

啊，是的！谢谢你指出来，我刚刚编辑了它。还要感谢你的实现，它对我非常完美。 - DWD 3

Answer 6

我猜你正在使用HashMap，因为你需要在以后查找某些东西？

如果不是这种情况，那么只需将你的HashMap更改为Array/ArrayList。

如果是这种情况，为什么不将对象存储在Map和ArrayList中，这样你就可以随机或按键查找。

或者，你可以使用TreeMap代替HashMap吗？我不知道你的键是什么类型，但你可以使用TreeMap.floorKey()与一些键随机器结合使用。

- TedTrippin

---

Treemap的插入和查找时间复杂度为log(n)，而非log(1)。 - Didac Montero

Answer 7

经过一段时间的研究，我得出结论，您需要创建一个模型，该模型可以由List<Map<A, B>>和List<A>支持以维护您的键。您需要保持对List<Map<A, B>>和List<A>的访问，只需向调用者提供操作/方法即可。通过这种方式，您将完全控制实现，并使实际对象免受外部更改的影响。

顺便说一下，您的问题引导我思考：

• 为什么java.util.Set<V>接口不提供get(Object o)方法？，以及
• Bimap：我试图聪明一些，但是它的values()方法也返回Set。

这个例子 IndexedSet 可以给你一个想法。

[编辑]

如果你决定创建自己的模型，这个类 SetUniqueList 可能会对你有所帮助。它明确说明它包装了 list，而不是复制。所以，我认为我们可以做一些像这样的事情，

List<A> list = new ArrayList(map.keySet());
SetUniqueList unikList = new SetUniqueList(list, map.keySet);
// Now unikList should reflect all the changes to the map keys
...
// Then you can do
unikList.get(i);

注意：我自己没有尝试过这个方法。稍后会尝试（现在赶回家）。

- Adeel Ansari

Answer 8

从Java 8开始，有一种O(log(N))的方法需要额外的O(log(N))内存:通过map.entrySet().spliterator()创建一个Spliterator，进行log(map.size())次trySplit()调用，并随机选择第一半或第二半。当Spliterator中剩下不到10个元素时，将它们倒入列表并进行随机选择。

- leventov

---

这会产生一个（更或少）均匀随机的哈希表元素吗？trySplit()是否总是将它们分成两半，还是怎么样？我对这个新例程的内部工作方式感到困惑。 - user1111929

当您将剩余元素转储到列表并进行随机选择时，截止大小越大，整体随机键的选择就越均匀。 10个元素是测试（均匀性）的起点。 我认为，在选择变得非常均匀时，实际值可能在8到32个元素之间。 - leventov

这可能取决于键的哈希码分布质量。如果质量不错，这就不是一个问题，但如果有很多精确的哈希码冲突，或者所有键都集中在表的某些部分，因为大多数或所有哈希码中的一些位是0或1，随机键选择的均匀性可能会受到影响。 - leventov

Answer 9

HashMap是否可以被包装在Map的另一种实现中？另一个Map维护了一个列表，在put()时执行以下操作：

if (inner.put(key, value) == null) listOfKeys.add(key);

我假设值不能为null，如果可以使用containsKey，但速度会慢一些。

- user3458

Answer 10

如果您确实需要访问HashMap中的Entry数组，可以使用反射。但是这样一来，您的程序将依赖于HashMap的具体实现。

如前所述，您可以为每个映射保留一个单独的键列表。您不需要保存键的深层副本，因此实际的内存去规范化并不会太大。

第三种方法是实现自己的Map实现，它将键保存在列表而不是集合中。

- Jakub Zaverka