计算出现次数的最有效方法是什么？

Question

我有一个字节数组（原始类型），它们可能具有随机值。我试图以最高效/最快的方式计算数组中它们的出现次数。目前我正在使用：

HashMap<Byte, Integer> dataCount = new HashMap<>();
for (byte b : data) dataCount.put(b, dataCount.getOrDefault(b, 0) + 1);

这个一行代码处理长度为24883200字节的byte[]需要大约500毫秒。 使用常规的for循环至少需要600毫秒。

我考虑构建一个Set(因为它们只包含每个元素中的一个)，然后使用Collections.frequency()将其添加到HashMap中，但是从基元构造Set的方法需要几个其他调用，所以我猜它不会那么快。

完成每个项出现次数计数的最快方法是什么？

我正在使用Java 8，如果可能，我希望避免使用Apache Commons。

- user_4685247

Answer 1

如果只是字节，使用数组而不是map。你需要使用掩码处理字节的有符号性质，但这并不是什么大问题。

int[] counts = new int[256];
for (byte b : data) {
   counts[b & 0xFF]++;
}

数组是如此紧凑和高效，以至于当你可以使用它们时，它们几乎不可能被击败。

- Louis Wasserman

---

这个方案是行得通的，但它也会为那些不存在的值分配内存。后面我还需要使用这些值的HashMap，当然不包括0值。 - user_4685247

看起来增加的这么多，我可以负担得起创建一个稍后复制到HashMap的副本！ - user_4685247

如果计数较大且除了这些不同的字节值外，其余236个值都为0，那么使用int [256]比使用HashMap更好，因为int []比HashMap更加紧凑，可以省下用于存储未出现值的内存。相比之下，如果有大约20个不同的字节，则int[256]更佳。 - Louis Wasserman

Answer 2

如果您确切知道需要跟踪的计数数量，我建议使用数组而不是HashMap：

int[] counts = new int[256];
for (byte b : data) {
    counts[b & 0xff]++;
}

这样做的好处是：

• 您无需对键或值进行任何装箱操作
• 不需要进行哈希码检查、相等性检查等操作
• 它尽可能地节省内存

请注意，& 0xff 用于获取范围在 [0, 255] 而非 [-128, 127] 的值，因此适合用作数组索引。

- Jon Skeet

---

我以前从未见过两个完全一样的代码同时出现。 - Paul Boddington

@pbabcdefp：Louis的代码中有大写十六进制数字，而且空格是三个而不是四个 :) - Jon Skeet

他的先到了，所以我接受了它，因为没有太大的区别 :) - user_4685247