前言

笔者最近看到两道iOS笔试题目，当时就呆住了。

    int a[5] = {1, 2, 3, 4, 5};
    int *ptr = (int *)(&a + 1);
    NSLog(@"a的地址 : %p", a);
    NSLog(@"a + 4 的地址: %p", a + 4);
    NSLog(@"ptr - 1 的地址 : %p", ptr - 1);
    NSLog(@"a + 1 的值 ： %d", *(a + 1));
    NSLog(@"p - 1 的值 ： %d", *(ptr - 1));

在C语言中，a和a[0]指向同一个地址。所以不难理解 a[1]的地址比a[0](即a）大了4。

声明了a[5]，存储类型为int。所以数组a的大小也确定了，为(5 * 4)。所以假设a地址为0,ptr的地址是21。由于p指针指向类型为int，所以(p - 1)理所当然也指向a[4]。

对于动态数组，则需要借助数据结构来实现。

于是笔者对iOS集合怎么存储提起了兴趣。

测试一遍，发现结果为23。感慨一句，NSSet究竟是怎么存储的。

开始前，先提一句，集合中不能存储基本数据类型，将保持与元素对象的强引用关系。

NSArray 和 NSMutableArray

NSArray : A static ordered collection of objects. NSMutableArray : A dynamic ordered collection of objects.

和C不一样，OC是门面向对象的语言。*array，当然指向数组对象的地址，而不是array[0]。换句话说，array和array[0]并不指向同一地方。那么array[0]、array[1]、array[2]是怎么找到该对象的，或者说怎么存储的呢？

于是笔者打下以下代码，发现取不到array[0]返回的指针地址。也想不出来怎么取。

于是查阅到两篇大牛写的文章，CFArray 的历史渊源及实现原理和NSMutableArray原理揭露

在修改元素的操作中，CFArray 也略显得暴力一些，先对数组进行大块的分区操作，再按照顺序填充数据，组合成为一块新的双端队列

简单地说（笔者看得不怎么懂，如果有误，欢迎指出），数组的数据结构是双端队列，_size表示数组空间，_used表示多少个元素,_offset表示a[0]的偏移量。所以中间位置的操作会慢于两端。

如图，类似缓冲区嵌套 map 表。

当不够容量时，扩容，修改_size，在缓冲区中标记下一块内容头地址在哪。有趣的是,_size只能增大，不会缩小。

NSSet 和 NSMutableSet

Set 和 Array的区别在于Set无序且没有重复元素。

先来看Set是怎么判断重复元素的。

Set对元素是否重复的判断在于两个方法，- (NSUInteger)hash和- (BOOL)isEqual:(id)object。iOS开发 之 不要告诉我你真的懂isEqual与hash!

在《Effective Objective-C 2.0》第8条:理解“对象等同性”提到：

根据等同性约定：若两对象相等，则其哈希码(hash)也相等，但是两个哈希码相同的对象却未必相等。

如果没有重写这两个方法，默认只比较指针值是否相等。

所以上面的笔试题中，Person没有重写这两个方法。指针person2指向person1，所以被加到NSSet时，被当成同一个元素。并且person2.age修改为2，person1.age同理。所以最终输出应该是23。

那么Set存储结构是怎么样的呢？

从上面我们可以看出，Set采用哈希表存储，运用散列算法。所以元素在内存中是不连续的。

NSDictionary 和 NSMutableDictionary

NSDictionary :A static collection of objects associated with unique keys. NSMutableDictionary: A dynamic collection of objects associated with unique keys.

又是一篇笔者看不怎么懂的文章NSDictionary 内部结构、实现原理。

NSDictionary的结构是链地址哈希表。