写在前面
在上一篇文章中已经全面地介绍了类的结构，但是还剩下一个cache_t cache没有进行详细的介绍，本文就将从源码层面分析cache_t.
一、初探cache_t
① cache_t结构
如下是类在底层的结构
其中cache_t的结构如下
其中的_bucketsAndMaybeMask is a buckets_t pointer,是bucket_t类型的结构体指针.
从以上bucket_t的属性和方法中可以看出它应该与imp有联系——事实上bucket_t作为一个桶，里面是用来装imp方法实现以及它的key.
所以通过上面两个结构体源码可知，而我们cache中缓存的正好是sel-imp.
整体的结构如下图所示
在cache_t中查找sel-imp
cache_t中查找存储的sel-imp，有以下两种方式
- 通过源码查找 --
LLDB调试 - 脱离源码在项目中查找
准备工作
-
定义一个
TCJPerson类，并定义两个属性及5个实例方法及其实现 -
在
main中定义TCJPerson类的对象person，并调用其中的3个实例方法，在person调用第一个方法处加一个断点
通过源码查找 一 LLDB调试
-
运行执行，断在
[person sayHello];部分，此时执行以下LLDB调试流程 cache属性的获取，需要通过pclass的首地址平移16字节(上篇文章讲过，类中isa指针占8字节，superclass指针占8字节)，即首地址+0x10获取cache的地址从源码的分析中，我们知道
sel-imp是在cache_t的_buckets属性中（目前处于macOS环境），而在cache_t结构体中提供了获取_buckets属性的方法buckets()获取了
_buckets属性，就可以获取sel-imp了，这两个的获取在bucket_t结构体中同样提供了相应的获取方法sel()以及imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls).
由上图可知，在没有执行方法调用时，此时的cache是没有缓存的，执行了一次方法调用，cache中就有了一个缓存，即调用一次方法就会缓存一次方法.
我们现在了解了如何获取cache中sel-imp，如何验证打印的sel和imp就是我们调用的呢？可以通过machoView打开target的可执行文件，在方法列表中查看其imp的值是否是一致的，如下所示，发现是一致的，所以打印的这个sel-imp就是TCJPerson的实例方法
- 接着上面的步骤，我们再次调用一个方法，这次我们想要获取第二个
sel，其调试的LLDB如下
第一个调用方法的存储获取很简单，直接通过_buckets的首地址调用对应的方法即可，那么获取第二个呢？在之前的iOS之武功秘籍④：类结构分析文章中，曾提及过一个概念 指针偏移，所以我们这里可以通过_buckets属性的首地址偏移，即 p *($9+1)即可获取第二个方法的sel 和imp
如果有多个方法需要获取，以此类推，例如p *($9+i)
脱离源码通过项目查找
脱离源码环境，就是将所需的源码的部分拷贝至项目中，其完整代码如下
这里有个问题需要注意，在源码中，objc_class的ISA属性是继承自objc_object的，但在我们将其拷贝过来时，去掉了objc_class的继承关系，需要将这个属性明确，否则打印的结果是有问题，如下图所示
加上ISA属性后，增加两个方法的调用，其正确的打印结果应该是这样的
在增加两个方法的调用，即解开sayMaster、sayNA的注释，其打印结果如下
针对上面的打印结果，有以下几点疑问
- 1、
_mask是什么？ - 2、
_occupied是什么？ - 3、为什么随着方法调用的增多，其打印的
occupied和mask会变化？ - 4、
bucket数据为什么会有丢失的情况？，例如调用四个方法时，只有sayMaster、sayNA方法有函数指针.
二、深入cache_t
找到切入点
- 首先，从
cache_t中的_mask属性开始分析，找cache_t中引起变化的函数，发现了incrementOccupied()函数
-
源码中，全局搜索
incrementOccupied()函数，发现只在cache_t的insert方法有调用 -
insert方法，理解为cache_t的插入，而cache中存储的就是sel-imp，所以cache的原理从insert方法开始分析，以下是cache原理分析的流程图
-
全局搜索
cache_t::insert，发现在写入之前，还有一步操作，即cache读取，即查找sel-imp，如下所示
insert方法分析
在insert方法中，其源码实现如下
主要分为以下几部分
- 【第一步】计算出当前的
缓存占用量 - 【第二步】根据
缓存占用量判断执行的操作 - 【第三步】针对需要存储的
bucket进行内部imp和sel赋值
【第一步】计算出当前的缓存占用量
根据occupied的值计算出当前的缓存占用量，当属性未赋值及无方法调用时，此时的occupied()为0，而newOccupied为1，如下所示
关于缓存占用量的计算，有以下几点说明：
-
alloc申请空间时，此时的对象已经创建，如果再调用init方法，occupied也会+1 - 当
有属性赋值时，会隐式调用set方法，occupied也会增加，即有几个属性赋值，occupied就会在原有的基础上加几个 - 当
有方法调用时，occupied也会增加，即有几次调用，occupied就会在原有的基础上加几个
【第二步】根据缓存占用量判断执行的操作
-
如果是第一次创建，则默认开辟
4个 -
如果缓存占用量
小于等于3/4，则不作任何处理 -
如果缓存占用量
超过3/4，则需要进行两倍扩容以及重新开辟空间
reallocate方法：开辟空间
该方法，在第一次创建以及两倍扩容时，都会使用，其源码实现如图所示
主要有以下几步
-
allocateBuckets方法：向系统申请开辟内存，即开辟bucket，此时的bucket只是一个临时变量
setBucketsAndMask方法：将临时的bucket存入缓存中，此时的存储分为两种情况： - 如果是
真机，根据bucket和mask的位置存储，并将occupied占用设置为0 - 如果
不是真机，正常存储bucket和mask，并将occupied占用设置为0
- 如果有旧的
buckets，需要清理之前的缓存，即调用collect_free方法，其源码实现如下
该方法的实现主要有以下几步：
-
_garbage_make_room方法：创建垃圾回收空间- 如果是
第一次，需要分配回收空间 - 如果
不是第一次，则将内存段加大，即原有内存*2
- 如果是
记录存储这次的
bucket-
cache_collect方法：垃圾回收，清理旧的bucket
【第三步】针对需要存储的bucket进行内部imp和sel赋值
这部分主要是根据cache_hash方法，即哈希算法 ，计算sel-imp存储的哈希下标，分为以下三种情况
- 如果哈希下标的位置
未存储sel，即该下标位置获取sel等于0，此时将sel-imp存储进去，并将occupied占用大小加1 - 如果当前哈希下标存储的
sel等于即将插入的sel，则直接返回 - 如果当前哈希下标存储的
sel不等于即将插入的sel，则重新经过cache_next方法 即哈希冲突算法，重新进行哈希计算，得到新的下标，再去对比进行存储
其中涉及的两种哈希算法，其源码如下
-
cache_hash：哈希算法
-
cache_next：哈希冲突算法
三、cache_t疑问点
① _mask是什么？
_mask是指掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标，其中mask等于capacity - 1
② _occupied 是什么？
_occupied表示哈希表中 sel-imp 的占用大小 (即可以理解为分配的内存中已经存储了sel-imp的的个数)
-
init会导致occupied变化 -
属性赋值，也会隐式调用set方法，导致occupied变化 -
方法调用，会导致occupied变化
③ 为什么随着方法调用的增多，其打印的occupied 和 mask会变化？
因为在cache初始化时，分配的空间是4个，随着方法调用的增多，当存储的sel-imp个数，即newOccupied + CACHE_END_MARKER（等于1）的和 超过 总容量的3/4,例如有4个时，当occupied等于2时，就需要对cache的内存进行两倍扩容.
④ 为什么是在 3/4 时进行扩容
在哈希这种数据结构里面，有一个概念用来表示空位的多少叫做装载因子——装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降
负载因子是3/4的时候，空间利用率比较高，而且避免了相当多的Hash冲突，提升了空间效率
具体可以阅读HashMap的负载因子为什么默认是0.75？
④ bucket数据为什么会有丢失的情况？
原因是在扩容时，是将原有的内存全部清除了，再重新申请了内存导致的
⑤ 方法缓存是否有序?
因为sel-imp的存储是通过哈希算法计算下标的，其计算的下标有可能已经存储了sel，所以又需要通过哈希冲突算法重新计算哈希下标，所以导致下标是随机的，并不是固定的
⑥ bucket与mask、capacity、sel、imp的关系
- 类
cls拥有属性cache_t，cache_t中的buckets有多个bucket——存储着方法实现imp和方法编号sel强转成的key值cache_key_t -
mask对于bucket来说，主要是用来在缓存查找时的哈希算法 -
capacity则可以获取到cache_t中bucket的数量
缓存的主要目的就是通过一系列策略让编译器更快的执行消息发送的逻辑
写在后面
和谐学习,不急不躁.我还是我,颜色不一样的烟火.
