不积跬步无以至千里。 ——送给第一篇博客

问题

NSMutableDictionary是怎么实现的？

解决方案

学习实现原理最好的办法就是查看源代码，这部分代码也很容易找到

/****************   Mutable Dictionary  ****************/

@interface NSMutableDictionary<KeyType, ObjectType> : NSDictionary<KeyType, ObjectType>

- (void)removeObjectForKey:(KeyType)aKey;
- (void)setObject:(ObjectType)anObject forKey:(KeyType <NSCopying>)aKey;
- (instancetype)init NS_DESIGNATED_INITIALIZER;
- (instancetype)initWithCapacity:(NSUInteger)numItems NS_DESIGNATED_INITIALIZER;
- (nullable instancetype)initWithCoder:(NSCoder *)aDecoder NS_DESIGNATED_INITIALIZER;

@end

@interface NSMutableDictionary<KeyType, ObjectType> (NSExtendedMutableDictionary)

- (void)addEntriesFromDictionary:(NSDictionary<KeyType, ObjectType> *)otherDictionary;
- (void)removeAllObjects;
- (void)removeObjectsForKeys:(NSArray<KeyType> *)keyArray;
- (void)setDictionary:(NSDictionary<KeyType, ObjectType> *)otherDictionary;
- (void)setObject:(nullable ObjectType)obj forKeyedSubscript:(KeyType <NSCopying>)key NS_AVAILABLE(10_8, 6_0);

@end

从源代码中我们可以看到NSMutableDictionary是继承自NSDictionary的，但是添加了增加删除等方法。将NSDictionary变成可变的字典类型。我们再打开NSDictionary的实现代码看一下。

@interface NSDictionary<KeyType, ObjectType> (NSExtendedDictionary)

@property (readonly, copy) NSArray<KeyType> *allKeys;//key数组
- (NSArray<KeyType> *)allKeysForObject:(ObjectType)anObject;
@property (readonly, copy) NSArray<ObjectType> *allValues;//value数组
@property (readonly, copy) NSString *description;

我们可以看到NSDictionary中包含了两个NSArray，及一个对应Key的NSArray和一个对应Value的NSArray。
从以上两端代码中我们可以看到NSDictionary以及NSArray的属性均为(readonly,copy)类型的，顾名思义其值是只读的，不可改变。这也符合了介绍，但是NSMutableDictionary以及NSMutableArray均继承于属性不可变的父类，那他是怎么实现可变的呢？由于SDK只开放了.h文件（其实就是只告诉了我们API），没有开放.m文件，我们无法获得其实现细节。我的猜测是把内容拷贝出来重新赋值给新的对象，在替换原地址，但是感觉好蠢。以后有能力可以细究一下。

意外发现

看源代码的时候发现NSArray中集成二分查找，但二分查找一般针对排序数组会有比较快的效率。百度了一下，发现一篇文章 ,这篇文章对iOS的各种集合类做了一定的分析。其中也提到了一开始对apple这种将很多集合分为可变和不可变的感觉很怪异，不过这样做可以使得其线程安全，这样其付出的代价也是值得的，有兴趣可以拜读一下。

typedef NS_OPTIONS(NSUInteger, NSBinarySearchingOptions) {
    NSBinarySearchingFirstEqual = (1UL << 8),
    NSBinarySearchingLastEqual = (1UL << 9),
    NSBinarySearchingInsertionIndex = (1UL << 10),
};

- (NSUInteger)indexOfObject:(ObjectType)obj inSortedRange:(NSRange)r options:(NSBinarySearchingOptions)opts usingComparator:(NSComparator)cmp NS_AVAILABLE(10_6, 4_0); // binary search