java - 有效地迭代多个 Java Map 键集的联合

Question

在我的一个 Java 6 项目中，我有一个 LinkedHashMap 数组实例作为方法的输入，该方法必须遍历所有键(即通过所有映射的键集的并集)并使用关联的值。并非所有键都存在于所有映射中，并且该方法不应多次遍历每个键或更改输入映射。

我目前的实现是这样的:

Set<Object> keyset = new HashSet<Object>();

for (Map<Object, Object> map : input) {
    for (Object key : map.keySet()) {
        if (keyset.add(key)) {
            ...
        }
    }
}

HashSet实例确保不会对任何键进行多次操作。

不幸的是，这部分代码在性能方面相当关键，因为它被非常调用。事实上，根据分析器，超过 10% 的 CPU 时间花在了 HashSet.add() 上。方法。

我正在努力尽可能地优化这段代码。 LinkedHashMap的使用凭借其更高效的迭代器(与普通的 HashMap 相比)是一个显着的提升，但我希望将本质上的簿记时间减少到最少。

通过使用 addAll() 预先将所有键放入 HashSet 中由于调用 HashSet.contains() 的成本，事实证明效率较低然后。目前，我正在研究是否可以使用位图(确切地说，是 boolean[])来完全避免 HashSet，但这可能根本不可能，具体取决于我的 key 范围。

有没有更有效的方法来做到这一点？最好是不会对按键造成限制的东西？

编辑:

一些澄清和评论:

• 我确实需要 map 中的所有值 - 我不能删除它们中的任何一个。

• 我还需要知道每个值来自哪个 map 。我的代码中缺少的部分 (...) 是这样的:

  for (Map<Object, Object> m : input) {
      Object v = m.get(key);
  
      // Do something with v
  }
  

  一个简单的例子来了解我需要用 map 做什么是像这样并行打印所有 map :

  Key Map0 Map1 Map2
  F   1    null 2
  B   2    3    null
  C   null null 5
  ...
  

  这不是我实际在做的，但你应该明白这个想法。

• 输入映射极度可变。事实上，此方法的每次调用都使用不同的一组。因此，我不会通过缓存他们的键的联合来获得任何好处。

• 我的键都是 String 实例。它们使用单​​独的 HashMap 在堆上进行排序，因为它们非常重复，因此它们的哈希码已经被缓存并且大多数哈希验证(当 HashMap 实现检查两个键是否实际上相等时，在它们的哈希码之后match) 归结为身份比较 (==)。探查器确认只有 0.5% 的 CPU 时间花费在 String.equals() 上。和 String.hashCode() .

编辑 2:

根据答案中的建议，我进行了一些测试、分析和基准测试。我最终获得了大约 7% 的性能提升。我做了什么:

• 我将 HashSet 的初始容量设置为所有输入映射的总大小的两倍。通过消除 HashSet 中的大部分(全部？)resize() 调用，这让我获得了大约 1-2% 的 yield 。

• 我对当前正在迭代的 map 使用了 Map.entrySet()。由于额外的代码以及担心额外的检查和 Map.Entry getter 方法调用会超过任何优势，我最初避免了这种方法。事实证明，整体代码速度稍快。

• 我敢肯定有些人会开始对我尖叫，但这里是:原始类型。更具体地说，我在上面的代码中使用了 HashSet 的原始形式。因为我已经使用 Object 作为它的内容类型，所以我没有失去任何类型安全性。调用 HashSet.add() 时无用的 checkcast 操作的成本显然很重要，删除后性能提高 4%。为什么 JVM 坚持检查对 Object 的强制转换我无法理解...

Answer 1

无法提供您的方法的替代品，但提供了一些(稍微)优化现有代码的建议。

1. 考虑用容量(所有映射的大小之和)初始化散列集。这避免/减少了在添加操作期间调整集合的大小
2. 请考虑不使用 keySet()，因为它总是会在后台创建一个新的集合。使用entrySet()，应该会快很多
3. 查看 equals() 和 hashCode() 的实现 - 如果它们“昂贵”，那么您会对 产生负面影响添加方法。