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

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

您可以尝试的一种方法是制作键-> 映射的多重映射，即遍历所有 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
  }
}

更新： 我运行一个快速基准测试，虽然它没有优化，但有一个明显的趋势：

"naive" 方法是遍历所有映射并检查所有后续映射，以便每对只检查一次。此外，我应用了 Holger 的建议来比较两张地图。

"map" 方法是我在此处发布的方法。

我机器上 1000 个地图的结果，每个地图有 100 个运行dom 字符串键，长度为 10：

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

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

Answer 2

创建您自己的地图，其中每个键都包含一组您的对象。如果您在键上调用 getter ，您将获得一组对象。如果你在这个集合上调用 size() ，你就会知道是否有多个对象映射到这个键。但是你不应该把所有的数据都放在一张地图上，因为这会降低硬核的速度。如果可以的话，最好对密钥进行排序。就像在一张地图中所有由数字组成的键，在一张地图中全部由字母组成，其余在第三张地图中。然后您可以检查密钥，获取属于它的地图并使用它。像这样：

public class MyMap{

private Map<String key, Set<Object>> stuff;

 public MyMap(){
  stuff = new HashMap<String key, Set<Object>>(); // Or any other map instead of HashMap
 }

 public void put(final String pKey, final Object pObject){
  Set<Object> objects = stuff.get(pKey);
  if(objects!=null)
   objects.add(pObject);
  else{
   Set<Object> objects = new HashSet<Object>();
   objects.add(pObject);
   stuff.put(pKey, objects);
  }
 }

 public Set<Object> get(String pKey){
  return stuff.get(pKey);
 }

 public void remove(String pKey){
  stuff.remove(pKey);
 }

}

但是要小心，如果你有这么多地图，这个 rlly 会破坏你的表现。您必须将密钥分开以使其更快 :) 您也可以使用任何其他 map/set。我使用 HashSet 是因为我认为如果你想像你告诉我们的那样进行检查，你不想将同一个对象两次添加到同一个键。

希望我能帮上忙:)

Answer 3

你没有说任何关于顺序的事情，但我假设所有 TreeMap 都具有相同的顺序。在这种情况下，您可以使用第二张地图的边界来缩小外部迭代范围。您的内部迭代已完全过时，因为您可以简单地询问地图是否包含密钥。

for(String s: map1.navigableKeySet().subSet(map2.firstKey(), true, map2.lastKey(), true)) {
    if(map2.containsKey(s)) {
        someFunction(map1, map2);
        break;
    }
}

解释：

假设您有以下地图键：

map2:    D, E, F, G, H
         |           |
       first        last
map1: A,    E,    G,   I
            |<--->|
          subset("D", true, "H", true)

这里，map2的第一个元素是"D"，最后一个元素是"H"。当将这些元素作为包含边界传递给 map1 的 navigableKeySet().subSet(…) 方法时，我们将获得最近的内部集 ["E", "G"] 作为搜索范围，因此我们在我们之前排除了 "A" 和 "I"甚至开始我们的线性搜索（请记住，这些只是示例占位符，它们可能代表大量键）。

想多了，比较时可以跳过两张图的任意范围：

public static boolean haveCommonKeys(TreeMap<String,?> map1, TreeMap<String,?> map2) {
    if(map1.isEmpty()) return false;
    for(String s=map1.firstKey(); s!=null; ) {
        String s2=map2.ceilingKey(s);
        if(s2==null) break;
        if(s2.equals(s)) return true;
        s=map1.ceilingKey(s2);
        if(s2.equals(s)) return true;
    }
    return false;
}

在此解决方案中，我们从映射的第一个（最小）键开始，并向每个映射询问一个与我们在另一个映射中找到的值相同或更大的键。这样我们将跳过一个地图的所有连续键，而另一个地图不包含中间键。

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

fast way to check if two sets contain at least one same element

java

set

treemap

解释：