Kotlin中groupingBy{ it }.eachCount()操作的时间复杂度是多少？

结论先行：平均时间复杂度为O(N)（N代表原集合的元素个数），极端哈希冲突的最坏情况下可能达到O(N²)，但实际开发中几乎不会遇到这种场景。

结合你提供的源代码，具体分析如下：

1. groupingBy{ it }的时间开销 #

从groupingBy的源码可以看到，它只是创建了一个Grouping接口的实现对象，没有对原集合做任何遍历、拷贝或计算操作，仅仅封装了原集合的迭代器和key选择逻辑。因此这一步的时间复杂度是O(1)。

public inline fun <T, K> Array<out T>.groupingBy(crossinline keySelector: (T) -> K): Grouping<T, K> {
    return object : Grouping<T, K> {
        override fun sourceIterator(): Iterator<T> = this@groupingBy.iterator()
        override fun keyOf(element: T): K = keySelector(element)
    }
}

2. eachCount()的时间开销 #

eachCount()的核心逻辑是通过foldTo遍历原集合，结合哈希表完成计数统计：

public actual fun <T, K> Grouping<T, K>.eachCount(): Map<K, Int> =
    foldTo(destination = mutableMapOf(),
           initialValueSelector = { _, _ -> kotlin.jvm.internal.Ref.IntRef() },
           operation = { _, acc, _ -> acc.apply { element += 1 } })
    .mapValuesInPlace { it.value.element }

具体步骤的时间消耗：

• foldTo会遍历原集合的每一个元素，这一步的时间复杂度是O(N)；
• 对每个元素，执行key选择（这里是{it}，时间复杂度O(1)），然后在mutableMapOf()（默认实现为HashMap）中查找对应的key：HashMap的平均查找/插入时间为O(1)；
• 最后调用mapValuesInPlace遍历哈希表中的所有条目（数量为M，M是不同key的个数，且M≤N），将包装的IntRef转换为实际的Int值，这一步的时间复杂度是O(M)。

由于M≤N，O(N + M)等价于O(N)，这就是平均情况下的时间复杂度。

极端场景下，如果所有元素的key哈希值完全相同，HashMap会退化为链表，此时每次查找/插入的时间变为O(N)，整体时间复杂度会达到O(N²)。不过这种情况几乎不会出现——HashMap会自动扩容，当链表长度超过阈值时还会转为红黑树，将最坏情况优化为O(logN)。

内容的提问来源于stack exchange，提问作者Liker Of Programming