cache_t

cache_t可以看做一个哈希表，以sel作为key，查找方法的imp。

struct cache_t {
    struct bucket_t *_buckets;
    mask_t _mask;
    mask_t _occupied;
     ...
}

struct bucket_t *_buckets是一个通过calloc函数得到的一块连续的内存，里面存储的是bucket_t的结构体，_buckets可以像数组一样通过下标index存取值，当存储的bucket_t超过限制时，会通过expand()函数进行扩容。

struct bucket_t {
    MethodCacheIMP _imp;
    cache_key_t _key;
...
};

bucket_t里面包含了我们要找的方法imp。
cache会通过一个哈希算法由sel得到一个index，然后从数组_buckets中取出对应的bucket_t得到imp。
哈希算法的实现：

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

对于有可能出现的哈希冲突，使用了再次哈希的方式来解决：

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    
    bucket_t *b = buckets();
    mask_t m = mask();
    mask_t begin = cache_hash(k, m);
    mask_t i = begin;
    do {
        if (b[i].key() == 0  ||  b[i].key() == k) {
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);
}

cache_next时出现冲突时再次hash得到的下标index。