Methods for implementing -hash on Cocoa mutable objects

Question

The documentation for -hash states that it should not change while the mutable object is stored in the collection, and similarly, the documentation for -isEqual: states that the -hash value must be the same for equal objects.

Given this, does anyone have any suggestions on the best way to implement -hash so that it matches these conditions, and yet it is actually calculated reasonably (i.e. does not return 0 )? Does anyone know how mutable versions of the classes provided by the infrastructure do this?

The easiest way to do this, of course, is simply to forget the first condition (without changing it) and just make sure that I have never accidentally mutated an object while it is in the collection, but I wonder if there is any solution that is more flexible.

EDIT: I am wondering if it is possible to maintain 2 contracts (where equal objects have equal hashes and hashes do not change while the object is in the collection) when I mutate the internal state of the object. My tendency is to say no if I am not doing something stupid, as always returning 0 for the hash, but that is why I ask this question.

Answer 1

An interesting question, but I think that you want it is logically impossible. Let's say you start with two objects: A and B. They are both different, and they start with different hash codes. You add both to the hash table. Now you want to mutate A, but you cannot change the hash code because it is already in the table. However, you can change A so that it equals .equals () B.

In this case, you have 2 options, none of which work:

• Change the hash code of A to be equal to B.hashcode, which violates the restriction of non-changing hash codes in the hash table.
• Do not change the hash code, in this case A.equals (B), but they do not have the same hash codes.

It seems to me that there is no possible way to do this without using a constant as a hash code.

Answer 2

My reading of the documentation is that the mutable value of an object for hash can (and probably should) change when it is mutated, but should not change if the object was not mutated. The part of the documentation referenced therefore says: "Do not mutate objects that are stored in the collection, because this will change their hash value."

For a direct quote from the NSObject documentation for hash :

If a volatile object is added to a collection that uses hash values ​​to determine the position of objects in the collection, the value returned by the hash method of the object should not change while the object is in the collection. Therefore, either the hash method should not rely on any of the information about the internal state of the objects, or you must make sure that the internal state information of the objects does not change while the object is in the collection.

(Emphasize mine.)

Answer 3

The question here is not how to satisfy both of these requirements, but rather the one you should meet with. Apple's documentation clearly states that:

a modified dictionary can be placed in a hash table, but you should not modify it while it is there.

In saying this, it seems more important that you satisfy the requirements of hashes of equality. An object hash should always be a way to check if an object is equal to another. If this is not the case, then this is not a true hash function.

To complete my answer, I will give an example of a good hash implementation. Let's say you write a -hash implementation in the collection you created. This collection stores an array of NSObjects as pointers. Since all NSObjects implement a hash function, you can use their hashes when calculating the hash collection:

 - (NSUInteger)hash { NSUInteger theHash = 0; for (NSObject * aPtr in self) { // fast enumeration theHash ^= [aPtr hash]; } return theHash; } 

Thus, two collection objects containing the same pointers (in the same order) will have the same hash.

Answer 4

Since you're already overriding -isEqual: for value-based comparisons, are you sure you really need to worry about -hash?

I can't guess what you need, of course, but if you want to make a cost-based comparison without deviating from the expected implementation of -isEqual: return YES only when the hashes are identical, the best approach might be mimick NSString -isEqualToString :, so for create your own method -isEqualToFoo: instead of using or overriding -isEqual :.

Answer 5

In Java, most mutable classes simply do not override Object.hashCode () , so the default implementation returns a value based on the address of the object and does not change. It can be exactly the same as with Objective C.