如何从Java中的HashMap中选择一个随机密钥？
我正在使用一个大型ArrayList<HashMap> ，我会反复需要从随机HashMap中选择一个随机密钥（并用它做一些事情）。 选择随机HashMap是微不足道的，但我该如何从这个HashMap中选择一个随机密钥？
速度很重要（因为我需要做10000次并且哈希图很大），所以只需在[0,9999]中选择一个随机数k，然后在迭代器上执行.next() k次，实际上不是一个选项。 类似地，在每个随机选择上将HashMap转换为数组或ArrayList实际上不是一种选择。 请在回复之前阅读此内容。
从技术上讲，我认为这应该是可能的，因为HashMap在内部将其键存储在Entry[] ，并且从数组中随机选择很容易，但我无法弄清楚如何访问此Entry[] 。 因此，任何访问内部Entry[]想法都非常受欢迎。 其他解决方案（只要它们不占用散列图大小的线性时间）也是受欢迎的。
注意：启发式方法很好，所以如果有一种方法可以排除1％的元素（例如，由于多个填充的桶），那就没有问题了。
从我的头顶
List keysAsArray = new ArrayList(map.keySet()) Random r = new Random()
然后就是
map.get(keysAsArray.get(r.nextInt(keysAsArray.size()))
您需要访问基础条目表。
// 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
这仍然必须遍历条目以找到那里的条目，因此最坏的情况是O（n）但典型的行为是O（1）。
听起来你应该考虑一个辅助的键列表或一个真实的对象，而不是一个Map，存储在你的列表中。
我设法找到了没有性能损失的解决方案。 我会在这里发布它，因为它可以帮助其他人 – 并且可能回答关于这个主题的几个开放性问题（我稍后会搜索这些）。
你需要的是第二个自定义Set like数据结构来存储密钥 – 而不是像这里建议的列表。 类似列表的数据结构从中删除项目的成本很高。 所需的操作是在恒定时间内添加/删除元素（以使其与HashMap保持同步）以及选择随机元素的过程。 以下类MySet这样做的
class MySet { ArrayList contents = new ArrayList(); HashMap indices = new HashMap(); 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)); contents.remove(contents.size()-1); indices.set(contents.get(contents.size()-1),index); indices.remove(a); } }
我假设您正在使用HashMap因为您需要在以后查看某些内容？
如果不是这样，那么只需将HashMap更改为Array / ArrayList 。
如果是这种情况，为什么不将对象存储在Map和ArrayList以便随机或按键查找。
或者，您可以使用TreeMap而不是HashMap吗？ 我不知道你的密钥是什么类型，但你使用TreeMap.floorKey()和一些关键的随机TreeMap.floorKey() 。
花了一些时间后，我得出的结论是，您需要创建一个可以由List和List来维护您的密钥。 您需要保持List和List的访问权限，只需向调用者提供操作/方法即可。 通过这种方式，您可以完全控制实现，实际对象将更安全地从外部更改。
顺便问一下，你的问题引导我，
- 为什么java.util.Set
接口不提供get（Object o）方法？ ，和 - Bimap ：我试图变得聪明，当然，它的
values()方法也会返回Set。
这个示例IndexedSet可以让您了解操作方法。
[编辑]
如果您决定创建自己的模型，则此类SetUniqueList可能会对您有所帮助。 它明确指出它包装list ，而不是副本。 所以，我认为，我们可以这样做，
List 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);
注意： 我自己没试过。 之后会这样做（赶回家）。
使用map.keySet()从地图键map.keySet()获取，并使用ArrayList选择随机键。 然后你可以用map.get(randomKey)获取值。
如果您绝对需要在HashMap中访问Entry数组，则可以使用reflection。 但是那时你的程序将依赖于HashMap的具体实现。
如建议的那样，您可以为每个地图保留一个单独的键列表。 你不会保留密钥的深层副本，因此实际的内存非规范化不会那么大。
第三种方法是实现自己的Map实现，即将密钥保存在列表而不是集合中的实现。
如何在另一个Map实现中包装HashMap？ 另一个映射维护一个List，而在put（）上它做：
if (inner.put(key, value) == null) listOfKeys.add(key);
（我假设不允许使用值的空值，如果它们使用containsKey，但速度较慢）