The hash value of NSDictionary

Question

I ran into a problem where I got the same hash value for different dictionaries. Maybe I'm doing something obvious wrong, but I thought that objects with different content (aka 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?

Answer 1

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

In the latest open source version of CoreFoundation, the CFDictionary hash (which is equivalent to 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 records stored in the collection. In other words, both the hash value [dictA hash] and [dictB hash] 1 , the number of entries in the dictionaries.

While this is a very bad hashing algorithm, CF has done nothing wrong here. If you need to get a more accurate hash value, you can provide it yourself in the Obj-C category.

Answer 2

With a dictionary with integers, strings, etc. I would use dict.description.hash as a quick code.

Answer 3

Solution based on igor-kulagin's answer, which is independent of the order:

 @implementation NSDictionary (Extensions) - (NSUInteger) hash { NSUInteger prime = 31; NSUInteger result = 1; for (NSObject *key in [[self allKeys] sortedArrayUsingSelector:@selector(compare:)]) { result = prime * result + [key hash]; result = prime * result + [self[key] hash]; } return result; } @end 

However, there is a chance of collision if the dictionary contains other dictionaries as values.

Answer 4

The hash function is not a real hash function. It gives different values ​​for strings (all predictable), but for collections (arrays and dictionaries) it just returns the count. If you need a unique hash, you can calculate it yourself using primes or srandom () and random () functions, or explore a real hash function like SHA1, available in CommonCrypto / CommonDigest.h

Answer 5

I created an NSDictionary category and an overridden hash method based on this answer: Recommendations for overriding isEqual: and a hash

 @implementation NSDictionary (Extensions) - (NSUInteger) hash { NSUInteger prime = 31; NSUInteger result = 1; NSArray *sortedKeys = [self.allKeys sortedArrayUsingSelector: @selector(compare:)]; for (NSObject *key in sortedKeys) { result = prime * result + key.hash; id value = self[key]; if ([value conformsToProtocol: @protocol(NSObject)] == YES) { result = prime * result + [value hash]; } } return result; } @end 

And the Swift implementation.

 extension Dictionary where Key: Comparable, Value: Hashable { public var hashValue: Int { let prime = 31 var result = 1 let sortedKeys = self.keys.sorted() for (key) in sortedKeys { let value = self[key]! result = Int.addWithOverflow(Int.multiplyWithOverflow(prime, result).0, key.hashValue).0 result = Int.addWithOverflow(Int.multiplyWithOverflow(prime, result).0, value.hashValue).0 } return result } } 

It also requires the implementation of the Equatable protocol for the Dictionary so that you can also add Hashable protocol Hashable .