在日常的IOS开发中NSMutableArray和NSDictionary的使用率很高，但是我们很少会去思考它们的现实原理。
NSMutableArray
C数组:
优点:查询速度很快，直接通过下表找到对应的值
缺点:修改、删除数据很慢，需要移动基于所有的其他的元素
插入和删除一个元素，需要移动后面所有的元素
改进的目标：实现快速增加，删除
NSMutableArray的内部数据结构如下:
几个主要变量:
offset: 有效数据起始位置偏移量
size: 实际占用的内存大小
used: 数组的实际的有效数据个数
*list: 实际内存的起始地址
删除元素
[arr removeObjecAtIndex:0];
[arr removeObjecAtIndex:0];
执行两次 remove的实现:
仅仅修改 offset即可，内存完全不需要移动。
那么问题来了，移走的这个元素的内存怎么释放的呢？
回到OBJC的引用计数，offset移走，这个对象的引用计数减一，对象引用计数到0之后，由autoreleasepool释放。over
插入元素
[arr insertObjec:@"test"atIndex:0];
执行insertObjec的实现:
如果buff的size还够用，不需要扩展buff，数据会在buff的末端添加进去，此时offset由0变成size-1,used+1.over
循环buff的牛逼之处就在于此，无需移动内存，实现插入元素。
删除元素
[arr removeObjecAtIndex:3];
实现:
删除头尾元素直接修改offset或者used即可
但是如果删除中间元素，就避免不了移动其他元素，不过NSArray会选择更少移动的那一边移动数据。
所以我们在实际使用过程中应该尽量避免这么做。
tip:
NSMutableArray *array = [NSMutableArray array];
for (int i = 0; i < 10000; i++) {
[array addObject:[NSObject new]];
}
[array removeAllObjects];
数组移除所有元素，buff并不会被立即清空
输出size的结果：
<colgroup style="margin: 0px; padding: 0px;"><col style="margin: 0px; padding: 0px; width: 130px;"><col style="margin: 0px; padding: 0px; width: 130px;"></colgroup>
|
1
|
Size: 14336
|
如果你在利用NSArray保存大量数据的时候，就要注意了。remove之后，记得置为nil,才能立刻释放掉buff.
总结:
1.数组越界奔溃: index > _used+offset 或 index < 0。
2.如果想要内存记录释放，remove之后记得置nil.或者直接置nil.猜想Array的dealloc的方法会自动给所有元素发release消息。
NSDictionary
NSDictionary（字典）是使用hash表来实现key和value之间的映射和存储的
方法：- (void)setObject:(id)anObject forKey:(id)aKey;
Objective-C中的字典NSDictionary底层其实是一个哈希表
根据数据结构可以发现dictionary内部使用了两个指针数组分别来保存keys和values，先不去讨论这两个数组的元素如何形成对应关系，已知的是dictionary采用的是连续存储的方式存储键值对，因此接下来我们将一步步了解字典是如何完成key-value的匹配过程。我们刚才在CFDictionary的结构体的时候看到了key和values这两个二级指针，可以基本断定为数组结构，由于是两个数组分别存储，因此，key哈希出来的数组下标地址，同样这个地址对应到values数组的下标，就是匹配到的值。因此keys和values这两个数组的长度一致才能保证匹配到数据。内部结构还有个_capacity表示当前通列表的扩充阀域 ，当count数量达到这个长度就扩容
可以看到，NSDictionary设置的key和value，key值会根据特定的hash函数算出建立的空桶数组，keys和values同样多，然后存储数据的时候，根据hash函数算出来的值，找到对应的index下标，如果下标已有数据，开放定址法后移动插入，如果空桶数组到达数据阀值，这个时候就会把空桶数组扩容，然后重新哈希插入。这样把一些不连续的key-value值插入到了能建立起关系的hash表中，当我们查找的时候，key根据哈希值算出来，然后根据索引，直接index访问hash表keys和hash表values，这样查询速度就可以和连续线性存储的数据一样接近O(1)了，只是占用空间有点大，性能就很强悍。如果删除的时候，也会根据_maker标记逻辑上的删除，除非NSDictionary（NSDictionary本体的hash值就是count）内存被移除。我们也会根据dictionary之所以采用这种设计，其一出于查询性能的考虑；其二dictionary在使用过程中总是会很快的被释放，不会长期占用内存。
哈希原理
散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。
给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。
哈希概念:哈希表的本质是一个数组，数组中每一个元素称为一个箱子(bin)，箱子中存放的是键值对。
三：哈希存储过程
1.根据 key 计算出它的哈希值 h。
2.假设箱子的个数为 n，那么这个键值对应该放在第 (h % n) 个箱子中。
3.如果该箱子中已经有了键值对，就使用开放寻址法或者拉链法解决冲突。
在使用拉链法解决哈希冲突时，每个箱子其实是一个链表，属于同一个箱子的所有键值对都会排列在链表中。
哈希表还有一个重要的属性: 负载因子(load factor)，它用来衡量哈希表的空/满程度，一定程度上也可以体现查询的效率，计算公式为:
负载因子 = 总键值对数 / 箱子个数
负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是 1，或者 0.75 等)时，哈希表将自动扩容。
哈希表在自动扩容时，一般会创建两倍于原来个数的箱子，因此即使 key 的哈希值不变，对箱子个数取余的结果也会发生改变，因此所有键值对的存放位置都有可能发生改变，这个过程也称为重哈希(rehash)。
哈希表的扩容并不总是能够有效解决负载因子过大的问题。假设所有 key 的哈希值都一样，那么即使扩容以后他们的位置也不会变化。虽然负载因子会降低，但实际存储在每个箱子中的链表长度并不发生改变，因此也就不能提高哈希表的查询性能。
转载自：
https://www.cnblogs.com/firstrate/p/8313443.html
https://blog.csdn.net/u012886093/article/details/90767481
