1.
1
2. 散列表（哈希表）是以空間換時(shí)間.
剛開始為cache_t分配一定的內(nèi)存, 如10, 當(dāng)內(nèi)存不夠用時(shí), 內(nèi)存擴(kuò)大2倍, 依次類推
3. 表格大概如下:
2
左邊是索引, 右邊是
bucket_t結(jié)構(gòu)體如上圖所示,
bucket_t包括_key與IMP, _key就是SEL
4.iOS arm64 散列表存儲(chǔ)原理:
- 初始時(shí), 為對(duì)象的
cach_t分配一個(gè)空間, 值為NULL
- 初始時(shí), 為對(duì)象的
- 調(diào)用方法時(shí), 為對(duì)象發(fā)送一個(gè)
SEL消息, 如@selector(personTest), 將這個(gè)方法緩存
- 調(diào)用方法時(shí), 為對(duì)象發(fā)送一個(gè)
- 系統(tǒng)用
SEL與_mask作按位與計(jì)算:@selector(personTest) & _mask, 假設(shè)其值==2,
- 系統(tǒng)用
- 檢查索引2 對(duì)應(yīng)的空間是否為
NULL, 如果為NULL就將這個(gè)bucket_t緩存在索引2對(duì)應(yīng)空間
- 檢查索引2 對(duì)應(yīng)的空間是否為
- 如果不為空, 索引減1, 再檢查是否為
NULL, 依次類推. 如果索引<0, 則使索引 =_mask- 1, 直至找到索引對(duì)應(yīng)空間為NULL, 再緩存
- 如果不為空, 索引減1, 再檢查是否為
5. 對(duì)應(yīng)的查找步驟:
- 調(diào)用方法時(shí), 為對(duì)象發(fā)送一個(gè)
SEL消息, 如@selector(personTest)
- 調(diào)用方法時(shí), 為對(duì)象發(fā)送一個(gè)
- 系統(tǒng)用
SEL與_mask作按位與計(jì)算:@selector(personTest) & _mask, 假設(shè)其值==2,
- 系統(tǒng)用
- 得到索引2 的
bucket_t, 判斷其中的SEL是否與傳過來的SEL相同, 如果相同, 這個(gè)_imp就是尋找的方法
- 得到索引2 的
- 如果不相同, 索引減1, 再比較
SEL, 依次類推. 如果索引<0, 則使索引 =_mask- 1, 直至找到_imp
- 如果不相同, 索引減1, 再比較
6. 為什么按位&_mask?
按位與 可保證得到的值 <= _mask, 這樣就不會(huì)超出分配的空間.
注: 有的系統(tǒng)是求余 %, 如java, 這樣也能保證 <= _mask
7. 為什么有 -1 的算法, 也是因?yàn)榘次慌c, 因?yàn)椴煌闹?& _mask, 可能結(jié)果相同. 如果已經(jīng)被占了, 就-1:
3
8. 如果空間超出原來的_mask, 則 _mask *= 2.
每一次_mask 擴(kuò)容, 散列表清空, 只留下一個(gè)方法占用, 是導(dǎo)致它擴(kuò)容的方法.
- 源碼:
4
- 實(shí)例:
5
9.打印散列表:
9.1
9.2
- 可看到有的空間為
NULL
- 可看到有的空間為
10. 測(cè)試 & _mask 得到方法:
10.1
打印:
10.2
注: selector 轉(zhuǎn)化成數(shù)字類型才能 & , 所以強(qiáng)轉(zhuǎn)成 long long.
11. 將地址 轉(zhuǎn)化 成方法名:
11
