Scala中如何高效移除列表内指定字段相同的重复元素？

原有实现的问题 #

你当前的实现时间复杂度为O(n²)，每次处理头结点时都需要对剩余列表做两次遍历过滤，同时列表拼接、contains判断都是线性复杂度，列表长度超过1万时性能会出现明显劣化。

最优实现方案 #

核心思路是将需要去重的5个字段组合为元组作为哈希键，通过哈希表记录已经出现过的键值，仅需遍历1次列表即可完成去重，时间复杂度降到O(n)。

Scala 2.13+ 版本（最简实现） #

直接使用内置的distinctBy方法，自动保留原列表顺序：

def removeDuplicates(originalList: List[MyObject]): List[MyObject] = 
  originalList.distinctBy(obj => (obj.name, obj.colour, obj.price, obj.height, obj.width))

兼容低版本Scala的实现 #

如果使用的Scala版本低于2.13，没有内置distinctBy方法，可以用可变哈希集合自行实现：

import scala.collection.mutable.HashSet

def removeDuplicates(originalList: List[MyObject]): List[MyObject] = {
  val existedKeys = HashSet[(String, String, Int, Int, Int)]()
  originalList.filter { obj =>
    val key = (obj.name, obj.colour, obj.price, obj.height, obj.width)
    val isNew = !existedKeys.contains(key)
    if (isNew) existedKeys.add(key)
    isNew
  }
}

实现说明 #

• 上述两种方案都严格保留原列表中每个重复分组第一条出现的元素，id、desc字段不会参与去重判断，完全符合需求
• 输入输出均为List[MyObject]类型，无需额外格式转换
• 哈希读写的时间复杂度为O(1)，整体性能比原有实现提升至少10倍以上，完全可支撑百万级长度的列表处理

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