• Class內(nèi)部結(jié)構(gòu)中有個(gè)方法緩存（cache_t），用散列表（哈希表）來(lái)緩存曾經(jīng)調(diào)用過(guò)的方法，可以提高方法的查找速度。

struct cache_t {
    struct bucket_t *_buckets; //散列表 （bucket_t, ...）
    mask_t _mask; //散列表的長(zhǎng)度 - 1
    mask_t _occupied; //已經(jīng)緩存的方法數(shù)量
};
|
|
struct bucket_t {
    cache_key_t _key; // SEL作為Key
    IMP _imp;  //函數(shù)的內(nèi)存地址
};

• 緩存查找：bucket_t * cache_t::find(cache_key_t k, id receiver)

散列表（哈希表）

散列表找元素的原理：

• f(key) = index
• 通過(guò)一個(gè)函數(shù)，傳入一個(gè)key,算出一個(gè)索引index。
• 如果這個(gè)索引沖突了，那就通過(guò)+ 1 、- 1或某個(gè)算法再算一遍，直到不沖突為止。

應(yīng)用

• 在存儲(chǔ)bucket_t時(shí)，將這個(gè)_key&_mask得到一個(gè)值，方法就存在相應(yīng)的位置；
• 取方法時(shí)，也是直接_key&_mask，去對(duì)應(yīng)的值里取bucket_t;

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

• 由圖表看到好多空間沒(méi)有使用到，故，這是一種犧牲空間使用效率，來(lái)?yè)Q取查詢效率的方法。

如_key&_mask的結(jié)果和之前的重復(fù)了怎么辦 ？

即： _key&_mask 之后，該位置上已經(jīng)有bucket_t了或者取出來(lái)的bucket_t的_key對(duì)不上。

解決：

以存為例：

• 得出的值，位置有bucket_t；
• 值 - 1 ,如果還有，繼續(xù)-1;
• 值 = 0 ，就直接等于mask（mask == 散列表的長(zhǎng)度 - 1）。

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

如果方法過(guò)多，散列表原來(lái)的長(zhǎng)度不夠了怎么辦？

• 擴(kuò)容為原來(lái)空間的2倍；
• 將原緩存清空。

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE; // 2倍
     .........
   reallocate(oldCapacity, newCapacity); //里面有個(gè)" cache_collect_free(oldBuckets, oldCapacity);"
}