NSDictionary 内部结构、实现原理

不知道大家有没有思考过NSDictionary和NSArray内部是怎么实现的，那么今天就深挖一下NSDictionary& NSArray的 内部结构。

首先咱们了解一下这几个概念：哈希表、时间复杂度、链表

看了上面的文章，估计大家都懵逼了。。。好吧，正文来了

NSDictionary

NSDictionary（字典）是使用 哈希表来实现key和value之间的映射和存储的， hash函数设计的好坏影响着数据的查找访问效率。数据在hash表中分布的越均匀，其访问效率越高。而在Objective-C中，通常都是利用NSString 来作为键值，其内部使用的hash函数也是通过使用 NSString对象作为键值来保证数据的各个节点在hash表中均匀分布。

- (void)setObject:(id)anObject forKey:(id <NSCopying>)aKey;� 

NSDictionary中的key是唯一的，key可以是遵循NSCopying 协议和重载- (NSUInteger)hash;、- (BOOL)isEqual:(id)object;方法的任何对象。也就是说在NSDictionary内部，会对 aKey 对象 copy 一份新的。而 anObject 对象在其内部是作为强引用（retain或strong)。

• hash 方法是用来计算该对象的 hash 值，最终的 hash 值决定了该对象在 hash 表中存储的位置。所以同样，如果想重写该方法，我们尽量设计一个能让数据分布均匀的 hash 函数。
• �isEqual : 方法是为了通过 hash 值来找到 对象 在hash �表中的位置。

在调用setObject: forKey: 后，内部会去调用 � key 对象的 hash 方法确定 object 在hash表内的入口位置，然后会调用 isEqual : 来确定该值是否已经存在于 NSDictionary中。
注：关于hash，isEqual :可以看看这篇文章 iOS开发 之 不要告诉我你真的懂isEqual与hash!

其实，NSDictionary使用NSMapTable实现。NSMapTable同样是一个key－value的容器，下面是NSMapTable的部分代码：

@interface NSMapTable : NSObject {
   NSMapTableKeyCallBacks   *keyCallBacks;
   NSMapTableValueCallBacks *valueCallBacks;
   NSUInteger             count;
   NSUInteger             nBuckets;
   struct _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位应该很正常。

补充一个小知识：iOS setValue和setObject的区别：

- (void)setObject:(ObjectType)anObject forKey:(KeyType <NSCopying>)aKey;
- (void)setValue:(nullable ObjectType)value forKey:(NSString *)key;

首先：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实现原理