iOS：NSMutableArray和NSDictionary、NSSet底层原理、NSCache、copy/mutableCopy

一、NSMutableArray底层原理

普通c数组&＃xff0c;就是一段能被方便读写的连续内存控件。
使用一段线性内存空间的一个最明显的缺点是&＃xff0c;在下标 0 处插入一个元素时&＃xff0c;需要移动其它所有的元素&＃xff0c;同样地&＃xff0c;假如想要保持相同的内存指针作为首个元素的地址&＃xff0c;移除第一个元素需要进行相同的动作

NSMutableArray本质是一个对象。它采用了环形缓冲区的结构。在两端插入和删除非常的快。插入头尾只是修改offset指针&＃xff0c;如果插入数据到达阀值&＃xff0c;一样需要扩容。

只有中间插入和删除时&＃xff0c;才需要移动较少的内容

二、NSDictionary底层原理

NSDictionary其实就是一个散列表&＃xff0c;
对key进行hash算法得到对应的index&＃xff0c;在对index进行 & 运算得到具体的桶的位置。

所以对NSMutableDictionary扩容时&＃xff0c;必须是2的倍数。例如原始长度是16&＃xff0c;扩容后的长度是32&＃xff0c;这样做是为了 & 运算的结果一致

static int indexFor(int h, int length) {return h & (length-1);}


var a &＃61; 21; // 10101// 00111
var b &＃61; a & 7; //长度是8&＃xff0c;这里要减1print("b is \(b)")
// 扩容后&＃xff0c;8变成16
b &＃61; a & 15; //01111
print("b is \(b)")//打印
b is 5
b is 5


可以发现&＃xff0c;&运算的结果一致。

但是扩容需要满足两个条件&＃xff1a;

1. 当前数据存储的数量&＃xff08;即size()&＃xff09;大小必须大于等于阈值
2. 当前加入的数据是否发生了hash冲突。

由于上面这两个条件&＃xff0c;所以存在下面这些情况

1. 就是hashmap在存值的时候&＃xff08;默认大小为16&＃xff0c;负载因子0.75&＃xff0c;阈值12&＃xff09;&＃xff0c;可能达到最后存满16个值的时候&＃xff0c;再存入第17个值才会发生扩容现象&＃xff0c;因为前16个值&＃xff0c;每个值在底层数组中分别占据一个位置&＃xff0c;并没有发生hash碰撞。

2. 当然也有可能存储更多值&＃xff08;超多16个值&＃xff0c;最多可以存26个值&＃xff09;都还没有扩容。原理&＃xff1a;前11个值全部hash碰撞&＃xff0c;存到数组的同一个位置&＃xff08;这时元素个数小于阈值12&＃xff0c;不会扩容&＃xff09;&＃xff0c;后面所有存入的15个值全部分散到数组剩下的15个位置&＃xff08;这时元素个数大于等于阈值&＃xff0c;但是每次存入的元素并没有发生hash碰撞&＃xff0c;所以不会扩容&＃xff09;&＃xff0c;前面11&＃43;15&＃61;26&＃xff0c;所以在存入第27个值的时候才同时满足上面两个条件&＃xff0c;这时候才会发生扩容现象。

三、NSSet

NSSet和NSMutableSet是无序的,但是它保证数据的唯一性。当插入相同的数据时&＃xff0c;不会有任何效果。从内部实现来说是hash表&＃xff0c;所以可以常数时间内查找一个数据。

常用函数&＃xff1a;

[NSSet setWithSet:(NSSet *)set];
用另外一个set对象构造[NSSet setWithArray:(NSArray *)array];用数组构造[NSSet setWithObjects:...]:创建集合对象&＃xff0c;并且初始化集合中的数值&＃xff0c;结尾必需使用nil标志。[set count] ;得到这个结合对象的长度。[set containsObject:...]:判断这个集合中是否存在传入的对象&＃xff0c;返回Bool值。[set objectEnumerator]:将集合放入迭代器。[enumerator nextObject]:得到迭代器中的下一个节点数据&＃xff0c;使用while遍历这个迭代器&＃xff0c;方可遍历集合对象中的对象。[set isEqualToSet:objset]:判断两个集合是否完全相等,返回Bool值。[set isSubsetOfSet:objset]:判断集合中的所有数据是否都相等与objeset集合中,返回Bool值。[set allObjects];

四、NSCache

NSCache 基本上就是一个会自动移除对象来释放内存的 NSMutableDictionary。无需响应内存警告或者使用计时器来清除缓存。唯一的不同之处是键对象不会像 NSMutableDictionary 中那样被复制

- (void)viewDidLoad {[super viewDidLoad];self.cache &＃61; [[NSCache alloc] init];[self.cache setDelegate:self];self.cache.countLimit &＃61; 40;for (int i &＃61; 0; i < 50; i &＃43;&＃43;) {[self.cache setObject:&＃64;(i) forKey:[NSString stringWithFormat:&＃64;"key_%d",i]];}NSLog(&＃64;"-|%&＃64;",[self.cache objectForKey:&＃64;"key_2"]);NSLog(&＃64;"-|%&＃64;",[self.cache objectForKey:&＃64;"key_12"]);}
- (void)cache:(NSCache *)cache willEvictObject:(id)obj {NSLog(&＃64;"---%&＃64;",obj);
}// ----------
2020-09-16 16:14:15.779289&＃43;0800 Test[40675:709451] ---0
2020-09-16 16:14:15.779461&＃43;0800 Test[40675:709451] ---1
2020-09-16 16:14:15.779563&＃43;0800 Test[40675:709451] ---2
2020-09-16 16:14:15.779648&＃43;0800 Test[40675:709451] ---3
2020-09-16 16:14:15.779727&＃43;0800 Test[40675:709451] ---4
2020-09-16 16:14:15.779803&＃43;0800 Test[40675:709451] ---5
2020-09-16 16:14:15.779873&＃43;0800 Test[40675:709451] ---6
2020-09-16 16:14:15.779935&＃43;0800 Test[40675:709451] ---7
2020-09-16 16:14:15.780014&＃43;0800 Test[40675:709451] ---8
2020-09-16 16:14:15.780199&＃43;0800 Test[40675:709451] ---9
2020-09-16 16:14:15.780408&＃43;0800 Test[40675:709451] -|(null)
2020-09-16 16:14:15.780667&＃43;0800 Test[40675:709451] -|12


NSCache提供了可设置缓存的数目与内存大小限制的方式。保证了处理的数据的线程安全性。缓存使用的key不需要是实现NSCopying的类。

当内存警告时内部自动清理部分缓存数据。
进入后台也会清理内存

五、copy/mutableCopy

这几个容器类的对象&＃xff0c;不管是copy还是mutableCopy&＃xff0c;都不会拷贝里面的对象&＃xff0c;如果想要拷贝里面的对象&＃xff0c;使用如下函数

- (instancetype)initWithDictionary:(NSDictionary<KeyType, ObjectType> *)otherDictionary copyItems:(BOOL)flag;- (instancetype)initWithSet:(NSSet<ObjectType> *)set copyItems:(BOOL)flag;- (instancetype)initWithArray:(NSArray<ObjectType> *)array copyItems:(BOOL)flag;