NSString哈希冲突不会弄乱NSDictionary [英] NSString hash collision doesn't mess up NSDictionary

问题描述

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

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

请注意，form1和form2相同.我们有一个哈希冲突.另请注意，foobar是nil.哈希冲突不会使NSDictionary晕眩.为什么是这样?有谁知道苹果在字典中避免哈希冲突时正在做什么/为此有什么好的策略吗?

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?

此处供参考，有关NSString哈希的详细信息.显然，该方法仅查看前32个字符；字符串中的其他任何内容都没有关系.

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.

推荐答案

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

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.

只要将YES返回到isEqual:的任何两个对象也具有相同的hash，就可以了.

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.

这篇关于NSString哈希冲突不会弄乱NSDictionary的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！