第十三章算法

第三章多线程面试

内存管理

内存布局

• stack 栈是从高地址向低地址扩展，所以栈是向下增长的，对象和block copy 后都会放在堆上
• heap 堆区向上增长

• 散列表方式

  • 自旋锁
    • 自旋锁是“忙等” 的锁
  • 引用计数表
  • 弱应用表

内存管理方案

• 小对象使用 TaggedPointer
• 64 位架构下面使用的是 NONPONINT_ISA 内存管理方案，非指针型的 isa，内部存储了一些
• 散列表结构 （Side Tables() 结构）
  • 自旋锁
  • 引用计数表
  • 弱引用表
  • Side Tables() 结构

为什么不是一个SideTable，而是多个组成了Side Tables

如果所有对象的存储都放在一张大表当中，因为每个对象是在不同的线程中创建的，要操作其中一个对象时，需要将表加锁处理保证数据安全，要等锁释放之后才能操作下一个对象，此时存在效率问题，引入分离锁技术方案

• 分离锁：把引用计数表分成多张表进行，
• Side Tables 本质是一张Hash 表

自旋锁

是“忙等”的锁，如果当前锁已被其他线程获取，当前线程会不断探测是否被释放，会第一时间获取，而其他锁比如信号量当它获取不到锁时，会把自己的线程阻塞休眠，等到其他线程释放这个锁时再唤醒这个锁

• 适用于轻量访问

引用计数表

使用过Hash表来实现，hash查找提高了查找高效率，插入和获取是通过Hash 算法来是实现的，避免了for循环

alloc 实现

经过一系列调用，最终调用了C函数 calloc， 并没有引用计数+1

retain 实现

底层经过了2次Hash表查找

release 实现

和 retain 实现相反

dealloc 实现原理

objc_destructInstance() 实现

clearDeallocating() 实现

MRC

手动引用计数

ARC

• 编译器在对应位置自动插入retain 和 release 操作，并和runtime协作达到自动引用计数管理内存的效果

• ARC 中禁止手动调用 retain/release

• ARC 中新增 weeak、strong 等关键字

弱引用管理

被声明为__weak 的对象指针经过编译后会进过调用以下方法，在最终的weak_register_no_lock() 方法中进行弱引用变量的添加。添加的位置是通过Hash算法查找的

weak 修饰的对象，释放时置为nil 如何实现的

当一个对象被 dealloc 之后，在dealloc内部实现当中会调用弱引用清除的相关函数，在相关函数当中会根据当前对象指针查找弱引用表，把当前对象下对应的弱应用都取出，遍历弱应用指针并置为nil。

自动释放池

是以栈为结点通过双向链表的形式组合而成，和线程一一对应

Autoreleasepool

循环引用

自循环引用

一个对象中有拥有一个 强持有他的 obj，如果给 obj 赋值为原对象就会造成自循环引用

相互循环引用

• 代理
• Block
• NSTimer
• 大环多循环

多循环引用

解决循环引用的方案

__weak

解决相互循环引用

__block

__unsafe_unretained

一般不建议使用

Runtime 相关问题

数据结构

objc_object 结构体

objc_class

对象、类对象、元类对象的区别

• 类对象存储实例方法列表等信息
• 元类对象存锤类方法列表等信息

消息传递

void objc_msgSend(void /* id self, SEL op, ... */)

经过编译器转变后
[self class] <==> objc_msgSend(self, @selector(class))
第一个参数是消息传递的接收者self, 第二个参数是传递的消息名称（选择器）

void objc_msgSendSuper(void /* struct objc_super *super, SEL op, ... */)
第一个参数是一个结构体指针

//
struuch objc_super {
__unsafe_unretained id receiver; // 就是当前的对象
}

[superclass] <==> objc_msgSendSuper(super, @selector(class))

无论调用[super class] 还是 [self class] 最终这条消息的接收者都是当前对象

图1

消息传递过程

图2

问题1

打印结果都是 Phone

原因:

• 无论调用[super class] 还是 [self class] 最终这条消息的接收者都是当前对象
• [self class] 在Phone的类对象中查找class 方法，没有去父类查找，父类也没有，如图1顺次往上查找到根类，调用根类中class 的具体实现
• [super class]只是跨越了当前类，直接从当前类的父类中查找 class 方法，父类中没有class 方法，如图1所示只能继续往上查找到根类对象，在NSObject 中有class 方法实现，所以接受者任然是当前的对象

缓存查找

根据给定的SEL（方法选择器）通过一个函数来映射出bucket_t 在数组当中的位置，本质上是哈希查找

当前类中查找

当前类中存在着对应的方法列表

• 对于已经排序好的列表，采用二分查找算法查找对应的执行函数
• 对于没有排序的列表，采用一般遍历查找方法查找对应的执行函数

父类逐级查找

图3

• 最关键是通过当前类的 superclass 成员变量去查找父类，或者访问父类
• curClass 的父类是否为 nil？如果是NSObject 类，他的父类为空，所以会结束查找
• 如果当前类有父类就要去该父类的缓存中查找，如果在缓存中命中，那么就结束查找，如果缓存中没有，就需要遍历当前类的父类的方法列表，如果没有就遍历父类的父类查找，沿着superclass指针逐级向上查找，直到查找到NSObject，再去Superclass。如果还是没有为nil时就结束父类逐级查找

消息转发

resolveInstanceMethod:

• 该方法是类方法不是实例方法，参数是SEL 方法选择器类型
• 返回值是一个BOOL值
• 告诉系统是否要解决当前实例方法的实现
• 如果返回YES，结束消息转发
• 如果返回NO，系统会给第二次机会处理这个消息，会回掉forwardingTargetForSelector:

forwardingTargetForSelector：

• 参数是 SEL 方法选择器
• 返回值是 id 类型，说明有哪个对象来处理，转发的对象是谁，如果返回了转发目标就会结束当前调用
• 如果返回为nil，系统会调用 methodSignatureForSelector:方法，最后一次机会处理这个消息

methodSignatureForSelector：

• 参数是 SEL 方法选择器
• 返回值是一个对象，实际上这个对象是对methodSignatureForSelector 方法的参数，参数个数，参数类型和返回值的包装
• 如果返回一个方法签名的话，就会调用 forwardInvocation: 方法
• 如果返回为nil，标记为消息无法处理，程序crash

forwardInvocation：

• 如果此方法不能处理消息，程序crash

代码示例

.h 文件

1
2
3
4

@interface RunTimeObject : NSObject
// 只声明，不实现，验证消息转发机制
- (void)test;
@end

.m 文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

@implementation RunTimeObject

// 实现消息转发流程 中的方法
/**
 是否要解决当前实例方法的实现
 */
+ (BOOL)resolveInstanceMethod:(SEL)sel {
    if (sel == @selector(test)) {
        NSLog(@"resolveInstanceMethod:");
        // 如果返回YES，消息转发就会结束
//        return YES;
        
        return NO;
    } else {
        
        NSLog(@"super resolveInstanceMethod:");
        // 返回父类的默认调用
        return [super resolveInstanceMethod:sel];
    }
}


/**
 - 参数是 SEL 方法选择器
 - 返回值是 id 类型，说明有哪个对象来处理，转发的对象是谁，如果返回了转发目标就会结束当前调用
 - 如果返回为nil，系统会调用 methodSignatureForSelector:方法，最后一次机会处理这个消息
 */
- (id)forwardingTargetForSelector:(SEL)aSelector {
    NSLog(@" forwardingTargetForSelector: ");
    return nil;
}

/**
 - 参数是 SEL 方法选择器
 - 返回值是一个对象，实际上这个对象是对`methodSignatureForSelector` 方法的参数，参数个数，参数类型和返回值的包装
 - 如果返回一个方法签名的话，就会调用 forwardInvocation: 方法
 - 如果返回为nil，标记为消息无法处理，程序crash
 
 */
- (NSMethodSignature *)methodSignatureForSelector:(SEL)aSelector {
    if (aSelector == @selector(test)) {
        NSLog(@"methodSignatureForSelector:");
        /**
         v: 表示这个方法返回值是 void
         
         固定参数@: 表示参数类型是 id, 即self
         固定参数`:` : 表示参数类型是选择器类型，即 @selector(test)
         */
        return [NSMethodSignature signatureWithObjCTypes:"v@:"];
    } else {
        
        NSLog(@"super methodSignatureForSelector:");
        // 返回父类的默认调用
        return [super methodSignatureForSelector:aSelector];
    }
}


- (void)forwardInvocation:(NSInvocation *)anInvocation {
    NSLog(@"forwardInvocation:");
}

@end

调用

1
2
3
4

- (void)runTiemTest {
    RunTimeObject *obj = [[RunTimeObject alloc] init];
    [obj test];
}

结果：

1
2
3
4
5

resolveInstanceMethod:
forwardingTargetForSelector:
methodSignatureForSelector:
super resolveInstanceMethod:
forwardInvocation:

为类动态添加方法

methond Swizzling

使用场景

• 页面中的进出添加统计信息，使用 methond Swizzling 替换viewillAppear 方法

动态添加方法

• perforSelector: 实际上是考察class_addMethod 的方法使用

动态方法解析

• @dynamic关键字
• 动态运行时语言将函数决议推迟到运行时
• 编译时不生成setter/getter 方法，而是在运行时才添加具体的执行函数

问题

[obj foo] 和 obj_msgSend()函数之间有什么关系？

• [obj foo]经过编译器处理过后会变成 obj_msgSend()有两个参数，一个是obj，第二个参数是foo 选择器

runtime 如何通过Selector找到对应的IMP地址的？

消息传递机制

能否向编译后的类增加实例变量

编译之前就完成了实例变量的布局，
runtime_r_t 表示是readonly 的，编译后的类是不能添加实例变量的，可以向动态添加的类中添加实例变量

RunLop

Blocks

Block 是什么？

Blocks 是 C 语言的扩充功能，将函数及其执行上下文封装起来的对象，带有自动变量（局部变量）的匿名函数

• 因为block 底层C++ 结构体中存在着 isa 指针，所以是一个对象
• 因为block 底层C++ 结构体中存在着一个函数指针 FuncPtr，所以是一个函数

什么是Block 调用

Block 的调用就是函数的调用
在终端使用 clang 编译之后查看文件内容可得出以下结论：

• 对其进行一个强制转换，转换之后取出成员变量 FuncPtr

截获变量

以下代码运行结果是 12

原因：block 对基本数据类型的局部变量会截获其值，在定义 block 时以值的方式传到了block 对应的结构体当中，而调用block 时直接使用的是block对应结构体当中已经传过来的那个值，所以值为12

• 局部变量截获

  • 基本数据类型的局部变量截获其值
  • 对象类型的局部变量连同所有权修饰符一起截获

• 局部静态变量： 已指针形式截获

• 全局变量：不截获

• 静态全局变量： 不截获

以下代码运行结果是 8

原因：block 对局部静态变量会以指针形式截获，所以值为8

__block 修饰符

• __block 修饰后的变量最后变成了对象，底层c++ 结构体中存在isa指针
• 一般情况下，对被截获变量进行赋值操作需要添加block 修饰符，而操作是不需要添加block 修饰符的
• 不需要__block 修饰符，全局变量和静态全局变量 block 是不截获的，所以不需要修饰，静态局部变量是通过指针截获的，修改外部的变量，也不需要添加
  • 静态局部变量
  • 全局变量
  • 静态全局变量

不需要添加__Block 修饰符

1
2
3
4
5
6
7
8

- (void)test {
    NSMutableArray *array = [NSMutableArray array];
    void(^block)(void) = ^{
        [array addObject:@1234];
    };
    
    block();
}

需要添加__Block 修饰符

1
2
3
4
5
6
7
8

- (void)test {
    __block NSMutableArray *tempArray = nil;
    void(^block)(void) = ^{
        tempArray = [NSMutableArray array];
    };
    
    block();
}

以下代码运行结果是 8

1
2
3
4
5
6
7
8

- (void)test__Block3 {
    __block int multiplier = 6;
    int(^Block)(int) = ^int(int num){
        return multiplier * num;
    };
    multiplier = 4;
    NSLog(@"__block--test__Block3---result is %d", Block(2));
}

原因

栈上Block 的block 变量中的 forwarding 指针指向的是自身

Block 的内存管理

Block 的 内存分布

Block 的 Copy 操作

• 全局block
• 堆block
• 栈block

Block 循环引用

• 如果当前block对当前对象的某一变量进行截获的话，block 会对对应变量有一个强引用，当前block因为当前的对象对其有个强引用，产生了自循环引用，通过声明为__weak变量来解决
• 如果定义了__block 修饰符的话也会产生循环引用，在ARC 下会产生循环引用，而在MRC 下不会，在ARC 下通过打破环来消除，但是存在弊端时当block 没有机会执行时，

循环引用1

解决方法：

大环循环引用2

以上代码，在MRC 下，不会产生循环引用，在ARC 下，会产生循环应用，引起内存泄露

解决方法

如果block 没有机会执行，那么循环引用将不会被打破

UITableView 相关

• 重用机制

• 并发访问，数据拷贝问题：主线程删除了一条数据，子线程数据由删除之前的数据源copy而来，子线程网络请求，数据解析，预排版等操作后，回到主线程刷新时已经删除的数据又会重现

  • 主线程数据源删除时对数据进行记录，子线程的数据回来后再进行一次同步删除操作，然后再刷新数据

  • 使用GCD中的串行队列，将数据删除和数据解析在此队列中进行

UIView 和CALayer 的关系

• UIView 为 CALayer 提供内容，负责处理触摸事件，参与响应链
• CALayer 负责显示内容，分工明确，UIView 的Layer 实际上就是CALayer， backgroundColor 等属性本质是对CALayer 做了一层包装

事件传递

• hitTest 方法是返回响应时间的试图
• pointInside withEvent 方法判断点击位置是否在当前视图范围内
• 倒序遍历最终响应事件的试图，最后添加的试图会最优先被遍历到

需求案例

只让正方形的view中圆形区域内可以响应事件，四个角的位置不响应事件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class CircularAreaResponseButton: UIButton {
    
    override func hitTest(_ point: CGPoint, with event: UIEvent?) -> UIView? {
        if self.isHidden || !self.isUserInteractionEnabled ||  self.alpha <= 0.01 {
            return nil
        }
        
        var hitView: UIView?
        if self.point(inside: point, with: event) {
            // 遍历当前视图的子试图
            for subView in subviews {
                // 坐标转换
                let convertPoint = self.convert(point, to: subView)
                if let hitTestView = subView.hitTest(convertPoint, with: event) {
                    // 找到了最终响应事件的试图
                    hitView = hitTestView
                    break;
                }
            }
            
            if hitView != nil {
                return hitView
            }
            return self
        }
        return nil
    }
    
    
    override func point(inside point: CGPoint, with event: UIEvent?) -> Bool {
        let x1 = point.x
        let y1 = point.y
        
        let x2 = self.frame.width / 2.0
        let y2 = self.frame.height / 2.0
        // 使用平面内两点见距离公式计算距离, 并且判断是否 <= 圆的半径
        return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) <= x2
    }
}

视图响应

UIView 都继承于 UIResponder，都有以下方法

1
2
3
4

func touchesBegan(_ touches: Set<UITouch>, with event: UIEvent?)
func touchesMoved(_ touches: Set<UITouch>, with event: UIEvent?) 
func touchesEnded(_ touches: Set<UITouch>, with event: UIEvent?)
func touchesCancelled(_ touches: Set<UITouch>, with event: UIEvent?)

如果事件沿着视图响应链一直传递到 UIApplicationDelegate 仍然没有任何一个视图处理事件，程序将会发生什么？

• 忽略掉了这个事件当作什么都没有发生

图像显示原理

CALayer 的 contents 是位图

• CPU的工作

  Layout | Display | Prepare | Commite |
  ———|———–|————|———|
  UI布局 | 绘制 | 图片编解码 | 提交位图 |
  文本计算 |

• GPU渲染管线

  定点着色 | 图元转配 | 光栅化 | 片段着色 | 片段处理 |
  ——–|——–|——-|———|———|

提交到帧缓冲区（frameBuffer）

UI卡顿掉帧的原因

1/60 ms 时间内， 由cpu 和GPU 协同产生最终的数据，当 CPU UI布局，文本计算所用的时间较长时，留给GPU渲染，提交到帧缓冲区的时间就会变短，这样以来就会发生掉帧情况

UIView 的绘制原理

CPU优化方案

• 对象的创建、调整、销毁放在子线程，节省cpu的一部分时间
• 预排版（布局计算，文本计算）放在子线程中
• 预渲染（文本等异步绘制，图片编解码）等

GPU优化方案

在屏渲染

指GPU的渲染操作是在当前用于显示的屏幕缓冲区域中进行

离屏渲染

指GPU在当前屏幕缓冲区域外新开劈了一个缓冲区域进行渲染操作
指定了UI视图图层的某些属性，标记为视图在未预合成之前不能用于在当前屏幕上直接显示的时候就会发生离屏渲染，例如图层的圆角设置和蒙层设置

• 离屏渲染何时触发

  • 设置layer 的圆角并且和 maskToBounds 一起使用时
  • 图层蒙版
  • 阴影
  • 光栅化

• 为何要避免离屏渲染

  • 离屏渲染，会增加 GPU 的工作量，GPU工作量的增加就很有可能导致CPU和GPU的总耗时超过1/60s，导致UI卡顿和掉帧

• 避免离屏渲染

###异步绘制

自动引用计数

什么是自动引用计数

内存管理中对引用采取自动计数的技术

内存管理

• 自己生成的对象，自己所持有
  • alloc
  • new
  • copy
  • mutableCopy
• 非自己生成的对象，自己也能持有
  • retain
• 不再需要自己持有的对象时释放
  • release

• 非自己持有的对象无法释放

• 废弃对象

  • dealloc

__strong

__strong 修饰符表示对对象的“强引用”

__unsafe_unretained 修饰符

__unsafe_unretained 是不安全的所有权修饰符， 被它修饰的变量不属于编译器的内存管理对象

1

id __unsafe_unretained objc = [[NSObject alloc] init];

Xcode 提示：Assigning retained object to unsafe_unretained variable; object will be released after assignment

将保留对象赋给unsafe_unretain变量;对象将在赋值后释放

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

id __unsafe_unretained obj1 = nil;
   
   {
       id __unsafe_unretained obj = [[NSObject alloc] init];
       
       // 自己生成并持有对象
       // 因为obj0 变量是__strong,强引用，所以自己持有对象
       id __strong obj0 = [[NSObject alloc] init];
       
       // obj0 变量赋值给你obj1
       // ojb1 变量不持有对象的强应用，也不持有弱引用
       obj1 = obj0;
       
       
       // 输出 obj1 变量表示的对象
       NSLog(@"A: %@", obj1);
   } // obj0变量 超出了其作用域，强引用失效自动释放自己持有的对象，除此之外没有其他持有者，所以废弃该对象
   
   
   
   
   // 输出 obj1 变量表示的对象
   // obj1 变量表示的对象因为无持有者已经销毁，坏的内存访问
   NSLog(@"B: %@", obj1);

swift类型检查和类型转换

is 关键字类型检查

判断父类和子类之间的关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14

func typeCheck() {
    let programmer = Programmer(name: "老张-php")
    if dev is iOSDeveloper {
        print("iOS 开发者")
    } else {
        print("其他开发者")
    }
    
    if programmer is Coder {
        print("老张-php是一农个码农")
    } else {
        print("")
    }
}

as 关键字类型转换

1
2

let ios = iosDev as? Programmer
let ios2 = iosDev as! Coder

判断是否遵守了协议

swift 中协议可以当作是一个类型使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

et ios = iosDev as? Programmer
    let ios2 = iosDev as Coder
    
    // 是否遵守了 Person 协议
    if iosDev is Person {
        print("遵守了Person协议")
    }
    
    let devs = [dev, iosDev, programmer] as [Any]
    
    for dev in devs {
        if let dev = dev as? Person {
            print(dev)
            print("遵守Person协议")
        } else {
            print("未遵守Person协议")
        }
    }

AnyObject Any

1
2
3
4

var anyObjectArray: [AnyObject] = [CGFloat(0.5) as AnyObject,
                             			1 as AnyObject,
                             			"string" as AnyObject,
                         				iOSODev]

swift是面向函数编程， 函数是一等公民，数组中可以存入一个函数，函数表达的是一个过程，不是一个名词或者物体，所以函数不是一个对象,需要使用 any 关键字

1
2
3
4

var anyArray: [Any] = [CGFloat(0.5),
							1,
							"string", 
							iOSODev]

放入函数

1

anyArray.append({ (a: Int) -> (Int) in return a * a })

ReactNative配置.npm 和cnpm 相关

npm

Nodejs的包管理工具

npm 常用命令

• 更新或卸载

  1	npm update/uninstall moduleName

• 查看当前目录下已安装的包

  1

  npm list

• 查看全局安装的包的路径

  1	npm root -g

• 全部命令

  1

  npm help

cnpm

因为npm安装插件是从国外服务器下载，受网络影响大，可能出现异常，cnpm 淘宝镜像

安装

1

npm install -g cnpm --registry=https://registry.npm.taobao.org

设置镜像源

1
2

cnpm set registry http://registry.cnpm.taobao.com
npm set registry http://registry.cnpm.taobao.com

配置 .npmrc 文件

前端项目开发离不开安装各种npm依赖包，可以选择远程的仓库也可以选择本地的仓库，但更改仓库地址需要在安装时控制台打命令，比较麻烦， 而npmrc可以很方便地解决上面问题

.npmrc 原理

当安装项目的依赖包时，会查找并读取项目根目录下的.npmrc文件的配置，自动指定仓库地址

• 打开 .npmrc

  1	open .npmrc

• 编辑文件, 指定特定的库的镜像源, 比如以@test开头的库镜像为：http://registry.cnpm.test.com/ 而其他的正常

  1 2	@test:registry=http://registry.cnpm.lietou.com/ registry=https://registry.npm.taobao.org/