0

我最近一直在为 C 中的一个项目制作自定义哈希映射。

我的哈希图目前是这样工作的：

  • 密钥通过Fowler–Noll–Vo 1a 散列函数进行散列以最小化冲突

  • 如果项目数超过桶数，则发出重新哈希，其中桶数加倍

  • 每个存储桶都包含一个必须在堆上分配的项目数组。这意味着每次创建哈希映射时，都会1 + numberOfBuckets完成堆分配。

我目前对这个哈希映射的一个问题是，创建它对于我的用例来说太慢了（我必须创建很多，在数百万的范围内）。

提高创建速度的一个简单解决方案是仅在需要时分配存储桶，但这实际上只会延迟分配，并且性能增益将是最小的。

还想到的一个想法是每个桶只有一个固定大小的项目数组。这样，如果操作正确，我只需要为每个映射分配一个大堆。但是，存储桶数组存在不可解决溢出的轻微风险，尤其是在较小的大小时。我计算过，从 32 个桶和 18 个项目的固定容量开始，这个概率大约是 10^(-19)（如果我的数学是正确的），并且桶越多它会变得更小。因此，发生该错误的可能性基本上可以忽略不计。

特别是本着面向数据设计的精神，我发现哈希映射的这个概念非常有趣，但我找不到任何关于忽略可忽略的错误风险是否是一种可以、现在或什至应该使用的编程实践一点也不。我真的很想知道这是否是任何地方的已知做法，以及是否可以在哈希映射之外的其他地方找到它。

4

2 回答 2

0

一如既往，答案是“视情况而定”。以尽可能最普遍的方式考虑这个问题，肯定存在真正的神圣用例，其中出于性能考虑，结果故意不正确（以分布式系统为例，最终一致性）。然而，对于任何使用此类系统的严肃系统，都需要对权衡（数学证明、市场分析等）进行深入分析，并对权衡有很好的理解和接受。

回到你的例子。为了简单起见，让我们稍微改变一下问题。假设如果发生错误，用户会收到一条错误消息，并且用户可以轻松地重新启动应用程序。这似乎相当合理。但这是您愿意为性能优势做出的可接受的权衡吗？只有你能回答。

现在你的真实用例很混乱，因为当数组溢出时，你的程序有未定义的行为。您无法知道程序将如何运行。您甚至无法知道程序何时以及是否错误。任何事情都有可能发生。该程序可以看起来工作，可以崩溃，可以开始给出奇怪的结果，真的什么。这是一个可以接受的权衡吗？再次，只有你可以回答。

但我的两分钱是你应该首先瞄准一个正确的程序。未定义的行为确实是您不希望在程序中出现的东西（除了错误行为之外，它也是一个安全问题）。肯定有加速分配的方法，例如通过使用池、处理碎片等。或者还有其他类型的哈希映射更适合特定用例。该主题研究得很好。我建议您探索这些，并强烈建议您不要故意将未定义的行为添加到您的程序中。

于 2021-08-30T03:07:11.487 回答
0

是否可以添加可忽略不计的错误风险以提高性能？（固定哈希映射桶大小）

当某些程序循环十亿次时，可以忽略不计的风险（意味着低概率）变得明显......不幸的是，经过多年的生产使用，这已成为许多错误的根源。这对通信协议设计产生了重大影响，如今，强大的验证工具用于测试任何微小但可能的违规行为。

只有在人类生命没有受到损害、影响很小以及修复错误的成本远高于错误可能产生的后果或损害的情况下，才能承认这一点。但有时仅仅确定影响可能代价高昂，因此建议不修复错误的情况非常小。

于 2021-09-03T09:55:18.887 回答