ios - NSString 哈希冲突不会弄乱 NSDictionary

Question

关闭。这个问题需要 details or clarity 。它目前不接受答案。












想改进这个问题？添加详细信息并通过 editing this post 澄清问题。

8年前关闭。




Improve this 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 。为什么是这样？有谁知道苹果正在做什么来避免字典中的哈希冲突/对此有什么好的策略？

编辑:作为引用， here 是关于 NSString 散列的更多细节。显然，该方法只查看第一个、中间和最后 32 个字符；字符串中的其他任何内容都无关紧要。

Answer 1

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

只要返回 YES 的任意两个对象至isEqual:也有相同的hash ，一切都很好。

把字典想象成一系列的桶。哈希决定了值在哪个桶中。一旦你知道了桶，你仍然需要寻找确切的键。