What are these surprisingly large numbers you've seen? I thought that linear scan optimizations are typically reserved for pretty small maps, like dozens or maybe hundreds of elements.

Hundreds sounds about right, maybe up to a thousand.

But nobody expects that. Hashmap is supposed to be faster once you have, like, ten elements. That's what was promised to us.