常见的基础原理相关的面试问题

19 June 2016

常见的基础原理相关的问题

数组：

数组存储区间是连续的，二分查找时间复杂度小，为O(1)，寻址容易，插入和删除困难；

链表：

链表存储区间离散，时间复杂度很大，达O（N），寻址困难，插入和删除容易；

哈希表：

哈希表是一种寻址容易，插入删除也容易的数据结构，既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。 Hash表实现原理：使用哈希函数将被查找的Key转换为数组的索引，如果发生hash索引值碰撞冲突，则拉链法(开放定址法)和线性探测法等方法解决冲突，直到找出一个不冲突的哈希地址。

解决hash冲突的常见办法

开放定址法（线性探测再散列，二次探测再散列，伪随机探测再散列）;
再哈希法;
链地址法;
建立一个公共溢出区;

Java中hashmap的解决办法就是采用的链地址法。

HashMap/Set实现原理：

HashMap对应的哈希表是由数组+链表组成的; HashSet:它是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存所有元素，因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，我们应该为保存到 HashSet 中的对象覆盖 hashCode() 和 equals()。

hash算法原理详解常见hash算法的原理 HashMap实现原理分析

图片、文件压缩原理：

几种常见文件压缩算法原理介绍

字典算法：字典算法是最为简单的压缩算法之一。它是把文本中出现频率比较多的单词或词汇组合做成一个对应的字典列表，并用特殊代码来表示这个单词或词汇。例如，有字典列表：
```
00=Chinese
01=People
02=China
```
源文本：I am a Chinese people,I am from China 压缩后的编码为：I am a 00 01,I am from 02。
固定位长算法（Fixed Bit Length Packing）:这种算法是把文本用需要的最少的位来进行压缩编码。比如八个十六进制数：1，2，3，4，5，6，7，8。转换为二进制为：00000001，00000010，00000011，00000100， 00000101，00000110，00000111，00001000。每个数只用到了低4位，而高4位没有用到（全为0），因此对低4位进行压缩编码后得到：0001，0010，0011，0100，0101，0110，0111，1000。然后补充为字节得到：00010010， 00110100，01010110，01111000。所以原来的八个十六进制数缩短了一半，得到4个十六进制数：12，34，56，78。这也是比较常见的压缩算法之一。
行程算法（RLE（Run Length Encoding））：是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用。
霍夫曼编码（Huffman Encoding）：哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。

作者：加刘景长链接：https://www.zhihu.com/question/19925039/answer/19738033 来源：知乎著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

图像可压缩的原因

因为有很多冗余信息，所以可压缩。常见图像、视频、音频数据中存在的冗余类型如下：

空间冗余:一幅图像表面上各采样点的颜色之间往往存在着空间连贯性，存在大量颜色相同或相近的区域；
时间冗余:这种冗余主要针对视频,运动图像（视频）一般为位于一时间轴区间的一组连续画面，其中的相邻帧往往包含相同的背景和移动物体，只不过移动物体所在的空间位置略有不同，所以后一帧的数据与前一帧的数据有许多共同的地方，这种共同性是由于相邻帧记录了相邻时刻的同一场景画面，所以称为时间冗余。
视觉冗余:人类的视觉系统由于受生理特性的限制，对于图像场的注意是非均匀的，人对细微的颜色差异感觉不明显。例如，人类视觉的一般分辨能力为26灰度等级，而一般的图像的量化采用的是28灰度等级，即存在视觉冗余。人类的听觉对某些信号反映不太敏感，使得压缩后再还原有允许范围的变化，人也感觉不出来。

数据压缩方法的分类

按照压缩方法是否产生失真分类 无失真压缩
- 无失真压缩要求解压以后的数据和原始数据完全一致。解压后得到的数据是原数据的复制，是一种可逆压缩。
- 无失真压缩法去掉或减少数据中的冗余，恢复时再重新插到数据中，因此是可逆过程根据目前的技术水平，无损压缩算法一般可以把普通文件的数据压缩到原来的1/2－1/4。
- 一些常用的无损压缩算法有赫夫曼(Huffman)算法和LZW(Lenpel-Ziv & Welch)压缩算法。 有失真压缩
- 解压以后的数据和原始数据不完全一致，是不可逆压缩方式。有失真压缩还原后，不影响信息的表达例如，图像、视频、音频数据的压缩就可以采用有损压缩方法，因为其中包含的数据往往多于我们的视觉系统和听觉系统所能接收的信息，丢掉一些数据而不至于对声音或者图像所表达的意思产生误解，但可大大提高压缩比。图像、视频、音频数据的压缩比可高达100:1，但人的主观感受仍不会对原始信息产生误解。
按照压缩方法的原理分类 预测编码:基本思想是利用已被编码的点的数据值，预测邻近的一个像素点的数据值. 变换编码:基本思想是将图像的光强矩阵变换到系数空间上，然后对系数进行编码压缩. 统计编码:根据信息出现概率的分布特性而进行的压缩编码。比如霍夫曼编码。

图像压缩编码

行程编码（RLE）:这是最好理解的一种编码了。现实中有许多这样的图像，在一幅图像中具有许多颜色相同的图块。在这些图块中，许多行上都具有相同的颜色，或者在一行上有许多连续的像素都具有相同的颜色值。在这种情况下就不需要存储每一个像素的颜色值，而仅仅存储一个像素的颜色值，以及具有相同颜色的像素数目就可以，或者存储像素的颜色值，以及具有相同颜色值的行数。
- 这种压缩编码称为行程编码(run length encoding，RLE)，具有相同颜色并且是连续的像素数目称为行程长度。例如,字符串AAABCDDDDDDDDBBBBB,利用RLE原理可以压缩为3ABC8D5B；
- RLE编码简单直观，编码/解码速度快，因此许多图形和视频文件，如.BMP .TIFF及AVI等格式文件的压缩均采用此方法；
- RLE适用于计算机生成的图像，例如。BMP、TIF等，灰度图像等，不适于颜色丰富的自然图像。
哈夫曼编码（Huffman)：由于图像中表示颜色的数据出现的概率不同，对于出现频率高的赋（编）予较短字长的码，对出现频率小的编于较长字长的码，从而减少总的代码量，但不减少总的信息量。
DCT编码：将在空域上描述的图象，经过某种变换（通常采用，余弦变换、傅立叶变换、沃尔什变换等），在某种变换域里进行描述。在变换域里，首先降低了图象的相关性；其次通过某种图象处理（如频域的二维滤波）以及熵编码，则可进一步压缩图象的编码比特率。这种变换常用于JPEG图像压缩。

24位bmp

24位bmp是公认最好的图片存储格式,存储了图片所有的信息，24位bmp是每像素用24位二进制存储该像素点的图像信息，相当于3字节。所以，图像占用空间大小就可以算了。

将图像长宽单位换位像素（比如：1024X960 800X600），则文件大小为（长X宽X３）字节. 如：800X600的图片大小为800X600X3＝1440000字节=1.44兆,1024X960的图像大小为2.95兆。 16位bmp则是24为的三分之二大小。 256色是２的８次方，相当于８位的bmp。

JPG的压缩过程：jpeg压缩分四个步骤实现

颜色模式转换及采样：rgb色彩系统是我们最常用的表示颜色的方式。jpeg采用的是ycbcr色彩系统。
- 要用jpeg基本压缩法处理全彩色图像，得先把rgb颜色模式图像数据，转换为ycbcr颜色模式的数据。y代表亮度，cb和cr则代表色度、饱和度。
- 通过计算公式可完成数据转换。y=0.2990r+0.5870g+0.1140b, cb=-0.1687r-0.3313g+0.5000b+128,cr=0.5000r-0.4187g-0.0813b＋128。
- 人类的眼晴对低频的数据比对高频的数据具有更高的敏感度，事实上，人类的眼睛对亮度的改变也比对色彩的改变要敏感得多，也就是说y成份的数据是比较重要的。
- 既然cb成份和cr成份的数据比较相对不重要，就可以只取部分数据来处理。以增加压缩的比例。
- jpeg通常有两种采样方式：yuv411和yuv422，它们所代表的意义是y、cb和cr三个成份的数据取样比例。
dct变换:dct变换的全称是离散余弦变换(discrete cosine transform)，是指将一组光强数据转换成频率数据，以便得知强度变化的情形。
- 压缩时，将原始图像数据分成8*8数据单元矩阵，例如亮度值的第一个矩阵内容如下：jpeg将整个亮度矩阵与色度cb矩阵，饱和度cr矩阵，视为一个基本单元称作mcu。
- 每个mcu所包含的矩阵数量不得超过10个。
- 例如，行和列采样的比例皆为4:2:2，则每个mcu将包含四个亮度矩阵，一个色度矩阵及一个饱和度矩阵。
量化:图像数据转换为频率系数后，还得接受一项量化程序，才能进入编码阶段。
编码:huffman编码无专利权问题，成为jpeg最常用的编码方式，huffman编码通常是以完整的mcu来进行的。

bmp/gif/jpg图象最底层原理分析图像压缩原理高压缩文件是如何实现的

category和extension

参考：深入理解Objective-C：Category

extension
- extension看起来很像一个匿名的category，但是extension和有名字的category几乎完全是两个东西。
- extension在编译期决议，它就是类的一部分，在编译期和头文件里的@interface以及实现文件里的@implement一起形成一个完整的类，它伴随类的产生而产生，亦随之一起消亡。
- extension一般用来隐藏类的私有信息，你必须有一个类的源码才能为一个类添加extension，所以你无法为系统的类比如NSString添加extension。
category
- category则完全不一样，它是在运行期决议的。
- extension可以添加实例变量，而category是无法添加实例变量的(可通过object_associate动态绑定变量)。
category真面目
- 所有的OC类和对象，在runtime层都是用struct表示的，category也不例外，在runtime层，category用结构体category_t（在objc-runtime-new.h中可以找到此定义），它包含了。 ``` 1)、类的名字（name） 2)、类（cls） 3)、category中所有给类添加的实例方法的列表（instanceMethods） 4)、category中所有添加的类方法的列表（classMethods） 5)、category实现的所有协议的列表（protocols） 6)、category中添加的所有属性（instanceProperties）
typedef struct category_t { const char *name; classref_t cls; struct method_list_t *instanceMethods; struct method_list_t *classMethods; struct protocol_list_t *protocols; struct property_list_t *instanceProperties; } category_t; ```
category的加载机制
- 首先编译器生成了实例方法列表OBJC$_CATEGORY_INSTANCE_METHODSMyClass$_MyAddition和属性列表OBJC$_PROP_LISTMyClass$_MyAddition。另外category的名字是用来给各种列表以及后面的category结构体本身命名，而且有static来修饰，所以在同一个编译单元里category名不能重复，否则会出现编译错误。
- 其次，编译器生成了category本身OBJC$_CATEGORYMyClass$_MyAddition，并用前面生成的列表来初始化category本身。
- 最后，编译器在DATA段下的objc_catlist section里保存了一个大小为1的category_t的数组L_OBJC_LABELCATEGORY$（当然，如果有多个category，会生成对应长度的数组^_^），用于运行期category的加载。
- 对于OC运行时，入口方法如下（在objc-os.mm文件中）：_objc_init(void)。_objc_init里面的调用的map_images最终会调用objc-runtime-new.mm里面的_read_images方法从而把category被附加到类上面。
- 在_read_images方法里的addUnattachedCategoryForClass会把类和category做一个关联映射，remethodizeClass则通过attachCategoryMethods把所有category的实例方法列表拼成了一个大的实例方法列表，然后转交给了attachMethodLists方法,从把category的实例方法添加到类上。同样在这个_read_images也把category的协议以及属性添加到类上，以及把category的类方法和协议添加到类的metaclass上。
注意：category的方法没有“完全替换掉”原来类已经有的方法，也就是说如果category和原来类都有methodA，那么category附加完成之后，类的方法列表里会有两个methodA；category的方法被放到了新方法列表的前面，而原来类的方法被放到了新方法列表的后面，这也就是我们平常所说的category的方法会“覆盖”掉原来类的同名方法，这是因为运行时在查找方法的时候是顺着方法列表的顺序查找的，它只要一找到对应名字的方法，就会停止往下找了。
关于在类和category中都可以有+load方法问题：
- 在类的+load方法调用的时候，是可以调用category中声明的方法的，因为附加category到类的工作会先于+load方法的执行。
- 而+load方法，调用顺序是先类，后category，而category的+load执行顺序是根据编译顺序决定的。
- 虽然对于+load的执行顺序是这样，但是对于“覆盖”掉的方法，则会先找到最后一个编译的category里的对应方法。
怎么调用到原来类中被category覆盖掉的方法？既然我们已经知道category其实并不是完全替换掉原来类的同名方法，只是category在方法列表的前面而已，所以我们只要顺着方法列表找到最后一个对应名字的方法，就可以调用原来类的方法。
在category里面是无法为category添加实例变量的。但是我们很多时候需要在category中添加和对象关联的值，这个时候可以求助关联对象来实现。所有的关联对象都由AssociationsManager管理，由一个静态AssociationsHashMap来存储所有的关联对象的，并且runtime的销毁对象函数objc_destructInstance里面会判断这个对象有没有关联对象，如果有，会调用_object_remove_assocations做关联对象的清理工作。

参考： iOS使用Category添加@property变量

关于autoreleasepool内存管理

OC对象发送一条autorelease消息，就会把这个对象添加到最近的自动释放池中也就是栈顶释放池中，Autorelease实际上是把对release的调用延迟了，对于每一次autorelease，系统只是把对象放入了当前的autorelease pool中，当pool被释放时，pool中所有的对象都会被调用release。
不要把大量循环放在autoreleasepool中，这样会造成内存峰值上升，因为里面创建的对象要等释放池销毁了才能释放，这种情况应该手动管理内存。
尽量避免大内存使用该方法，对于这种延迟释放机制，尽量少用。
SDK中利用静态方法创建并返回的对象都已经autorelease，不需要我们自己手动release。

参考：黑幕背后的Autorelease

Objective-C Associated Objects 的实现原理

每一个对象地址对应一个 ObjectAssociationMap 对象，而一个 ObjectAssociationMap 对象保存着这个对象的若干个关联记录。

AssociationsManager 是顶级的对象，维护了一个从 spinlock_t 锁到 AssociationsHashMap 哈希表的单例键值对映射；

AssociationsHashMap 是一个无序的哈希表，维护了从对象地址到 ObjectAssociationMap 的映射；

ObjectAssociationMap 是一个 C++ 中的 map ，维护了从 key 到 ObjcAssociation 的映射，即关联记录； 4.ObjcAssociation 是一个 C++ 的类，表示一个具体的关联结构，主要包括两个实例变量，_policy 表示关联策略，_value 表示关联对象。

一个对象的所有关联对象是在这个对象被释放时调用的 _object_remove_assocations 函数中被移除；

关联对象与被关联对象本身的存储并没有直接的关系，它是存储在单独的哈希表中的；

关联对象的五种关联策略与属性的限定符非常类似，在绝大多数情况下，我们都会使用 OBJC_ASSOCIATION_RETAIN_NONATOMIC 的关联策略，这可以保证我们持有关联对象；关联对象的释放时机与移除时机并不总是一致，比如实验中用关联策略 OBJC_ASSOCIATION_ASSIGN 进行关联的对象，很早就已经被释放了，但是并没有被移除，而再使用这个关联对象时就会造成 Crash 。

参考： bjective-C Associated Objects 的实现原理

Runloop相关

深入理解RunLoop

KVO原理：基于KVC及观察者模式实现

Key-Value Coding(KVC)，即是指NSKeyValueCoding，一个非正式的Protocol，提供一种机制来间接访问对象的属性。KVO就是基于KVC实现的关键技术之一。

KVC里的valueForKey 和 valueForKeyPath

NSString *personsName = [p valueForKey:@"name"];
NSString *spousesName = [p valueForKeyPath:@"spouse.name"];

Key-Value Observing (KVO),Key-Value Observing (KVO) 建立在 KVC 之上，它能够观察一个对象的 KVC key path 值的变化。以下实现步骤：

[p addObserver:self forKeyPath:@"address" options:0 context:KVO_CONTEXT_ADDRESS_CHANGED];添加观察者，即注册监听；回调方法：observeValueForKeyPath:ofObject:change:context: 在被观察的 key path 的值变化时调用； dealloc 记得停止观察；

参考：KVC 与 KVO 理解

iOS中集合遍历方法的比较和技巧

参考：iOS中集合遍历方法的比较和技巧

ios中常用的遍历运算方法

经典for循环
for in (NSFastEnumeration) (参考：http://nshipster.com/enumerators/)
makeObjectsPerformSelector
kvc集合运算符(参考：http://www.jianshu.com/p/7675709d14a7)
enumerateObjectsUsingBlock
enumerateObjectsWithOptions(NSEnumerationConcurrent)
dispatch_apply

比较后的结论

对于集合中对象数很多的情况下，for in (NSFastEnumeration)的遍历速度非常之快，但小规模的遍历并不明显（还没普通for循环快）；
使用kvc集合运算符运算很大规模的集合时，效率明显下降（100万的数组离谱的21秒多），同时占用了大量内存和cpu；
enumerateObjectsWithOptions(NSEnumerationConcurrent)和dispatch_apply(Concurrent)的遍历执行可以利用到多核cpu的优势（实验中在双核cpu上效率基本上x2）；
enumerateObjectsWithOptions，对于遍历的外部是保持同步的（遍历都完成后才继续执行下一行），猜想内部大概是gcd的dispatch_group或者信号量控制。
虽然说上面的测试结果表明，在集合内元素不多时，经典for循环的效率要比forin要高，但是从代码可读性上来看，就远不如forin看着更顺畅；
同样的还有kvc的集合运算符，一些内置的操作以keypath的方式声明，相比自己用for循环实现，一行代码就能搞定，清楚明了，还省去了重复工作；
在framework中增加了集合遍历的block支持后，对于需要index的遍历再也不需要经典for循环的写法了。

同步/异步的的实现方法总结

同步：

gcd的dispatch_group、或者信号量控制、或加锁(NSLock)；
dispatch_barrier_sync和dispatch_barrier_async;

异步：

几个GCD相关

dispatch_barrier_sync和dispatch_barrier_async其实是类似的(除了sync与async的区别), 所以本文重点讨论其中的一个接口 * 通过dispatch_barrier_async添加的block会等到之前添加所有的block执行完毕再执行； * 在dispatch_barrier_async之后添加的block会等到dispatch_barrier_async添加的block执行完毕再执行； * dispatch_barrier_async的上述特点只在自己创建的concurrent queue有效, 在serial queue和global concurrent queues中的作用和dispatch_sync完全相同；

设计模式相关

###继承相对于组合模式的缺点；

策略模式：

策略模式的用意是针对一组算法，将每一个算法封装到具有共同接口的独立的类中，从而使得它们可以相互替换。
策略模式使得算法可以在不影响到客户端的情况下发生变化。使用策略模式可以把行为和环境分割开来。
环境类负责维持和查询行为类，各种算法则在具体策略中提供。由于算法和环境独立开。算法的修改都不会影响环境和客户。

策略模式应用：对象的比较、排序方法的实现,java中的Sortable接口,OC里的NSSortDescriptor。

参考：iOS中的对象等同性

参考

参考：iOS面试题小结