一、字典原理

NSDictionary底层使用哈希表（NSHashTable）来实现，哈希表本质上是一个数组，数组中的每一个元素被称为一个箱子（bin），箱子中存放着键值对（key-value）。
实际的存储过程为：

• 使用哈希函数对key值进行计算，得出哈希值；
• 假设哈希表的数组长度，即箱子个数为n，则该键值对应该存放在第（h%n）个箱子中；
• 如果产生了哈希冲突，则使用 链地址法 处理；
• 如果装载因子（总键值对数/箱子个数）过高，则应该进行扩容（创建两倍于原来的箱子个数）；
• 由于箱子个数发生变化（n变化），原来计算的键值对的存储位置均失效，则应该进行重哈希（对原有数据重新进行哈希运算）。

二、哈希存储过程

1. 首先根据key计算出它的哈希值h

2. 如果箱子的个数为n，那么key值是应该放在第（h%n）个箱子中

3. 如果该箱子已经有了值，就使用开放寻址法或者拉链法进行解决冲突。

4. 如果我们在使用拉链法解决哈希冲突时候，每个箱子都是一个链表，属于同一个箱子的所有键值都会排列在链表中。

拓展

哈希表有一个比较重要的属性：负载因子（load factor）：是用来衡量哈希表的空/满程度，公式如下：

负载因子 = 总键值对数 / 箱子个数

如果负载因子越大，意味着哈希表越满，也就越容易导致冲突，性能也就是越低。在日常开发中，当负载因子大于某个常数（1或者0.75）时，哈希表就会自动扩展。

哈希表在自动扩容时，一般会创建两倍于原来的箱子，因此即使key的哈希值不变，对箱子个数取余的结果也会发生变化，因此所有键值对的存放位置都有可能发生变化，这叫重哈希。

哈希表的扩容虽然可以解决部分问题，但并不总是有效的解决负载因子过大的问题。假如所有的哈希值都一样，即使扩容之后，位置也不会发生改变，虽然负载因子降低，但不能提高哈希表的查找性能。

综上 发现哈希表有两个问题：

1.如果哈希表中箱子键值本来就很多，仅仅扩容移动数据，性能影响较大。

2.如果哈希函数设计不是很合理，那么在极端的情况下会变成线性表，性能非常低

二、哈希扩容后一定能提高查询效率吗

虽然一定会减小装载因子，但不一定能提高查询效率。假设所有key的哈希值都一样（全部都哈希冲突），那么即使扩容后它们仍会是一个长长的链条（存放位置可能变化），那么就不能提高查询效率。

二、NSDictionary的keys是有序的吗？

在iOS 11 之前，NSDictionary 的keys 是无序的。也就是说，如果你遍历一个 NSDictionary 中的keys，你不能保证它们的顺序和你添加它们的顺序是一致的。

从iOS11 开始，NSDictionary 的keys 会按照它们被添加的顺序进行排序。这个改变是由于 Apple 引入了一种新的哈希算法，它能够保证 NSDictionary 的keys 的顺序。

需要注意的是，虽然 NSDictionary 的keys 是有序的，但是它们并不一定是按照它们的值进行排序的。而是按照它们在哈希表中的位置进行排序的。因此，如果你需要按照key的值进行排序，你应该使用 NSArray 中的sortedArrayUsingGomparator：方法进行排序

三、NSSet

集合的特点

1. 集合中的元素都是唯一的

2. 集合中的元素都是无序的

3. 集合中只能方对象类型的元素

Foundation框架中提供了NSSet,它是一组单值对象的集合.同NSArray不同,NSSet存储的是无序的对象,同一个对象也只能保存一个.

四、字典&数组&集合有何区别

1.有序的角度: 数组有序, 字典和集合都是无序的

2.能否通过下标来访问: 数组可以, 字典和集合都不可以

3.元素是否可以重复: 数组可以重复, 字典中key值不可以重复,value值可以重复, 集合中元素不可以重复

4.打印的样式: 数组: () 字典: {} 集合:  {()}

四、 如何监听数组的变化KVO