在HashMap中，remove（）比get（）更快吗？

我已经写了基准get和HashMap如下remove：在HashMap中，remove（）比get（）更快吗？

@BenchmarkMode(Mode.AverageTime) 
@OutputTimeUnit(TimeUnit.NANOSECONDS) 
public class HashMapBenchmark { 

    @State(Scope.Benchmark) 
    public static class Mystate { 
     HashMap<String,String> hashmapVar = new HashMap<String,String>(); 
     String key0 = "bye"; 

     @Setup(Level.Iteration) 
     public void setup(){ 
      hashmapVar.put(key0,"bubye"); 
     } 
    } 

    @Benchmark 
    public void hashmapGet(Mystate state ,Blackhole bh) { 
     bh.consume(state.hashmapVar.get(state.key0)); 
    } 

    @Benchmark 
    public void hashmapRemove(Mystate state ,Blackhole bh) { 
     bh.consume(state.hashmapVar.remove(state.key0)); 
    } 
}

它产生如下结果：

Benchmark        Mode Samples Score Score error Units 
c.b.HashMapBenchmark.hashmapGet  avgt  60 6.348  0.320 ns/op 
c.b.HashMapBenchmark.hashmapRemove avgt  60 5.180  0.074 ns/op

作为每结果，remove()比get()稍快。即使删除一个元素，首先它必须检索元素，不是吗？

那么remove()怎么快？或者我错过了什么？

更新采用了最新的江铃控股有限公司（1.11.3）和下面是结果后：

Benchmark         Mode Cnt Score Error Units 
HashMapBenchmark.hashmapGet    avgt 60 9.713 ± 0.277 ns/op 
HashMapBenchmark.hashmapRemove   avgt 60 7.677 ± 0.166 ns/op

来源

2016-01-20 Ram

您的样本量太小，甚至没有意义。对于这种“轻量级”操作，通常应该在计算平均值之前进行5-10秒的采样和采样。 –

@Norwæ他正在使用jmh执行60次运行，这应该足够好并且还会给出统计错误。 – assylias

你使用的是什么java版本和jmh版本？ – AdamSkywalker

所以问题是，这些基准测量不同的东西：get()从一个人口稠密的地图，和remove()从（最终）空地图。比较是没有意义的，你可以把基准扔掉。

您必须保证操作是针对相同的HashMap完成的。不幸的是，要求要么使用@Setup(Invocation)，这是对自己的坏（阅读Javadoc中！），或吸干HashMap建设成本为基准本身：

@BenchmarkMode(Mode.AverageTime) 
@OutputTimeUnit(TimeUnit.NANOSECONDS) 
public class HashMapBenchmark { 

    @Benchmark 
    public String get() { 
     HashMap<String, String> hm = createMap(); 
     return hm.get("bye"); 
    } 

    @Benchmark 
    public String remove() { 
     HashMap<String, String> hm = createMap(); 
     return hm.remove("bye"); 
    } 

    // extra protection from optimization 
    @CompilerControl(CompilerControl.Mode.DONT_INLINE) 
    private HashMap<String, String> createMap() { 
     HashMap<String, String> hm = new HashMap<>(); 
     hm.put("bye", "bye"); 
     return hm; 
    } 
}

你可以额外小心，剥离地图创建成独立的不可内联的方法：今天的编译器不会跨通话进行优化。在我的i7-4790K上，4.0 GHz，Linux x86_64，JDK 8u66：

Benchmark    Mode Cnt Score Error Units 
HashMapBenchmark.get  avgt 15 24.343 ± 0.351 ns/op 
HashMapBenchmark.remove avgt 15 24.611 ± 0.369 ns/op

没有太大的区别。事实上，如果您使用-prof perfasm来查看生成的代码，那么在那里会产生一些可量化的差异。或者，您可以使用-prof perfnorm快速表征这两种工作负载。

请注意，这种情况确实是而不是回答在实际地图上是否有一种方法更好。可以这样做的理由是：get不修改地图，因此不会导致内存存储，remove可能有助于加载因子，以便下一个remove会变得更快等。单个基准和一段文本远远地远来自任何富有成果的讨论。

来源

2016-01-20 21:52:49

但是为什么内联映射创建不好，如果两种方法都一样？仅仅因为它不会立即内联，只是在一些热身之后？ – AdamSkywalker

好吧，这本身并没有坏处，但我可以想象世界末日场景，其中集合实现足够简单，编译器可以折叠背靠背'put'和'get' /'remove'的重要部分。这是一个额外的保护水平 - 如果你对每个案例研究生成的代码非常懒惰。 –

当你第一次迭代之后调用remove()没有什么可以删除，你不必在任何地方复制结果（或者参考结果）（它只是简单地返回null）。但是当调用get()时，你必须在某处复制或存储返回的引用（未查找实现Blackhole），这需要分配内存，因此比仅仅返回null更昂贵，因为它可能会在几次迭代后被JIT优化。

来源

2016-01-20 13:18:23 JiriS

性能分析不是一个可以无需任何证据就谈论JIT优化的地方 – AdamSkywalker

误解是关于状态的Level.Iteration设置。使用的正确级别是“Invocation”，除非基准太短，所以在这里并不适用。 – biziclop

@AdamSkywalker但主要的事情是真的，在第一次调用remove（）后，地图是空的。您甚至不需要JIT来加快速度，因为循环遍历桶中的内容将被完全跳过。 – biziclop

在HashMap中，remove（）比get（）更快吗？

回答

相关问题