Why does [NSSet containsObject] fail for SKNode me

Question

Two objects are added to an NSSet, but when I check membership, I can't find one of them.

The test code below worked fine in iOS7 but fails in iOS8.

SKNode *changingNode = [SKNode node];
SKNode *unchangingNode = [SKNode node];
NSSet *nodes = [NSSet setWithObjects:unchangingNode, changingNode, nil];

changingNode.position = CGPointMake(1.0f, 1.0f);

if ([nodes containsObject:changingNode]) {
  printf("found node\n");
} else {
  printf("could not find node\n");
}

Output:

could not find node

What happened between iOS7 and iOS8, and how can I fix it?

Answer 1

SKNode's implementations of isEqual and hash have changed in iOS8 to include data members of the object (and not just the memory address of the object).

The Apple documentation for collections warns about this exact situation:

If mutable objects are stored in a set, either the hash method of the objects shouldn’t depend on the internal state of the mutable objects or the mutable objects shouldn’t be modified while they’re in the set. For example, a mutable dictionary can be put in a set, but you must not change it while it is in there.

And, more directly, here:

Storing mutable objects in collection objects can cause problems. Certain collections can become invalid or even corrupt if objects they contain mutate because, by mutating, these objects can affect the way they are placed in the collection.

The general situation is described in other questions in detail. However, I'll repeat the explanation for the SKNode example, hoping it helps those who discovered this problem with the upgrade to iOS8.

In the example, the SKNode object changingNode is inserted into the NSSet (implemented using a hash table). The hash value of the object is computed, and it is assigned a bucket in the hash table: let's say bucket 1.

SKNode *changingNode = [SKNode node];
SKNode *unchangingNode = [SKNode node];
printf("pointer %lx hash %lu\n", (uintptr_t)changingNode, (unsigned long)changingNode.hash);
NSSet *nodes = [NSSet setWithObjects:unchangingNode, changingNode, nil];

Output:

pointer 790756a0 hash 838599421

Then changingNode is modified. The modification results in a change to the object's hash value. (In iOS7, changing the object like this did not change its hash value.)

changingNode.position = CGPointMake(1.0f, 1.0f);
printf("pointer %lx hash %lu\n", (uintptr_t)changingNode, (unsigned long)changingNode.hash);

Output:

pointer 790756a0 hash 3025143289

Now when containsObject is called, the computed hash value is (likely) assigned to a different bucket: say bucket 2. All objects in bucket 2 are compared to the test object using isEqual, but of course all return NO.

In a real-life example, the modification to changedObject probably happens elsewhere. If you try to debug at the location of the containsObject call, you might be confused to find that the collection contains an object with the exact same address and hash value as the lookup object, and yet the lookup fails.

Alternate Implementations (each with their own set of problems)

• Only use unchanging objects in collections.

• Only put objects in collections when you have complete control, now and forever, over their implementations of isEqual and hash.

• Track a set of (non-retained) pointers rather than a set of objects: [NSSet setWithObject:[NSValue valueWithPointer:(void *)changingNode]]

• Use a different collection. For instance, NSArray will be affected by changes to isEqual but won't be affected by changes to hash. (Of course, if you try to keep the array sorted for quicker lookup, you'll have similar problems.)

• Often this is the best alternative for my real-world situations: Use an NSDictionary where the key is the [NSValue valueWithPointer] and the object is the retained pointer. This gives me: quick lookup of an object that will be valid even if the object changes; quick deletion; and retention of objects put in the collection.

• Similar to the last, with different semantics and some other useful options: Use an NSMapTable with option NSMapTableObjectPointerPersonality so that key objects are treated as pointers for hashing and equality.