java - 有没有一种有效的方法来统计Java中大量字符串的出现次数？

Question

我必须计算 Java 中不同字符串的重复次数。这些字符串可能很大，来自多个数据源，并且有大量重复的字符串。

我需要从那些每小时频率最高的字符串中获取仅有的 20 个。

我考虑过统计每个字符串的出现次数，存储在一个巨大的HashMap中，用一个PriorityQueue来保持出现在最前面的字符串，但是这样也会消耗很多的内存。在每个小时的开始，旧的 HashMap 将被删除，一个新的 HashMap 将被创建以计算新小时的 20-top-frequent 字符串。这可能会导致 JVM 花费很长时间对该内存进行垃圾回收。

String#intern 能帮上一点忙，不过 HashMap 也是个内存问题，以后我也想把聚合数据存起来-堆，但不确定的不同字符串数量使得很难估计堆外内存和存储这些字符串的方式。有什么建议可以避免在堆外进行映射吗？

我对基数估计也很感兴趣，但似乎很难用它来计算每个字符串的复制次数。

Answer 1

HashMap 就是答案。它使用的内存比您想象的要少，因为映射包含对唯一字符串的引用，并且每个条目使用 O(1) 空间。没有必要存储每个字符串的一个副本，因此映射不会比(唯一的)字符串本身占用更多的内存。只需累加每个字符串出现的总次数，然后用它找出前 20 个。

如果内存不足，则必须在磁盘上实现映射，例如关系数据库或 NoSql 或其他。使用 map (或类似 map 的结构)的原则是要走的路。