基于字符频率排序的CustomComparator的HashMap填充时机问题

结论 #

HashMap仅在CustomComparator实例初始化时填充一次，后续所有排序过程中的比较操作都会直接复用已统计好的频率值，不会重新填充。

原理说明 #

• 你在调用Arrays.sort(array,new CustomComparator(s))时，才会执行CustomComparator的构造方法：

  public CustomComparator(String s) {
      this.map = new HashMap<>();
      for(char ch : s.toCharArray()) {
          map.put(ch,map.getOrDefault(ch,0)+1);
      }
  }
  

  构造方法仅在实例创建阶段执行唯一一次，完成所有字符的频率统计填充到HashMap中。
• 排序过程中Arrays.sort只会反复调用你重写的compare方法：

  @Override
  public int compare(Character ch1,Character ch2) {
      return map.get(ch2) - map.get(ch1);
  }
  

  这个方法里只有从已有的HashMap中读取频率做差值的逻辑，没有任何修改、重新生成HashMap的代码，所以不会重新统计频率。

额外说明 #

这种实现是性能最优的写法：如果把频率统计逻辑写到compare方法里，每次比较都重新遍历字符串统计的话，排序的时间复杂度会飙升到O(n² log n)，你现在的实现仅会做一次O(n)的频率统计，排序整体复杂度是O(n log n)，符合设计预期。

内容的提问来源于stack exchange，提问作者Sukha_Coder02