That makes sense, thanks! For microbenchmarks, I try to remove any overheads during runtime by precomputing. That means fully populating the map (only hits) an

That makes sense, thanks! For microbenchmarks, I try to remove any overheads during runtime by precomputing. That means fully populating the map (only hits) and generating the distribution of keys. Then the threads start at a random index and increment for the key on each operation. This is a good example in Java, https://github.com/ben-manes/caffeine/blob/master/caffeine/src/jmh/java/com/github/benmanes/caffeine/cache/GetPutBenchmark.java https://github.com/ben-manes/caffeine/blob/master/caffeine/s... I would expect ~15-30ns per integer key lookup on a decent hashtable, w/o concurrency, at a modest size (few collisions). Using a concurrent map that supports lock-free reads doesn't have to be significantly different. Since hashtable design make such a big difference, it sounds like you've narrowed it down to that as a reasonable bottleneck. Thanks for investigating. https://tessil.github.io/2016/08/29/benchmark-hopscotch-map.html https://tessil.github.io/2016/08/29/benchmark-hopscotch-map....