博客> ios 中 Array 和 Dictionary 的原理
ios 中 Array 和 Dictionary 的原理
2018-12-12 23:20 评论:0 阅读:987 飞哥
ios NSArray Dictionary

一、NSArray和NSMutableArray NSArray 其实是一个线性表二位链表,当数据是一个有序序列的时候,查找相当方便,因为线性表 是之前就开辟好了空间的, 它的查询 速度 非常快 只需要 首地址+位置*元素大小,但是进行插入删除代驾非常大(NSArray不允许进行插入删除等操作), NSMutableArray 是一个链表结构,不同的是,链表的查询相当慢,但是插入却挺快的,插入只需要把 插入位置之前的 next 指向新元素 把新元素的next指向 插入位置的下一个就行了next->next->next,但是查询就得用for循环了,虽然,那几个查询算法都进过改进了,但是效率依然很低

因为对于程序来说,找到一个元素,其实就是找到那个元素的地址。

二、NSDictionary 和 NSMutableDictionary;

1、NSDictionary 和 NSMutableDictionary 的数据结构是一样的,都是平衡二叉树,广义来说是一个哈希表,但是就效率而言,这是一个平衡二叉树,因为查找速度很快。

在字典内部有一个逻辑,就是把你的key做了一个排序, 最后的key是一个按一定规律排序之后的序列,比如 1、2、3、4、5、6、7、8、9等,然后么一个key就对应于一个序号。举一个例子来说:

 0F87E054-AD98-4EFB-A398-BB192E42A276.png

这样,当要查找数据的时候,首先就会用key跟50比较,假如 key < 50 ,那么就会在左边查找,然后再会 key 和32 比较,假如key < 32 那么就直接找到 16了,这样就不必需要for循环,而for循环的效率是n*n,那么假设有1024个数据,log2N,也只需要10次,这样的效率是for无法比拟的。

收藏
1
sina weixin mail 回到顶部