有一种方法可以尝试,就是创建一个键->映射的多重映射,即遍历所有500k个映射,并将它们添加到它们包含的每个键中。
然后再次遍历键,如果一个键有两个或更多的映射,则这些映射共享该键。
采用这种方法,复杂度应该从O(n² * m)
降至O(n * m)
(n
是映射的数量,m
是键的数量)。
大致概述:
Multimap<Key, Map<Key, Value>> mapsContainingKey = ... ;
for(Map<Key, Value> m : largeSetOfTreeMaps ) {
for(Key k : m.keySet() ) {
mapsContainingKey.put( k, 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 ) {
}
}
更新:
我进行了快速基准测试,虽然它并没有经过优化,但有一个明显的趋势:
"天真"的方法是循环遍历所有地图,并检查所有后续地图,以便每对只被检查一次。此外,我应用了Holger建议用于比较两个地图的方法。
"Map"方法就是我在这里发布的方法。
我的机器上对1000张地图进行测试,每张地图都有100个长度为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张地图,每张地图上的键数量和键长都不同(键越多,冲突越多)。
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
正如您所看到的,地图的数量对此产生的影响最大,其次是键的数量。