https://github.com/apple/swift-evolution/blob/master/proposals/0154-dictionary-key-and-value-collections.md#proposed-solution Keys 実装目的の最初に挙げられているくらいなので、O(1) だと思うんですが、実装追えてないです。

swift-evolution - This maintains proposals for changes and user-visible enhancements to the Swift Programming Language.