HashMap的性能

问题描述：

我必须处理约450万次的450个独特字符串。每个字符串都有唯一的整数标识有两种选择供我使用。HashMap的性能

有人可以建议哪些选项在处理方面会更有效率吗？

你的问题不清楚。请澄清每个选项的含义。标识符来自哪里？ “处理”5亿次是什么意思？来自稠密集合的标识符（即连续整数，比如说1-450）？如果不是，分布是什么样的。这里缺少大量信息，这些信息在决定使用哪种数据结构时非常重要。 – 2014-09-06 03:39:52

难道你不能创建一个有两个字段的类，'theString'和'theIdentifier'吗？ – DaoWen 2014-09-06 03:39:57

这可能与你做它的方式无关。 “查找”字符串和/或在查找后处理它们的开销可能大大超过字符串“识别”过程的开销。（如果不是，则需要解释更大的上下文。） – 2014-09-06 03:49:12

答

如果您编写的代码足够好，将字符串拆分应该更快。事实上，如果你已经有了int-id，我没有理由只发送字符串并保持一个映射。

加入HashMap需要每次散列传入的字符串。所以你基本上是比较哈希函数的性能和你写的附加代码的性能（预先计算可能有点棘手），并在接收端解析。

OTOH，只有450个字符串不是什么大不了的事情，如果你进入它，编写你自己的哈希算法/函数实际上是最优雅和高性能的。

分割字符串将创建两个新的字符串，然后这些字符串必须被GCed。引用HashMap会便宜得多。 – 2014-09-07 03:48:30

@HotLicks，阅读。“如果你写得够好的代码”，“你已经有了int-id”，“编写你自己的哈希算法/函数实际上是最优雅和高性能的”，最后，争辩说GC需要时间也是太很多讨论的话题。 – Kashyap 2014-09-11 15:35:35

您不能讨论Java性能并忽略GC。 – 2014-09-11 15:38:36

答

这一切都取决于字符串的大小等。

你可以做各种各样的事情。

您可以使用二进制搜索来获取列表中的索引，并且该索引是标识符。

假设字符串有一个OK分布，您可以只散列前两个字符，而不是整个字符串，这可能比二进制搜索更快。

如果第一个字符或前两个字符作为指向标识符的255或65K大型数组中的“完美索引”是唯一的，则可以使用它们。

此外，如果您的标识符是数字，最好预先计算，而不是随时随地转换它。文本 - >二进制文件实际上相当昂贵（二进制 - >文本更糟糕）。所以如果可能的话，避免这种情况可能会很好。

但是，你应该解决这个问题。每个1ms 1百万件，是20分钟的处理。在500米处，浪费的每纳秒浪费加起来超过8分钟的额外处理时间。你可能不在意，但只是证明在这些尺度上“每一点点都有帮助”。

所以，不要拿我们的话说，测试不同的东西，找到什么给你最好的结果，你的工作集，然后去。还要考虑过多的对象创建，并避免这种情况。通常情况下，我不会再考虑。对象创建速度很快，但是纳秒是纳秒。

如果您使用的是Java，并且您不需要Unicode（即您正在使用0-255范围内的单个字符），则根本不会使用字符串。我会使用原始字节。字符串基于Java字符，即UTF-16。 Java阅读器每次将UTF-8转换为UTF-16。单。时间。 5亿次。对！另外几个纳秒。 8纳秒可为您的处理增加一个小时。

所以，再看看所有的角落。或者，不要轻易写出来，把它烧起来，在周末运行它并完成它。

答

如果每个字符串都有一个唯一的标识符，那么只有在hashmaps的情况下检索是O（1）。

我不会建议第一种方法，因为您将每个字符串拆分为450 * 500m，除非您的订单是500m次的一个字符串，然后再转到下一个字符串。正如威尔所说，将数字附加到字符串，然后检索可能看起来很直接，但不建议。

所以如果你的数据是静态的（只有450个字符串），把它们放在一个HashMap中并对它进行实验。祝你好运。

答

使用HashMap<Integer, String>.分割字符串以获取标识符是一项昂贵的操作，因为它涉及到创建新的字符串。

答

我不认为任何人都会给你一个令人信服的“正确”答案，尤其是因为你没有提供计算的所有背景/属性。（例如，字符串的平均长度可能会产生很大的差异。）

所以我认为你最好的选择是编写一个基准...使用实际的字符串，你将要处理。

我也想找一种方法来提取和测试不需要分割字符串的“唯一整数标识符”。