专栏首页老沙课堂isa详解(二)cache和散列表

isa详解(二)cache和散列表

一. isa成员介绍

  1. nonepointer 0 :代表普通指针,存储着class mate-class指针 1 :代表优化后的指针
  2. has_assoc 是否有==设置过==关联对象。如果没有,释放更快
  3. has_cxx_dtor 是否有c++的析构函数(.cxx.destruct), 如果没有,释放更快
  4. shiftcls class 或者meta-class对象的地址值
  5. magic 分辨对象是否初始化
  6. weakly_referenced 是否被弱引用过,如果没有,释放更快
  7. deallocating 是否被释放
  8. has_sidetable_rc 引用计数器是否大过无法存储在isa中 如果为1 就存储在SideTable类的属性中
  9. extra_rc (retain count) 存放引用计数器(存储引用计数器-1)

上面为什么说释放更快

源码中查找 objc_destructinstance 销毁一个实例对象。发现需要进行相关判断。所以如果没有的话。释放更快

二. class 结构中的cache

在源码中我们可以找到class的结构。我们看一下cache

  1. 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

  1. 查找SEL方法
    1. @selector() 或者sel_registerName()获得
    2. 可以通过sel_getName() 和NSStringFromSelector()转成字符串
    3. 不同类中相同方法 名字的方法,对应的方法选择器是相同的
  2. types
    1. @encode() 苹果官方type encoding
    2. types含义 数字含义 以及字符含义
  3. 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

本文分享自微信公众号 - 老沙课堂(gh_f73a6b772d4f),作者:rui4u

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-08-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • NSProxy 设计消息转发

    继承于NSProxy的类 找实现方法的时候 只会找当前类是否实现 而不找super,如果没找到直接进入消息动态解析,以及消息转发机制。比继承NSObject的类...

    老沙
  • 数据结构与算法(二)数组

    在堆中连续开辟的一段空间,每个元素占有相同大小的空间。一经开辟,即固定大小,无法改变长短。

    老沙
  • 消息转发及super

    **消息转发的时候。由于oc的底层原理是消息机制,所以可以添加c语言函数等 **

    老沙
  • 浅谈 KVO 的实现原理

    KVO 全称 KeyValueObserving 是 Objective-C 对观察者模式(Observer Pattern)的实现;KVO 提供一种机制,当指...

    s_在路上
  • uniapp之w-picker使用采坑

    watch:{ 'formData.hospital': (val,oldval) => { debugger thi...

    老梁
  • Android 动态加载so文件

    在开发中,我们时常会遇到包体积过大的情况。其中,一个大的第三方so文件,经常会让人头痛。那么,能否动态加载.so文件呢?答案是可以的。

    Oceanlong
  • 学 Guava 发现:不可变特性与防御性编程

    问:String 类是可变的吗? 答:emm……由于String类的底层是 final 关键字修饰,因此它是不可变的。 问:它被设计为不可变的好处有哪些呢? 答...

    周三不加班
  • 数据挖掘从入门到放弃(三):朴素贝叶斯

    朴素贝叶斯是一种常用的分类算法,适用于维度非常高的数据集,具有速度快,可调参数少有点,非常适合为分类问题提供快速粗糙的基本方案,经常用于垃圾邮件分类等场景中,相...

    数据社
  • 数据挖掘从入门到放弃(三):朴素贝叶斯

    朴素贝叶斯是一种常用的分类算法,适用于维度非常高的数据集,具有速度快,可调参数少有点,非常适合为分类问题提供快速粗糙的基本方案,经常用于垃圾邮件分类等场景中,相...

    abs_zero
  • AttributeError: __enter__

    于小勇

扫码关注云+社区

领取腾讯云代金券