一. Class的内部结构

在isa指针和superclass指针+窥探Class中，我们初步窥探了Class的内部结构，如下：

窥探struct objc_class的结构.png.png

如上图，objc_class内部有isa指针（继承objc_object得来的），superclass，cache方法缓存，bits&FAST_DATA_MASK获取class_rw_t表，等等。

其实上图关于methods数组的结构是不准确了，应该是array_t数组里面装的是list_t数组，list_t数组里面装的是method_t方法，上图是为了简单理解直接写成list_t数组了，正确的应该是如下：

class_rw_t.png

class_rw_t里面的methods、properties、protocols是二维数组，是可读可写的，包含了类的初始内容、分类的内容。
比如，上图，methods数组里面存放许多method_list_t数组，一个method_list_t数组代表一个初始的类或者分类（分类的东西在前面，因为分类的东西合并到类的时候插到数组的最前面了），method_list_t数组里面的内容就是method_t方法了，代表初始的类或者分类里面的方法。

class_ro_t里面的baseMethodList、baseProtocols、ivars、baseProperties是一维数组，是只读的，包含了类的初始内容，如下：

class_ro_t.png

看了class_rw_t和class_ro_t可知道，class_rw_t中的一部分东西是从class_ro_t里面搬过来的，这个也可以在源码中看出，具体可参考Category分类。

我们主要学习methods数组，其他两个是类似的。

二. method_t

method_t是对方法\函数的封装，在objc4搜索“struct method_t {”可找到method_t的实现，如下：

struct method_t {
    SEL name;  //函数名(选择器)
    const char *types; //返回值类型、参数类型的编码
    IMP imp; //指向函数的指针(函数地址)
};

一个method_t就需要上面三个东西就够了，一个method_t就是一个方法。

1. SEL name;

1. SEL代表方法\函数名，一般叫做选择器，底层结构跟char *类似
2. 可以通过@selector()和sel_registerName()获得
3. 可以通过NSStringFromSelector()和sel_getName()转成字符串
4. 不同类中相同名字的方法，所对应的方法选择器是相同的，比如：

 [self performSelector:@selector(test)];
 [person performSelector:@selector(test)];

上面的代码，传入的都是@selector(test)，可以打印@selector(test)地址，发现地址都是一样的，但是他们各自调用自己的方法。

NSLog(@"%p %p %p", @selector(test), @selector(test), sel_registerName("test"));
打印结果：0x101e4ba2e 0x101e4ba2e 0x101e4ba2e

SEL底层定义：

typedef struct objc_selector *SEL;

objc_selector不是开源的，就没法再进去看了。

2. const char *types;

types包含了函数返回值类型、参数类型的编码

types.png

3. IMP imp;

IMP代表函数的具体实现，就是指向函数的地址

typedef id _Nullable (*IMP)(id _Nonnull, SEL _Nonnull, ...); 

4. 验证

① 验证imp就是指向函数的地址

MJPerson *person = [[MJPerson alloc] init];
mj_objc_class *cls = (__bridge mj_objc_class *)[MJPerson class];
class_rw_t *data = cls->data();
//"i24@0:8i16f20"
[person test:10 height:20];

在最后一行和tset:height:方法里面打断点，鼠标放到“ data”上，点击叹号：

imp

打印如下：(注意上图的types里面的值，下面有用)

Printing description of data->methods->first.imp:
(IMP) imp = 0x000000010edba890 (Interview01-位运算`-[MJPerson test:height:] at MJPerson.m:12)

进入tset:height: 方法里面的断点，勾选使用汇编：

汇编

结果如下：

方法地址

发现tset:height: 方法的地址值也是0x000000010edba890，验证了imp的确是指向函数的指针。

② 验证types里面包含返回值、参数

在验证types之前我们先看encode指令，iOS中提供了一个叫做@encode的指令，可以将具体的类型表示成字符串编码：

encode指令.png

比如：

NSLog(@"%s", @encode(int));

打印结果为 i，就把int类型转成 i 字符串了。

所以，上上上上面图中的types里面的"i 24 @ 0 : 8 i 16 f 20"，解释如下：

1. i代表返回值是int类型，@代表第一个隐式参数(id)self，：代表第二个隐式参数(SEL)_cmd当前方法名，i代表第三个参数int类型，f代表第四个参数float类型。
2. 后面数字，24代表所有参数总共占用的字节数（id SEL int float，id 和SEL都是指针各占8字节，int、float各占4字节，一共24字节），0代表这个参数从第0个字节开始，8代表这个参数从第8个字节开始，16代表这个参数从第16个字节开始......以此类推。

相信对于无参无返回值的方法，它的types是v16@0:8，应该很容易理解了。

三. cache方法缓存

这里用对象方法解释，因为对象方法和类方法其实是一样的，就是放的位置不一样。

1. 查找方法的过程

1. 当某个对象调用某个方法，先根据isa找到当前类对象，在当前类对象的cache里面查找方法，如果查到就调用方法，查不到就去当前类对象的methods数组里面查找方法，如果查到就调用方法，并把方法缓存到cache里面。
2. 如果当前类对象没查到，就根据superclass查找父类，同样先查找父类的cache，如果查到就调用方法，然后把父类cache里面的方法缓存到当前类对象的cache里面，如果父类的cache里面没查到，就去父类的methods数组里面查找方法，如果查到就调用这个方法并把父类的这个方法缓存到当前类对象的cache里面。
3. 如果父类也没有这个方法，再查找基类，同样先查找基类的cache再查找基类的methods数组，如果基类有这个方法就调用这个方法并把基类的这个方法放到当前类对象的cache缓存里面，这样下次再次调用这个方法就直接在当前类对象的cache里面取了，就不用遍历methods数组了。

2. cache

Class内部结构中有个方法缓存（cache_t cache），用散列表（哈希表）来缓存曾经调用过的方法，可以提高方法的查找速度，底层结构如下：

struct cache_t {
    struct bucket_t *_buckets; //散列表 里面缓存着方法
    mask_t _mask; //散列表的长度减一
    mask_t _occupied; //已经缓存的方法数量
}

其中_buckets是个数组，里面放着每个bucket_t，如下：

bucket_t.png

struct bucket_t {
private:
    cache_key_t _key; //SEL作为key
    IMP _imp; //函数的内存地址
}

注释已经写的很详细了，对于bucket_t结构体，例如：_key = @selector(personTest)，_imp = personTest的地址，当发现_key相同，就会拿到这个_key对应的_imp函数地址进行调用。

① 用空间换时间

想要明白如何根据_key在散列表中找到_imp，就要知道散列表的原理，先看表：

散列表.png

如上：

1. 当第一次调用personTest，调用完方法，存储到cache的时候，会根据@selector(personTest)& _mask得到一个我们需要的索引，假如是2，然后存入到上图的那个位置。
2. 当第二次调用personTest，通过@selector(personTest)& _mask得到索引2，就可以直接拿到索引2的值。

总结：可以看出，存入的时候并不是从头开始存的，所以其他地方可能为空，但是取的效率很高，这就是典型的用空间换时间。

② 为什么_mask是散列表的长度减1？

当一个值& _mask的时候，结果只会小于等于_mask的值，比如：

0001 0100
0001 1100 &
__________
0001 0100

就比如散列表长度为10，那_mask就是9，这样做& _mask运算之后结果才为0-9，才能存10个值。

③ 万一两个不同的值@selector(不同方法)& _mask得到的索引是一样的怎么办？

在objc4看源码：

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    //k就是key
    assert(k != 0); 
    bucket_t *b = buckets();
    mask_t m = mask(); //就是_mask
    mask_t begin = cache_hash(k, m); //返回一个索引
    mask_t i = begin;
    do {
        //如果key相等，就取出索引的值
        if (b[i].key() == 0  ||  b[i].key() == k) {
            return &b[I];
        }
    } while ((i = cache_next(i, m)) != begin);

    // hack
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);
}

上面的k就是@selector(personTest)，m就是_mask，进入cache_hash：

static inline mask_t cache_hash(cache_key_t key, mask_t mask) 
{
    return (mask_t)(key & mask);
}

可以发现就是根据key & mask返回索引，如果key相等就取出索引的值，如果key不相等，就将当前的索引和mask传进去，进入:cache_next

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

如果索引非0就索引 - 1，否则mask。

说了这么多究竟是啥意思呢？如下图：

存值取值

假设里面已经有两个方法了，如果调用第三个方法，通过@selector(personTest3) & _mask = 4，获取到索引为4，存入的时候发现4位置有值了，这时候会直接将4减1变为3，然后存在3的位置，如下图：

personTest3)

当再次调用personTest3，通过@selector(personTest3) & _mask = 4，获取到索引为4，去4位置取，发现这里面的key跟我们要的key不一样，这样就把4减一1变成3，取3位置的值，发现3位置的key跟我们要的是一样的，然后就拿到我们想要的了。
如果减到0还是没找到，从上面代码我们也可以看出，如果是0就变成mask（假如散列表为10，mask为9），然后从9再开始找，直到找到为止。

所以，运气好一次就找到了，就算运气再差也就是遍历一遍数组而已。

④ _mask是变化的，为什么？

当上面的数组扩容了，比如从10变化成20个，这时候_mask就会变成一个新的值，因为数组变化了，通过旧的_mask获取的索引值就不一样了，这个时候系统就会把缓存清掉，这一点在源码里面也是有体现的，如下：

void cache_t::expand() //扩容方法
{
    cacheUpdateLock.assertLocked();
    
    //扩容两倍
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;

    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        // mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }

    reallocate(oldCapacity, newCapacity);
}

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();

    bucket_t *oldBuckets = buckets();
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    // Cache's old contents are not propagated. 
    // This is thought to save cache memory at the cost of extra cache fills.
    // fixme re-measure this

    assert(newCapacity > 0);
    assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);

    //设置新的mask为newCapacity长度减一
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        //这里会清空掉缓存
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

可以看出，当扩容后，会把新mask设置为newCapacity长度减一，然后清空缓存。

总结：

所有散列表（哈希表）的原理都是一样的，不同的散列表就是算法不一样。
都是通过一个函数，这个函数传入一个key（这里就是@selector(方法名)），通过这个key算出一个索引，根据索引存值和取值，如果索引冲突了就加1或者减1，直至不冲突为止。

最后自己回想一下cache存值和取值的过程。

验证：方法调用完，会将方法缓存到cache里面

执行如下代码：

MJPerson *person = [[MJPerson alloc] init];
mj_objc_class *personClass = (__bridge mj_objc_class *)[MJPerson class];

[person personTest]; //断点

NSLog(@"123"); //断点

personTest方法调用之前，断点情况如下：

1.png

可以发现，_mask为3，所以散列表长度为4，occupied为1，说明缓存了一个方法，很明显是init方法。

personTest方法调用之后，断点情况如下：

2.png

可以发现，occupied变为2，说明缓存了两个方法，init方法和personTest方法。

注意：上面展开_buckets展示的是第0位存的东西，所以下次展开以后如果是空的或者其他值也是正常。

下面演示更复杂的情况：

继承关系为MJGoodStudent：MJStudent：MJPerson，这三个类分别实现自己的方法。

MJGoodStudent *goodStudent = [[MJGoodStudent alloc] init];
mj_objc_class *goodStudentClass = (__bridge mj_objc_class *)[MJGoodStudent class];

[goodStudent goodStudentTest]; //断点①
[goodStudent studentTest]; //断点②
[goodStudent personTest]; //断点③
[goodStudent goodStudentTest]; //断点④
[goodStudent studentTest]; //断点⑤
NSLog(@"--------------------------");//断点⑥

在断点①停下：
_mask为3，occupied为1。
在断点②停下：
_mask为3，occupied为2。
在断点③停下：
_mask为3，occupied为3。
在断点④停下：
_mask为7，occupied为1。
在断点⑤停下：
_mask为7，occupied为2。
在断点⑥停下：
_mask为7，occupied为3。

可以发现在在断点④停下时，容量已经翻倍了（这个在上面的源码也可以看出来），这是因为在存第三行的时候，发现容量不太够了，系统就自动扩容，然后把缓存清空了，再把第三行存进去，所以到最后断点6的时候，cache缓存的方法为：personTest、goodStudentTest、studentTest（init方法已经被清空了）。

再添加如下代码，将缓存里面的方法打印出来：

cache_t cache = goodStudentClass->cache;
bucket_t *buckets = cache._buckets;

for (int i = 0; i <= cache._mask; i++) {
    bucket_t bucket = buckets[i];
    NSLog(@"%s %p", bucket._key, bucket._imp);
}

打印结果为：

goodStudentTest 0x100000bc0
personTest 0x100000e20
(null) 0x0
(null) 0x0
studentTest 0x100000b90
(null) 0x0
(null) 0x0
(null) 0x0

可以发现，结果正如我们所料。

我们再尝试通过key & _mask获取索引，通过索引获取方法：

//有可能算出的索引不是你想要的
bucket_t bucket = buckets[(long long)@selector(studentTest) & cache._mask];
NSLog(@"%s %p", bucket._key, bucket._imp);

打印结果：

studentTest 0x100001980

这里碰巧获取的是对的，但是实际情况下有可能那个索引对应的是其他方法，因为没有判断key是否一样。下面模仿系统进行优化：

IMP imp(SEL selector)
    {
        mask_t begin = _mask & (long long)selector;
        mask_t i = begin;
        do {
            //判断key是否一样
            if (_buckets[i]._key == 0  ||  _buckets[i]._key == (long long)selector) {
                return _buckets[i]._imp;
            }
          //key不一样，索引减一，再找下一个
        } while ((i = cache_next(i, _mask)) != begin);
        return NULL;
    }

执行代码：

//模仿系统，传入key，自动生成索引，然后再找索引对应的值
NSLog(@"%s %p", @selector(personTest), cache.imp(@selector(personTest)));
NSLog(@"%s %p", @selector(studentTest), cache.imp(@selector(studentTest)));
NSLog(@"%s %p", @selector(goodStudentTest), cache.imp(@selector(goodStudentTest)));

打印结果：

personTest 0x100001e10
studentTest 0x100001980
goodStudentTest 0x1000019b0

这样通过key获取到的方法才没有问题，也验证了：方法调用完，会将方法缓存到cache里面。

Demo地址：Class补充