一种快速的方法来检查两个集合是否包含至少一个相同的元素

Question

我有两个TreeMap，我想检查它们是否至少包含一个相同的键（这些键是字符串）。因此，我使用两个循环进行比较：

boolean found = false;
for(String key1 : map1.keySet()){
    for(String key2 : map2.keySet()){
        if(key1.equals(key2)){
            found = true;
            break;
        }
    }
    if(found){
        break;
    }
}
if(found){
    someFunction(map1, map2);
}

因为我有500,000个TreeMap（每个约有1000个键），并且我想对照每个地图检查每个地图，所以需要很长时间。有谁知道更快的解决方案？

*编辑：每当我发现两个映射至少有一个相同的键时，我想调用“ someFunction（）”方法。我认为在所有案例中> 90％found == false

Answer 1

您可以尝试的一种方法是制作一个key-> maps的多重映射，即遍历所有500k映射，并为它们包含的每个密钥添加它们。

然后再次遍历键，如果一个键有两个或多个映射，则这些映射共享它。

通过这种方法，复杂度应该从降低O(n² * m)到O(n * m)（n即地图m的数量和键的数量）。

粗略的轮廓：

Multimap<Key, Map<Key, Value>> mapsContainingKey = ... ;//could be a Guava Multimap
//O(n * m) complexity
for(Map<Key, Value> m : largeSetOfTreeMaps ) {
  for(Key k : m.keySet() ) {
    mapsContainingKey.put( k, m );
  }
}

//O(m)
for( Entry<Key, Map<Key, Value>> entry : mapsContainingKey.entries() ) {
  Key key = entry.getKey();
  Collection<Map<Key, Value>> mapsWithSameKey = entry.getValue();
  if( mapsWithSameKey.size() > 1 ) {
    //all maps in that collection share this key
  }
}

更新： 我运行了一个快速基准测试，尽管它没有进行优化，但是有一个明显的趋势：

“幼稚”的方法是遍历所有映射，并对照所有后续映射进行检查，以便每对仅检查一次。另外，我应用了Holger建议的比较两个地图的方法。

我在这里发布的是“地图”方法。

我的机器上有1000张地图的结果，每张地图都有100个长度为10的随机String键：

naive: 11656 ms
map:     235 ms

更新2：更多具有不同大小的结果：

1000张地图，其中包含100个不同长度的按键（按键越长，碰撞越少）

key length   1        2         3         4         5        10        20
naive      417 ms  3221 ms  10937 ms  11273 ms  11357 ms  11383 ms  11706 ms
map         16 ms    43 ms     86 ms    224 ms    245 ms    210 ms    154 ms

1000个地图，每个地图的按键数量各不相同，按键长度为10（按键越多，碰撞越多）

key count    50       100       500
naive      4865 ms  11368 ms  81280 ms 
map          64 ms    206 ms    913 ms

数量不一的地图（每个地图有1000个键，键长为10）（地图越多，碰撞越多）

map count    500     1000      2000
naive      6323 ms  12766 ms  47798 ms 
map         139 ms    206 ms    333 ms

如您所见，地图数量对此影响最大，其次是键的数量。