通过有效地连接几个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.contains()之后调用的成本,事先将所有密钥放在HashSet中,使用证明效率较低.目前我正在研究是否可以使用位图(好吧,boolean[]确切地说)来完全避免使用HashSet,但根据我的键范围,它可能根本不可能.

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

编辑:

一些澄清和评论:

• 我确实需要地图中的所有值 - 我不能放弃它们中的任何一个.

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

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

  一个简单的例子来了解我需要对地图做什么,就像这样并行打印所有地图:

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

  这不是我实际做的,但你应该明白这一点.

• 输入映射非常多变.实际上,此方法的每次调用都使用不同的一组.因此,我不会通过缓存他们的键的联合来获得任何东西.

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

编辑2:

根据答案中的建议,我做了一些测试,分析和基准测试.最终我的性能提升了大约7%.我做了什么:

• 我将HashSet的初始容量设置为所有输入映射的集合大小的两倍.通过消除resize()HashSet中的大多数(所有？)调用,这在1-2%的区域内获得了一些东西.

• 我用于Map.entrySet()我目前正在迭代的地图.由于额外的代码以及担心额外的检查和Map.Entrygetter方法调用将超过任何优点,我最初避免使用这种方法.原来,整体代码略快一些.

• 我相信有些人会开始尖叫我,但这里是:原始类型.更具体地说,我在上面的代码中使用了原始形式的HashSet.由于我已经将Object其用作内容类型,因此我不会失去任何类型的安全性.checkcast呼叫时无用操作的成本HashSet.add()显然非常重要,足以在移除时将性能提高4%.为什么JVM坚持检查强制转换Object是我的...

Answer 1

无法提供您的方法的替代方案，但提供一些（稍微）优化现有代码的建议。

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