NSString hash collision doesn't mess up NSDict

2019-08-10 21:41发布

问题:

Run this code in the debugger and stop afterward (I'm in the iOS 7 simulator in Xcode 5.0.1).

NSString *nsStr = @"/Users/123456789012/Library/Application Support/iPhone Simulator/7.0/Applications/94F31827-6DAD-4BD5-AC91-B215176265E1/Documents/libraries/shared/17517_abPub/OEBPS/indexes/Index.sqlite";
NSString *nsStr2 = @"/Users/123456789012/Library/Application Support/iPhone Simulator/7.0/Applications/94F31827-6DAD-4BD5-AC91-B215176265E1/Documents/libraries/shared/16583_abPub/OEBPS/indexes/Index.sqlite";
NSUInteger form1 = [nsStr hash];
NSUInteger form2 = [nsStr2 hash];

NSMutableDictionary *dict = [[[NSMutableDictionary alloc]init]autorelease];
[dict setObject:@"foo" forKey:nsStr];

id foobar = [dict objectForKey:nsStr2];

Note that form1 and form2 are the same. We have a hash collision. Also note that foobar is nil. The hash collision does not faze NSDictionary. Why is this? Does anyone know what Apple is doing to survive hash collision in their dictionary / what some good strategies are for this?

EDIT: For reference, here is more detail on NSString hashing. Apparently the method only looks at the first, middle, and last 32 characters; anything else in the string doesn't matter.

回答1:

A hash value is not unique. Many different values can have the same hash value. The implementation of the dictionary knows this. The use of the hash is simply a way to optimize the lookup. But it's the actual key value that matters, not the hash value.

As long as any two objects that return YES to isEqual: also have the same hash, things are fine.

Think of a dictionary as a series of buckets. The hash determines which bucket the value is in. Once you know the bucket, you still need to look for the exact key.