NSDictionary 、NSSArray、NSSet

NSSArray 用于对象有序集合(NSObject对象)
NSSet 用于对象的无序，不重复集合
NSDictionary无序键值映射
以上为不可变

可变的为以下三种
NSMutableArray
NSMutableSet
NSMutableDictionary

实现原理

NSDictionary（字典）是使用哈希表 Hash table（也叫散列表）来实现的。哈希表是根据键（Key）而直接访问在内存存储位置的数据结构。也就是说，它通过计算一个关于键（key）值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做哈希表。也就是说哈希表的本质是一个数组，数组中每一个元素其实就是NSDictionary键值对。

若关键字为k，则其值存放在f(k)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为哈希函数。

哈希冲突：如果关键字k不同，但是通过哈希函数f(k)得到的结果是一样的，这样就会出现哈希冲突，也就是说，得到的这个地址有可能已经存在键值对了。

解决冲突：可以通过优化哈希函数来减少冲突的几率，如果冲突已经发生，可以通过开放寻址法或者拉链法解决冲突。
拉链法解决冲突:大概原理就是将同一个存储位置的所有元素保存在一个链表中。

哈希表的查找效率

影响哈希表的查找效率主要问题是冲突问题，如果冲突较多，查找效率就会低。
冲突原因主要是以下三个

哈希函数是否均匀；
哈希冲突处理的方法；
哈希表的负载因子 。

哈希表的负载因子 = 填入表中的元素个数 / 哈希表的长度

也就是说，哈希表越满，负载因子越大。

面试题

Q：当用一个不存在的key来查找两个不同长度的字典，那么哪个效率会高？
A：表面上看可能是一样快，因为字典底层都用了哈希表，查找的时间复杂度为 O(1)，（最差的时候是O(n)）都是一样的，但是可能会由于两个哈希表的负载因子不同，倒是查找的时间也是不同的。