Kotlin中如何高效统计SortedMap的重复值数量，降低内存开销

你当前的实现除了HashSet的内存开销外，还有一处不必要的内存浪费：filter操作会生成一个临时List存储所有符合条件的条目，百万级数据下这部分开销完全可以避免，直接使用count的谓词判断即可，优化后代码如下：

val uniqueValueSet = hashSetOf<String>()
val numDuplicates = cache.count { !uniqueValueSet.add(it.value) }

这行改动可以直接省掉和重复值数量相等的内存占用，不需要额外逻辑成本。

如果需要100%准确的统计结果，可根据你的场景二选一：

• 场景：值重复率较高
  可以用频率统计字典替代HashSet，最终通过频率计算重复数，内存占用和HashSet方案一致，但CPU开销更低：

  var numDuplicates = 0
  val freqMap = hashMapOf<String, Int>()
  cache.values.forEach { value ->
      val count = freqMap.getOrDefault(value, 0)
      if (count >= 1) {
          numDuplicates++
      }
      freqMap[value] = count + 1
  }
  

• 场景：内存极端受限，允许少量CPU和IO开销
  利用排序后重复值连续的特性，先将所有值导出做外部归并排序，再遍历排序后的结果统计重复数，整个过程只需要占用几MB的排序缓冲区内存，不需要存储全量不同值，适合内存不足的离线统计场景。

如果业务允许2%以内的统计误差，推荐使用HyperLogLog算法实现，仅需要12KB的固定内存即可完成数百万甚至数十亿级数据的不同值计数，最终通过「总条目数 - 不同值数量」得到重复值总数，内存开销几乎可以忽略。
Kotlin/Java环境可以直接使用Guava提供的HyperLogLog实现，示例逻辑如下：

val hll = HyperLogLog(10) // 精度参数，数值越大误差越小，内存占用越高
cache.values.forEach { hll.offer(it) }
val approxUniqueCount = hll.cardinality()
val approxDuplicates = cache.size - approxUniqueCount

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