必备知识架构-数据结构

[toc]

一、Stack

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

必备知识架构-数据结构

[toc]

一、单链表

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

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

有环的单链表

分析：把环想象成操作。

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

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

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

带环单链表去掉环

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

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

必备知识架构-数据结构

[toc]

一、

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

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

必备知识架构-数据结构-①nil、isEqual

[toc]

前言：你真的懂isEqual与hash？

参考文章：

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验证示例

equal

四、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

其他参考：

在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;
}

必备知识架构-数据结构

[toc]

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

img

个结点 (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

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

哈弗曼树2

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

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

二叉树遍历

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

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

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

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

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

二叉树遍历

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

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

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

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

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

数据结构-②哈希表

[toc]

二、Hash

1、背景

为了提高在一堆数据中查找指定数据的速度，我们引入hash。

问：为什么需要hash？

答：为了提高查找的速度。(附：主要是用于在Hash Table查询成员用的)

问：和数组相比，基于hash值索引的Hash Table【查找某个成员的过程】就是

Step 1: 通过hash值直接找到查找目标的位置；
Step 2: 如果目标位置上有多个相同hash值得成员, 此时再按照数组方式进行查找。

问：基于hash值索引的Hash Table在【查找某个成员的过程】如何确定找的对象是我们想要的？或hash方法与isEqual的关系?（优化判等）

答：我们以基于hash的NSSet和NSDictionary举例，其在判断成员是否相等时, 为了优化判等的效率，会这样做
Step 1: 集成成员的hash值是否和目标hash值相等, 如果相同进入Step 2, 如果不等, 直接判断不相等；
Step 2: hash值相同(即Step 1)的情况下, 再进行对象判等, 作为判等的结果。

2、Hash 表的实际应用

  • 应用1：找出两文件找出重复的元素

假设有两个文件，文件中均包含一些短字符串，字符串个数分别为n。它们是有重复的字符串，现在需要找出所有重复的字符串。
最笨的解决办法可能是：遍历文件 1 中的每个元素，取出每一个元素分别去文件 2 中进行查找，这样的时间复杂度为O（n^2）。
但是借助 Hash 表可以有一种相对巧妙的方法，我们知道相同元素的 Hash 值相同。所以我们分别遍历文件 1 中的元素和文件 2 中的元素，然后放入 Hash Table 中，对于遍历的每一个元素我们只要简单的做一下计数处理即可。最后遍历整个 Hash 列表，找出所有个数大于 1 的元素即为重复的元素。

  • 应用2：找出两文件找出出现次数最多的元素

同找出两文件找出重复的元素这样的问题解决方案类似，只是在最后遍历的时找计数最大的元素，即为出现次数最多的元素。

3、hash什么时候调用

hash方法只在对象被添加至NSSet和设置为NSDictionary的key时会调用。

HashTable是一种基本数据结构，NSSet和NSDictionary都是使用HashTable存储数据的，因此可以可以确保他们查询成员的速度为O(1)。而NSArray使用了顺序表存储数据，查询数据的时间复杂度为O(n)。

三、哈希(Hash)表/散列表

参考文章：

哈希（Hash）的本质是一种算法，它能够将任意长度的输入（通常是字符串）通过一系列复杂的计算转换成固定长度的输出，这个输出被称为哈希值或哈希码。

NSDictionary 通常是基于哈希表的数据结构。在 NSDictionary 中，键（key）通过哈希函数转换成一个哈希值，然后使用这个哈希值来找到键值对在内存中的存储位置。

哈希表提供了快速的查找、插入和删除操作，这些操作的平均时间复杂度是 O(1)。

1、哈希函数 & Hash地址

要想知道什么是哈希表，那得先了解哈希函数。

hash函数就是根据key计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表

地址index=H（key）

通过Hash函数和关键字计算出来的存储位置（注意这里的存储位置只是表中的存储位置，并不是实际的物理地址）称作为Hash地址。

重要：相同元素的 Hash 值相同。附：两个相等的实例，他们的hash值一定相等。但是hash值相等的两个实例，不一定相等。

2、哈希函数的构造方法

除留余数法用的较多，H（key）=key MOD p （p<=m，m为表长，p为质数时候可以减少地址冲突）

比如key = 7，39，18，24，33，21时取表长m为9，p为7 那么存储如下

index 0 1 2 3 4 5 6 7 8
key 7 21(冲突后移) 24 39 18(冲突后移) 33(冲突后移)

哈希冲突的解决

哈希冲突即不同key值产生相同的地址，H（key1）=H（key2）。

比如我们上面说的存储7和21，p取7时 7 MOD 7 == 21MOD 7。此时7和21都发生了hash冲突。上面的哈希冲突解决方案我们使用的是开放寻址法（Open Addressing）：当发生冲突时，会寻找表中的下一个空闲位置来存储元素。这通常通过某种探测序列（如线性探测、二次探测或双重散列）来实现。开放寻址法处理冲突的基本原则就是出现冲突后按照一定算法查找一个空位置存放。

其他哈希冲突解决方案：

链地址法（Chaining）：每个哈希表槽位（或称为“桶”）都关联一个链表，所有映射到该索引的元素都存储在这个链表中。这种方法在处理冲突时比较简单，且无堆积现象，非同义词决不会发生冲突，因此平均查找长度较短。链地址法适用于经常进行插入和删除的情况，且在用链地址法构造的散列表中，删除结点的操作易于实现。

哈希表的扩容：

哈希表的大小，即桶（buckets）的数量，是根据存储在其中的对象数量动态变化的。当字典中的元素数量增加到某个阈值时，哈希表会进行扩容，通常是通过增加桶的数量来实现的，以保持操作的效率。

当哈希表进行扩容时，表中的桶（buckets）数量会增加，这意味着原有的哈希值可能不再适用于新的桶数组。因此，当扩容发生时，存储在哈希表中的所有键值对的哈希值通常会重新计算，以便将它们分配到新的桶位置。

在处理哈希冲突时，可能使用开放定址法来解决冲突，这种方法会在哈希表中寻找下一个空闲的桶来存储新的键值对。当哈希表的负载因子（即已使用的桶与总桶数量的比率）达到一定阈值时，哈希表会进行扩容，通常是通过增加桶的数量来实现的。这样可以保持哈希表的操作效率，使得查找、插入和删除操作的平均时间复杂度接近 O(1)。附：数组查找元素需要 O(n) 的时间复杂度，因为它可能需要遍历整个数组。所以哈希表相比数组，查找效率更高。除此之外，哈希表可以在插入时快速检查重复，这对于确保集合中元素的唯一性非常有用。

4、hash表的查找

查找过程和造表过程一致，假设采用开放定址法处理冲突，则查找过程为：
对于给定的key，计算hash地址index = H（key）
如果数组arr【index】的值为空 则查找不成功
如果数组arr【index】== key 则查找成功
否则 使用冲突解决方法求下一个地址，直到arr【index】== key或者 arr【index】==null

哈希表（hash table，也叫散列表），是根据键（key）直接访问访问在内存储存位置的数据结构。

哈希表本质是一个数组，数组中的每一个元素成为一个箱子，箱子中存放的是键值对。根据下标index从数组中取value。关键是如何获取index，这就需要一个固定的函数（哈希函数），将key转换成index。

哈希表—什么是哈希表 有助于理解哈希表

必备知识架构-线程-⑤面试

[toc]

六、队列 -> 任务 -> 线程 -> 数据安全

有队列，就有需要处理的任务，有任务就有线程相关的要考虑(附队列本身也处在线程中)，有多线程的考虑，就要考虑数据安全。

常见笔试/面试题

3、队列和数据安全

那我们先来知道一个非常重要的事情：

——- 队列只是负责任务的调度，而不负责任务的执行 ———

——- 任务是在线程中执行的 ———

所以，这个问题其实问得就不大对。让人不知怎么答。

我们这里说下，分情况。

如果是串行队列，数据是安全的。

如果是并发队列，在读写的时候，数据是不安全的。我们可以通过以下几种方式将其处理成安全的。

①、并发队列，改成串行执行。

可以通过

任务是同步任务；

异步任务用依赖；

异步任务用信号量控制并发量为1

②、加锁

@synchronized

NSLock

dispatch_semaphore

必备知识架构-线程与网络-①锁

[toc]

–

知识架构

iOS知识库

Android知识库

四、线程安全问题

< 返回目录

1、线程安全

当多个线程访问同一块资源时，很容易引发数据错乱和数据安全问题。就好比几个人在同一时修改同一个表格，造成数据的错乱。

参考：iOS中保证线程安全的几种方式与性能对比

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
性能对比
对以上各个锁进行1000000此的加锁解锁的空操作时间如下：
OSSpinLock: 46.15 ms
dispatch_semaphore: 56.50 ms
pthread_mutex: 178.28 ms
NSCondition: 193.38 ms
NSLock: 175.02 ms
pthread_mutex(recursive): 172.56 ms
NSRecursiveLock: 157.44 ms
NSConditionLock: 490.04 ms
@synchronized: 371.17 ms

总的来说：

OSSpinLock 自旋锁(性能最高的锁)和 dispatch_semaphore 信号量的效率远远高于其他。
@synchronized和NSConditionLock效率较差。

dispatch_semaphore 是信号量，但当信号总量设为 1 时也可以当作锁来。相对于 OSSpinLock 来说，它的优势在于等待时不会消耗 CPU 资源。
OSSpinLock 自旋锁，性能最高的锁。原理很简单，就是一直 do while 忙等。它的缺点是当等待时会消耗大量 CPU 资源，所以它不适用于较长时间的任务。 不过最近YY大神在自己的博客不再安全的 OSSpinLock中说明了OSSpinLock已经不再安全，请大家谨慎使用。 


鉴于OSSpinLock的不安全，所以我们在开发中如果考虑性能的话，建议使用dispatch_semaphore。
如果不考虑性能，只是图个方便的话，那就使用@synchronized。

NSDateFormatter在iOS7之后(包括iOS7)才是线程安全的

2、死锁

死锁是指两个或两个以上的进程（线程）在运行过程中因争夺资源而造成的一种僵局（Deadly-Embrace) ) ，若无外力作用，这些进程（线程）都将无法向前推进。

死锁的4个必要条件

一、@synchronized

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
NSObject *obj = [[NSObject alloc] init];
  
  dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
      @synchronized(obj) {
          NSLog(@"需要线程同步的操作1 开始");
          sleep(3);
          NSLog(@"需要线程同步的操作1 结束");
      }
  });
  
  dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
      sleep(1);
      @synchronized(obj) {
          NSLog(@"需要线程同步的操作2");
      }
  });

@synchronized(obj)指令使用的obj为该锁的唯一标识，只有当标识相同时，才为满足互斥，如果线程2中的@synchronized(obj)改为@synchronized(self),刚线程2就不会被阻塞，

二、NSLock

1
2
3
4
5
6
7
8
9
NSLock *lock = [[NSLock alloc] init];
  dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
      [lock lock];	// 加锁
    	NSLog(@"需要线程同步的操作1 开始");
    	sleep(2);
    	NSLog(@"需要线程同步的操作1 结束");
      [lock unlock]; // 解锁
      
  });

三、NSRecursiveLock递归锁的使用

我们先写一个典型的死锁情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
NSLock *lock = [[NSLock alloc] init];	// 此锁在本代码中会造成死锁
//NSRecursiveLock *lock = [[NSRecursiveLock alloc] init]; //要想下面的递归调用不会造成死锁，只要这里将锁改成递归锁NSRecursiveLock就可以了。NSRecursiveLock递归锁，这个锁可以被同一线程多次请求，而不会引起死锁。这主要是用在循环或递归操作中。

dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{

    static void (^RecursiveMethod)(int);

    RecursiveMethod = ^(int value) {
        [lock lock];
        if (value > 0) {
            NSLog(@"value = %d", value);
            sleep(2);
            RecursiveMethod(value - 1);	// 此时lock还没解锁，就有执行这个block，而block里又给加了次锁，从而造成了死锁
        }
        [lock unlock];
    };

    RecursiveMethod(5);
});

在是跟你面的代码中，在我们的线程中，RecursiveMethod是递归调用的。所以每次进入这个block时，都会去加一次锁，而从第二次开始，由于锁已经被使用了且没有解锁，所以它需要等待锁被解除，这样就导致了死锁，线程被阻塞住了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
NSLock *lock = [[NSLock alloc] init];

dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{

    static void (^RecursiveMethod)(int);

    RecursiveMethod = ^(int value) {
        if (value > 0) {
            NSLog(@"value = %d", value);
            sleep(2);
            RecursiveMethod(value - 1);
        }
    };

		[lock lock];
    RecursiveMethod(5);
    [lock unlock];
});

四、NSCondition & NSConditionLock 条件锁

wait方法是傻等；

waitUntilDate:方法是等一会；

signal是唤起一个在等待的线程。

通过wait()和waitUntilDate(limit: NSDate) -> Bool这两个方法都可以实现线程阻塞即线程睡眠。

不同之处在于

wait()会使线程一直处于休眠状态，直到收到signal()为止；

而waitUntilDate(limit: NSDate) -> Bool在使线程睡眠的同时会设置睡眠的终止时间。

如果在终止时间前收到了signal()就会唤醒线程；
当到达终止时间的时候，即使没有收到signal()，也会直接唤醒线程，而不会像wait()方法那样一直睡眠下去。

1、NSCondition

基本的条件锁，手动的控制。wait

2、NSConditionLock 条件锁

条件锁，这里的条件并不是bool表达式中的条件，而是一个特定的int值。

条件锁，不是简单的加锁/解锁， 而是需要根据一定条件满足后进行 加锁/解锁.

以一个生产中与消费者的例子，介绍条件锁的用法。

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
static NSInteger CONDITION_NO_DATA        //条件一： 没有数据
static NSInteger CONDITION_HAS_DATA       //条件二： 有数据

// 初始化锁时，指定一个默认的条件
NSConditionLock *lock = [[NSConditionLock alloc] initWithCondition:CONDITION_NO_DATA];

//生产者，加锁与解锁的过程
while (YES) {
    
    //1. 当满足 【没有数据的条件时】进行加锁
    [lock lockWhenCondition:CONDITION_NO_DATA];

    //2. 生产者生成数据 
    //.....

    //3. 解锁，并设置新的条件，已经有数据了
    [locker unlockWithCondition:CONDITION_HAS_DATA];
}


//消费者，加锁与解锁的过程 
while (YES) {
    
    //1. 当满足 【有数据的条件时】进行加锁
    [lock lockWhenCondition:CONDITION_HAS_DATA];

    //2. 消费者消费数据 
    //.....

    //3. 解锁，并设置新的条件，没有数据了
    [locker unlockWithCondition:CONDITION_NO_DATA];
}

五、OSSpinLock自旋锁 & os_unfair_lock

由于OSSpinLock不再安全，所以这里我们就直接说一下os_unfair_lock，这个是苹果用于代替OSSpinLock的。效率很高用法很简单如下

1
2
3
4
5
os_unfair_lock_t lock = OS_UNFAIR_LOCK_INIT;

os_unfair_lock_lock(&lock);
NSLog(@"os_unfair_lock_t");
os_unfair_lock_unlock(&lock);
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
#import "ViewController.h"
#import <libkern/OSAtomic.h>
@interface ViewController ()
@property (nonatomic,assign)  int ticket;
//@property (nonatomic,assign)  OSSpinLock lock;
@end

@implementation ViewController
- (void)viewDidLoad {
    [super viewDidLoad];
//    self.lock = OS_SPINLOCK_INIT;
    self.ticket=50;
    [self ticketsTest];
    // Do any additional setup after loading the view.
}

-(void)ticketsTest{
  	// 这里我们开两个线程处理同一件事
    dispatch_queue_t queue = dispatch_get_global_queue(0, 0);
    dispatch_async(queue, ^{
        for (int i =0; i<5; i++) {
            [self saleTicket];
        }
    });
    dispatch_async(queue, ^{
        for (int i =0; i<5; i++) {
            [self saleTicket];
        }
    });
}

-(void)saleTicket{
    //静态创建、则不需要新建属性
    static OSSpinLock lock = OS_SPINLOCK_INIT;
    //若后面是个函数、则需
    /*
    static OSSpinLock lock = nil;
    static dispatch_once_t onceToken;
    dispatch_once(&onceToken, ^{
        lock = OS_SPINLOCK_INIT;
    });
     */
    //其他线程执行到这里时，发现锁被加锁了 就会再这排队等待、直到这个锁被打开
    //加锁
    OSSpinLockLock(&lock);
    int ticket = self.ticket;
    sleep(.2);
    ticket--;
    self.ticket=ticket;
    NSLog(@"%d",self.ticket);
    //解锁
    OSSpinLockUnlock(&lock);
}

iOS - 互斥锁&&自旋锁 多线程安全隐患

iOS - 互斥锁&&自旋锁 多线程安全隐患

一、多线程安全隐患

资源共享
一块资源可能会被多个线程共享，也就是多个线程可能会访问到一块资源
比如多个线程访问同一个对象，同一个变量，同一个文件。
当多线程访问同一块资源的时候，很容易引发数据错乱和数据安全问题
二、原子和非原子属性
1>OC 在定义属性的时候有nonatomic和atomic两种选择
* atomic：原子属性，为 setter 方法加锁
* nonatomic：非原子属性，不会为 setter 方法加锁
普通情况下都是在主线程做操作，所以一般都不会加锁。
对比：
* atomic：线程安全，需要消耗大量的资源
* nonatomic：非线程安全，适合内存小的移动设备
2>synchronized 与 atomic
* synchronized：互斥锁
* atomic：自旋锁
共同点：都能保证同一时刻只能有一个线程操作锁住的代码
区别：
互斥锁：当上一个线程的任务没有执行完毕的时候（被锁住），那么下一个线程会进入睡眠状态等待任务执行完毕，当上一个线程的任务执行完毕，下一个线程会. 自动唤醒然后执行任务。
自旋锁：当上一个线程的任务没有执行完毕的时候（被锁住），那么下一个线程会一直等待（不会睡眠），当上一个线程的任务执行完毕，下一个线程会立即执行。
自旋锁应用场景：比较适合做一些不耗时的操作
三、互斥锁
· 注意点：
- 如果多线程访问同一个资源，那么必须使用同一把锁才能锁住
- 在开发中，尽量不要加锁，能在服务端做尽量在服务端做，如果必须要加锁，一定要记住，锁的范围不能太大，哪里有安全隐患就加在哪里。
技巧：因为必须使用同一把锁，开发中如果需要加锁，直接使用 self 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
@synchronized(self) {
  //线程1进来之后，锁住，2和3都再外面等待
  //1、查询剩余的票数 NSUInteger count = self.totalCount;
  //2、判断是否还有余票
  //2.1卖票
  //3 、提示客户，没有票了
  if (count>0) {
    [NSThread sleepForTimeInterval:0.1];
    self.totalCount = count-1;
    NSLog(@"%@卖了一张票,还剩%zd票",[NSThread currentThread].name,self.totalCount);
  }
  else
  {
    NSLog(@"没票了");
    break;
  }
}
//解锁

四、自旋锁
注意点:
只会给 setter 方法加锁，并不会给getter方法加锁。

ObjC 多线程简析（一）-多线程简述和线程锁的基本应用

在iOS10之后apple废弃了OSSpinLock自旋锁，使用os_unfair_lock互斥锁来替代。

在iOS10之后apple已经不再建议使用OSSpinLock自旋锁了，它的替代方案是一个互斥锁，所以一般情况下我们使用互斥锁来解决线程同步的问题才是比较合理的。

1
2
3
4
5
6
7
8
9
10
11
// 初始化OSSpinLock
_osspinlock = OS_SPINLOCK_INIT;

// 加锁
OSSpinLockLock(&_osspinlock);

// 操作数据
// ...

// 解锁
OSSpinLockUnlock(&_osspinlock);
1
2
3
4
5
6
7
8
9
10
11
// 初始化os_unfair_lock
_osunfairLock = OS_UNFAIR_LOCK_INIT;

// 加锁
os_unfair_lock_lock(&(_osunfairLock));

// 操作数据
// ...

// 解锁
os_unfair_lock_unlock(&(_osunfairLock));

iOS中的线程同步方案

自旋锁、互斥锁比较:

a, 什么情况使用自旋锁比较划算？

预计线程等待锁的时间很短

加锁的代码（临界区）经常被调用，但竞争情况很少发生

CPU资源不紧张

多核处理器

b,什么情况使用互斥锁比较划算？

预计线程等待锁的时间较长

单核处理器

临界区有IO操作

临界区代码复杂或者循环量大

临界区竞争非常激烈

(4)、自己延伸的问题：什么队列能同时存在同步任务和异步任务？(并发队列)

eg：主线程的主队列是串行队列，不可能在该队列上添加同步任务，否则会造成死锁。所以，同时存在同步任务和异步任务的队列应该只能是并发队列。

最终的执行顺序，还是看这些各式各样的任务所在的队列是什么队列，串行的还是并发的。

1、死锁探究：GCD死锁及报错提示(EXC_BAD_INSTRUCTION)

(1)、死锁举例：通过串行队列里的任务，往这个串行队列里添加同步任务，会造成死锁

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
- (IBAction)testDeadlock1:(id)sender {
    //测试死锁
    dispatch_queue_t q1 = dispatch_queue_create("serial_queue_1", DISPATCH_QUEUE_SERIAL);
    dispatch_async(q1, ^{
    	NSLog(@"1(属任务①).验证通过串行队列里的任务，往这个串行队列里添加同步任务，会造成死锁%@", [NSThread currentThread]);
    	dispatch_sync(q1, ^{ // 添加的同步任务和外面的任务是同一个串行队列
    			sleep(2);
    			NSLog(@"2(属任务②).验证通过串行队列里的任务，往这个串行队列里添加同步任务，会造成死锁%@", [NSThread currentThread]);
    	});
    	NSLog(@"3(属任务①).验证通过串行队列里的任务，往这个串行队列里添加同步任务，会造成死锁%@", [NSThread currentThread]);
    });
}
(2)、死锁结论：往串行队列里添加的同步任务不能卡住该串行队列，否则会造成死锁(这句话非常重要)
(3)、死锁原因分析：

要了解通过串行队列里的任务，往这个串行队列里添加同步任务，会造成死锁，或者说往串行队列里添加的同步任务卡住该串行队列的时候会发生死锁的原因，我们首先需要知道几个概念：

知识点①：创建同步任务的操作，在创建完之后，需要立马执行所创建的同步任务。即创建完同步任务的操作后，只有连其所创建的同步任务也结束了才能继续执行下去；

知识点②：而创建异步任务的操作，在创建完之后，即可继续执行下去，不需要等待所创建的异步任务结束。

附：在线程组的使用中，我们会遇到需要监听多个子线程中的所有任务都结束后，才去执行最后的更新UI的操作。假设最后更新UI的操作，除了需要子线程的任务结束，还需要子线程中的异步线程，如网络请求也结束后，才能更新UI，那么为了不让子线程提前退出，而是等到网络请求也结束后才退出，我们通常会通过使用gcd的enter leave或者信号量来等待。

知识点③：串行队列里的任务是一个执行完，才接着执行下一个；

所以，由以上①②③知识点，我们就能分析出其造成死锁的原因如下：

首先，对于标记1、2、3，先只看是同步任务还是异步任务，而不管是串行队列，还是并行队列，或者说是哪个队列。

从代码上我们很容易看出其是同步任务，所以由以上同步的知识点②，可以知道，最终标记输出的正确顺序应该依次是标记1、标记2、标记3。

即我们的关注点是标记2能否在标记1之后输出。

答，在上述代码中，标记2处的同步任务是被添加到串行队列的，而且还是当前的串行队列。

我们知道串行队列里的任务是一个执行完，才接着执行下一个的，也就是说，往串行队列里添加的任务要执行的条件一定是在所添加的新任务之前的所有任务都已经全部执行完了后，才会执行到这一个的。

这里我们依次往串行队列里添加了第一个任务块和第二个任务块。

要完成第一个任务块需要同时完成任务1+第二个任务块2+任务3。

第二个任务块要执行，根据串行队列的性质，我们知道第二个任务块要等待第一个任务块结束才会执行。（如果两个任务即使都是添加到串行队列，但是他们是不同串行队列的时候就不会需要等待）

由此死锁。

显然这里任务②需要等到任务①真正完成，而任务①的真正完成需要等任务②完成，这样的一个互相等待也就构成了一个死锁，导致我们 EXC_BAD_INSTRUCTION的崩溃了。

那么以上死锁的问题，怎么解决呢？

答：其实只要解决标记2即任务②，可以在标记1执行之后执行就可以了。
解决方法有：将任务②改成异步任务，或者将任务②这个同步任务添加到非本串行队列下，可以是其他串行队列，也可以是其他并行队列都可以。即以下这种修改方案是能够解决死锁的。

1
2
3
4
5
6
7
8
9
10
11
12
13
- (IBAction)testDeadlock2:(id)sender {
    //测试死锁
    dispatch_queue_t q1 = dispatch_queue_create("serial_queue_1", DISPATCH_QUEUE_SERIAL);
    dispatch_async(q1, ^{
    ​    NSLog(@"1(属任务①).验证通过串行队列里的任务，往其他串行队列里添加同步任务，不会造成死锁%@", [NSThread currentThread]);
    ​    dispatch_queue_t q2 = dispatch_queue_create("serial_queue_2", DISPATCH_QUEUE_SERIAL);
    ​    dispatch_sync(q2, ^{
    ​        sleep(2);
    ​        NSLog(@"2(属任务②).验证通过串行队列里的任务，往其他串行队列里添加同步任务，不会造成死锁%@", [NSThread currentThread]);
    ​    });
    ​    NSLog(@"3(属任务①).验证通过串行队列里的任务，往其他串行队列里添加同步任务，不会造成死锁%@", [NSThread currentThread]);
    });
}

2、主队列中的死锁：在主队列开启同步任务，一定为什么会阻塞线程(看同步任务是不是加在主队列里去了)？

回答本问题前，我们需要先了解的知识点是：

知识点①：主线程和主队列的关系：

主队列是主线程中的一个串行队列。每一个应用程序只有唯一的一个主队列用来update UI。所有的和UI的操作(刷新或者点击按钮)都必须在主线程中的主队列中去执行，否则无法更新UI。

因为主线程是一个串行队列，所以往主队列里添加同步任务（如果不是往主队列添加同步任务就不会）是很有可能发生死锁卡死的。如以下代码就会发生死锁。代码如下：

1
2
3
4
5
6
7
8
9
10
- (void)viewDidLoad {
    [super viewDidLoad];

    NSLog(@"打印1");

    dispatch_sync(dispatch_get_main_queue(), ^{
    ​    NSLog(@"打印2");
    });
    NSLog(@"打印3");
}

由引述，我们已经知道往串行队列里添加的同步任务，如果卡住的是该串行队列，则会发生死锁，所以显然即执行往这个串行队列里添加同步任务的该任务也是在这个串行队列里的话，那么由于相互等待会造成死锁。

最简单的解决方法：将sync同步方法，替换成异步方法

1
2
3
4
5
6
7
8
9
10
11
12
- (void)viewDidLoad {
    [super viewDidLoad];

    NSLog(@"标记1");

    dispatch_async(dispatch_get_main_queue(), ^{
        NSLog(@"标记3");
    });
    
    NSLog(@"标记5");
}
//输出结果为 标记1、标记5、标记3

其他修改方法：将同步任务卡住的队列改成并发队列。如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
- (void)testDeadLock {
    NSLog(@"标记1");
    dispatch_queue_t other_queue = dispatch_queue_create("other_queue", DISPATCH_QUEUE_SERIAL);//不管是串行队列还是并发队列，都能解决这个死锁问题，因为它同步方法没有卡住这个other_queue。
    dispatch_async(other_queue, ^{
    ​    NSLog(@"标记2");
    ​    dispatch_sync(dispatch_get_main_queue(), ^{
    ​        NSLog(@"标记3");
    ​    });
    ​    NSLog(@"标记4");
    });
    sleep(2);
    NSLog(@"标记5");
}
//输出结果为 标记1、标记2、标记5、标记3、标记4。

有了这些基础，你再看以下文章中的例子时，就能轻松判断是否会造成死锁了 。

####

iOS中自旋锁与互斥锁的区别

自旋锁（spinlock）：是指当一个线程在获取锁的时候，如果锁已经被其它线程获取，那么该线程将循环等待，然后不断的判断锁是否能够被成功获取，直到获取到锁才会退出循环。（附：获取锁的线程一直处于活跃状态，但是并没有执行任何有效的任务，使用这种锁会造成busy-waiting。自旋锁不会使线程状态发生切换，一直处于用户态，即线程一直都是active活跃状态的；不会使线程进入阻塞状态，减少了不必要的上下文切换，执行速度快）

其他参考文章：iOS中自旋锁与互斥锁的区别

pthread_mutex 表示互斥锁。互斥锁可以传入不同参数，实现递归锁pthread_mutex(recursive)。

NSLock，NSCondition，NSRecursiveLock，NSConditionLock都是内部封装的pthread_mutex，即都属于互斥锁。@synchronized是NSLock的一种封装，牺牲了效率，简洁了语法。

OSSpinLock 表示自旋锁，从上图可以看到自旋锁的效率最高，但是现在的iOS因为优先级反转的问题，已经不安全，所以推荐使用pthread_mutex或者dispatch_semaphore。

总结：
　　自旋锁会忙等: 所谓忙等，即在访问被锁资源时，调用者线程不会休眠，而是不停循环在那里，直到被锁资源释放锁。
　　互斥锁会休眠: 所谓休眠，即在访问被锁资源时，调用者线程会休眠，此时cpu可以调度其他线程工作。直到被锁资源释放锁。此时会唤醒休眠线程。

优缺点：
　　自旋锁的优点在于，因为自旋锁不会引起调用者睡眠，所以不会进行线程调度，cpu时间片轮转等耗时操作。所有如果能在很短的时间内获得锁，自旋锁的效率远高于互斥锁。
　　缺点在于，自旋锁一直占用CPU，他在未获得锁的情况下，一直运行－－自旋，所以占用着CPU，如果不能在很短的时 间内获得锁，这无疑会使CPU效率降低。自旋锁不能实现递归调用。

必备知识架构

–

知识架构

iOS知识库

Android知识库

iOS与JS交互

  • iOS与JS交互的4种方法

    1
    2
    3
    4
    5
    6
    7
    iOS与JS交互的方法：
    1.拦截url（适用于UIWebView和WKWebView） 
    2.JavaScriptCore（只适用于UIWebView，iOS7+） 
    3.WKScriptMessageHandler（只适用于WKWebView，iOS8+） 
    4.WebViewJavascriptBridge（适用于UIWebView和WKWebView，属于第三方框架）

    更详细介绍，请点击以上链接进入查看。

多线程、锁、队列

信号量

1
2
3
①dispatch_semaphore_t sem = dispatch_semaphore_create(0);
②dispatch_semaphore_signal(sem);
③dispatch_semaphore_wait(sem, DISPATCH_TIME_FOREVER);

GCD

1
2
3
4
5
6
7
①dispatch_group_t group = dispatch_group_create();
②dispatch_group_enter(group);
③dispatch_group_leave(group);
④dispatch_group_notify(group, dispatch_get_main_queue(), ^{
        这里跑去干自己的事情。。。。
    });
>

用信号量时候，

某个线程锁住后，就处于等待状态，即该线程也就无法再继续操作，所以试图尝试在该线程锁住的时候去发送信号，增加信号量，会造成死锁。

举例：

信号量使用场景

任务

iOS 实现并发和串行任务
串行队列如何知道任务已经完成
iOS开发中的并发、串行队列，同步、异步任务

iOS代码同步到主线程的三种方法

autoreleasepool 使用场景、什么时候释放

临时变量什么时候释放

RunLoop和线程间的关系

每条线程都有唯一的一个与之对应的RunLoop对象，RunLoop保存在一个全局的Dictionary里，线程作为key,RunLoop作为value，主线程的RunLoop已经自动创建好了，子线程的RunLoop需要主动创建，RunLoop在第一次获取时创建，在线程结束时销毁。

1
2