SwissMap：更小、更快的Golang哈希表

SwissMap，这是一个基于SwissTable的新Golang哈希表，比Golang的内置地图更快，使用的内存更少。我们将介绍这个新软件包的动机、设计和实施，并为您提供一些尝试的理由。这个博客是我们关于Go编程语言的深度潜水系列的一部分。过去的迭代包括关于并发、“继承”和与Golang管理流程的帖子。

mapmap

积极性

ChunkStoreChunkStore[20]byte

uint64uint32m log(n)mn

mapmap

SwissTable设计

std::unordered_mapmap

map

map

hash(key) mod size

将SwissTable移植到Golang

find()find()Get()Has()Put()Delete()

keyGet()Has()Delete()returnPut()matchEmpty

Golang对SSE指令和一般SIMD指令的支持很少。为了利用这些内在因素，SwissMap使用出色的Avo软件包使用相关的SSE指令生成汇编功能。你可以在这里找到代码生成方法。

map

comparablemap

最后，让我们看看SwissMap的内存消耗。我们构建SwissMap的最初动机是为我们的块索引获得恒定的时间查找性能，同时最大限度地降低额外的内存成本。SwissMap支持比内置地图（81.25%）更高的最大负载系数（87.5%），但仅凭这种差异并不能说明全部情况。使用Golang的pprof分析器，我们可以测量一系列密钥集大小的每张地图的实际负载系数。测量代码可以在这里找到。

在上面的图表中，我们看到SwissMap和内置地图之间明显不同的内存消耗模式。为了进行比较，我们包括了存储同一组数据的数组的内存消耗。内置地图的内存消耗遵循阶梯功能，因为它总是用两个桶的功率构造。原因来自经典的位黑客优化模式。

%%n

为了绕过余除法的缓慢，以及双大小大小的内存膨胀，我们对SwissMap的实现使用了不同的模量映射，首先由Daniel Lemire建议。这个想法看似简单：

uint322 ^ 36