iOS常用集合小结
在iOS中常见集合如下表总结：
| 集合类型 | 说明 |
|---|---|
| NSArray | 不可变有序数组，允许重复元素存在的 |
| NSMutableArray | 可变有序数组，是NSArray的子类，允许重复元素存在的 |
| NSSet | 不可变无序数组，相对于NSArray在判断对象contained的时候效率更高，不允许重复元素存在的。 |
| NSMutableSet | 可变无序数组，是NSSet的子类，相对于NSMutableArray在判断对象contained的时候效率更高。 |
| NSHashTable | NSSet 的通用版本，NSSet / NSMutableSet 不同的是，NSHashTable 具有下面这些特性： 1. NSSet / NSMutableSet 持有成员的强引用，通过 hash 和 isEqual: 方法来检测成员的散列值和相等性。 2. NSHashTable 是可变的，没有不可变的对应版本。 3. NSHashTable 可以持有成员的弱引用 4. NSHashTable 可以在加入成员时进行 copy 操作 5. NSHashTable 可以存储任意的指针（主要是和C相关的API结合在一起），通过指针来进行相等性和散列检查 |
| NSDictionary | 不可变字典，key要实现NSCopying协议，对保存Value进行强引用 |
| NSMutableDictionary | 是NSDictionary的子类，key、value管理方式一样。 |
| NSMapTable | NSDictionary通用版，其关系和NSSet与NSHashTable类似。也就是key，value内存管理方式可以自定义。 |
在项目NSHashTable和NSMapTable用得比较少，并且也是在iOS6之后才加入到Foundation框架中。主要是为了解决集合中对外界保存对象进行强引用的问题。在iOS6之前如果要对外界对象弱引用一般通过NSValue中的valueWithNonretainedObject:的方式来转换一层。
NSArray / NSMutableArray
由于允许重复元素存在的，那么这种设计就表明了集合存储没法使用里面的元素做 hash table 的 key 进行相关的快速操作。
- containsObject:，containsObject:，indexOfObject，removeObject: 会遍历里面元素查看是否与之匹对，所以复杂度等于或大于 O(n)
- objectAtIndex:，firstObject:，lastObject:，addObject:，removeLastObject: 这些只针对栈顶栈底操作的时间复杂度都是 O(1)
- indexOfObject:inSortedRange:options:usingComparator: 使用的是二分查找，时间复杂度是 O(log n)
NSSet / NSMutableSet / NSCountedSet
无序没有重复元素。这样就可以通过 hash table 进行快速的操作。比如 addObject:, removeObject:, containsObject: 都是按照 O(1) 来的。需要注意的是将数组转成 Set 时会将重复元素合成一个，同时失去排序。
NSDictionary / NSMutableDictionary
和 Set 差不多，多了键值对应。添加删除和查找都是 O(1) 的。需要注意的是 Keys 必须是符合 NSCopying。
NSHashTable
相比于NSSet/NSMutableSet，NSHashTable最大的优势在于支持弱引用关系。
NSHashTableOptions中定义了如下几种内存管理方式。
- NSHashTableStrongMemory：等同于NSPointerFunctionsStrongMemory，这是默认的管理方式，这样等同于NSSet。
- NSHashTableWeakMemory：等同于NSPointerFunctionsWeakMemory，使用对象的弱引用进行读写操作，当在对象被释放之后会返回NULL
- NSHashTableZeroingWeakMemory：已经被弃用，用NSHashTableWeakMemory替换
- NSHashTableCopyIn：等同于NSPointerFunctionsCopyIn，使用copy的方式加入对象
- NSHashTableObjectPointerPersonality：等同于NSPointerFunctionsObjectPointerPersonality，使用移位指针(shifted pointer)来做hash检测及确定两个对象是否相等，使用description方法来描述NSHashTable。
下表示对NSMutableArray，NSMutabelSet，NSHashTable针对创新5000000对象，并添加到集合中的耗时统计
| 集合类型 | 耗时 |
|---|---|
| NSMutableArray | 2.000553 |
| NSMutableSet | 2.407068 |
| NSHashTable | 4.042974 |
可以看到NSHashTable在添加对象的时候，效率是三种中最差的，也就是系统提供的API功能越丰富，效率越低。。
NSMapTable
相比于NSDictionary/NSMutableDictionary，NSMapTable最大的优势也是在于支持弱引用关系。
是 NSDictionary 的通用版本。和 NSDictionary / NSMutableDictionary 不同的是，NSMapTable 具有下面这些特性
- NSDictionary / NSMutableDictionary 对键进行拷贝，对值持有强引用。
- NSMapTable 是可变的，没有不可变的对应版本。
- NSMapTable 可以持有键和值的弱引用，当键或者值当中的一个被释放时，整个这一项就会被移除掉。
- NSMapTable 可以在加入成员时进行 copy 操作。
- NSMapTable 可以存储任意的指针，通过指针来进行相等性和散列检查。
总结
在NShipster文章结束时写道：永远先从最高的抽象层次去尝试解决问题。NSSet 和 NSDictionary 都是 非常好 的工具。在 99% 的情况下，它们毋庸置疑是正确的选择。如果你碰到的问题包含上面提到的具体的内存管理需求，那么 NSHashTable 和 NSMapTable 值得你一看。
也就是NSHashTable 和 NSMapTable 应用场景更多是处理弱引用的内存管理。
