NSDictionary的实现原理

作者: conowen | 来源:发表于2018-04-19 17:11 被阅读660次

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))都是一样的,但是可能会由于两个哈希表的负载因子不同,倒是查找的时间也是不同的。

相关文章

  • NSDictionary底层实现原理

    3.NSDictionary底层实现原理 笔者自语:当有一个面试官问我NSDictionary底层实现原理,我平时...

  • NSDictionary实现原理

    NSDictionary是基于key - value 方式,把key映射到一个hash表中实现的 key 需要支持...

  • NSDictionary实现原理

    NSDictionary(字典)是使用 hash表来实现key和value之间的映射和存储的, hash函数设计的...

  • NSDictionary实现原理

    字典原理 NSDictionary(字典)是使用hash表来实现key和value之间的映射和存储的 方法:- (...

  • NSDictionary实现原理

    NSDictionary介绍 NSDictionary(字典)是使用 hash表来实现key和value之间的映射...

  • NSDictionary实现原理

    字典原理 NSDictionary(字典)是使用 hash表来实现key和value之间的映射和存储的, hash...

  • iOS 字典的实现原理

    一、NSDictionary使用原理 1.NSDictionary(字典)是使用hash表来实现key和value...

  • hash表原理

    一、NSDictionary使用原理 1.NSDictionary(字典)是使用hash表来实现key和value...

  • iOS 字典的实现原理

    一、NSDictionary使用原理1.NSDictionary(字典)是使用hash表来实现key和value之...

  • NSDictionary的实现原理

    NSDictionary 、NSSArray、NSSet NSSArray 用于对象有序集合(NSObject对象...

网友评论

    本文标题:NSDictionary的实现原理

    本文链接:https://www.haomeiwen.com/subject/ahfikftx.html