O(n) って書いてあったのってここ↓じゃありませんっけ？ https://github.com/apple/swift/blob/8afa9b1dcd2b535fb2b84ec87cafd36457d8eca6/stdlib/public/core/Dictionary.swift#L658 (edited)

swift - The Swift Programming Language