CODEWITHSUNDEEP
swifttime-complexity
davidchuyaya
davidchuyaya

Reputation: 4011

Swift Dictionary: remove time complexity

As stated by the official website, removing by key from a dictionary (or map, in other languages) is O(n) in Swift, making it a decently inefficient operation.

Why isn't it O(1) if put() and get() should be O(1) based on hashing?

enter image description here

Upvotes: 10

Views: 1929

Answers (1)

vxst
vxst

Reputation: 79

The source code of removeValue is:

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

While the uncheckedRemove's code is:

_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)

And the endureUnique is defined as:

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

While most operation will be run on O(1), the ensureUnique func may have O(n), if the item is not unique, the hashmap will do a copy(), which spends O(n) time complexity.

Upvotes: 1

Related Questions