如何在Java中使用HashMap更快地记录字符串出现频率？

Question

我在研究决策树，算法有一部分是从文件中记录字符串频率。此文件有 30,000 个案例和 1.68MB 大小。

我尝试使用 HashMap 来做到这一点，在我的主要算法代码中，替换方法运行大约 9 亿次，花了我大约 30 秒。我有什么办法可以更快地做到这一点？

下面是我的主要算法代码的简化代码，我花了大约10秒。

Map<String, Integer> classesCount = new HashMap<>();
int target = 900000000;

classesCount.put("a", 0);
classesCount.put("b", 0);

for(int i = 0; i < target; i++) {
    if (i % 2 == 0) {
        classesCount.replace("a", classesCount.get("a") + 1);
    }
    else {
        classesCount.replace("b", classesCount.get("b") + 1);
    }
}

为了让我的实际代码更清楚，我有一个 class 值，我在 main 方法中有一个值 class 的数组，这是值 class 如下.

public class Value<T extends Comparable<T>> implements Comparable<Value<T>> {
public T value;
public String result;

public Value(T value, String result) {
    this.value = value;
    this.result = result;
}

public int compareTo(Value<T> v) {
    return value.compareTo(v.value);
}

}

主要方法代码如下。假设 arrayOfValue 已经有很多元素并且每个值的结果只有“a”和“b”：

Map<String, Integer> classesCountA = new HashMap<>();
Map<String, Integer> classesCountB = new HashMap<>();
Value[] arrayOfValue = new Value[];
int splitIndex = 55;

classesCountA.put("a", 0);
classesCountA.put("b", 0);
classesCountB.put("a", 0);
classesCountB.put("b", 0);

for(int i = 0; i < arrayOfValue.length; i++) {
    if(i < splitIndex) {
        classesCountA.replace(arrayOfValue[i].result, classesCount.get(arrayOfValue[i].result) + 1);
    }
    else {
        classesCountB.replace(arrayOfValue[i].result, classesCount.get(arrayOfValue[i].result) + 1);
    }
}

Answer 1

您根本不需要替换地图的值。与键相比，映射值允许可变，因此您只需要一个可变结构来保存每个值的频率。

因此你可以这样做（简化）：

class Frequency {
  int value;
}

Map<String, Frequency> frequencyMap = new HashMap<>();

//iterate over the words
for(String word : words) {
  //get the mutable frequency for each word
  Frequency f = frequencyMap.get(word);

  //if the entry doesn't exist yet put it into the map
  //(you could use computeIfAbsent but it would be slower
  if( f == null ) {
     f = new Frequency();
     frequencyMap.put(word, f);
  }

  //just mutate the frequency - no need to change the map again
  f.value++;
}

在我的机器上，这比 replace(key, get(key) + 1) 方法快大约 5 倍。

如何在Java中使用HashMap更快地记录字符串出现频率？

How to record a string appear frequency faster using HashMap in Java?

java

file

hashmap

frequency