scala - Scala 中 Map.clear 的时间复杂度

Question

在Map上调用时，clear的时间复杂度在 map 的大小上是O(1)还是O(n)？

Answer 1

在不可变映射的情况下，没有 clear 因为它们是不可变的，但它们确实有 empty 返回该类型的新空映射。因为它只是一个对象创建，所以它是 O(1)。然而，可变映射是 O(n)，其中 n 基于底层数据结构，因为它们必须清除该数据结构。对于典型的可变 HashMap，这将是一个表。表格大小将介于 Map 过去的最大大小的 0.75 到 1.5 之间。