How can a set offer better search performance than an array While reading the following tutorial on iOS development Working with Foundation (section on Sets near the bottom), I came across the following statement: "Because sets don’t maintain order, they offer faster performance than arrays do when it comes to testing for membership."

The author doesn't mention the underlying data structure and as it stands, I don't see how the second part of this statement can be inferred from the first.

If the NSSet class is implemented using a hash table, I agree that it will have faster lookup performance than an NSArray class but in principle both classes could be implemented using arrays, in which case both would have a lookup performance of O(n).

Am I missing something or is this just an incomplete statement?
I think the key is that NSSets aren't required to "maintain order," meaning that you cannot access elements with an index, nor can you extract elements in any particular order.  Because NSSets don't offer those kinds of accesses the implementation is free to use hashing, trees or anything else that gives speedier membership checks.