NSDictionary实现原理
NSDictionary介绍
NSDictionary（字典）是使用 hash表来实现key和value之间的映射和存储的， hash函数设计的好坏影响着数据的查找访问效率。数据在hash表中分布的越均匀，其访问效率越高。而在Objective-C中，通常都是利用NSString 来作为键值，其内部使用的hash函数也是通过使用 NSString对象作为键值来保证数据的各个节点在hash表中均匀分布。
NSDictionary内部结构
参考cocotron的源代码，NSDictionary是使用NSMapTable来实现。
NSMapTable同样是一个key－value的容器，下面是NSMapTable的部分代码：
typedef struct {
NSMapTable *table;
NSInteger i;
struct _NSMapNode *j;
} NSMapEnumerator;
上述结构体描述了遍历一个NSMapTable时的一个指针对象，其中包含table对象自身的指针，计数值，和节点指针。
typedef struct {
NSUInteger (*hash)(NSMapTable *table,const void *);
BOOL (*isEqual)(NSMapTable *table,const void *,const void *);
void (*retain)(NSMapTable *table,const void *);
void (*release)(NSMapTable *table,void *);
NSString *(*describe)(NSMapTable *table,const void *);
const void *notAKeyMarker;
} NSMapTableKeyCallBacks;
上述结构体中存放的是几个函数指针，用于计算key的hash值，判断key是否相等，retain，release操作。
typedef struct {
void (*retain)(NSMapTable *table,const void *);
void (*release)(NSMapTable *table,void *);
NSString *(*describe)(NSMapTable *table, const void *);
} NSMapTableValueCallBacks;
上述存放的三个函数指针，定义在对nsmaptable插入一对key－value时，对value对象的操作。
struct NSMapTable {
NSMapTableKeyCallBacks *keyCallBacks;
NSMapTableValueCallBacks *valueCallBacks;
NSUInteger count;
NSUInteger nBuckets;
NSMapNode **buckets;
};
可以看出来NSMapTable是一个哈希＋链表的数据结构，因此在NSMapTable中插入或者删除一对对象时， 寻找的时间是O(1)＋O(m)，m最坏时可能为n。
- O(1)：为对key进行hash得到bucket的位置
- O(m)：遍历该bucket后面冲突的value，通过链表连接起来。
因此NSDictionary中的Key-Value遍历时是无序的，至如按照什么样的顺序，跟hash函数相关。NSMapTable使用NSObject的哈希函数。
-(NSUInteger)hash {
return (NSUInteger)self>>4;
}
上述是NSObject的哈希值的计算方式，简单通过移位实现。右移4位，左边补0。因为对象大多存于堆中，地址相差4位应该很正常。
NSDictionary的KVC实现
@implementation NSDictionary (NSKeyValueCoding)
-(id)valueForKey:(NSString*)key;
{
if([key hasPrefix:@"@"])
return [super valueForKey:[key substringFromIndex:1]];
return [self objectForKey:key];
}
-(void)setValue:(id)value forKey:(NSString*)key
{
[NSException raise:NSInvalidArgumentException format:@"%@ called on immutable dictionary %@", NSStringFromSelector(_cmd), self];
}
@end
@implementation NSMutableDictionary (NSKeyValueCoding)
-(void)setValue:(id)value forKey:(NSString*)key
{
if(value)
[self setObject:value forKey:key];
else
[self removeObjectForKey:key];
}
@end
setObject: ForKey:是NSMutableDictionary特有的；setValue: ForKey:是KVC的主要方法。
(1)
setValue: ForKey:的value是可以为nil的（但是当value为nil的时候，会自动调用removeObject：forKey方法）；setObject: ForKey:的value则不可以为nil。
(2)setValue: ForKey:的key必须是不为nil的字符串类型；
setObject: ForKey:的key可以是不为nil的所有继承NSCopying的类型。
NSDictionary copy key对象
NSDictionary 提供了 key -> object 的映射。从本质上讲，NSDictionary 中存储的 object 位置是由 key 来索引的。
由于对象存储在特定位置，NSDictionary 中要求 key 的值不能改变（否则 object 的位置会错误）。为了保证这一点，NSDictionary 会始终copy key 到自己私有空间。而且object对象在其内部是作为强引用(retain或strong);
这个 key 的copy行为也是 NSDictionary 如何工作的基础，但这也有一个限制：你只能使用 OC 对象作为 NSDictionary 的 key，并且必须支持 NSCopying 协议。此外，key 应该是小且高效的，以至于复制的时候不会对 CPU 和内存造成负担。
这意味着，NSDictionary 中真的只适合将值类型的对象作为 key（如简短字符串和数字）。并不适合自己的模型类来做对象到对象的映射。
