Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is remove() faster than get() in HashMap?

I have written a benchmark for get and remove of HashMap as below:

@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));
  }
}

It produces this result:

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

As per the result, remove() is slight faster than get(). Even to remove an element, first it has to retrieve the element, doesn't it?

How can remove() be faster? Or am I missing something?

Update After using the latest JMH (1.11.3) and here is the result:

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
like image 787
RamValli Avatar asked Jan 20 '16 12:01

RamValli


People also ask

How fast is HashMap get?

Since HashMap stores its values in hash buckets, you can generally get between O(1) and O(N) for a lookup depending on the amount of hash collisions the map hash.

Which is faster than HashMap?

Performance The speed of HashSet is slower than that of HashMap. The reason that HashMap is faster than HashSet is that the HashMap uses the unique keys to access the values. It stores each value with a corresponding key and we can retrieve these values faster using keys during iteration.

Are Hashmaps slower than arrays?

According to a stackoverflow post, "HashMap uses an array underneath so it can never be faster than using an array correctly".

Is HashMap faster than if else?

compared the two version, even i used the input which will reach the last of the "if else" statements, the "if else" version is still 4-5 times faster than hashmap (hashmap is initialized at the beginning and cached).


1 Answers

So the trouble is, these benchmarks measure different things: get() from a populated map, and remove() from an (eventually) empty map. The comparison is meaningless, and you may throw the benchmark away.

You have to guarantee the operation is done against the same HashMap. Unfortunately, that requires either using @Setup(Invocation), which is bad on its own (read the Javadoc!), or sucking up the HashMap construction costs into the benchmark itself:

@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;
    }
}

You can be extra-careful and peel the map creation into a separate non-inlineable method: today's compilers do not optimize across calls. On my 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

No drastic difference. In fact, if you look into the generated code with -prof perfasm, it would yield a few quantifiable differences in there. Or, you can quickly characterize both workloads with -prof perfnorm.

Note that this case does not answer whether one method or the other better on real maps. The argument could be made for both: get does not modify map, and therefore does not cause memory stores, remove may help load factors so that next remove would get faster, etc. A single benchmark and a paragraph of text is far, far away from any fruitful discussion.

like image 58
Aleksey Shipilev Avatar answered Sep 24 '22 20:09

Aleksey Shipilev