std::unordered_map与自定义Hashmap常量时间性能表现疑问

基准测试实现存在的问题 #

• 计时方式误差过大：你当前的实现对每一次插入、查询操作都单独调用high_resolution_clock计时，纳秒级计时本身的调用开销通常在十几到几十纳秒，和哈希表操作本身的耗时处于同一量级，计时开销会严重污染测试结果。正确的实现应该是批量执行N次目标操作，统计总耗时后再除以N得到单次平均耗时，避免反复启停计时器的开销。
• 测试用例过于理想化：你使用连续递增的整数作为测试key，针对整数的哈希函数通常直接返回原值，连续key几乎不会产生哈希冲突，完全无法模拟真实业务场景中随机key的冲突开销，测试结果不具备通用性。
• 未排除自动扩容的干扰：std::unordered_map和自定义HashMap都会在负载因子达到阈值时触发rehash，扩容时的全量数据拷贝开销会被分摊到相邻的插入操作统计中，不同实现的扩容策略（例如扩容倍数、预分配逻辑）差异也会导致结果失真。如果要统计纯插入的耗时，建议提前给两个容器预留足够的桶空间，排除rehash的影响。

关于缓存溢出预期的问题 #

你预期元素量超百万就会触发缓存溢出导致变慢，这个判断和实际硬件参数不符：目前主流消费级CPU的L3缓存普遍在16MB~64MB区间，一对size_t类型的键值对仅占16字节，100万条数据总大小才16MB，完全可以被L3缓存容纳，自然不会出现明显的耗时上涨。当数据量增长到超过L3缓存容量（比如千万条级别，总大小160MB以上）时，才会出现明显的缓存miss导致耗时上升。

另外你当前的查询操作都是访问刚刚插入的key，这些数据大概率还留在L1/L2缓存中，也会让测得的查询耗时远低于真实随机访问场景的水平。

内容的提问来源于stack exchange，提问作者Alex Peniz