Once a hash table has outgrown all caches, it should have linear performance. It's just that caches accelerate it at sufficiently small sizes.