NSMutableArray
数据结构
- _used 计数
- _list 缓冲区指针
- _size 缓冲区大小
- _offset 缓冲区里的数组的第一个元素索引
_NSArrayM使用的底层实现主要是“环形缓冲区”，这个数据结构相当简单，只是比常规数组或缓冲区复杂一点。环形缓冲区的内容能在到达任意一端时绕向另一端。
插入/删除
环形缓冲区在未满的情况下插入或删除数据，不会要求移动任何内存。在任意一端插入或者删除，只是修改offset参数，不需要移动内存。访问数组元素的时候是通过index+offset来定位内存地址的。插入数组中间时，环形结构会根据最少移动内存的指针插入（_NSArrayM试着去最小化内存的移动，因此会移动最少的一边元素）。
与此类似，在删除头部元素的时候，也只是需要修改offset。在删除中间元素时，也只是会移动最少的一边元素。
与C风格数组对比
NSMutableArray是一个高级抽象数组，解决了C风格数组对应的缺点（C数组插入的时候都会移动内存，不是O(1))，用到了环形缓冲区数据结构来处理内存移动的损耗。而NSMutableArray在任意一端插入或删除的时候有固定时间的性能，而在中间插入/删除的时候都会试着去移动最小化内存。
优化
环形缓冲区的数据结构如果是连续数组结构，在扩容的时候需要移动大量内存，从这个角度看，用链表实现环形缓冲更好。
NSMutableDictionary
数据结构
- _base
- _count
- _capacity 扩充阈值
- _bucketsNum
- _marker
- _context
- _deletes
- _xflags
- _keys
- _values
底层实现
NSDictionary底层其实是一个哈希表。根据数据结构可以发现NSDictionary内部使用了两个数组分别来保存keys和values。
NSDictionary采用连续存储的方式存储键值对，并由两个数组分别存储。key哈希出来数组的下标地址，同样的这个地址对应到values数组的下标，就是匹配到的值。因此keys和values这两个数组的长度一致才能保证匹配到数据。内部结构还有个_capacity表示当前列表的扩充阈值，当count数量达到这个长度就扩容。
NSDictionary设置的key和value，key值会根据特定的hash函数算出建立的空桶数组，keys和values同样多，然后存储数据的时候，根据hash函数算出来的值，找到对应的index下标。如果下标已有数据，开放定址法后移动插入。如果空桶数组的数量达到数据阈值，这个时候就把空桶数组扩容，然后重新哈希插入。
这样把一些不连续的key-value值插入到能建立起关系的hash表中，当我们查找的时候，key根据哈希值算出来，然后根据索引，直接index访问hash表的hash和values，这样查询速度就可以和连续线性存储的数据一样接近O(1)了，只是占用空间有点大。删除的时候，根据marker标记逻辑上的删除，除非NSDictionary内存被移除。
