isa詳解（二）cache和散列表
- 2019 年 10 月 8 日
- 筆記
一. isa成員介紹
- nonepointer 0 ：代表普通指針,存儲著class mate-class指針 1 ：代表優化後的指針
- has_assoc 是否有==設置過==關聯對象。如果沒有，釋放更快
- has_cxx_dtor 是否有c++的析構函數(.cxx.destruct), 如果沒有，釋放更快
- shiftcls class 或者meta-class對象的地址值
- magic 分辨對象是否初始化
- weakly_referenced 是否被弱引用過，如果沒有，釋放更快
- deallocating 是否被釋放
- has_sidetable_rc 引用計數器是否大過無法存儲在isa中 如果為1 就存儲在SideTable類的屬性中
- extra_rc (retain count) 存放引用計數器（存儲引用計數器-1)
上面為什麼說釋放更快
源碼中查找 objc_destructinstance 銷毀一個實例對象。發現需要進行相關判斷。所以如果沒有的話。釋放更快
二. class 結構中的cache
在源碼中我們可以找到class的結構。我們看一下cache
- class結構
struct objc_class : objc_object { // Class ISA; Class superclass; cache_t cache; // formerly cache pointer and vtable class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags class_rw_t *data() { return bits.data(); } ... 複製程式碼
class_rw_t* data() { return (class_rw_t *)(bits & FAST_DATA_MASK); } 複製程式碼
struct class_rw_t { // Be warned that Symbolication knows the layout of this structure. uint32_t flags; uint32_t version; const class_ro_t *ro; method_array_t methods; property_array_t properties; protocol_array_t protocols; ... } 複製程式碼
class method_array_t : public list_array_tt<method_t, method_list_t> //內部存為method_t 元素的method_list_t列表 //所以method_array_t為二位數組 複製程式碼
可以在bits中找到方法列表,方法列表中存著method_t的數組 我們看一下method_t的結構 2. method_t
- 查找SEL方法
- @selector() 或者sel_registerName()獲得
- 可以通過sel_getName() 和NSStringFromSelector()轉成字元串
- 不同類中相同方法 名字的方法，對應的方法選擇器是相同的
- types
- @encode() 蘋果官方type encoding
- types含義 數字含義 以及字元含義
- cache_t 方法快取 用==散列表==來快取曾經調用過的方法，可以提高方法的查找速度 struct cache_t { struct bucket_t *buckets // 散列表 mask_t _masks //散列表長度-1 massk_t _occupied // 已經快取方法的數量 } struct bucket_t { cache_ket_t _key; //SEL 做key IMP _imp; //函數的記憶體地址 } 複製程式碼
三. 散列表
散列表結構
角標:
根據key & mark的值獲取
因為marks的值是不變的，定義為數組長度-1
當index = key& mark時,所有的index 都<= mark，所以數組並不會越界
賦值：
當角標衝突時: 對角標進行 index – -操作。直到找到空閑位置，並賦值
取值：
同樣角標通過 key &mark
當選出的key和傳入的key不符合的時候 index- -操作 找到和key相同的值 並返回
擴容：
每次記錄賦值個數，當賦值個數大於數組的時候 對原數組進行擴容。並且清除散列表中的數據。重置mark為數組長度-1
自定義一個hash表(散列表)
#import "SRHash.h" @interface SRHash_t:NSObject @property (nonatomic, assign) char *key; @property (nonatomic, strong) NSObject *value; @end @implementation SRHash_t @end #define kCapacityBase 4 @interface SRHash() @property (nonatomic, strong) NSMutableArray <SRHash_t *>* hashs; @property (nonatomic, assign) NSInteger masks; // maks 數組長度-1 @property (nonatomic, assign) NSInteger occupied; //已快取個數 @end @implementation SRHash - (instancetype)init { self = [super init]; if (self) { self.hashs = [self creatHashsWithCapacity:(kCapacityBase * 1)]; } return self; } - (void) setHashValue:(id)value forKey:(NSString *)key { // 如果快取個數超過數組長度 則擴容 if (self.occupied > self.masks) { self.hashs = [self creatHashsWithCapacity:self.hashs.count * 2]; } // NSString 轉化為char 用char的地址存儲 char *charKey = [self formartKey:key]; // 找到索引 通過&mask NSInteger beginIndex = [self findMask:charKey]; NSInteger index = beginIndex; //發生碰撞 if (![self isNil:self.hashs[index]] && self.hashs[index].key != charKey) { // 不為空 && key不同 do { //遍曆數組。如果找到空位置/或者遍歷一圈 跳出循環 index = index - 1; index = (index < 0) ? index = self.masks : index; } while (![self isNil:[self objectFromHashs:index]] && beginIndex != index); } SRHash_t *hash = [SRHash_t new]; hash.key = charKey; hash.value = value; self.hashs[index] = hash; // 存儲個數+1 self.occupied ++; } - (id)hashValueForKey:(NSString *)key { char *charKey = [self formartKey:key]; NSInteger beginIndex = [self findMask:charKey]; NSInteger index = beginIndex; SRHash_t *hash = [self objectFromHashs:index]; if (![self isNil:hash] && hash.key != charKey) { // 如果找到hash存在並且與key不等 do { // 遍歷 在遍歷一個周期內 找到key相等的hash值 index = index - 1; index = (index < 0) ? index = self.masks : index; hash = [self objectFromHashs:index]; } while (hash.key != charKey && beginIndex != index); // 如果未找到 if (hash.key != charKey) { return nil; } } return hash.value; } #pragma mark - private API - (NSInteger) findMask:(char *) key { NSLog(@"%p",key); return ((long long)key) & _masks; } // 初始化數組 @""為空 - (NSMutableArray *) creatHashsWithCapacity:(NSInteger) capacity { NSMutableArray * array = [NSMutableArray arrayWithCapacity:capacity]; for (int i = 0 ; i < capacity; i ++) { [array addObject:@""]; } _masks = array.count - 1; _occupied = 0; return array; } // 是否為空 - (BOOL) isNil:(id) hash { return [hash isKindOfClass:[NSString class]] || hash == nil; } // 從數組中查找hash元素 - (SRHash_t *) objectFromHashs:(NSInteger) index { SRHash_t *temp = self.hashs[index]; if ([temp isKindOfClass:[SRHash_t class]]) { return temp; } return nil; } - (char *) formartKey:(NSString *)key{ return (char *)[key UTF8String]; } @end
