Oct 30, 2024

This also creates some slight curvature even between 400k and 800k. The hash maps are not actually constant time unless they are full memory resident (paging increases with store size and insufficient memory), and there are fewer hash collisions with empty tables. So there will also be some slight amount of non-linearity as the chain builds, but query for a full chain will remain constant with sufficient RAM, regardless of the chain size (assuming proper hashmap bucketization).