祭最近的一次面试

最近工作事情不多,本着紧跟潮流的想法,在公司附近找了几家公司面试,涨涨经验顺便看看最近iOS都在招什么方向的的人！ 本人计算机专业毕业(不过基本已经把老师讲的还给老师了),因此在这次面试中 完全被虐。因此,打算写一篇文章来祭奠我的这次面试！

面试题目

都学过哪些数据结构？

数据结构：是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成
包括三个组成成分：数据的逻辑结构、物理结构（存储结构）、数据运算结构。

数据的逻辑结构：

• 1、集合（数据之间无关系）
• 2、线性结构（一对一）
• 3、树形结构（一对多）
• 4、图形结构（多对多）

数据的物理结构：指数据在计算机存储空间的存放形式

顺序存储、链表存储、索引存储、散列存储

常用的数据结构：

• 1、数组
• 2、栈（先进后出、线性表）
• 3、队列（先进先出、后进后出、线性表）
• 4、链表（每个节点包括两个部分：一个存储数据元素的数据域、另一个存储下一个节点地址的指针域）
• 5、树
• 6、图
• 7、堆（是一种动态的树形结构）
• 8、散列表

数组和链表的区别

顺序表

顺序表是在计算机内存中以数组的形式保存的线性表，是指用一组地址连续的存储单元依次存储数据元素的线性结构。只要确定了起始位置，表中任一元素的地址都通过下列公式得到：LOC（ai）=LOC（a1）+（i-1）*L 　1≤i≤n 其中，L是元素占用存储单元的长度。

特点

• 长度固定，必须在分配内存之前确定数组的长度。
• 存储空间连续，即允许元素的随机访问。
• 存储密度大，内存中存储的全部是数据元素。
• 要访问特定元素，可以使用索引访问，时间复杂度为 。
• 要想在顺序表中插入或删除一个元素，都涉及到之后所有元素的移动，因此时间复杂度为 。

链表

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。它的数据是以结点（类型一般为结构体）来表示的，每个结点的构成：数据（类型为要存储的数据的类型） + 指针（结构体指针），数据就是链表里具体要存储的东西，指针就是用来把每个节点都连接起来，使它们形成一个链状

特点

• 长度不固定，可以任意增删。
• 存储空间不连续，数据元素之间使用指针相连，每个数据元素只能访问周围的一个元素（根据单链表还是双链表有所不同）。
• 存储密度小，因为每个数据元素，都需要额外存储一个指向下一元素的指针（双链表则需要两个指针）。
• 要访问特定元素，只能从链表头开始，遍历到该元素，时间复杂度为 。
• 在特定的数据元素之后插入或删除元素，不涉及到其他元素的移动，因此时间复杂度为 。双链表还允许在特定的数据元素之前插入或删除元素。

区别和优缺点

空间的开辟

顺序表的实现一般是实现连续开辟一段空间，然后在进行数据的增删查改（静态顺序表），所以顺序表一般是固定空间大小的；而单链表则是一次只开辟一个结点的空间，用来存储当前要保存的数据及指向下一个结点或NULL的指针，所以单链表的空间大小时动态变化的。（当然，顺序表也可以在初始化时利用malloc函数来开辟一块空间，每当空间不够用时，再用realloc来把当前空间扩容成2倍，从而也能实现空间的动态变化（动态顺序表））。

空间的使用

当我们不知道要存储多少数据时，用顺序表来开辟的空间如果太大，就会造成一定程度上的浪费，而用单链表是实现时，因为是每需要存储一个数据时，才开辟一个空间，虽然有非数据项的指针占空间，但相比顺序表来说，浪费不是那么明显；反之，当我们知道存储的数据的数量时，用顺序表来开辟对应的空间大小，来存储数据，因为顺序表中每个元素的存储密度为 1，就完全不会有浪费的空间，而用单链表，因为每个结点都会有非数据项得指针，那么就会造成空间的浪费。再者 链表可能会产生内存碎片

访问随机元素的时间复杂度

因为顺序表的结构就像是数组一样，可以用下标来访问它的元素，所以它的元素是支持随机访问的；相比之下，单链表的数据是链式存储的，它的元素是不支持随机访问的，想要知道某个元素，只能从头结点开始遍历整个链表，知道找到了该元素为止。因此顺序表访问随机元素的时间复杂度是O（1），而单链表访问随机元素的平均时间复杂度是O（n）。

随机位置插入、删除元素的时间复杂度

因为顺序表的元素是连续存储的，因此要在特定位置插入、删除元素需要把它之后的元素全部后移或前移一个元素的位置，时间开销很大；而单链表在插入或删除元素时，只需要改变它的前驱元素及插入或删除元素的指向即可。因此，顺序表在插入随机位置插入、删除元素的平均时间复杂度是O（n），单链表在插入随机位置插入、删除元素的时间复杂度是O（1）。

综上 在查询操作使用的比较频繁时，使用顺序表会好一些；在插入、删除操作使用的比较频繁时，使用单链表会好一些。

树学过哪些树 什么是完全二叉树 霍夫曼树 红黑树 图

二叉树

二叉树是有限个结点的集合，这个集合或者是空集，或者是由一个根结点和两株互不相交的二叉树组成，其中一株叫根的做左子树，另一棵叫做根的右子树

二叉树的性质：

• 性质1：在二叉树中第 i 层的结点数最多为2^(i-1)（i ≥ 1）
• 性质2：高度为k的二叉树其结点总数最多为2^k－1（ k ≥ 1）
• 性质3：对任意的非空二叉树 T ，如果叶结点的个数为 n0，而其度为 2 的结点数为 n2，则：n0 = n2 + 1

满二叉树

深度为k且有2^k －1个结点的二叉树称为满二叉树

• 性质4：具有 n 个结点的完全二叉树的深度为 log2n + 1

注意:仅有前序和后序遍历，不能确定一个二叉树，必须有中序遍历的结果

完全二叉树

深度为 k 的，有n个结点的二叉树，当且仅当其每个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应，称之为完全二叉树。（除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点）

堆

如果一棵完全二叉树的任意一个非终端结点的元素都不小于其左儿子结点和右儿子结点（如果有的话） 的元素，则称此完全二叉树为最大堆。

同样，如果一棵完全二叉树的任意一个非终端结点的元素都不大于其左儿子结点和右儿子结点（如果 有的话）的元素，则称此完全二叉树为最小堆。

最大堆的根结点中的元素在整个堆中是最大的；

最小堆的根结点中的元素在整个堆中是最小的。

哈弗曼树

定义：给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

构造：

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：

• 将w1、w2、…，wn看成是有 n 棵树的森林(每棵树仅有一个结点)；
• 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
• 从森林中删除选取的两棵树，并将新树加入森林；
• 重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

二叉排序树

二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

• 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
• 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
• 左、右子树也分别为二叉排序树；
• 没有键值相等的节点

二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)（相当于顺序查找）

平衡二叉树

平衡二叉树（balanced binary tree）,又称 AVL 树。它或者是一棵空树,或者是具有如下性质的二叉树：

• 它的左子树和右子树都是平衡二叉树，
• 左子树和右子树的深度之差的绝对值不超过1。

平衡二叉树是对二叉搜索树(又称为二叉排序树)的一种改进。二叉搜索树有一个缺点就是，树的结构是无法预料的，随意性很大，它只与节点的值和插入的顺序有关系，往往得到的是一个不平衡的二叉树。在最坏的情况下，可能得到的是一个单支二叉树，其高度和节点数相同，相当于一个单链表，对其正常的时间复杂度有O(log(n))变成了O(n)，从而丧失了二叉排序树的一些应该有的优点

B-树

B-树：B-树是一种非二叉的查找树， 除了要满足查找树的特性，还要满足以下结构特性：

一棵 m 阶的B-树：

• 树的根或者是一片叶子(一个节点的树),或者其儿子数在 2 和 m 之间。
• 除根外，所有的非叶子结点的孩子数在 m/2 和 m 之间。
• 所有的叶子结点都在相同的深度。

B-树的平均深度为logm/2(N)。执行查找的平均时间为O(logm)；

Trie 树

Trie 树，又称前缀树，字典树， 是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie 树查询和插入时间复杂度都是 O(n)，是一种以空间换时间的方法。当节点树较多的时候，Trie 树占用的内存会很大。

Trie 树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

哈希表 给一个数据如何存到哈希表中 如何得到这个key

定义

哈希表（Hash Table，也叫散列表），是根据关键码值 (Key-Value) 而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。哈希表的实现主要需要解决两个问题，哈希函数和冲突解决。

哈希函数

根据key,计算出key对应记录的储存位置

position = f(key)

哈希函数也叫散列函数，它对不同的输出值得到一个固定长度的消息摘要。理想的哈希函数对于不同的输入应该产生不同的结构，同时散列结果应当具有同一性（输出值尽量均匀）和雪崩效应（微小的输入值变化使得输出值发生巨大的变化）

冲突解决

现实中的哈希函数不是完美的，当两个不同的输入值对应一个输出值时，就会产生“碰撞”，这个时候便需要解决冲突。

常见的冲突解决方法有开放定址法，链地址法，建立公共溢出区等。实际的哈希表实现中，使用最多的是链地址法

链地址法

链地址法的基本思想是，为每个 Hash 值建立一个单链表，当发生冲突时，将记录插入到链表中。

例 2 设有 8 个元素 { a,b,c,d,e,f,g,h } ，采用某种哈希函数得到的地址分别为： {0 ， 2 ， 4 ， 1 ， 0 ， 8 ， 7 ， 2} ，当哈希表长度为 10 时，采用链地址法解决冲突的哈希表如下图所示：

算法学过哪些

常见排序算法

常见的稳定排序算法有：

• 冒泡排序（Bubble Sort） — O(n²)
• 插入排序（Insertion Sort）— O(n²)
• 桶排序（Bucket Sort）— O(n); 需要 O(k) 额外空间
• 计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间
• 合并排序（Merge Sort）— O(nlogn); 需要 O(n) 额外空间
• 二叉排序树排序 （Binary tree sort） — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间
• 基数排序（Radix sort）— O(n·k); 需要 O(n) 额外空间

常见的不稳定排序算法有：

• 选择排序（Selection Sort）— O(n²)
• 希尔排序（Shell Sort）— O(nlogn)
• 堆排序（Heapsort）— O(nlogn)
• 快速排序（Quicksort）— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排

常见排序算法小结

常用查找算法

• 顺序查找 时间复杂度为O(n)
• 二分查找 O(log2n)
• 分块查找
• 树表查找
• 哈希表查找

常用查找算法

内存的分区？

一个程序的可执行文件在内存中的结果，从大的角度可以分为两个部分：只读部分和可读写部分。只读部分包括程序代码（.text）和程序中的常量（.rodata）。可读写部分（也就是变量）大致可以分成下面几个部分：

• .data： 初始化了的全局变量和静态变量
• .bss： 即 Block Started by Symbol， 未初始化的全局变量和静态变量（这个我感觉上课真的没讲过啊我去。。。）
• heap： 堆，使用 malloc, realloc, 和 free 函数控制的变量，堆在所有的线程，共享库，和动态加载的模块中被共享使用
• stack： 栈，函数调用时使用栈来保存函数现场，自动变量（即生命周期限制在某个 scope 的变量）也存放在栈中。
• 文字常量区 —常量字符串就是放在这里的。程序结束后由系统释放
• 程序代码区—存放函数体的二进制代码。

堆和栈的区别？ 系统如何去管理栈的内存 是运行期间还是编译之后就确定了?

栈

栈是用于存放本地变量，内部临时变量以及有关上下文的内存区域。程序在调用函数时，操作系统会自动通过压栈和弹栈完成保存函数现场等操作，不需要程序员手动干预。

栈是一块连续的内存区域，栈顶的地址和栈的最大容量是系统预先规定好的。能从栈获得的空间较小。如果申请的空间超过栈的剩余空间时，例如递归深度过深，将提示stackoverflow。

栈是机器系统提供的数据结构，计算机会在底层对栈提供支持：分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高

堆

堆是用于存放除了栈里的东西之外所有其他东西的内存区域，当使用malloc和free时就是在操作堆中的内存。对于堆来说，释放工作由程序员控制，容易产生memory leak。

堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。

对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，因为栈是先进后出的队列，永远都不可能有一个内存块从栈中间弹出。

堆都是动态分配的，没有静态分配的堆。栈有2种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配由alloca函数进行分配，但是栈的动态分配和堆是不同的，他的动态分配是由编译器进行释放，无需我们手工实现。

计算机底层并没有对堆的支持，堆则是C/C++函数库提供的，同时由于上面提到的碎片问题，都会导致堆的效率比栈要低

堆和栈的区别

申请方式

• 栈：由系统自动分配
• 堆： 需要程序员自己申请，并指明大小，在c中malloc函数

申请后系统的响应

• 栈：只要栈的剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢
  出。

• 堆：首先应该知道操作系统有一个记录空闲内存地址的链表，当系统收到程序的申请时，
  会遍历该链表，寻找第一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表
  中删除，并将该结点的空间分配给程序，另外，对于大多数系统，会在这块内存空间中的
  首地址处记录本次分配的大小，这样，代码中的delete语句才能正确的释放本内存空间。
  另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会自动的将多余的那部
  分重新放入空闲链表中。

申请大小的限制

• 栈 ：栈顶的地址和栈的最大容量是系统预先规定好的 如果申请的空间超过栈的剩余空间时，将
  提示overflow。因此，能从栈获得的空间较小

• 堆：是不连续的内存区域 堆的大小受限于计算机系统中有效的虚拟内存

申请效率

• 栈：栈由系统自动分配，速度较快。但程序员是无法控制的。
• 堆：堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便.

存储内容

• 栈:在函数调用时，第一个进栈的是主函数中后的下一条指令（函数调用语句的下一条可
  执行语句）的地址，然后是函数的各个参数，在大多数的C编译器中，参数是由右往左入栈
  的，然后是函数中的局部变量。注意静态变量是不入栈的。

• 堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。

存取效率

栈>堆

那种内存容易产生内存碎片? 为什么会产生内存碎片

内存碎片容易发生在堆上,因为只有堆我们才会自己去管理内存的申请使用和释放,栈区是不会碎片化的,因为栈区一直遵守后进先出的逻辑。

内存碎片

内存分配有静态分配和动态分配两种

静态分配在程序编译链接时分配的大小和使用寿命就已经确定，而应用上要求操作系统可以提供给进程运行时申请和释放任意大小内存的功能，这就是内存的动态分配

动态分配会导致内存的碎片化

内存碎片类型

内部碎片：

因为所有的内存分配必须起始于可被 4、8 或 16 整除（视处理器体系结构而定）的地址或者因为MMU的分页机制的限制，决定内存分配算法仅能把预定大小的内存块分配给客户。假设当某个客户请求一个 43 字节的内存块时，因为没有适合大小的内存，所以它可能会获得 44字节、48字节等稍大一点的字节，因此由所需大小四舍五入而产生的多余空间就叫内部碎片。

外部碎片

频繁的分配与回收物理页面会导致大量的、连续且小的页面块夹杂在已分配的页面中间，就会产生外部碎片。假设有一块一共有100个单位的连续空闲内存空间，范围是099。如果你从中申请一块内存，如10个单位，那么申请出来的内存块就为09区间。这时候你继续申请一块内存，比如说5个单位大，第二块得到的内存块就应该为1014区间。如果你把第一块内存块释放，然后再申请一块大于10个单位的内存块，比如说20个单位。因为刚被释放的内存块不能满足新的请求，所以只能从15开始分配出20个单位的内存块。现在整个内存空间的状态是09空闲，1014被占用，1524被占用，2599空闲。其中09就是一个内存碎片了。如果1014一直被占用，而以后申请的空间都大于10个单位，那么09就永远用不上了，变成外部碎片

内存的对齐

看的我一脸懵逼 直接放别人的文章吧,以后慢慢参悟！

C/C++内存对齐

线程调度算法 什么是优先级反转？

线程调度算法

先到先服务算法

用一个FIFO（先进先出）队列就可以满足要求。所有的线程构成一个队列，最先进入队列的线程获得处理器执行权，等到放弃处理器执行权时，又回到队列尾部，下一个线程继续执行。若有新的线程进来，则添加到队列尾部。此算法简单，易于实现，但是，如果每个线程执行的任务单元所需要的时间长短不一的话，则算法的实际效果可能非常不公平。

时间片轮转调度算法

处理器的时间被分成了最大长度不超过某个值的时间片段，称为时间片，然后，用轮转方法分配给每一个线程。当一个线程获得了处理器执行权以后，按照自身的逻辑执行下去，直到时间片用完，或者自己主动放弃执行权（比如要等待一个信号量）。系统在获得了处理器控制权以后，用轮转方法找到下一个正在等待运行的线程，让它继续执行。这种线程调度方法实现简单，所有满足运行条件的线程排成一个队列，然后按照时间片的间隔，轮流让每一个线程获得处理器执行权。由于时钟中断每次都要打断一个线程的运行，所以，这种做法存在固有的线程切换开销，而时间片长短的选择会影响到线程切换开销所占的比例。在现代操作系统中，时间片通常设置为几毫秒到几十、上百毫秒。由于现代计算机的指令周期越来越短，线程切换开销（通常几百条指令或几千条指令，取决于算法实现的复杂程度）也在减小。这种算法使用很广泛，它不仅简单，也确实能公平地分配处理器资源。

优先级调度算法。

在时间片轮转算法中，一个基本的假设是所有的线程都同等重要。这一假设在专用计算机上可能是非常合理的，但是，在现代多用途的计算机上，可能难以胜任多种不同类型的应用程序并发执行的实际情形。优先级调度算法是这种算法的一个改进，其基本思路是，每个线程都有一个优先级值，高优先级的线程总是优先被考虑在处理器上执行。操作系统在管理线程时，可以使用一个优先级队列，或者每一个优先级用一个队列来存放所有满足执行条件的线程，这样，当一个线程用完了它的时间片或者自动放弃处理器执行权时，系统选择优先级最高的线程作为下一个要运行的线程。每一个线程在队列中的位置是由它的优先级来决定的。同等优先级的线程使用轮转或先到先执行的策略。

简单优先级算法的潜在问题是，高优先级的线程可能会霸占处理器资源不放，从而导致低优先级的线程一点执行机会都没有。所以，一些变种的优先级算法考虑引入动态优先级，即每个线程有静态的优先级和动态的优先级。所谓动态的优先级是在静态优先级的基础上根据某些特定的条件提升或降低线程的优先级，系统调度器根据线程的动态优先级来安排它们的执行顺序。例如，连续执行了多个时间片的线程可能要降低优先级，而长时间没有得到时间片的低优先级线程可能会得到优先级提升。

优先级反转

多线程编程之优先级翻转问题

OC的对象存在哪里 存的是那些东西？

OC的对象肯定是存放子啊堆中的！

存放的具体内容 应该是这个对象所属的类所具有的 例如

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

struct objc_class {
    Class _Nonnull isa  OBJC_ISA_AVAILABILITY;  //isa指针指向类的元类(metaClass)

#if !__OBJC2__
    Class _Nullable super_class                              OBJC2_UNAVAILABLE; //父类
    const char * _Nonnull name                               OBJC2_UNAVAILABLE; //类名
    long version                                             OBJC2_UNAVAILABLE; //类版本
    long info                                                OBJC2_UNAVAILABLE; //类的信息
    long instance_size                                       OBJC2_UNAVAILABLE; //类实例对象的大小
    struct objc_ivar_list * _Nullable ivars                  OBJC2_UNAVAILABLE; //实例变量的列表
    struct objc_method_list * _Nullable * _Nullable methodLists                    OBJC2_UNAVAILABLE;//方法列表
    struct objc_cache * _Nonnull cache                       OBJC2_UNAVAILABLE; //方法的缓存
    struct objc_protocol_list * _Nullable protocols          OBJC2_UNAVAILABLE; //协议列表
#endif

} OBJC2_UNAVAILABLE;

父类和子类的内存是分配在一起的吗？ 爷爷类 父类 子类 ！

创建一个对象的时候，发生了两件事情，一是分配对象所需的内存，二是调用构造函数进行初始化。子类对象包含从父类对象继承过来的成员，实现上来说，一般也是子类的内存区域中有一部分就是父类的内存区域。调用父类构造函数的时候，这块父类对象的内存区域就被初始化了。为了避免未初始化的问题，语法强制子类调用父类构造函数。

属性（包括父类）都保存在对象本身的存储空间内；本类的实例方法保存在类对象中，本类的类方法保存在元类对象中；父类的实例方法保存在各级 super class 中，父类的类方法保存在各级 super meta class 中。

子类的对象的大小实际是包含着父类一直到根类的大小的集合。跟方法没有关系。每个类的方法(实例方法和类方法都是固定的) 跟实际的对象没关系！只跟类有关系

调用方法的流程 对象方法和类方法

如果当前类(元类)没有找到对应的实例方法(类方法),那么就去他的父类(父类的元类)查找,如果一直到根类仍然无法找到这个方法，那么会抛出unrecognized selector sent to instance异常

如果想要阻止这次异常 可以使用运行时的方法进行补救！

元类是个什么东西 元类只是存放类方法吗？

类对象(class object)中包含了类的实例变量，实例方法的定义，而元类对象(metaclass object)中包括了类的类方法(也就是C++中的静态方法)的定义。类对象和元类对象中水果公司当然还会包含一些其它的东西，以后也可能添加其它的内容，但对于我们了解其内存布局来说，只需要记住：类对象存的是关于实例对象的信息(变量，实例方法等)，而元类对象(metaclass object)中存储的是关于类的信息(类的版本，名字，类方法等)。要注意的是，类对象(class object)和元类对象(metaclass object)的定义都是objc_class结构，其不同仅仅是在用途上，比如其中的方法列表在类对象(instance object)中保存的是实例方法(instance method)，而在元类对象(metaclass object)中则保存的是类方法(class method)。

15、为什么类方法和实例方法分开存？

• 类方法不需要创建一个类的实例就可以调用！对象方法必须创建这个类的实例才可以调用
• 如果放在一起 可能存在重名的情况

谈谈Runloop

深入理解RunLoop
RunLoop

runloop和线程是什么关系？ runloop和autoreleasepool是什么关系

Runloop和线程

线程和 RunLoop 之间是一一对应的，其关系是保存在一个全局的 Dictionary 里。线程刚创建时并没有 RunLoop，如果你不主动获取，那它一直都不会有。RunLoop 的创建是发生在第一次获取时，RunLoop 的销毁是发生在线程结束时。你只能在一个线程的内部获取其 RunLoop（主线程除外）。

首先我们要明确一个概念，线程一般都是一次执行完任务，就销毁了。
而添加了runloop，并运行起来，实际上是添加了一个do,while循环，这样这个线程的程序一直卡在这个do,while循环上，这样相当于线程的任务一直没有执行完，所以线程一直不会销毁。

所以，一旦我们添加了一个runloop，并run了，我们如果要销毁这个线程，必须停止runloop

Runloop和 autoreleasepool

App启动后，苹果在主线程 RunLoop 里注册了两个 Observer，其回调都是 _wrapRunLoopWithAutoreleasePoolHandler()。

第一个 Observer 监视的事件是 Entry(即将进入Loop)，其回调内会调用 _objc_autoreleasePoolPush() 创建自动释放池。其 order 是-2147483647，优先级最高，保证创建释放池发生在其他所有回调之前。

第二个 Observer 监视了两个事件： BeforeWaiting(准备进入休眠) 时调用_objc_autoreleasePoolPop() 和 _objc_autoreleasePoolPush() 释放旧的池并创建新池；Exit(即将退出Loop) 时调用 _objc_autoreleasePoolPop() 来释放自动释放池。这个 Observer 的 order 是 2147483647，优先级最低，保证其释放池子发生在其他所有回调之后。

在主线程执行的代码，通常是写在诸如事件回调、Timer回调内的。这些回调会被 RunLoop 创建好的 AutoreleasePool 环绕着，所以不会出现内存泄漏，开发者也不必显示创建 Pool 了

一个runloop中可以有多个autoreleasepool吗？

可以,这个不多说!

如何拿到一个runloop的所有状态

CFRunLoopObserverRef是观察者，能够监听RunLoop的状态改变

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

//创建一个runloop监听者

    CFRunLoopObserverRef observer = CFRunLoopObserverCreateWithHandler(CFAllocatorGetDefault(),kCFRunLoopAllActivities, YES, 0, ^(CFRunLoopObserverRef observer, CFRunLoopActivity activity) {

        NSLog(@"监听runloop状态改变---%zd",activity);

    });

    //为runloop添加一个监听者

    CFRunLoopAddObserver(CFRunLoopGetCurrent(), observer, kCFRunLoopDefaultMode);

    CFRelease(observer);

监听的状态:

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

typedef CF_OPTIONS(CFOptionFlags, CFRunLoopActivity) {

    kCFRunLoopEntry = (1UL << 0),   //即将进入Runloop

    kCFRunLoopBeforeTimers = (1UL << 1),    //即将处理NSTimer

    kCFRunLoopBeforeSources = (1UL << 2),   //即将处理Sources

    kCFRunLoopBeforeWaiting = (1UL << 5),   //即将进入休眠

    kCFRunLoopAfterWaiting = (1UL << 6),    //刚从休眠中唤醒

    kCFRunLoopExit = (1UL << 7),            //即将退出runloop

    kCFRunLoopAllActivities = 0x0FFFFFFFU   //所有状态改变

};

NSTimer是准确的timer吗？为什么？

NSTimer不是准确的timer 其所在的 RunLoop 会定时检测是否可以触发 NSTimer 的事件，但由于 iOS 有多个 RunLoop 的运行模式，如果被切到另一个 run loop，NSTimer 就不会被触发。每个 RunLoop 的循环间隔也无法保证，当某个任务耗时比较久，RunLoop 的下一个消息处理就只能顺延，导致 NSTimer 的时间已经到达，但 Runloop 却无法及时触发 NSTimer，导致该时间点的回调被错过。

苹果官方文档：

1

A timer is not a real-time mechanism; it fires only when one of the run loop modes to which the timer has been added is running and able to check if the timer’s firing time has passed. If a timer’s firing time occurs during a long callout or while the run loop is in a mode that is not monitoring the timer, the timer does not fire until the next time the run loop checks the timer.

其他更准确的Timer

CADisplayLink

CADisplayLink是一个频率能达到屏幕刷新率的定时器类。iPhone屏幕刷新频率为60帧/秒，也就是说最小间隔可以达到1/60s。

1
2
3

CADisplayLink * displayLink = [CADisplayLink displayLinkWithTarget:self selector:@selector(logInfo)];
[displayLink addToRunLoop:[NSRunLoop currentRunLoop] forMode:NSDefaultRunLoopMode];

GCD定时器

我们知道，RunLoop是dispatch_source_t实现的timer，所以理论上来说，GCD定时器的精度比NSTimer只高不低。

1
2
3
4
5
6
7

NSTimeInterval interval = 1.0;
_timer = dispatch_source_create(DISPATCH_SOURCE_TYPE_TIMER, 0, 0, dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0));
dispatch_source_set_timer(_timer, dispatch_walltime(NULL, 0), interval * NSEC_PER_SEC, 0);
dispatch_source_set_event_handler(_timer, ^{
    NSLog(@"GCD timer test");
});
dispatch_resume(_timer);

mach_absolute_time

使用mach_absolute_time()来实现更高精度的定时器。
iPhone上有这么一个均匀变化的东西来提供给我们作为时间参考，就是CPU的时钟周期数（ticks）。
通过mach_absolute_time()获取CPU已运行的tick数量。将tick数经过转换变成秒或者纳秒，从而实现时间的计算。

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

#include <mach/mach.h>
#include <mach/mach_time.h>
 
static const uint64_t NANOS_PER_USEC = 1000ULL;
static const uint64_t NANOS_PER_MILLISEC = 1000ULL * NANOS_PER_USEC;
static const uint64_t NANOS_PER_SEC = 1000ULL * NANOS_PER_MILLISEC;
 
static mach_timebase_info_data_t timebase_info;

static uint64_t nanos_to_abs(uint64_t nanos) {
    return nanos * timebase_info.denom / timebase_info.numer;
}

void waitSeconds(int seconds) {
    mach_timebase_info(&timebase_info);
    uint64_t time_to_wait = nanos_to_abs(seconds * NANOS_PER_SEC);
    uint64_t now = mach_absolute_time();
    mach_wait_until(now + time_to_wait);
}

理论上这是iPhone上最精准的定时器，可以达到纳秒级别的精度

21、performselector在一个子线程执行,是会自动执行的吗？

performSelector原理是：设置一个timer，添加到当前线程Runloop，默认是NSDefaultRunLoopMode；通过NSTimer的 scheduledTimerWithTimeIntervaly创建的定时器，也是自动被添加到当前RunLoop中，默认是NSDefaultRunLoopMode；

在子线程中，因为默认没有RunLoop，所以他们不执行；想要执行，需要创建并启动Runloop

手动开启：

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

- (void)viewDidLoad
{
    [super viewDidLoad];
    
    [self threadInfo:@"UI"];
    
    _isNewThreadAborted = NO;
    _thread = [[NSThread alloc] initWithTarget:self selector:@selector(newThread:) object:nil];
    //开始线程
    [_thread start];
    //在另一个线程中的Run Loop中执行Selector
    [self performSelector:@selector(test:) onThread:_thread withObject:nil waitUntilDone:NO];    
}

//在新线程中创建并开始一个NSRunLoop
- (void)newThread:(id)obj
{
    @autoreleasepool
    {
        NSRunLoop *currentRunLoop = [NSRunLoop currentRunLoop];
        while (!_isNewThreadAborted)
        {
            [currentRunLoop runMode:NSDefaultRunLoopMode beforeDate:[NSDate distantFuture]];
        }
        NSLog(@"线程停止");
    }
}

//Selector执行
- (void)test:(id)obj
{
    [self threadInfo:@"test"];
    _isNewThreadAborted = YES;
}

- (void)threadInfo:(NSString*)category
{
    NSLog(@"%@ - %@", category, [NSThread currentThread]);
}

GCD 队列和线程是什么关系？

队列

• 主队列
• 串行队列
• 并发队列
• 全局队列

线程

• 同步执行
• 异步执行

交叉出现的情况

串行队列，同步执行

不会开线程，顺序执行

串行队列，异步执行

会开线程(1条)，顺序执行

并发队列，异步执行

会开线程，不会顺序执行，具体开几条线程取决于队列

并发队列，同步执行

和串行队列同步执行效果一样

主队列，异步执行

不开线程，异步任务必须等待主线程上的任务完成之后才会被调用

主队列、同步执行

会发生死锁，因为，同步任务要求必须顺序执行，但是同步任务必须等待主队列中没有任务可以被调用的时候才会被执行，因此这两方会造成死锁的情况

同步任务的特点

可以再多个异步任务调度前，指定一个同步任务，让所有的异步任务，等待同步任务执行完成，这就是所谓的依赖关系

全局队列

系统提供给程序员，方便程序员使用的全局队列，有关服务质量的问题，使用下面的代码能够做到IOS7&IOS8的适配，全局队列本质上就是一个异步队列

一个队列可以管理多少线程？

并发队列可以分配多个线程，同时处理不同的任务；效率虽然提升了，但是多线程的并发是用时间片轮转方法实现的，线程创建、销毁、上下文切换等会消耗CPU 资源。

目前iPhone的处理器是多核（2个、4个），适当的并发可以提高效率，但是无节制地并发，如将大量任务不加思索就用并发队列来执行，这只会大量增加线程数，抢占CPU资源，甚至会挤占掉主线程的 CPU 资源（极端情况）。

可以使用 NSOperationQueue 设置maxConcurrentOperationCount 最大并发数

串行队列中的所有任务都会在一条线程中执行吗

串行队列中的任务不会开多条线程,回一个一个执行,但是每一个任务所在的线程不一定是一个,但同时只会存在一条线程

白板画线(如何在点之间连线) 用什么去重绘的

利用贝塞尔曲线

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

-(UIBezierPath*)drawSigleLine:(NSArray*)line needStroke:(BOOL)needStroke
{
    NSUInteger pointsCount = line.count;
    
    ArtWhiteBoardPoint *firstPoint = [line objectAtIndex:0];
    UIBezierPath *path = [[UIBezierPath alloc] init];
    path.lineWidth = [self getDrawWidth:firstPoint.penStyle.lineWidth];
    path.lineJoinStyle = kCGLineJoinRound;
    path.lineCapStyle = kCGLineCapRound;
    UIColor *lineColor;
    if (firstPoint.penStyle.isEarser) {
        lineColor = [UIColor clearColor];
    }
    else{
        lineColor = [UIColor colorWithHexString:firstPoint.penStyle.colorString alpha:1.0];
    }
    if (lineColor == [UIColor clearColor]) {
        path.lineCapStyle = kCGLineCapSquare;
        path.lineWidth = [self getDrawWidth:[self.dataSource earserWidth:firstPoint.penStyle.isLargeEarser]];
    }
    for (NSUInteger j = 0 ; j < pointsCount; j ++) {
        ArtWhiteBoardPoint *point = [line objectAtIndex:j];
        CGPoint p;
        p = CGPointMake(point.xScale * self.frame.size.width ,  point.yScale * self.frame.size.height);
        
        if (j == 0) {
            [path moveToPoint:p];
        }
        else {
            if (self.controlP1.x==p.x&&self.controlP1.y==p.y) {
                
            }
            else{
                [path addQuadCurveToPoint:CGPointMake((self.controlP1.x+p.x)/2, (self.controlP1.y+p.y)/2) controlPoint:self.controlP1];
            }
            
            
        }
        self.controlP1 = p;
    }
    if (needStroke) {
        [lineColor setStroke];
        
        if (lineColor == [UIColor clearColor]) {
            [path strokeWithBlendMode:kCGBlendModeCopy alpha:1.0];
        }else {
            [path strokeWithBlendMode:kCGBlendModeNormal alpha:1.0];
        }
    }
    
    return path;
}

iOS开发之画图板(贝塞尔曲线)

参考文档

面试基础-哈希表