「重学 OC」内存管理05 - Objective-C中的方法缓存

我们在分析清楚方法列表和方法的结构后，我们再来看一下方法的调用是怎么一个流程呢？是直接去方法列表里面遍历查找对应的方法吗？

其实不然，我们在分析类的结构的时候，除了bits(指向类的具体信息，包括rw_t、ro_t等等一些内容）外，还有一个方法缓存:cache,用来缓存曾经调用过的方法。

所以系统查找对应方法不是通过遍历rw_t这个二维数组来寻找方法的，这样做太慢，效率太低，系统是先从方法缓存中找有没有对应的方法，有的话就直接调用缓存里的方法，根据imp去调用方法，没有的话，就再去方法数组中遍历查找，找到后调用并保存到方法缓存里，流程如下：

那么方法是怎么缓存到cache中的呢？系统又是怎么查找缓存中的方法的呢？我们通过源码来看一下cache的结构：

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

我们可以看到，cache_t里面就三个成员，后两个代表长度和数量，是int类型，肯定不是存储方法的地方，所以方法应该是存储在_buckets这个散列表中。散列存储的是一个个的bucket_t的结构体，那么这个bucket_t又是个什么结构呢？

所以cache_t底部结构是这样的：

我们看到，bucket_t就两个值，一个key一个imp，key的话就是方法名，也就是SEL，而imp就是Value，也就是当我们调用一个方法是来到方法缓存中查找，通过比对方法名是不是一致，一致的话就返回对应的imp，也就是方法地址，从而可以调用方法，那么这个散列表是怎么查找的呢？难道也是通过遍历吗？我们通过阅读源码来一探究竟：

通过上面代码的阅读，我们可以知道系统在cache_t中查找方法并不是通过遍历，而是通过方法名SEL&mask得到一个索引，直接去读数组索引中的方法，如果该方法的SEL与我们调用的方法名SEL一致，那么就返回这个方法，否则就一直向下寻找直到找完为止。

好，既然取值的时候不是遍历，而是直接读的索引，那么将方04法存储到缓存中也肯定是通过这种方式了，直接方法名&mask拿到索引，然后将_key和_imp存储到对应的索引上，这一点我们通过源码也可以确认：

我们看到无论是存还是读，都是调用了find函数，查看SEL&mask对应的索引的方法，不合适的话再向下寻找直到找到合适的位置。

• 那么这里有两个疑问，为什么SEL&mask会出现不是该方法名(读)或者不为空(写)的情况呢？散列表扩容后方法还在吗？

  首先，SEL&mask这个问题，是因为不同的方法名&mask可能出现同一个结果，比如test方法的SEL是011，run方法的SEL是010，mask是010，那么无论是test的SEL&mask还是run的SEL&mask 记过都是010，如果大家都存在这个索引里面是会出问题的，所以为了解决这个索引重复的问题需要先做判断，即拿到索引后先判断这个索引对应的值是不是你想要的，是的话你拿走用，不是的话向下继续找，方法缓存也是同样的道理。我们先调用test方法，缓存到010索引，再调用run方法，发现010位置不为空了，那就判断010下面的索引是否为空，为空的话就将run方法缓存到这个位置。

  关于散列表扩容后，缓存方法在不在的问题，通过源码就可以知道，旧散列表已经释放掉了，所以是不存在的，再次调用的时候就得重新去rw_t中遍历找方法然后重新缓存到散列表中，比如下面这个例子:

  

我们前面讲到当SEL&mask出来一个索引发现被占用或者不是我想要的时候，系统是向索引下一位再次寻找，这个地方失误了，不是向下是向上寻找，这个地方看源码的时候忽略了条件，在x86或者i386架构中是向下寻找，在arm64架构中是向上寻找：(因为上面图片资源都已经删掉了就没有再更改，这里需要注意一下)

到现在我们清楚了，那就是散列表中并不是按照索引依次排序或者遍历索引依次读取，那么就会出现个问题，因为SEL&mask是个小于mask的随机值且散列表存储空间超过3/4的时候就要扩容，那就会导致散列表中有一部分空间始终被限制。确实，散列表当分配内存后，每个地方最初都是null的，当某个位置的索引被用到时，对应的位置才会存储方法，其余位置仍处于空闲状态，但是这样做可以极大提高查找速度(比遍历快很多)，所以这是一种空间换时间的方式。