前言

笔者最近看到两道iOS笔试题目，当时就呆住了。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]。数组

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

因而笔者对iOS集合怎么存储提起了兴趣。数据结构

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

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

NSArray 和 NSMutableArray

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

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

因而笔者打下如下代码，发现取不到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的结构是链地址哈希表。