1. You should use JMH to handle warmup, jit, timings, averaging of runs, etc. You might enjoy the following talks on the subject, though I am sure there are other gems out there.
- Performance Anxiety: https://wiki.jvmlangsummit.com/images/1/1d/PerformanceAnxiet...
- Benchmarking for Good: https://www.youtube.com/watch?v=SKPdqgD1I2U
- (The Art of) (Java) Benchmarking: https://shipilev.net/talks/j1-Oct2011-21682-benchmarking.pdf
- A Crash Course in Modern Hardware: https://www.youtube.com/watch?v=OFgxAFdxYAQ
- How NOT to Write a Microbenchmark https://www.slideshare.net/slideshow/2002-microbenchmarks/28...
- Anatomy of a flawed microbenchmark https://web.archive.org/web/20110513090823/http://www.ibm.co...
2. An uncontended lock is basically free, as you noticed.
3. Guava does implement the Map interface via asMap(). It also have a concurrencyLevel to adjust its performance. It is based on Java 5's CHM.
4. Caffeine is a Guava Cache rewrite based on Java 8's CHM rewrite, plus many learnings. You might look at its benchmarks for ideas: https://github.com/ben-manes/caffeine/wiki/Benchmarks
5. Data structures are surprisingly tricky. For example see this analysis showing an accidental misunderstanding degrading an LRU to O(n) eviction. https://gist.github.com/ben-manes/6312727adfa2235cb7c5e25cae...
6. It is important to remember that the goal of a benchmark is never which is faster or by how much. It is to ask (a) is it fast enough? (b) might I reach a point where it will not be? and (c) does it degrade unexpectedly? == This is to say the winner is of little interest, once all the choices are good enough then it is about usability, features, documentation, friendliness, and so on.