bgu*_*uiz 56 java iteration performance hashmap map
给定以下代码,使用两种替代方法来迭代它,
这两种方法之间是否有任何性能差异？
Map<String, Integer> map = new HashMap<String, Integer>();
//populate map
//alt. #1
for (String key : map.keySet())
{
Integer value = map.get(key);
//use key and value
}
//alt. #2
for (Map.Entry<String, Integer> entry : map.entrySet())
{
String key = entry.getKey();
Integer value = entry.getValue();
//use key and value
}
我倾向于认为这alt. #2是迭代整个过程的更有效方法map(但我可能是错的)
Amo*_*are 60
您的第二个选项肯定更有效,因为您在第一个选项中只进行一次查找而不是n次.
但是,没有什么比在可能的情况下尝试更好.所以这里 -
(不完美,但足以验证假设,无论如何都在我的机器上)
public static void main(String args[]) {
Map<String, Integer> map = new HashMap<String, Integer>();
// populate map
int mapSize = 500000;
int strLength = 5;
for(int i=0;i<mapSize;i++)
map.put(RandomStringUtils.random(strLength), RandomUtils.nextInt());
long start = System.currentTimeMillis();
// alt. #1
for (String key : map.keySet()) {
Integer value = map.get(key);
// use key and value
}
System.out.println("Alt #1 took "+(System.currentTimeMillis()-start)+" ms");
start = System.currentTimeMillis();
// alt. #2
for (Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
Integer value = entry.getValue();
// use key and value
}
System.out.println("Alt #2 took "+(System.currentTimeMillis()-start)+" ms");
}
结果(一些有趣的)
使用int mapSize = 5000; int strLength = 5;
Alt#1需要26 ms
Alt#2需要20 ms
使用int mapSize = 50000; int strLength = 5;
Alt#1花了32 ms
Alt#2需要20 ms
使用int mapSize = 50000; int strLength = 50;
Alt#1需要22 ms
Alt#2需要21 ms
使用int mapSize = 50000; int strLength = 500;
Alt#1需要28 ms
Alt#2需要23 ms
使用int mapSize = 500000; int strLength = 5;
Alt#1花了92毫秒
Alt#2花了57毫秒
...等等
SLa*_*aks 10
第二个片段会稍快一些,因为它不需要重新查找键.
所有HashMap迭代器都调用该nextEntry方法,该方法返回一个Entry<K,V>.
您的第一个片段会丢弃条目(in KeyIterator)中的值,然后在字典中再次查找它.
您的第二个代码段直接使用键和值(来自EntryIterator)
(这两个keySet()和entrySet()是便宜的电话)
地图:
Map<String, Integer> map = new HashMap<String, Integer>();
除了2个选项,还有一个选项.
1)中的keySet() -如果你需要使用用它仅在按键
for ( String k : map.keySet() ) {
...
}
2)entrySet() - 如果你需要:键和值,则使用它
for ( Map.Entry<String, Integer> entry : map.entrySet() ) {
String k = entry.getKey();
Integer v = entry.getValue();
...
}
3)值() -如果你需要使用它只有在值
for ( Integer v : map.values() ) {
...
}
最有效的方法（根据我的基准）是使用HashMap.forEach()Java 8 或HashMap.entrySet().forEach().
JMH 基准：
@Param({"50", "500", "5000", "50000", "500000"})
int limit;
HashMap<String, Integer> m = new HashMap<>();
public Test() {
}
@Setup(Level.Trial)
public void setup(){
m = new HashMap<>(m);
for(int i = 0; i < limit; i++){
m.put(i + "", i);
}
}
int i;
@Benchmark
public int forEach(Blackhole b){
i = 0;
m.forEach((k, v) -> { i += k.length() + v; });
return i;
}
@Benchmark
public int keys(Blackhole b){
i = 0;
for(String key : m.keySet()){ i += key.length() + m.get(key); }
return i;
}
@Benchmark
public int entries(Blackhole b){
i = 0;
for (Map.Entry<String, Integer> entry : m.entrySet()){ i += entry.getKey().length() + entry.getValue(); }
return i;
}
@Benchmark
public int keysForEach(Blackhole b){
i = 0;
m.keySet().forEach(key -> { i += key.length() + m.get(key); });
return i;
}
@Benchmark
public int entriesForEach(Blackhole b){
i = 0;
m.entrySet().forEach(entry -> { i += entry.getKey().length() + entry.getValue(); });
return i;
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder()
.include(Test.class.getSimpleName())
.forks(1)
.warmupIterations(25)
.measurementIterations(25)
.measurementTime(TimeValue.milliseconds(1000))
.warmupTime(TimeValue.milliseconds(1000))
.timeUnit(TimeUnit.MICROSECONDS)
.mode(Mode.AverageTime)
.build();
new Runner(opt).run();
}
结果：
Benchmark (limit) Mode Cnt Score Error Units
Test.entries 50 avgt 25 0.282 ± 0.037 us/op
Test.entries 500 avgt 25 2.792 ± 0.080 us/op
Test.entries 5000 avgt 25 29.986 ± 0.256 us/op
Test.entries 50000 avgt 25 1070.218 ± 5.230 us/op
Test.entries 500000 avgt 25 8625.096 ± 24.621 us/op
Test.entriesForEach 50 avgt 25 0.261 ± 0.008 us/op
Test.entriesForEach 500 avgt 25 2.891 ± 0.007 us/op
Test.entriesForEach 5000 avgt 25 31.667 ± 1.404 us/op
Test.entriesForEach 50000 avgt 25 664.416 ± 6.149 us/op
Test.entriesForEach 500000 avgt 25 5337.642 ± 91.186 us/op
Test.forEach 50 avgt 25 0.286 ± 0.001 us/op
Test.forEach 500 avgt 25 2.847 ± 0.009 us/op
Test.forEach 5000 avgt 25 30.923 ± 0.140 us/op
Test.forEach 50000 avgt 25 670.322 ± 7.532 us/op
Test.forEach 500000 avgt 25 5450.093 ± 62.384 us/op
Test.keys 50 avgt 25 0.453 ± 0.003 us/op
Test.keys 500 avgt 25 5.045 ± 0.060 us/op
Test.keys 5000 avgt 25 58.485 ± 3.687 us/op
Test.keys 50000 avgt 25 1504.207 ± 87.955 us/op
Test.keys 500000 avgt 25 10452.425 ± 28.641 us/op
Test.keysForEach 50 avgt 25 0.567 ± 0.025 us/op
Test.keysForEach 500 avgt 25 5.743 ± 0.054 us/op
Test.keysForEach 5000 avgt 25 61.234 ± 0.171 us/op
Test.keysForEach 50000 avgt 25 1142.416 ± 3.494 us/op
Test.keysForEach 500000 avgt 25 8622.734 ± 40.842 us/op
正如你所看到的，HashMap.forEach并HashMap.entrySet().forEach()执行最适合大地图，并通过for循环被连接在entrySet()小地图以获得最佳性能。
键方法较慢的原因可能是因为它们必须为每个条目再次查找值，而其他方法只需要读取对象中的字段即可获取值。我希望迭代器方法变慢的原因是它们正在执行外部迭代，这需要对每个元素进行两次方法调用 (hasNext和next) 并将迭代状态存储在迭代器对象中，而内部迭代则forEach需要只有一种方法调用accept.
您应该使用目标数据在目标硬件上进行分析，并在循环中执行目标操作以获得更准确的结果。