NSString哈希冲突不会搞乱NSDictionary

Question

在调试器中运行此代码并在之后停止(我在Xcode 5.0.1中的iOS 7模拟器中).

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];

请注意form1并且form2是相同的.我们有哈希冲突.还要注意的foobar是nil.哈希冲突不会引起混乱NSDictionary.为什么是这样？有谁知道Apple正在做什么来在他们的字典中克服哈希冲突/这有什么好的策略？

编辑:作为参考,这里有更多关于NSString散列的细节.显然,该方法只查看第一个,中间和最后32个字符; 字符串中的任何其他内容都无关紧要.

Answer 1

一个hash值不是唯一的.许多不同的值可以具有相同的哈希值.字典的实现知道这一点.使用散列只是优化查找的一种方法.但它是重要的实际键值,而不是哈希值.

只要任何两个物体返回YES到isEqual:也有相同的hash,一切都很好.

把字典想象成一系列的桶.哈希确定值所在的桶.一旦知道了桶,您仍然需要查找确切的密钥.