Swift set contains complexity

Question

Set has contains function which returns true if member exists in the set; otherwise, false.

and its complexity is O(1).

I want to know how its complexity is constant O(1) i.e. it does not depends on size

Here are the docs : https://developer.apple.com/documentation/swift/set/1540013-contains

Leong

Who says that the complexity is O(1)? It strongly depends on the distribution of the hash values of the elements. – Nutshell

@MartinR Who says? The documentation. If that's incorrect, a documentation bug report should be filed. – Kaitlinkaitlyn

docs link added in question – Leong

Disclaimer: it's at the bottom, under the code example. – Parang

@CharlesSrstka it's not O(1) on every iteration. It's O(1) on average, assuming that you have a good hash function. See discussion here and here, also this proposal for improvement to Swift hashValue. – Phototelegraphy

Dictionary.swift mentions that "Native storage is a hash table with open addressing and linear probing." and I think the same is true for Set. If all elements have the same hash value then the lookup degenerates to O(N). – Nutshell

@CodeDifferent I'm not taking a stand on whether it's O(1) or not. I'm pointing out that the documentation states it's O(1), and that if this is demonstrably untrue, then someone should file a report against the documentation. Because as long as the documentation claims the complexity is O(1), it's not unreasonable to assume the complexity will be O(1). – Kaitlinkaitlyn

Answer 1

It will use hash function to insert, search. Good hash function will lead to 0(1) time complexity. https://en.wikipedia.org/wiki/Hash_table

Bustup

Answer 2

If you see the header of Apple documentation. You should see Collection / Set.

So this is not an Array where contains method have a complexity of O(n).

A Set use hash table with low complexity to insert, search and delete a value.

I add 2 Apple documentations one for contains method from Set and other one for Array.

1. https://developer.apple.com/documentation/swift/set/contains(_:)
2. https://developer.apple.com/documentation/swift/array/contains(_:)

Gelatinoid