华原朋美种子HashTable是开发中常用的数据结构。本文从C++ STL中的HashTable讲起，分析其存在的性能问题，对比业界改进的实现方式。通过基准测试对比其实际性能表现，总结更优的实现版本。

　　查找key值时，需要遍历对应的链表，寻找值相同的key。链表中节点内存分布不连续，相邻节点处于同一cache line的概率很小，因此会产生较多的cpu cache miss，降低查询效率。

　　查找key时，以二次探测方式遍历hash值相等的pair，寻找值相等的key。hash值相同的pair存储在相邻内存位置处，内存局部性好，对cpu cache友好，可提高查询效率。

　　需要注意，absl::flat_hash_map在rehash时，会对pair进行move，因此pair的指针会失效，类似下述用法会访问非法内存地址。

　　为了解决上述pair指针失效问题，google absl::node_hash_map将pair存储在单独分配的节点中，在连续内存中存放指向这些节点的指针，其他设计与flat_hash_map相同，如图3所示。

　　下面对absl两种HashTable的核心逻辑源码进行探索（省略不相关部分的代码）：

　　基准测试结果如下（为了显示更清晰，将元素个数小于1024的和大于1024的分开展示）：

　　写操作：rehash友好，性能最好；读操作：内存不连续，cpu cache命中率较低，性能最差

　　写操作：性能略差于std::unordered_map；读操作：内存连续，cpu cache命中率较高，性能最好

　　特别声明：以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布，本平台仅提供信息存储服务。

　　专访中信证券首席经济学家明明：M2增速下行速率将逐步放缓，下半年不排除有降准的可能

　　“运动科技第一股”Keep登陆港交所，“90后”创始人王宁身价达30亿港元

　　重大进展！微软以690亿美元收购动视暴雪获批准！动视暴雪股价大涨10%

　　苹果和索尼为PS4/PS5用户提供Apple TV+免费试用，最长6个月

　　AMD 悄然推出 R7 5700 和 R3 5100 处理器，预计仅供 OEM 端