哈希表概述：
Objective-C 中的字典NSDictionary底层其实是一个哈希表，实际上绝大多数语言中字典都通过哈希表实现。哈希表的本质是一个数组，数组中每一个元素称为一个箱子(bin)，箱子中存放的是键值对。
哈希表的存储过程如下:
1、根据 key 计算出它的哈希值 h。
2、假设箱子的个数为 n，那么这个键值对应该放在第(h % n)个箱子中。
3、如果该箱子中已经有了键值对，就使用开放寻址法或者拉链法解决冲突（不甚了解，稍后在仔细了解一下，但oc这边是直接对value进行的替换）。
哈希表还有一个重要的属性: 负载因子(load factor)，它用来衡量哈希表的空/满程度，一定程度上也可以体现查询的效率，计算公式为:。
负载因子 = 总键值对数 / 箱子个数
负载因子越大，意味着哈希表越满，越容易导致冲突，性能也就越低。因此，一般来说，当负载因子大于某个常数(可能是 1，或者 0.75 等)时，哈希表将自动扩容。
哈希表在自动扩容时，一般会创建两倍于原来个数的箱子，因此即使 key 的哈希值不变，对箱子个数取余的结果也会发生改变，因此所有键值对的存放位置都有可能发生改变，这个过程也称为重哈希(rehash)。
哈希表的扩容并不总是能够有效解决负载因子过大的问题。假设所有 key 的哈希值都一样，那么即使扩容以后他们的位置也不会变化。虽然负载因子会降低，但实际存储在每个箱子中的链表长度并不发生改变，因此也就不能提高哈希表的查询性能。
基于以上总结，可能会发现哈希表的两个问题:
如果哈希表中本来箱子就比较多，扩容时需要重新哈希并移动数据，性能影响较大。
如果哈希函数设计不合理，哈希表在极端情况下会变成线性表，性能极低。
具体详细介绍《深入理解哈希表》
网友评论