Git的其他参考文章：

• Git 面試題

• 問：用一般方式的合併，跟使用 rebase 方式合併，有什麼不同？各有何優缺點？

  一般的合併方式，有些情況（非快轉合併）會產生一個額外的 commit 來接合兩邊分支，而 rebase 合併分支跟一般的合併分支的明顯差別，就是使用 rebase 方式合併分支不會有這個合併的 Commit。

  如果就以最後的的結果來說，檔案內容來說是沒什麼差別，但在 Git 的歷史紀錄上來說就有一些差別，誰 rebase 誰，會造成歷史紀錄上先後順序不同的差別。例如 cat 分支 rebase 到 dog 分支的話，表示 cat 分支會被接到 dog 分支的後面；反之如果是 dog 分支 rebase 到 cat 上的話，表示 dog分支 會被接到 cat 分支的後面。

  使用 rebase 的好處，是整理出來的歷史紀錄不會有合併用的 commit，看起來比較乾淨（也是有些人不覺得這乾淨多少），另外歷史紀錄的順序可以依照誰 rebase 誰而決定先後關係（不過這點不一定是優點或缺點，端看整理的人而定）；缺點就是它相對的比一般的合併來得沒那麼直覺，一個不小心可能會弄壞掉而且還不知道怎麼 reset 回來，或是發生衝突的時候就會停在一半，對不熟悉 rebase 的人來說也許是個困擾。

  通常在還沒有推出去但感覺得有點亂（或太瑣碎）的 commit，我會先使用 rebase 來整理分支後再推出去。rebase 等於是在修改歷史，這個行為會做出平行時空，修改已經推出去的歷史可能會對其它人帶來困擾，所以對於已經推出去的內容，請不要任意使用 rebase。

【狀況題】怎麼有時候推不上去…

偶爾在執行 Push 指令的時候會出現這個錯誤訊息：

1
2
3
4
5
6
7
8
9

$ git push
To https://github.com/eddiekao/dummy-git.git
 ! [rejected]        master -> master (fetch first)
error: failed to push some refs to 'https://github.com/eddiekao/dummy-git.git'
hint: Updates were rejected because the remote contains work that you do
hint: not have locally. This is usually caused by another repository pushing
hint: to the same ref. You may want to first integrate the remote changes
hint: (e.g., 'git pull ...') before pushing again.
hint: See the 'Note about fast-forwards' in 'git push --help' for details.

這段訊息的意思是線上版本的內容比你電腦裡這份還要新，所以 Git 不讓你推上去。

怎麼造成的？

通常這個狀況會發生在多人一起開發的時候，想像一下這個情境：

1. Sherly 跟 Eddie 兩個人在差不多的時間都從 Git Server 上拉了一份資料下來準備進行開發。
2. Sherly 手腳比較快，先完成了，於是先把做好的成果推一份上去。
3. Eddie 不久後也完成了，但當他要推上去的時候發現推不上去了…

怎麼解決？

解決方法算是有兩招

第一招：先拉再推

因為你電腦裡的內容是比較舊的，所以你應該先拉一份線上版本的回來更新，然後再推一次：

1
2
3
4
5
6
7
8
9

$ git pull --rebase
remote: Counting objects: 3, done.
remote: Compressing objects: 100% (2/2), done.
remote: Total 3 (delta 1), reused 3 (delta 1), pack-reused 0
Unpacking objects: 100% (3/3), done.
From https://github.com/eddiekao/dummy-git
   37aaef6..bab4d89  master     -> origin/master
First, rewinding head to replay your work on top of it...
Applying: update index

這裡加了 --rebase 參數是表示「內容抓下來之後請使用 Rebase 方式合併」，當然你想用一般的合併方式也沒問題。合併如果沒發生衝突，接著應該就可以順利往上推了。

第二招：無視規則，總之就是聽我的！（誤）

凡事總有先來後到，在上面的例子中，Sherly 先推上去的內容，後推的人就是應該拉一份下來更新，不然照規定是推不上去的。不過這規則也是有例外，只要加上了 --force 或是 -f 參數，它就會強迫硬推上去，把 Sherly 之前的內容蓋掉：

1
2
3
4
5
6
7
8
9

$ git push -f
Counting objects: 19, done.
Delta compression using up to 4 threads.
Compressing objects: 100% (17/17), done.
Writing objects: 100% (19/19), 2.16 KiB | 738.00 KiB/s, done.
Total 19 (delta 6), reused 0 (delta 0)
remote: Resolving deltas: 100% (6/6), done.
To https://github.com/eddiekao/dummy-git.git
 + 6bf3967...c4ea775 master -> master (forced update)

雖然這樣一定會成功，但接下來你就要去面對 Sherly，跟她解釋為什麼你把她的進度蓋掉了。更多關於 Force Push 的說明，可參考「【狀況題】聽說 git push -f 這個指令很可怕，什麼情況可以用它呢？」章節介紹。

等待异步

有时候执行某个动作，需要等到另一个事件结束，可以用Completer类。

常见的有：

执行某个动作，需要弹窗等待用户选择某条件后再执行后续代码，

//事例

var c = Completer<bool>();
 
Dialogs.tipsCard(title, tip,
  failMsg: '',
  actions: [i18n.ok],
  callback: (index) => c.complete(true),
  dismissCallBack: () {
    if (!c.isCompleted)
      c.complete(false);
  },
);
 
return c.future;

其他：

Completer

Completer允许你做某个异步事情的时候，调用c.complete(value)方法来传入最后要返回的值。最后通过c.future的返回值来得到结果，（注意：宣告完成的complete和completeError方法只能调用一次，不然会报错）。看下面的例子更容易理解。

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

test() async {
   Completer c = new Completer();
   for (var i = 0; i < 1000; i++) {
     if (i == 900 && c.isCompleted == false) {
       c.completeError('error in $i');
     }
     if (i == 800 && c.isCompleted == false) {
       c.complete('complete in $i');
     }
   }

   try {
     String res = await c.future;
     print(res); //得到complete传入的返回值 'complete in 800'
   } catch (e) {
     print(e);//捕获completeError返回的错误
   }
 }

怎么将一个Callback回调转化成Future同步方法（Callback to Future），可以配套async / await去使用呢？

使用场景：dio请求使用call，但外部基本还是习惯使用future方式，为了减少接口的改动，使用callback转future方式。

参考文章：Flutter&Dart Callback转Future

compute

在一个页面中做耗时比较大的运算时，就算用了async / await异步处理， ui页面的动画还是会卡顿，因为还是在这个UI线程中做运算，异步只是说我可以先运行其他的，等我这边有结果再返回，但是，记住，我们的计算仍旧是在这个UI线程，仍会阻塞UI的刷新，异步只是在同一个线程的并发操作。

要解决这个卡顿问题，可以把运算移到另一个线程中，在dart中，这里不是称呼线程，是Isolate，直译叫做隔离，是因为隔离不共享数据，每个隔离中的变量都是不同的，不能相互共享。

Isolate的操作比较复杂，dart中封装了一层简单的实现

1
2

/// package:flutter/foundation.dart
Future<R> Function<Q, R>(FutureOr<R> Function(Q), Q, {debugLabel: String})compute

使用方法

1
2
3
4
5
6
7
8

import 'package:flutter/foundation.dart';

function callback( val ){
  ...
  return res
}
/// `callback` 必须是顶级方法或者是类的静态方法
var res = await compute( callback , val );

简单来讲就是运行var res = await compute( callback , val )函数。callback的传入参数是val, return的数据就是callback的res;

使用场景

• 方法执行在几毫秒或十几毫秒左右的，应使用Future
• 如果一个任务需要几百毫秒或之上的，则建议compute（只有一次返回）或Isolate（用于订阅或有多次返回的）

Flutter/Dart :如何在app启动前等待异步任务？

我在一个dart应用程序上工作，我想获取缓存(SharedPreferences)中存在的数据，然后在应用程序的UI (主屏幕)上显示它。

问题:由于SharedPreferences是一个等待调用，我的主页加载，试图读取数据，应用程序崩溃，因为还没有从SharedPreferences中获取数据，并且应用程序在此之前加载。

其他参考文章：

多任务

dart笔记13：用future实现等待多个任务完成后，再得到所有的执行结果

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

import 'dart:async';

void main() {
  print('start');

  Future task1 = Future(() {
    print('task1');
    return 1;
  });

  Future task2 = Future(() {
    print('task2');
    return 2;
  });

  Future task3 = Future(() {
    print('task3');
    return 3;
  });

  Future future = Future.wait([task1, task2, task3]);

  future.then((value) {
    print(value);
  }).catchError((e){
 
  });


  print('end');

  //执行结果：
  //start
  //end
  //task1
  //task2
  //task3
  //[1, 2, 3]
}

FutureBuilder

Flutter：使用 Completer 实现自定义任务队列

• Flutter：使用 Completer 实现自定义任务队列

环境变量

Mac 配置环境变量

环境变量的设置文件：

非M1类型的Mac：~/.bash_profile

是M1类型的Mac：~/.zshrc

修改方法：

非M1类型的Mac：终端输入open -n ~/.bash_profile

是M1类型的Mac：终端输入open -n ~/.zshrc

编辑完保存并退出

非M1类型的Mac：输入 source ~/.bash_profile 使环境变量生效。

是M1类型的Mac：输入 source ~/.zshrc 使环境变量生效。

• 图论算法——环和有向无环图

  寻找环利用了DFS方法，维护一个递归调用期间已访问的顶点的栈，若(在递归调用期间，通过判断onStack标记数组)两次访问了某个顶点，则说明有环；若DFS递归调用完毕，说明无环。

• 十一、谈谈设计模式

• 十二、如何优化过于臃肿的Controller

• 十三、谈谈性能优化(功耗)

• 十四、UITableView的优化、重用

• 十五、布局 layoutsubview、drawrect等

• 十六、有逼格的代码

• 十七、单元测试

• 十八、APP审核

• 常见笔试/面试题

• END

• iOS进阶–App功耗优化看这篇就够了
• iOS耗电量检测与优化

UITableView的优化、重用

< 返回目录

布局 layoutsubview、drawrect等

< 返回目录

有逼格的代码

typedef NSString * NSRunLoopMode NS_EXTENSIBLE_STRING_ENUM;
提升自己逼格的编程之美之代码规范
iOS开发细节 | 通知怎么写？
实现NS_ENUM的自定义反射

单元测试

< 返回目录

APP审核

< 返回目录

1、如何使用一个for循环输出九九乘法表

NSJSONSerialization

1
2

NSData *data = [operation.responseString dataUsingEncoding:NSUTF8StringEncoding];
    NSMutableDictionary *responseObject_dic = [NSJSONSerialization JSONObjectWithData:data options:NSJSONReadingMutableContainers | NSJSONReadingMutableLeaves error:nil];

//NSJSONReadingMutableContainers的作用: http://blog.csdn.net/chenyong05314/article/details/45691041

1
2
3

NSJSONReadingMutableContainers：返回可变容器，NSMutableDictionary或NSMutableArray。
NSJSONReadingMutableLeaves：返回的JSON对象中字符串的值为NSMutableString
NSJSONReadingAllowFragments：允许JSON字符串最外层既不是NSArray也不是NSDictionary，但必须是有效的JSON Fragment。例如使用这个选项可以解析 @“123” 这样的字符串。

iOS中常见Crash总结

• iOS中常见Crash总结
• iOS开发之调试技巧Xcode7中你一定要知道的炸裂调试神技、Address Sanitizer EXC_BAD_ACCESS

• iOS App 签名的原理 （非常好，非常详细的文章）

1. CertificateSigningRequest：本地公钥。
2. p12：本地私钥，可以导入到其他电脑。
3. 证书：内容是公钥或私钥，由其他机构对其签名组成的数据包。
4. Entitlements：包含了 App 权限开关列表。
5. Provisioning Profile：包含了 证书 / Entitlements 等数据，并由苹果后台私钥签名的数据包。

概览

四种方式安装一个APP的方式

1. 从 AppStore 下载
2. 开发 App 时可以直接把开发中的应用安装进手机进行调试。
3. In-House 企业内部分发，可以直接安装企业证书签名后的 APP。
4. AD-Hoc 相当于企业分发的限制版，限制安装设备数量，较少用。

区别：

App Store 下载的是Apple后台用私钥A对其进行重签名，

而其他的是用Xcode配置的对应该证书的本地私钥L对app进行签名。

一、App Store 下载的签名机制（最简单的签名）

当App 提交审核通过后，Apple会对App重签名，所以从App Store下载的app都是苹果的官方签名。

流程如下：

1、Apple 官方有自己固定的一对公钥和私钥，私钥A存在Apple后台，公钥A存在iOS设备

2、app审核通过后，Apple后台用私钥A对其进行重签名

3、app下载到iOS设备后，iOS设备内置的公钥A会对app的签名进行验证

4、如果验证通过，则可运行，否则不能

当然除了这个方式，还有一下三种方式安装一个app：

1. 开发时，直接通过USB将应用安装到手机进行调试；
2. In-House 企业内部分发，可直接安装企业证书签名的App；
3. Ad-Hoc 相当于企业分发的限制版，限制安装设备数量。

①、KeyChain 里的“从证书颁发机构请求证书”，本地生成一对公私钥。（其中：公钥L是保存的CertificateSigningRequest(CSR)，而私钥L保存在电脑本地，可以导出为p12）

附：Apple 官方也有自己固定的一对公钥和私钥，私钥A存在Apple后台，公钥A内置在iOS设备

（因为这里的这个私钥是本地Mac持有，所以团队开发时，可在KeyChain导出私钥，存为.p12文件，其他Mac即可导入这个私钥）

2、在Member Center把CertificateSigningRequest上传到苹果后台生成证书（即上传之后Apple后台用Apple 官方自己固定的私钥A对我们上传的公钥L进行签名，将得到的签名+公钥L打包起来，称为证书），下载到本地。

Apple 官方有自己固定的一对公钥和私钥，私钥A存在Apple后台，公钥A内置在iOS设备

3、在Member Center配置AppID、添加设备UUID／Entitlements, 生成app对应的 Provisioning Profile 文件，并下载到本地
4、在XCode中配置好证书，打包编译时，**用Xcode配置的对应该证书的本地私钥L对app进行签名，并把 Provisioning Profile 文件一起打包进App去(文件名为 embedded.mobileprovision)**。这里对App的签名数据分两部分，Mach-O 可执行文件把签名直接写进这个文件，其他资源文件则保存在_CodeSignature目录下

5、安装APP到手机上时，iOS设备内置的公钥A(指Apple官方自己固定的公钥)对embedded.mobileprovision的数字签名进行验证，同时对里面的证书的签名也会验证
如果验证通过，确保了embedded.mobileprovision的数据是苹果授权后，再取出里面数据做各种验证，包括公钥L对app签名进行验证，验证设备ID，AppID，权限开关。

前言：你真的懂isEqual与hash？

参考文章：

• iOS开发 之 不要告诉我你真的懂isEqual与hash!
• 哈希算法详解（附带 iOS 开发中实际应用）
• iOS weak关键字实现原理

eg：

1
2

1、NSMutableSet/NSSet中添加对象的时候，就会调用- (NSUInteger)hash方法。
2、NSMutableSet/NSSet中添加 obj2 对象的时候，如果NSMutableSet/NSSet 中之前就已经存在 obj1 对象，且 obj1 对象的 - (NSUInteger)hash 返回值和当前要添加的 obj2 的- (NSUInteger)hash 返回值相等, 则 obj2 会继续调用- (BOOL)isEqual:方法，其中此方法以 obj1 为参数；否则不等, 继续下一个元素判断。

通过重写isEqual，我们可以做到对象的判等可以完全由您决定, 即使两个完全不同的对象。

一、基础

1、nil, Nil,NULL 与 NSNull 的区别

• nil 指向一个对象的指针为空,在objc.h 的定义如下: NSString *name = nil;
• Nil 指向一个类的指针为空,定义如下: Class aClass = Nil;
• NULL 指向C类型的指针为空, 例如: int*pInt = NULL;
• NSNull 在Objective-C中是一个类,只是名字中有个Null，多用于集合(NSArray,NSDictionary)中值为空的对象

2、==、 isEqualToString、isEqual

2.1、背景：为什么要有isEqual方法?

答：判断两个对象是否相等（而不是判断两个对象的地址是否相等）。

对于基本类型, ==运算符比较的是值;
对于对象类型, ==运算符比较的是对象的地址(即是否为同一对象)

1
2
3
4
5
6
7
8

UIColor *color1 = [UIColor colorWithRed:0.5 green:0.5 blue:0.5 alpha:1.0];
UIColor *color2 = [UIColor colorWithRed:0.5 green:0.5 blue:0.5 alpha:1.0];
NSLog(@"color1 == color2 = %@", color1 == color2 ? @"YES" : @"NO");
NSLog(@"[color1 isEqual:color2] = %@", [color1 isEqual:color2] ? @"YES" : @"NO");

// 打印结果如下：
color1 == color2 = NO
[color1 isEqual:color2] = YES

总结：

1、==
判断指针指向的地址，即指针值，是否相等
①对于基本类型, ==运算符比较的是值;
②对于对象类型, ==运算符比较的是对象的地址(即是否为同一对象)）

2、isEqualToString
直接判断字符串内容是否相等

3、isEqual
先判断两个对象的地址是否相同，再判断类型是否一致，然后再判断对象的具体内容是否一致
//情况①：地址相同则肯定相等；
//情况②：地址不同时候，如果类型一致且里面的内容相等，则也算相等

2.1、苹果官方重写isEqual 的demo

isEqual：先判断两个对象的地址是否相同(采用==)，再判断类型是否一致(采用isKindOfClass)，然后再判断对象的具体内容是否一致

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

- (BOOL)isEqual:(id)object {
    if (self == object) {
        return YES;
    }

    if (![object isKindOfClass:[Person class]]) {
        return NO;
    }

    return [self isEqualToPerson:(Person *)object];
}

- (BOOL)isEqualToPerson:(Person *)person {
    if (!person) {
        return NO;
    }

    BOOL haveEqualNames = (!self.name && !person.name) || 
      										[self.name isEqualToString:person.name];
    BOOL haveEqualBirthdays = (!self.birthday && !person.birthday) || 
      										[self.birthday isEqualToDate:person.birthday];

    return haveEqualNames && haveEqualBirthdays;
}

附：通过重写isEqual，我们可以做到对象的判等可以完全由您决定, 即使两个完全不同的对象。

2.2、==、 isEqualToString、isEqual验证示例

四、weak

以下内容来自： iOS weak关键字实现原理

• 1、weak关键字修饰对象的【初始化及重新赋值】实现原理
• 2、weak关键字是如何保证在weak对象执行语句时内存对象不被释放的呢？
• 3、当weak对象指向的内存对象被释放后，weak对象自动置为nil。原理是怎样？

1、weak关键字修饰对象初始化及重新赋值实现原理

objc_initWeak：当初始化一个weak对象并将内存对象赋值给该weak对象时会调用该方法。

objc_storeWeak：当为一个weak对象赋新值时会调用该方法。

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

objc_initWeak(id *location, id newObj)
{
    //对内存对象进行非nil判断
    if (!newObj) {
        *location = nil;
        return nil;
    }
    
    //调用storeWeak方法，三个参数的意义在storeWeak方法中描述
    return storeWeak<false/*old*/, true/*new*/, true/*crash*/>
        (location, (objc_object*)newObj);
}

1
2
3
4
5
6

objc_storeWeak(id *location, id newObj)
{
    //调用storeWeak方法，三个参数的意义在storeWeak方法中描述
    return storeWeak<true/*old*/, true/*new*/, true/*crash*/>
        (location, (objc_object *)newObj);
}

由官方文档可知，无论是初始化weak对象还是为weak对象赋值，最终都会调用到 storeWeak方法，不同点在于，二者传入三个模板值不同。

如果weak对象与旧内存对象的关联，则先调用weak_unregister_no_lock，将weak对象与旧内存对象解除指向关系。

然后在将weak对象与旧内存对象的关联解除后，就调用 weak_register_no_lock方法将weak对象与新内存对象进行关联

至此，weak关键字修饰对象的初始化和重新赋值流程就完成了。

2、weak关键字是如何保证在weak对象执行语句时内存对象不被释放的呢？

问：weak关键字是如何保证【在weak对象执行语句时】内存对象【不被释放】的呢？

答：其实很简单，就是对内存对象进行计数增加。

每次在使用weak对象时，都相当于调用一次 objc_loadWeak。

在weak对象执行的语句中，weak对象所指向的内存对象计数会+1，这样就保证在语句中不会发生执行一半而释放内存对象的问题。

3、当weak对象指向的内存对象被释放后，weak对象自动置为nil。原理是怎样？

当内存对象释放时，会调用到一个叫weak_claer_no_lock的方法。在 weak_claer_no_lock方法中，会进行对weak对象的置空操作。

4、Weak-Strong搭配使用的误解

在使用Block时，我们可以使用weak关键字来避免外部变量被Block强引用而导致的循环引用，同时为了Block中的代码能够正常执行，许多开发者提出了Weak-Strong搭配使用的方式，类似如下：

1
2
3
4
5
6
7
8

{
    __weak typeof(self) weakSelf = self;
    self.block = ^{
        __strong typeof(weakSelf) strongSelf = weakSelf;
        [strongSelf test1];
        [strongSelf test2];
    };
}

以上代码相对于单独使用weak来说还是有好处的，使用Weak-Strong搭配的方式的话，可以保证在执行 [strongSelf test1]和 [strongSelf test2]时，是向同一对象发送消息。

为什么这么说呢？当开始执行Block语句时，若self还存在，那么strongSelf可以保证在整个Block代码块中不会被释放，即使Block中调用无数次strongSelf，strongSelf也不会因为多线程而在半途被释放；若开始执行Block时，self已经被释放，那么之后所有的消息都会被发送至nil。所以Weak-Strong搭配可以保证Block中语句被处理为一个事务。

1
2
3
4
5
6
7

{
    __weak typeof(self) weakSelf = self;
    self.block = ^{
        [weakSelf test1];	// 可能这时候self还没释放，有值。
        [weakSelf test2];	// 而到这时候self刚好释放，为ni。导致Block中语句不是被发送给同一对象去处理。
    };
}

所以说，Weak-Strong并不能保证Block中语句一定会被执行，它只能保证Block中语句作为一个事务被发送到同一对象处。只要理解了weak实现原理，我们就能明白何时单独使用weak也能完成代码功能，而何时必须使用Weak-Strong来保证代码事务能力。

5、weak关键字涉及到的数据结构

略。请查看 iOS weak关键字实现原理

1、SideTables

SideTables本质上是一个全局的 StripedMap。而StripedMap本质是一个数组。

在 SideTables中， Item类型为 SideTable

2、SideTable

SideTable中包含三个元素，分别是 1.自旋锁 2.记录对象引用计数的字典 3.记录对象弱引用信息的数据结构 weak_table_t。

3、weak_table_t

weak_table_t本质上是一个数组，其中每个Item为 weak_entry_t。

4、weak_entry_t

weak_entry_t就比较有意思了，它本质上是个字典。其中的key值为对象，而value对应为一个数组，数组中保存的值均为 weak_referrer_t类型的数据。

5、weak_referrer_t

weak_referrer_t本质上是 objc_object **，即Objective-C对象的地址。

所以，weak_entry_tvalue数组中，每一个Item均为一个地址，即weak对象的地址。

在项目中有某个功能需要用到多个delegate对象，这就需要把delegate放到容器中，但又只能弱引用weak保存delegate，否则会导致delegate对象不能被释放。所以，我们的需求就是希望能在容器中只保存弱引用的delegate对象。

在OC中Foundation框架中的常用容器类（NSSet，NSDictionary，NSArray）及其可变子类在加入元素时，均会对元素进行强引用。有的时候（比如持有多个Delegate对象时），希望有对应的弱引用容器使用。

支持弱引用的容器类，有如下：

[NSHashTable weakObjectsHashTable]

[NSPointerArray weakObjectsPointerArray]

[NSPointerArray pointerArrayWithOptions:]

详见：YYKit学习笔记之NSHashTable与NSMapTable

其他参考：

• OC弱引用容器实现方案总结

• iOS如何在容器类中使用弱引用(weak reference)

• 数组或字典如何弱引用对象

• iOS - 如何实现弱引用字典

*在iOS项目开发过程中，我们经常会使用到NSSet、NSArray、NSDictionary三个类，它们为我们设计较友好的数据结构时提供了很方便的方法*

对于NSSet来说，object是强引用的，和NSDictionary中的value是一样的。而NSDictionary中的key则是copy的，因此当开发者想要使NSSet的objects或者NSDictionary的values为weak，或者NSDictionary使用没有实现协议的对象作为key时，比较麻烦（需要使用NSValue的方法valueWithNonretainedObject）。
还好苹果为我们提供了相对于NSSet和NSDictionary更通用的两个类NSHashTable和NSMapTable。

关联对象实现原理

iOS底层原理总结 - 关联对象实现原理

关联对象并不是存储在被关联对象本身内存中，而是存储在全局的统一的一个AssociationsManager中，如果设置关联对象为nil，就相当于是移除关联对象。

回过头来看objc_AssociationPolicy policy 参数: 属性以什么形式保存的策略。

1
2
3
4
5
6
7
8

typedef OBJC_ENUM(uintptr_t, objc_AssociationPolicy) {
    OBJC_ASSOCIATION_ASSIGN = 0,  // 指定一个弱引用相关联的对象
    OBJC_ASSOCIATION_RETAIN_NONATOMIC = 1, // 指定相关对象的强引用，非原子性
    OBJC_ASSOCIATION_COPY_NONATOMIC = 3,  // 指定相关的对象被复制，非原子性
    OBJC_ASSOCIATION_RETAIN = 01401,  // 指定相关对象的强引用，原子性
    OBJC_ASSOCIATION_COPY = 01403     // 指定相关的对象被复制，原子性   
};
复制代码

我们会发现其中只有RETAIN和COPY而为什么没有weak呢？

NSPointerArray

1、NSPointerArray

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

- (instancetype)init {
  if (self = [super init]) {
    _delegates = [NSPointerArray weakObjectsPointerArray];
  }
  return self;
}

// 添加对象指针
- (void)addDelegate:(id)delegate {
  [_delegates addPointer:(__bridge void*)delegate];
}
// 和 NSArray在概念上不一样的地方是，NSPointerArray需要添加的是对象的指针地址，尽管他俩都是在操作指针。所以在添加对象时，需要将其转换为指针类型，__bridge转换十分具有 CoreFoundation特色


// 移除对象指针
- (void)removeDelegate:(id)delegate {
  NSUInteger index = [self indexOfDelegate:delegate];
  if (index != NSNotFound) {
    [_delegates removePointerAtIndex:index];
  }
  [_delegates compact];
}

- (NSUInteger)indexOfDelegate:(id)delegate {
  for (NSUInteger i = 0; i < _delegates.count; i += 1) {
    if ([_delegates pointerAtIndex:i] == (__bridge void*)delegate) {
      return i;
    }
  }
  return NSNotFound;
}

Here are main question we will ask during interview:
1.Data Structure:
a.linked lists
b.Stacks
c.Queues
d.binary trees
e.hash tables
2.Algorithms:
a.Sort (like quick sort and merge sort), binary search, greedy algorithms.
b.Binary tree(like traversal, construction, manipulation..)
You can find more to do exercises on https://leetcode.com/

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

以下是我们在面试中要问的主要问题：

1.数据结构：
a、 链接列表
b、 堆栈
c、 队列
d、 二叉树
e、 哈希表

2.算法：
a、 排序（像快速排序和合并排序），二进制搜索，贪婪算法。
b、 二叉树（比如遍历、构造、操作…）

你可以找到更多的练习https://leetcode.com/

一、二叉树

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。

在二叉树中，一个元素也称作一个结点。

节点:二叉树中每个元素都称为节点。

叶子结点：就是出度为0的结点，就是没有子结点的结点。

二、几种二叉树

满二叉树、完全二叉树、平衡二叉树、最优二叉树

1、完全二叉树

若设二叉树的深度为k，除第 k 层外，其它各层 (1～k-1) 的结点数都达到最大个数，第k 层所有的结点都连续集中在最左边，这就是完全二叉树。

2、满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。

也就是说，如果一个二叉树的层数为K，且结点总数是(2^k) -1 ，则它就是满二叉树。

满二叉树的第i层上有2

个结点 (i≥1)。

满二叉树肯定是完全二叉树，而完全二叉树不一定是满二叉树。

3、平衡二叉树

一文读懂平衡二叉树｜技术头条

二叉搜索树（Binary Search Tree），又叫二叉排序树，简单而言就是左子树上所有节点的值均小于根节点的值，而右子树上所有结点的值均大于根节点的值，左小右大，并不是乱序，因此得名二叉排序树。

二叉搜索树的结构与值的插入顺序有关，同一组数，若其元素的插入顺序不同，二叉搜索树的结构是千差万别的。

为了避免二叉搜索树变成“链表”，我们引入了平衡二叉树(平衡二叉树必须是二叉搜索树)，即让树的结构看起来尽量“均匀”，左右子树的节点数尽量一样多。

举例：给出一组数[1,3,5,8,9,13]。假设我们就按[1,3,5,8,9,13]这样的顺序插入，其流程是这样的：

4、最优二叉树（哈夫曼树）

漫画：什么是 “哈夫曼树”？

在介绍哈弗曼树之前，我们必须先弄清楚和树相关的四个概念。

概念1：什么是路径？

在一棵树中，从一个结点到另一个结点所经过的所有结点，被我们称为两个结点之间的路径。

概念2：什么是路径长度？

在一棵树中，从一个结点到另一个结点所经过的“边”的数量，被我们称为两个结点之间的路径长度。

概念3：什么是结点的带权路径长度？

结点的带权路径长度，是指树的【根结点到该结点的路径长度】和【该结点权重】的【乘积】。

概念4：什么是树的带权路径长度？

在一棵树中，【所有】【叶子结点】的带权路径长度之和，被称为树的带权路径长度，也被简称为WPL。

哈夫曼树（Huffman Tree）是在叶子结点和权重确定的情况下，带权路径长度最小的二叉树，也被称为最优二叉树。

问：怎样构建二叉树，才能保证其带权路径长度最小？

答：原则上，我们应该让权重小的叶子结点远离树根，权重大的叶子结点靠近树根。

例：下图左侧的这棵树就是一颗哈夫曼树，它的WPL是46，小于之前例子当中的53。

1*3+3*3+4*2+6*2+8*2=48 （3+6)*3+（1+4+8）*2=27+26=53

需要注意的是，同样叶子结点所构成的哈夫曼树可能不止一颗，下面这几棵树都是哈夫曼树

问：怎么利用给定的结点和权重，构建哈弗曼树？

答：想看 漫画：什么是 “哈夫曼树”？ 还是很好理解的。

二叉树遍历

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。

参考文章：二叉树的遍历（前序、中序、后序、已知前中序求后序、已知中后序求前序）

前序遍历：根节点->左子树->右子树（根->左->右）

中序遍历：左子树->根节点->右子树（左->根->右）

后序遍历：左子树->右子树->根节点（左->右->根）

• 前序遍历结果：GDAFEMHZ
• 中序遍历结果：ADEFGHMZ
• 后序遍历结果：AEFDHZMG

进入正题，已知两种遍历结果求另一种遍历结果（其实就是重构二叉树）

1、前序遍历的第一元素是整个二叉树的根节点

2、中序遍历中根节点的左边的元素是左子树，根节点右边的元素是右子树

3、后序遍历的最后一个元素是整个二叉树的根节点

一、Stack

stack翻译为栈，时STL中实现的一个后进先出的容器。

一、单链表

• 算法面试题：如何判断单链表中是否存在环

我们都知道单链表中结点都是一个结点指向下一个结点这样一个一个链接起来的，直到尾结点的指针域没有指向，单链表就到此结束了。

题目：已知下列是一个有环的单链表，请问如何判断单链表是否存在环

分析：把环想象成操作。

则我们通过使用快慢指针判断单链表是否存在环。
使用slow、fast 2个指针，slow慢指针每次向前走1步，fast快指针每次向前走2步，
若存在环的话，必定存在某个时候 slow = fast 快慢指针相遇。
list 带头结点的单链表
返回值 >0:存在环返回环的位置 0:不存在环

在相遇点，由于两个指针继续一个走一步，一个走两步，当再次相遇时，走一步的指针所走过的节点数记为环/操场的长度。

*那么问题来了，既然知道该单链表是代码单链表，那么我怎样将其还原为正常单链表呢？*

带环单链表去掉环

我们只需要将尾结点的next指针域置为NULL就还原为正常单链表了。我们怎样找到尾结点呢？请看代码。

1. 去掉单链表中的环，将尾结点的next域置位空。
2. 环位置结点之后的结点，判断其next域是否为环结点，如果是环节点，说明是尾结点