洋仔的博客 洋仔的博客
首页
  • 个人心法总结

    • 价值心法
  • 技术文档
  • GitHub技巧
  • Nodejs
  • 博客搭建
  • iOS基础知识
  • 前端
  • 学习
  • 面试
  • 心情杂货
  • 实用技巧
  • 投资体系
  • 毛选
  • 友情链接
关于
收藏
  • 分类
  • 标签
  • 归档
GitHub (opens new window)

洋仔

奋斗的小青年
首页
  • 个人心法总结

    • 价值心法
  • 技术文档
  • GitHub技巧
  • Nodejs
  • 博客搭建
  • iOS基础知识
  • 前端
  • 学习
  • 面试
  • 心情杂货
  • 实用技巧
  • 投资体系
  • 毛选
  • 友情链接
关于
收藏
  • 分类
  • 标签
  • 归档
GitHub (opens new window)
  • 技术文档

  • GitHub技巧

  • Nodejs

  • 博客搭建

  • iOS基础知识

    • iOS底层相关

      • OC基础之常见知识
        • OC是动态语言,如何理解
          • 动态类型识别
          • 动态绑定
          • 动态加载
        • 面向对像编程
          • 面向对象和面向过程的区别?
          • 对象方法和类方法的区别?
          • 手写单例
          • 什么是僵尸对象? 野指针?
          • C和 OC 如何混编
          • 遇到过BAD_ACCESS的错误吗?你是怎样调试的?
          • Objective-C 如何实现多重继承?
        • 什么是类簇
        • APNS的推送机制原理
        • 说一下静态库和动态库之间的区别
        • cocoa touch底层技术架构?
        • 什么是类工厂方法?
        • Objective-C 中的字典 NSDictionary 底层其实是一个哈希表,实际上绝大多数语言中字典都通过哈希表实现,
          • 开放寻址法
          • 拉链法
          • 为什么HashMap加载因子一定是0.75?而不是0.8,0.6?
          • 那么为什么不可以是0.8或者0.6呢?
          • 建立一个公共溢出区
        • 如何对 NSMutableArray 进行 KVO
        • 符号表
      • OC基础之属性关键字
      • OC基础之底层系列
      • OC反射机制系列
      • 分类与扩展
      • load跟initialize
      • isa指针是什么
      • 引用计数管理
      • 字典系列
    • Runloop系列

    • Runtime系列

    • 内存管理系列

    • Block系列

    • 线程系列

    • KVC跟KVO系列以及通知中心

    • UI系列

    • 离屏渲染系列

    • 组件化系列跟架构

    • OC跟webview交互系列

    • 持久化系列

    • APP编译系列

    • APP性能优化系列

    • cocoapods系列

    • swift系列

    • Git系列

    • 网络相关

    • 三方库系列

    • 系统原理

    • 总结系列

    • 算法系列

    • 数据结构系列

  • 前端

  • 技术
  • iOS基础知识
  • iOS底层相关
xugaoyi
2023-08-13
目录

OC基础之常见知识

# OC是动态语言,如何理解

OC的动态特性可从三方面描述

  • 动态类型识别(Dynamic typing):最终判定该类的实例类型是在运行期间
  • 动态绑定(Dynamic binding):在运行时确定调用的方法
  • 动态加载(Dynamic loading):在运行期间可添加模块(类、方法)

# 动态类型识别

  • OC中有一个可以表示任何实例对象类型的关键字--id,将对象声明为id类型,可根据需要,赋予不同类型的实例对象。
  • 父类指针同样也可以指向子类实例对象,编译期指针类型为父类,运行后可判断为具体的某个子类。
  • 这段代码也可以很好的解释OC的动态类型识别:NSData *test = [[NSString alloc] init]; 在编译期test被认为NSData类型,运行后则为NSString类型,其值为空字符串("")。

# 动态绑定

关于动态绑定,苹果官网的给的解释为:(determining the method to invoke at runtime)。我理解为运行时决定调用方法(更专业的应该叫消息发送,大家不要纠结这细节哈)。动态绑定是实现OC多态的基础,所谓多态指的是不同对象对同一方法(叫函数也行)有着不同实现,常见于子类继承父类,重写父类方法,不同的子类实现该方法不同,通过父类指针指向子类来完成。

# 动态加载

1.动态添加属性:

原理:给一个类声明属性,其实本质就是给这个类添加关联,并不是直接把这个值的内存空间添加到类存空间。 对象关联允许开发者对已经存在的类在 Category 中添加自定义的属性:

提示

OBJC_EXPORT void objc_setAssociatedObject(id object, const void *key, id value, objc_AssociationPolicy policy)

参数1:object 是源对象

参数2:value 是被关联的对象

参数3:key 是关联的键,objc_getAssociatedObject 方法通过不同的 key 即可取出对应的被关联对象

参数4:policy 是一个枚举值,表示关联对象的行为,从命名就能看出各个枚举值的含义

要取出被关联的对象使用 objc_getAssociatedObject 方法即可,要删除一个被关联的对象,使用 objc_setAssociatedObject 方法将对应的 key 设置成 nil 即可.

这个也可以取消关联

void objc_removeAssociatedObjects(id object)

应用情景

给NSObject类添加一个name属性 给UIButton或UIView添加一个单击事件回调属性 给控件(UILable,UIButton,UIView等)添加一个角标显示的信息的属性,以及信息的颜色,字体大小等属性 下面我们以给 UIButton 添加一个监听单击事件的 block 属性为例:


#import <UIKit/UIKit.h>

typedef void(^clickBlock)(void);

@interface UIButton (block)

/*
 * 在分类中声明一个属性时,只会生成setter和getter方法的声明,并不能生成setter和getter方法的
 * 实现以及带下划线的成员变量.
 * 所以, 在分类中有两种方式声明一个属性
 */

/** 第一种写法 */
@property (nonatomic,copy) clickBlock click;

/** 第二种写法 */
//@property clickBlock click;

@end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#import "UIButton+block.h"
#import <objc/runtime.h>

/** 定义关联的key */
static const void *clickKey = "click";

@implementation UIButton (block)

//Category中的属性,只会生成setter和getter方法,不会生成成员变量

-(void)setClick:(clickBlock)click{

    /* 产生关联,让某个对象(name)与当前对象的属性(name)产生关联
     参数1: id object :表示给哪个对象添加关联
     参数2: const void *key : 表示: id类型的key值(以后用这个key来获取属性) 属性名
     参数3: id value : 属性值
     参数4: 策略, 是个枚举(点进去,解释很详细)

     单词Associated 关联
     */
    objc_setAssociatedObject(self, clickKey, click, OBJC_ASSOCIATION_COPY_NONATOMIC);

    [self removeTarget:self action:@selector(buttonClick) forControlEvents:UIControlEventTouchUpInside];

    if (click) {
        [self addTarget:self action:@selector(buttonClick) forControlEvents:UIControlEventTouchUpInside];
    }
}

- (clickBlock)click{
    return objc_getAssociatedObject(self, clickKey);
}

- (void)buttonClick{
    if (self.click) {
        self.click();
    }
}

@end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
UIButton *button = [[UIButton alloc] init];

button.frame = self.view.bounds;

[self.view addSubview:button];

button.click = ^{

    NSLog(@"点击了button");

};
1
2
3
4
5
6
7
8
9
10
11

2.动态添加方法

动态添加方法,就是使用performSelector来添加方法,也就相当于懒加载机制。 如果一个类的方法很多,加载类到内存的时候耗费资源,需要给每个方法生成映射表,可以使用动态给某个类,添加方法解决。

首先创建一个对象Child,引入runtime头文件,

#import <objc/message.h>

实现动态添加方法,首先要实现这个方法:resolveInstanceMethod。 resolveInstanceMethod调用:当一个方法没有实现,但是又调用了这个,就会调用。

resolveInstanceMethod作用:知道哪些方法没有实现,从而动态添加方法。

class_addMethod(Class cls, SEL name, IMP imp, const char *types): 动态添加方法时调用:

  1. class:给哪个类添加方法
  2. SEL:方法编号
  3. IMP:方法的实现,函数入口(指针) 如果是C方法的话可直接写方法名,如果是OC方法的话,可通过class_getMethodImplementation(Class cls, SEL name)方法获得;
  4. types:方法类型,返回值类型,是个C字符串,"V@:"表示返回值类型为空,无参,"i@:"返回值为int,无参,"i@😡",返回值为int,一个参数。
Panda *pan = [[Panda alloc] init];

// 默认Panda,没有实现eat方法,不能直接调用,可以通过performSelector调用,但是会报错。
// 动态添加方法就不会报错

/** 无参 */
//[pan performSelector:@selector(eat)];

/** 有参 */
[pan performSelector:@selector(eat:) withObject:@521];
1
2
3
4
5
6
7
8
9
10
#import "Panda.h"
#import <objc/runtime.h>

@implementation Panda

// 默认方法都有两个隐式参数,
// 定义添加的方法
void eat(id self, SEL sel, NSNumber *meter)
{
    NSLog(@"\n%@\n%@\n%@",self,NSStringFromSelector(sel),meter);
}

// 当一个对象调用未实现的方法,会调用这个方法处理,并且会把对应的方法列表传过来.
// 刚好可以用来判断,未实现的方法是不是我们想要动态添加的方法
+ (BOOL)resolveInstanceMethod:(SEL)sel
{

    if (sel == NSSelectorFromString(@"eat:")) {
        // 动态添加eat方法

        // 第一个参数:给哪个类添加方法
        // 第二个参数:添加方法的方法编号
        // 第三个参数:添加方法的函数实现(函数地址)
        // 第四个参数:函数的类型,(返回值+参数类型) v:void @:对象->self :表示SEL->_cmd
        class_addMethod(self, sel, (IMP) eat, "v@:");

        return YES;
    }

    return [super resolveInstanceMethod:sel];
}

@end
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

注意

  • 动态添加的方法的作用就是去处理未实现的实例方法或者是类方法,它的调用时刻: 只要我们调用了一个不存在的方法时,它就会动态方法解析,接下来就会进入消息转发流程,这此过程中我们可以拦截然后动态的添加方法,防止程序崩溃。

  • 如果一个类方法非常多,加载类到内存的时候也比较耗费资源,需要给每个方法生成映射表,可以使用动态给某个类添加方法解决。

  • 有没有使用performSelector,其实主要想问你有没有动态添加过方法。使用performSelector可以调用一个没有实现的方法,但是会报错。

使用场景:

一个类方法非常多,一次性加载到内存,比较耗费资源,为什么动态添加方法? OC都是懒加载,有些方法可能很久不会调用。

比如电商,视频,社交等一些软件会有有收费项目或者会员机制,那么只有在开通会员的时候才会拥有特定功能,然而存在相当一部门用户是没有使用收费功能,或者是没有开通开通会员的,我们就在这些用户使用时不加载这些方法(这个方法的类是要加载的),后面利用Runtime动态的添加这些方法,以达到性能最大化。

3.动态添加类

通过objc_allocateClassPair(Class _Nullable superclass, const char * _Nonnull name,size_t extraBytes) 添加要动态创建的类,然后添加方法和变量,最终将创建的类注册到runtime中 objc_registerClassPair(Class _Nonnull cls)

导入头文件#import <objc/runtime.h>,动态添加类,创建一个继承 NSString 的类NSStringSubClass类,如下代码

// 类名也可以直接使用C字符串写法 ”NSStringSubClass“
NSString *className = @"NSStringSubClass";  

// Creates a new class and metaclass.
Class newClass = objc_allocateClassPair(NSString.class, className.UTF8String, 0);    
class_addMethod(newClass, @selector(eat), (IMP)EatFunction, "v@:");
objc_registerClassPair(newClass);
1
2
3
4
5
6
7

调用objc_allocateClassPair()函数,对类对(class and metaClass)进行分配内存,Pair的意思就是一对。三个参数,

一是父类:NSString类;

二是类名称:“NSStringSubClass”;

三是额外字节:0。

动态加态资源

根据需求加载所需要的资源,这点很容易理解,对于iOS开发来说,基本就是根据不同的机型做适配。最经典的例子就是在Retina设备上加载@2x的图片,而在老一些的普通屏设备上加载原图。

# 面向对像编程

面向对象编程有三大特性:封装、继承、多态。

  • 封装: 隐藏对象的属性和实现细节,仅对外提供公共访问方式,将变化隔离,便于使用,提高复用性和安全性。
  • 继承: 提高代码复用性;建立了类之间的关系;子类可以拥有父类的所有成员变量的方法;继承是多态的前提。
  • 多态: 所谓多态指的是不同对象对同一方法(叫函数也行)有着不同实现,常见于子类继承父类,重写父类方法,不同的子类实现该方法不同,通过父类指针指向子类来完成。

# 面向对象和面向过程的区别?

  • 面向过程:注重的是解决问题的步骤,比如C语言

  • 面向对象:关注的是解决问题的去要那些对象,OC语言就是面向对象

# 对象方法和类方法的区别?

  • 对象方法:以减号开头,只可以被对象调用,可以访问成员变量

  • 类方法:以加号开头只能用类名调用,对象不可以调用,类方法不能访问成员变量

# 手写单例

static ClassName *_instance;
+ (instancetype)sharedInstance{
   @synchronized (self) {
       if(!_instance)   {
           _instance = [self alloc]init];
       }
    }
    return _instance;
} 
1
2
3
4
5
6
7
8
9

方式二: 注意多线程问题 GCDdispatch_once 默认是线程安全的

static ClassName *_instance;
  + (instancetype)sharedInstance{
      static dispatch_one_t oneToken;
      dispatch_once(&onetoken,^{
          _instance = [self alloc]init];
      });
      return _instance;
  }

  + (instancetype)allocWithZone:(NSZone *) zone{
    static dispatch_t onetoken;
    dispatch_once(&oncetoken ^{
        _instance = [super allocwithzone:zone];
    })
    retun _instance
  }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 什么是僵尸对象? 野指针?

  • 僵尸对象: 已经被销毁的对象(不能再使用的对象),内存已经被回收的对象。
  • 野指针: 指向僵尸对象(不可用内存/已经释放的内存地址)的指针
NSObject *obj = [NSObject new];
[obj release]; // obj 指向的内存地址已经释放了,
obj 如果再去访问的话就是野指针错误了.
野指针错误形式在Xcode中通常表现为:Thread 1:EXC_BAD_ACCESS,因为你访问了一块已经不属于你的内存。
1
2
3
4

# C和 OC 如何混编

xcode可以识别一下几种扩展名文件:

.m文件,可以编写 OC语言 和 C 语言代码 .cpp: 只能识别C++ 或者C语言(C++兼容C) .mm: 主要用于混编 C++和OC代码,可以同时识别OC,C,C++代码

# 遇到过BAD_ACCESS的错误吗?你是怎样调试的?

BAD_ACCESS 报错属于内存访问错误,会导致程序崩溃,错误的原因是访问了野指针(悬挂指针)。

设置全局断点快速定位问题代码所在行。 开启僵尸对象诊断 Analyze分析 重写object的respondsToSelector方法,现实出现EXEC_BAD_ACCESS前访问的最后一个object。 Xcode 7 已经集成了BAD_ACCESS捕获功能:Address Sanitizer。 用法如下:在配置中勾选✅Enable Address Sanitizer。

# Objective-C 如何实现多重继承?

Object-c的类没有多继承,只支持单继承,如果要实现多继承的话,可使用如下几种方式间接实现

通过组合实现

A和B组合,作为C类的组件

通过协议实现

C类实现A和B类的协议方法

消息转发实现

forwardInvocation:方法

# 什么是类簇

类簇是Foundation框架广泛使用的设计模式。类簇在公共抽象父类下对多个私有的具体子类进行分组。以这种方式对类进行分组简化了面向对象框架的公共可见体系结构,而不会降低其功能丰富度。类簇是基于抽象工厂设计模式的。

OC中有哪些类簇呢?NSData、NSArray、NSDictionary、NSString、NSNumber等都是类簇。日常开发debug过程中我们可能会发现_NSCFString、__NSArrayI这样的类,其实这就是其类簇下面的私有子类

为什么苹果要这样设计呢?以NSArray为例,为了保持数组存取的高效,针对不同情况(可变、不可变、单元素等情况)必然要有相应的子类来优化实现。如果全部都用可见子类来实现的话,那么对于程序员来说,就要熟知大量的子类及其API,并且在调用的时候也要分情况去调用,这样使用起来太复杂了。而且如果子类实现改变的话,有可能导致接口也改变,框架API变化也就更加频繁,不利于使用。 为了解决这个问题,NSArray和NSMutableArray作为公开抽象父类,抽象了array功能的接口,但是具体的实现则是通过私有的具体子类来实现。再结合抽象工厂设计模式,程序员就可以通过抽象父类引用而指向私有具体子类,由子类根据自身情况实现父类抽象的方法。这样接口十分简洁,框架底层子类变化时也不会影响到接口的变化,增强了接口稳定性。

# APNS的推送机制原理

  1. 由App向iOS设备发送一个注册通知,用户需要同意系统发送推送。
  2. iOS向APNs远程推送服务器发送App的Bundle Id和设备的UDID。
  3. APNs根据设备的UDID和App的Bundle Id生成deviceToken再发回给App。
  4. App再将deviceToken发送给远程推送服务器(自己的服务器), 由服务器保存在数据库中。
  5. 当自己的服务器想发送推送时, 在远程推送服务器中输入要发送的消息并选择发给哪些用户的deviceToken,由远程推送服务器发送给APNs。
  6. APNs根据deviceToken发送给对应的用户。
  • APNs 服务器就是苹果专门做远程推送的服务器。
  • deviceToken是由APNs生成的一个专门找到你某个手机上的App的一个标识码。
  • deviceToken 可能会变,如果你更改了你项目的bundle Identifier或者APNs服务器更新了可能会变。

# 说一下静态库和动态库之间的区别

静态库:以.a 和 .framework为文件后缀名。链接时会被完整的复制到可执行文件中,被多次使用就有多份拷贝。

动态库:以.tbd(之前叫.dylib) 和 .framework 为文件后缀名。 链接时不复制,程序运行时由系统动态加载到内存,系统只加载一次,多个程序共用(如系统的UIKit.framework等),节省内存。

// 静态库.a 和 framework区别.a 主要是二进制文件,不包含资源,需要自己添加头文件 .framework 可以包含头文件+资源信息

# cocoa touch底层技术架构?

cocoa touch底层技术架构 主要分为4层:

  • 可触摸层 Cocoa Touch : UI组件,触摸事件和事件驱动,系统接口
  • 媒体层 Media: 音视频播放,动画,2D和3D图形
  • Core Server: 核心服务层,底层特性,文件,网络,位置服务区等
  • Core OS: 内存管理,底层网络,硬盘管理

# 什么是类工厂方法?

类工厂方法就是用来快速创建对象的类方法, 他可以直接返回一个初始化好的对象,具备以下特征:

  • 一定是类方法
  • 返回值需要是 id/instancetype 类型
  • 规范的方法名说说明类工厂方法返回的是一个什么对象,一般以类名首字母小写开始;
  • 比如系统 UIButton 的buttonWithType 就是一个类工厂方法:
// 类工厂方法
+ (instancetype)buttonWithType:(UIButtonType)buttonType;
// 使用
+ UIButton * button = [UIButton buttonWithType:UIButtonTypeCustom];
1
2
3
4

# Objective-C 中的字典 NSDictionary 底层其实是一个哈希表,实际上绝大多数语言中字典都通过哈希表实现,

哈希表的本质是一个数组,数组中每一个元素称为一个箱子(bin),箱子中存放的是键值对。数组长度即箱子数。 哈希表还有一个重要的属性: 负载因子(load factor),它用来衡量哈希表的 空/满 程度,一定程度上也可以体现查询的效率,计算公式为: 负载因子 = 总键值对数 / 箱子个数 负载因子越大,意味着哈希表越满,越容易导致冲突,性能也就越低。因此,一般来说,当负载因子大于某个常数(0.75)时,哈希表将自动扩容

# 开放寻址法

又称开放定址法,当哈希冲突发生时,从发生冲突的那个单元起,按照一定的次序,从哈希表中寻找一个空闲的单元,然后把发生冲突的元素存入到该单元。这个空闲单元又称为开放单元或者空白单元。开放寻址法需要的表长度要大于等于所需要存放的元素数量,非常适用于装载因子较小(小于0.5)的散列表。

查找时,如果探查到空白单元,即表中无待查的关键字,则查找失败。

开放定址法的缺点在于删除元素的时候不能真的删除,否则会引起查找错误,只能做一个特殊标记,直到有下个元素插入才能真正删除该元素。 类似找停车位:

线性探查法

线性探查法(Linear Probing):di = 1,2,3,…,m-1 简单地说,就是以当前冲突位置为起点,步长为1循环查找,直到找到一个空的位置,如果循环完了都占不到位置,就说明容器已经满了。举个栗子,就像你在饭点去街上吃饭,挨家去看是否有位置一样。

平方探测法(Quadratic Probing):di = ±12, ±22,±32,…,±k2(k≤m/2

相对于线性探查法,这就相当于的步长为di = i2来循环查找,直到找到空的位置。以上面那个例子来看,现在你不是挨家去看有没有位置了,而是拿手机算去第i2家店,然后去问这家店有没有位置。

伪随机探测法:di = 伪随机数序

这个就是取随机数来作为步长。还是用上面的例子,这次就是完全按心情去选一家店问有没有位置了。

但开放定址法有这些缺点:

这种方法建立起来的哈希表,当冲突多的时候数据容易堆集在一起,这时候对查找不友好; 删除结点的时候不能简单将结点的空间置空,否则将截断在它填入散列表之后的同义词结点查找路径。因此如果要删除结点,只能在被删结点上添加删除标记,而不能真正删除结点; 如果哈希表的空间已经满了,还需要建立一个溢出表,来存入多出来的元素。

再哈希法

Hi = RHi(key), 其中i=1,2,…,k RHi()函数是不同于H()的哈希函数,用于同义词发生地址冲突时,计算出另一个哈希函数地址,直到不发生冲突位置。这种方法不容易产生堆集,但是会增加计算时间。

所以再哈希法的缺点是:增加了计算时间。

# 拉链法

拉链法 的实现比较简单,将链表和数组相结合。也就是说创建一个链表数组,数组中每一格就是一个链表。若遇到哈希冲突,则将冲突的值加到链表中即可。

将冲突位置的元素构造成链表。在添加数据的时候,如果哈希地址与哈希表上的元素冲突,就放在这个位置的链表上。

拉链法的优点:

处理冲突的方式简单,且无堆集现象,非同义词绝不会发生冲突,因此平均查找长度较短; 由于拉链法中各链表上的结点空间是动态申请的,所以它更适合造表前无法确定表长的情况; 删除结点操作易于实现,只要简单地删除链表上的相应的结点即可。 拉链法的缺点:需要额外的存储空间。

从HashMap的底层结构中我们可以看到,HashMap采用是数组+链表/红黑树的组合来作为底层结构,也就是开放地址法+链地址法的方式来实现HashMap。

Screenshot-2023-08-30-at-17

# 为什么HashMap加载因子一定是0.75?而不是0.8,0.6?

从上文我们知道,HashMap的底层其实也是哈希表(散列表),而解决冲突的方式是链地址法。HashMap的初始容量大小默认是16,为了减少冲突发生的概率,当HashMap的数组长度到达一个临界值的时候,就会触发扩容,把所有元素rehash之后再放在扩容后的容器中,这是一个相当耗时的操作。

而这个临界值就是由加载因子和当前容器的容量大小来确定的:

临界值 = DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR 即默认情况下是16x0.75=12时,就会触发扩容操作。

那么为什么选择了0.75作为HashMap的加载因子呢?这个跟一个统计学里很重要的原理——泊松分布有关。

泊松分布是统计学和概率学常见的离散概率分布,适用于描述单位时间内随机事件发生的次数的概率分布。有兴趣的读者可以看看维基百科或者阮一峰老师的这篇文章:泊松分布和指数分布:10分钟教程[1]

Screenshot-2023-08-30-at-17

等号的左边,P 表示概率,N表示某种函数关系,t 表示时间,n 表示数量。等号的右边,λ 表示事件的频率。

# 那么为什么不可以是0.8或者0.6呢?

HashMap中除了哈希算法之外,有两个参数影响了性能:初始容量和加载因子。初始容量是哈希表在创建时的容量,加载因子是哈希表在其容量自动扩容之前可以达到多满的一种度量。

在维基百科来描述加载因子:

对于开放定址法,加载因子是特别重要因素,应严格限制在0.7-0.8以下。超过0.8,查表时的CPU缓存不命中(cache missing)按照指数曲线上升。因此,一些采用开放定址法的hash库,如Java的系统库限制了加载因子为0.75,超过此值将resize散列表。

在设置初始容量时应该考虑到映射中所需的条目数及其加载因子,以便最大限度地减少扩容rehash操作次数,所以,一般在使用HashMap时建议根据预估值设置初始容量,以便减少扩容操作。

选择0.75作为默认的加载因子,完全是时间和空间成本上寻求的一种折衷选择。

为啥HashMap 桶中超过 8 个才转为红黑树

最开始的 Map 是空的,因为里面没有任何元素,往里放元素时会计算 hash 值,计算之后,第 1 个 value 会首先占用一个桶(也称为槽点)位置,后续如果经过计算发现需要落到同一个桶中,那么便会使用链表的形式往后延长,俗称“拉链法”

当链表长度大于或等于阈值(默认为 8)的时候,如果同时还满足容量大于或等于 MIN_TREEIFY_CAPACITY(默认为 64)的要求,就会把链表转换为红黑树。同样,后续如果由于删除或者其他原因调整了大小,当红黑树的节点小于或等于 6 个以后,又会恢复为链表形态

那为什么不一开始就用红黑树,反而要经历一个转换的过程呢?

通过查看源码可以发现,默认是链表长度达到 8 就转成红黑树,而当长度降到 6 就转换回去,这体现了时间和空间平衡的思想,最开始使用链表的时候,空间占用是比较少的,而且由于链表短,所以查询时间也没有太大的问题。可是当链表越来越长,需要用红黑树的形式来保证查询的效率。对于何时应该从链表转化为红黑树,需要确定一个阈值,这个阈值默认为 8,并且在源码中也对选择 8 这个数字做了说明,

如果 hashCode 分布良好,也就是 hash 计算的结果离散好的话,那么红黑树这种形式是很少会被用到的,因为各个值都均匀分布,很少出现链表很长的情况。在理想情况下,链表长度符合泊松分布,各个长度的命中概率依次递减,当长度为 8 的时候,概率仅为 0.00000006。这是一个小于千万分之一的概率,通常我们的 Map 里面是不会存储这么多的数据的,所以通常情况下,并不会发生从链表向红黑树的转换。

但是,HashMap 决定某一个元素落到哪一个桶里,是和这个对象的 hashCode 有关的,JDK 并不能阻止我们用户实现自己的哈希算法,如果我们故意把哈希算法变得不均匀,

这里 hashCode 计算出来的值始终为 1,那么就很容易导致 HashMap 里的链表变得很长。

链表长度超过 8 就转为红黑树的设计,更多的是为了防止用户自己实现了不好的哈希算法时导致链表过长,从而导致查询效率低,而此时转为红黑树更多的是一种保底策略,用来保证极端情况下查询的效率。

通常如果 hash 算法正常的话,那么链表的长度也不会很长,那么红黑树也不会带来明显的查询时间上的优势,反而会增加空间负担。所以通常情况下,并没有必要转为红黑树,所以就选择了概率非常小,小于千万分之一概率,也就是长度为 8 的概率,把长度 8 作为转化的默认阈值。

# 建立一个公共溢出区

假设哈希函数的值域为[0, m-1],设向量HashTable[0,…,m-1]为基本表,每个分量存放一个记录,另外还设置了向量OverTable[0,…,v]为溢出表。基本表中存储的是关键字的记录,一旦发生冲突,不管他们哈希函数得到的哈希地址是什么,都填入溢出表。

但这个方法的缺点在于:查找冲突数据的时候,需要遍历溢出表才能得到数据。

# 如何对 NSMutableArray 进行 KVO

一般情况下只有通过调用 set 方法对值进行改变才会触发 KVO。但是在调用NSMutableArray的 addObject或removeObject 系列方法时,并不会触发它的 set 方法。所以为了实现NSMutableArray的 KVO,官方为我们提供了如下方法:

@property (nonatomic, strong) NSMutableArray *arr;

//添加元素操作
[[self mutableArrayValueForKey:@"arr"] addObject:item];
//移除元素操作
[[self mutableArrayValueForKey:@"arr"] removeObjectAtIndex:0];
1
2
3
4
5
6

# 符号表

iOS 构建时产生的符号表,是内存地址、函数名、文件名和行号的映射表。格式大概是:

提示

<起始地址> <结束地址> <函数> [<文件名:行号>]

Crash 时的堆栈信息,全是二进制的地址信息。如果利用这些二进制的地址信息来定位问题是不可能的,因此我们需要将这些二进制的地址信息还原成源代码种的函数以及行号,这时候符号表就起作用了。利用符号表将原始的 Crash 的二进制堆栈信息还原成包含行号的源代码文件信息,可以快速定位问题。iOS 中的符号表文件(DSYM) 是在编译源代码后,处理完 Asset Catalog 资源和 info.plist 文件后开始生成,生成符号表文件(DSYM)之后,再进行后续的链接、打包、签名、校验等步骤。

编辑 (opens new window)
上次更新: 2024/10/23, 23:26:17
vdoing主题效果图
OC基础之属性关键字

← vdoing主题效果图 OC基础之属性关键字→

最近更新
01
数组
10-25
02
数组双指针系列之对撞指针
10-25
03
数组双指针系列之快慢指针
10-25
更多文章>
Theme by Vdoing | Copyright © 2019-2024 Evan Xu | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式