实现相等性判断与哈希

#Original (English)

Source: https://www.mikeash.com/pyblog/friday-qa-2010-06-18-implementing-equality-and-hashing.html

Welcome back to a late edition of Friday Q&A. WWDC pushed the schedule back one week, but it’s finally time for another one. This week, I’m going to discuss the implementation of equality and hashing in Cocoa, a topic suggested by a reader.

Equality Object equality is a fundamental concept that gets used all over the place. In Cocoa, it’s implemented with the isEqual: method. Something as simple as [array indexOfObject:] will use it, so it’s important that your objects support it.

It’s so important that Cocoa actually gives us a default implementation of it on NSObject. The default implementation just compares pointers. In other words, an object is only equal to itself, and is never equal to another object. The implementation is functionally identical to:

1
    - (BOOL)isEqual: (id)other
2
    {
3
        return self == other;
4
    }

Implementing Custom Equality Sometimes you need a deeper implementation of equality. It’s common for objects, typically what you might refer to as a “value object”, to be distinct from another object but be logically equal to it. For example:

1
    // use mutable strings because that guarantees distinct objects
2
    NSMutableString *s1 = [NSMutableString stringWithString: @"Hello, world"];
3
    NSMutableString *s2 = [NSMutableString stringWithFormat: @"%@, %@", @"Hello", @"world"];
4
    BOOL equal = [s1 isEqual: s2]; // gives you YES!

1
    MyClass *c1 = ...;
2
    MyClass *c2 = ...;
3
    BOOL equal = [c1 isEqual: c2];

Testing for equality is fairly straightforward most of the time. Gather up the relevant properties of your class, and test them all for equality. If any of them are not equal, then return NO. Otherwise, return YES.

One subtle point with this is that the class of your object is an important property to test as well. It’s perfectly valid to test a MyClass for equality with an NSString, but that comparison should never return YES (unless MyClass is a subclass of NSString, of course).

A somewhat less subtle point is to ensure that you only test properties that are actually important to equality. Things like caches that do not influence your object’s externally-visible value should not be tested.

Let’s say your class looks like this:

1
    @interface MyClass : NSObject
2
    {
3
        int _length;
4
        char *_data;
5
        NSString *_name;
6
        NSMutableDictionary *_cache;
7
    }

1
    - (BOOL)isEqual: (id)other
2
    {
3
        return ([other isKindOfClass: [MyClass class]] &&
4
                [other length] == _length &&
5
                memcmp([other data], _data, _length) == 0 &&
6
                [[other name] isEqual: _name])
7
                // note: no comparison of _cache
8
    }

If you’re familiar with how hash tables work, you may want to skip the next paragraph or two.

A hash table is basically a big array with special indexing. Objects are placed into an array with an index that corresponds to their hash. The hash is essentially a pseudorandom number generated from the object’s properties. The idea is to make the index random enough to make it unlikely for two objects to have the same hash, but have it be fully reproducible. When an object is inserted, the hash is used to determine where it goes. When an object is looked up, its hash is used to determine where to look.

In more formal terms, the hash of an object is defined such that two objects have an identical hash if they are equal. Note that the reverse is not true, and can’t be: two objects can have an identical hash and not be equal. You want to try to avoid this as much as possible, because when two unequal objects have the same hash (called a collision) then the hash table has to take special measures to handle this, which is slow. However, it’s provably impossible to avoid it completely.

In Cocoa, hashing is implemented with the hash method, which has this signature:

1
    - (NSUInteger)hash;

1
    - (NSUInteger)hash
2
    {
3
        return (NSUInteger)self;
4
    }

Implementing Custom Hashing Because of the semantics of hash, if you override isEqual: then you must override hash. If you don’t, then you risk having two objects which are equal but which don’t have the same hash. If you use these objects in a dictionary, set, or something else which uses a hash table, then hilarity will ensue.

Because the definition of the object’s hash follows equality so closely, the implementation of hash likewise closely follows the implementation of isEqual:.

An exception to this is that there’s no need to include your object’s class in the definition of hash. That’s basically a safeguard in isEqual: to ensure the rest of the check makes sense when used with a different object. Your hash is likely to be very different from the hash of a different class simply by virtue of hashing different properties and using different math to combine them.

Generating Property Hashes Testing properties for equality is usually straightforward, but hashing them isn’t always. How you hash a property depends on what kind of object it is.

For a numeric property, the hash can simply be the numeric value.

For an object property, you can send the object the hash method, and use what it returns.

For data-like properties, you’ll want to use some sort of hash algorithm to generate the hash. You can use CRC32, or even something totally overkill like MD5. Another approach, somewhat less speedy but easy to use, is to wrap the data in an NSData and ask it for its hash, essentially offloading the work onto Cocoa. In the above example, you could compute the hash of _data like so:

1
    [[NSData dataWithBytes: _data length: _length] hash]

The easiest way is to simply add them together, or use the bitwise xor property. However, this can hurt your hash’s uniqueness, because these operations are symmetric, meaning that the separation between different properties gets lost. As an example, consider an object which contains a first and last name, with the following hash implementation:

1
    - (NSUInteger)hash
2
    {
3
        return [_firstName hash] ^ [_lastName hash];
4
    }

How to best combine hashes is a complicated subject without any single answer. However, any asymmetric way of combining the values is a good start. I like to use a bitwise rotation in addition to the xor to combine them:

1
    #define NSUINT_BIT (CHAR_BIT * sizeof(NSUInteger))
2
    #define NSUINTROTATE(val, howmuch) ((((NSUInteger)val) << howmuch) | (((NSUInteger)val) >> (NSUINT_BIT - howmuch)))
3

4
    - (NSUInteger)hash
5
    {
6
        return NSUINTROTATE([_firstName hash], NSUINT_BIT / 2) ^ [_lastName hash];
7
    }

1
    - (NSUInteger)hash
2
    {
3
        NSUInteger dataHash = [[NSData dataWithBytes: _data length: _length] hash];
4
        return NSUINTROTATE(dataHash, NSUINT_BIT / 2) ^ [_name hash];
5
    }

A Note on Subclassing You have to be careful when subclassing a class which implements custom equality and hashing. In particular, your subclass should not expose any new properties which equality is dependent upon. If it does, then it must not compare equal with any instances of the superclass.

To see why, consider a subclass of the first/last name class which includes a birthday, and includes that as part of its equality computation. It can’t include it when comparing equality with an instance of the superclass, though, so its equality method would look like this:

1
    - (BOOL)isEqual: (id)other
2
    {
3
        // if the superclass doesn't like it then we're not equal
4
        if(![super isEqual: other])
5
            return NO;
6

7
        // if it's not an instance of the subclass, then trust the superclass
8
        // it's equal there, so we consider it equal here
9
        if(![other isKindOfClass: [MySubClass class]])
10
            return YES;
11

12
        // it's an instance of the subclass, the superclass properties are equal
13
        // so check the added subclass property
14
        return [[other birthday] isEqual: _birthday];
15
    }

Now consider an instance of the subclass for “John Smith” with a birthday of 6/7/1994, which I’ll call C. C is not equal to B, which is what we expect. C is equal to A, also expected. But now there’s a problem. A equals both B and C, but B and C do not equal each other! This breaks the standard transitivity of the equality operator, and leads to extremely unexpected results.

In general this should not be a big problem. If your subclass adds properties which influence object equality, that’s probably an indication of a design problem in your hierarchy anyway. Rather than working around it with weird implementations of isEqual:, consider redesigning your class hierarchy.

A Note on Dictionaries If you want to use your object as a key in an NSDictionary, you need to implement hashing and equality, but you also need to implement -copyWithZone:. Techniques for doing that are beyond the scope of today’s post, but you should be aware that you need to go a little bit further in that case.

Conclusion Cocoa provides default implementations of equality and hashing which work for many objects, but if you want your objects to be considered equal even when they’re distinct objects in memory, you have to do a bit of extra work. Fortunately, it’s not difficult to do, and once you implement them, your class will work seamlessly with many Cocoa collection classes.

That’s it for this week. Check back in two more weeks for another edition. Until then, keep sending me your requests for topics. Friday Q&A is driven by user submissions, so if you have an idea for a topic to cover here, please send it in.