cache_t 缓存机制（方法缓存）

知识点图片

cache_t 是 Objective-C Runtime 中非常核心的一个结构体，用于方法缓存。它的主要目的是为了优化方法调用的性能。

在 Objective-C 中，方法调用本质上是消息发送（objc_msgSend）。如果没有缓存，每次调用方法都需要去类的方法列表（method_list）中遍历查找，甚至需要沿着继承链向上查找，效率非常低。cache_t 的存在就是为了将“查找过的方法”保存起来，下次调用时直接从缓存取，将时间复杂度从 O(n) 降低到 O(1)。

以下是关于 cache_t 缓存机制的详细解析：

1. 底层数据结构

cache_t 定义在 objc-runtime-new.h 中，它本质上是一个哈希表（Hash Table/散列表）。

核心结构体定义 (简化版)

plaintext

struct cache_t {
    struct bucket_t *_buckets; // 散列桶数组（哈希表存储数据的容器）
    mask_t _mask;              // 掩码（用于计算哈希索引，值为 capacity - 1）
    mask_t _occupied;          // 当前已占用的槽位数量
    
    // ... 其他辅助方法
};

桶元素 `bucket_t`

_buckets 数组中存放的是 bucket_t 结构体，它存储了具体的缓存内容：

plaintext

struct bucket_t {
    SEL _sel;  // 方法选择子 (Key)
    IMP _imp;  // 函数实现地址 (Value)
};

Key: SEL (方法名)
Value: IMP (函数指针，指向代码实现)

2. 缓存查找流程 (读操作)

当你调用 [object method] 时，objc_msgSend 的汇编代码会优先执行以下步骤：

获取类对象：通过 object->isa 找到类对象。
计算哈希下标：利用 SEL 和 _mask 进行位运算（通常是 SEL & mask），计算出该方法在 _buckets 数组中的初始下标。
哈希查找：
- 检查该下标处的 bucket。
- 如果 bucket._sel 等于当前调用的 SEL，命中缓存 (Cache Hit)，直接返回 bucket._imp 执行。
- 如果 bucket._sel 为空，说明没缓存过，未命中 (Cache Miss)，进入慢速查找流程（去 class_rw_t 的方法列表中找）。
- 如果 bucket._sel 不匹配（哈希冲突），则根据冲突解决算法（通常是向前或向后线性探测）寻找下一个下标，直到找到或遇到空桶。

3. 缓存写入与扩容 (写操作)

当方法在缓存中未找到，Runtime 会去类的方法列表或父类中查找。一旦找到，就会将这个方法（SEL + IMP）插入到 cache_t 中，以便下次快速调用。

插入流程

计算哈希：同样通过 SEL & mask 计算下标。
哈希冲突处理：Objective-C Runtime 使用开放寻址法（Open Addressing）中的线性探测（Linear Probing）来解决冲突。
- 如果计算出的位置已经被占用了，就查看 index - 1 (在某些架构下是 index + 1)，直到找到空位。

扩容机制 (关键点)

cache_t 的容量是有限的。当缓存填满到一定程度（通常是 3/4 或 7/8）时，会触发扩容。

扩容规则：容量通常翻倍（例如从 4 -> 8 -> 16）。
清除旧缓存：这是 cache_t 最特殊的地方。当扩容发生时，Runtime 会释放旧的 _buckets，并创建一个新的、更大的空数组。旧的缓存数据会被全部丢弃！
- 为什么丢弃？ 重新将旧数据哈希到新数组的成本太高（涉及重新计算哈希、处理冲突等）。Runtime 认为“懒加载”更快：既然扩容了，说明之前的缓存可能不够热了，不如清空，等下次调用时再重新缓存真正“热”的方法。

4. 为什么需要 Mask？

_mask 的值总是 capacity - 1。
例如，如果容量是 4，mask 就是 3 (二进制 011)。

作用：用于快速取模。
在计算机中，x % n 比较慢，而当 n 是 2 的倍数时，x & (n-1) 等价于 x % n，但位运算速度极快。
公式：index = (long long)SEL & mask。这保证了计算出的 index 永远在 0 到 capacity-1 之间，不会越界。

5. 总结：cache_t 的特点

速度极快：基于哈希表，查找时间复杂度接近 O(1)。
局部性原理：只缓存被调用过的方法。
非持久性：
- 程序重启后缓存消失。
- 扩容时缓存清空（这是面试常考点）。
线程不安全：但在 objc_msgSend 层面通过锁或原子操作保证了读取的安全性，写入时底层会有锁保护。

6. 面试常见问题

Q: 如果父类实现了方法，子类调用，缓存存在哪里？
- A: 存在子类的 cache_t 中。因为消息发送的主体是子类对象，查找是从子类开始的，找到后就缓存在当前类（子类）里。
Q: 发生哈希冲突怎么办？
- A: 使用线性探测法（Linear Probing），在桶数组中向前或向后寻找下一个空位。
Q: 扩容时发生了什么？
- A: 开辟新的内存空间（通常大小翻倍），设置新的 mask，丢弃所有旧的缓存数据。

播面