Facebook开源C ++ F14哈希表

散列 被开发人员用来从一组相似的对象中快速识别出特定的，唯一的对象。例如，您的驾驶执照号码是一个散列，当您被拉到超过限速时，可以用来拉您的驾驶记录。在计算领域，Facebook上有成千上万的约翰·史密斯(John Smiths)，您可以做任何有助于加快找到自己的好友约翰·史密斯(John Smith)的事情，这是一件好事。现在，Facebook已经开源F14，14路探测哈希表内的愚蠢，它的开源C ++库。

从计算的早期开始，人们就一直在致力于完善哈希。结果是散列方法和表的数量几乎是无穷无尽。Facebook也面临这个问题。在其办公室内，Facebook开发人员创建了许多哈希表实现，每种实现都有自己的优缺点。使用F14，Facebook开发人员Nathan Bronson和Xiao Shi声称：“ F14哈希表在避免其病态的同时胜过了我们以前的专门实现。F14是一个很好的默认值–通常是一个不错的选择，而无论用例如何，它都是一个不错的选择。 ”

那不容易。开发人员在使用哈希表时面临的问题包括：

您是否保留条目的长期引用或指针?

您是否更关心CPU或内存?

您的钥匙有多大?

您的桌子有多大?

插入，搜索和迭代之间的操作混合是什么?

钥匙串是吗?

您多久擦除一次?

尽管如此，Facebook指出：

显然，当要考虑的因素太多时，很难做出最佳选择。使用F14，我们将该列表浓缩为一个简单的选择：如果您不保留对条目的长期引用，请从folly :: F14FastMap / Set开始。否则，从folly :: F14NodeMap / Set开始。

F14通过双哈希解决冲突(映射到相同数组索引的多个键)。在单个哈希表位置的块中最多存储14个键。高速矢量指令集 -x86_64 SSE2和 aarch64 NEON- 用于在块内进行过滤。通过一次筛选多达14个键，哈希表可以以很高的最大负载率进行操作，同时仍然保持探针链非常短。

通过允许程序的更多数据放入缓存中，此新代码还减少了内存浪费。它针对多种用例执行此操作，因为它支持针对不同场景的多种内存布局。这可以加速哈希表及其周围的代码。

这不仅仅是一个理论。Facebook每天都会使用F14，因为它运行良好。F14是一个很好的哈希选择，因为它可以提供CPU和RAM效率，并且在许多情况下都非常可靠。

F14可以让您的哈希相关程序更快地处理而冲突更少吗?只有一种方法可以找出答案，那就是自己尝试一下。代码在那里。祝好运。