Swift如何不使用Set实现Collection指定属性唯一性校验扩展

你编写了一个Collection扩展，用于检查集合内元素的指定属性取值是否唯一，初始实现代码如下：

func isPropertyUnique <T: Hashable> (by: ((Element) -> (T))) -> Bool {
    var set = Set<T>()
    for value in self {
      set.insert(by(value))
    }
    return set.count > 1
}

方法调用方式：

items.isPropertyUnique { $0.propertyName }

该实现借助Set完成唯一性校验，你希望找到不使用Set的实现方案。

注：初始实现存在明显逻辑错误：判断唯一性的返回逻辑写反了。当集合所有元素的目标属性都唯一时方法应返回true，但原实现：

• 集合仅1个元素时，set.count == 1会错误返回false
• 集合存在重复属性但去重后数量大于1时（例如元素属性为[1,1,2]），会错误返回true

方案1：数组存储+存在性检查（适合小数据量场景） #

不需要Hashable约束，仅要求属性类型遵守Equatable协议。遍历过程中把已经遍历过的属性值存在数组里，每拿到一个新的属性值就检查数组里是否已经存在相同值，存在则直接判定为不唯一，提前终止遍历；遍历完所有元素都没发现重复则判定为唯一。

extension Collection {
    func isPropertyUnique<T: Equatable>(by keyExtractor: (Element) -> T) -> Bool {
        var encounteredValues: [T] = []
        for element in self {
            let value = keyExtractor(element)
            if encounteredValues.contains(value) {
                return false
            }
            encounteredValues.append(value)
        }
        return true
    }
}

该实现时间复杂度为O(n²)，因为数组的contains方法每次都要做线性查找，数据量小的时候性能足够，代码也最直白好懂。

方案2：排序+相邻元素比较（适合大数据量场景） #

不需要Hashable约束，仅要求属性类型遵守Comparable协议。先把所有元素的目标属性提取出来排序，排序后如果存在重复值，重复值一定是相邻位置，只需要遍历一次检查相邻元素是否相等即可得出结果。

extension Collection {
    func isPropertyUnique<T: Comparable>(by keyExtractor: (Element) -> T) -> Bool {
        let sortedValues = self.map(keyExtractor).sorted()
        guard sortedValues.count > 1 else { return true }
        for index in 1..<sortedValues.count {
            if sortedValues[index] == sortedValues[index - 1] {
                return false
            }
        }
        return true
    }
}

该实现时间复杂度为O(n log n)，耗时主要在排序步骤，数据量较大时性能远高于方案1。

你之前觉得用Set实现是“取巧”其实是个常见的误解：基于哈希表实现的Set做存在性检查的平均时间复杂度是O(1)，整体实现平均时间复杂度为O(n)，是通用场景下性能最优的实现方式，唯一要求是属性遵守Hashable协议，而Swift标准库中绝大多数常用类型（Int、String、Bool等）都默认遵守该协议，实际开发中完全可以优先使用。
另外上面给出的两个方案都做了提前终止优化，比你最初全量遍历插入Set再比较count的实现性能更好——最初的实现无论有没有重复值都会遍历完整个集合，而提前终止的实现遇到第一个重复值就会返回结果，在重复值出现较早的场景下性能优势非常明显。

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