Swift Dictionary:删除时间复杂度

Question

正如官方网站所述,从字典(或地图,其他语言)中删除密钥是Swift中的O(n),使其成为一种效率低下的操作.

为什么不是O(1)如果put()和get()应该是基于散列的O(1)？

Answer 1

removeValue的源代码是：

let (bucket, found) = asNative.find(key)
guard found else { return nil }
let isUnique = isUniquelyReferenced()
return asNative.uncheckedRemove(at: bucket, isUnique: isUnique).value

而 uncheckedRemove 的代码是：

_internalInvariant(hashTable.isOccupied(bucket))
let rehashed = ensureUnique(isUnique: isUnique, capacity: capacity)
_internalInvariant(!rehashed)
let oldKey = (_keys + bucket.offset).move()
let oldValue = (_values + bucket.offset).move()
_delete(at: bucket)
return (oldKey, oldValue)

持久唯一性定义为：

if _fastPath(capacity <= self.capacity && isUnique) {
  return false
}
if isUnique {
  resize(capacity: capacity)
  return true
}
if capacity <= self.capacity {
  copy()
  return false
}
copyAndResize(capacity: capacity)
return true

虽然大多数操作将在 O(1) 上运行，但 EnsureUnique 函数可能具有 O(n)，如果该项目不唯一，则哈希图将执行 copy()，这会花费 O(n) 时间复杂度。