CODEWITHSUNDEEP
iosobjective-csearchnsstring
hpique
hpique

Reputation: 120324

Efficiently search for NSString in a set

Consider a set of thousands of NSString objects, in memory.

What is the most efficient way to search for a particular NSString in the set? Would using NSDictionary suffice? Or is it guaranteed that NSSet's search is O(1) (couldn't find any documentation that says so)?

And would the same strategy apply to NSData objects?

Upvotes: 5

Views: 152

Answers (2)

dreamlax
dreamlax

Reputation: 95335

This page shows the following note about sets:

Note: If the objects in the set have a good hash function, accessing an element, setting an element, and removing an element all take constant time. With a poor hash function (one that causes frequent hash collisions), these operations take up to linear time. Classes such as NSString that are part of Foundation have a good hash function.

So for NSString you could expect constant time based on the above.

Upvotes: 4

svena
svena

Reputation: 2779

NSSet uses hash table in its implementation and tests for equality between all elements that are in hash collision. So performance is directly tied to the hash efficiency of its elements.

Upvotes: 0

Related Questions