objective-ccocoansdictionary

Hash value of NSDictionary

I ran into an issue, where I got the same hash value for different dictionaries. Maybe I'm doing something obvious wrong, but I thought, objects with different content (a.k.a. not equal objects) should have different hash values.

NSDictionary *dictA = @{ @"foo" : @YES };
NSDictionary *dictB = @{ @"foo" : @NO };

BOOL equal = [dictA hash] == [dictB hash];

NSAssert(!equal, @"Assuming, that different dictionaries have different hash values.");

Any thoughts?

Solution

  • There is no guarantee that two different objects will have different hash values.

    In the latest open-source version of CoreFoundation, the hash of a CFDictionary (which is equivalent to an NSDictionary) is defined as:

    static CFHashCode __CFDictionaryHash(CFTypeRef cf) {
    return __CFBasicHashHash((CFBasicHashRef)cf);
}

    and __CFBasicHashHash is defined as:

    __private_extern__ CFHashCode __CFBasicHashHash(CFTypeRef cf) {
    CFBasicHashRef ht = (CFBasicHashRef)cf;
    return CFBasicHashGetCount(ht);
}

    which is simply the number of entries stored in the collection. In the other words, both [dictA hash] and [dictB hash]'s hash value are 1, the number of entries in the dictionaries.

    While it is a very bad hash algorithm, CF didn't do anything wrong here. If you need to have a more accurate hash value, you can provide one yourself in an Obj-C category.