NSDictionary使用原理
1、NSDictionary (字典)是使用hash表来实现key和value之间的映射存储的,hash函数设计的好坏影响着数据查找访问效率
2、Objective-C 中的字典NSDictionary底层其实就是一个哈希表,实际上绝大多数语言中字典都是通过哈希表实现,
哈希原理
1 | 哈希概念:哈希表的本质是一个数组,数组中每一个元素称为一个箱子(bin),箱子中存放的是键值对。 |
哈希表的存储过程:
- 根据key计算出它的哈希值h。
- 假设箱子的个数为n,那没这个键值对应该放在第(h % n)个箱子中。
- 如果该箱子中已经有了键值对,就使用开放寻址法或者拉链法解决冲突
1 | 在使用拉链法解决哈希冲突时,每个箱子其实是一个链表,属于同一个箱子的所用键值都会排列在链表中。 |
重哈希概念:
哈希表在自动扩容时,一般会创建两倍于原来个数的箱子,因此即使key的哈希值不变,对箱子个数取余结果也会发生改变,因此所有键值对的存放位置可能发生改变,这个过程称为重哈希(rehash)
哈希表的扩容并不是总能够有效的解决负载因子过大的问题。假设所有的key的哈希值都一样,那么即使扩容以后他们的位置也不会变化。因为负载因子会降低,但实际存储在每个箱子中的链表长度并不发送改变,因此也就不能提高哈希表的查询性能
总结
1、如果哈希表中本来箱子就比较多,扩容时需要重新设计哈希并移动数据,性能影响较大。
2、如果哈希函数设计不合理,哈希表在极端情况下会变成线性表。性能极低。