这篇主要用来记录一下学习到的关于哈希表的知识点。
文章结构
- 哈希表
- 哈希表的定义
- 哈希表的优缺点
- 哈希碰撞
- 负载因子
- 扩容
- iOS中哈希表的引用
- NSSet
- NSDictionary
- Associated Object
- @synchronized
- weak
哈希表的定义
哈希表是根据key值找到内存地址的数据结构。
它的本质是一个数组,数组中的每一个元素叫做箱子(Bin),箱子中存放的是键值对。根据下标index从数组中获取value值。
通过一个固定函数(哈希函数)将key转换成index。
哈希表优缺点
优点:
- 可以提供快速的操作。
缺点:
- 基于数组的难扩展。
- 有序遍历困难。
Hash碰撞
通过哈希函数不同的key值也会得到相同hash值,这样就会造成哈希冲突(碰撞)的问题。
哈希碰撞的解决方案
开放定址
开放定址法是通过哈希函数计算的index值,如果发生碰撞,则将index++,直到找到那个未被使用的index。拉链法
拉链法简单来说是数组+链表。数组中每个元素指向一个链表,链表中每个节点存储hash出来的索引值为节点下标的键值对。
优缺点:
- 拉链法指针需要额外空间,所以如果结点规模较小的时候适合用开放定址法
- 结点规模大使用开放定址会造成堆积问题、浪费空间。
- 拉链法处理冲突简单,容易删除节点,但节点是动态申请的,无法造表前确定表大小。
负载因子
负载因子 = 总键值数/数组的个数
负载因子是用来衡量哈希表的空/满程度的,负载因子大于(0.75)时,哈希表会自动扩容,一般会创建两倍于原数组长度。因此就算key值无变化,对数组取余后位置也会发生变化,这个过程称为重哈希(rehash)。
扩容
- 数组较多的时候,重新哈希并移动数据,性能影响较大。
- 若哈希函数设计不合理,使得计算的hash值都相同,这样即使扩容它们的位置也在同一个链表上,性能低。
iOS中对哈希表的使用
NSSet、NSDictionary
hash
OC 中有hash方法,通过hash方法计算hash值。通过hash值查找目标位置,如果发生冲突,就解决冲突的方式查找。
相等变量的hash结果总是相同的,不想等变量的hash结果也可能相同。
hash化是一个取得变量特征的过程,这个过程可以是取出变量的特征,也可能是一个计算。
hash方法的调用
Person *person1 = [Person personWithName:kName1 birthday:self.date1];
Person *person2 = [Person personWithName:kName2 birthday:self.date2];
NSMutableArray *array1 = [NSMutableArray array];
[array1 addObject:person1];
NSMutableArray *array2 = [NSMutableArray array];
[array2 addObject:person2];
NSLog(@"array end -------------------------------");
NSMutableSet *set1 = [NSMutableSet set];
[set1 addObject:person1];
NSMutableSet *set2 = [NSMutableSet set];
[set2 addObject:person2];
NSLog(@"set end -------------------------------");
NSMutableDictionary *dictionaryValue1 = [NSMutableDictionary dictionary];
[dictionaryValue1 setObject:person1 forKey:kKey1];
NSMutableDictionary *dictionaryValue2 = [NSMutableDictionary dictionary];
[dictionaryValue2 setObject:person2 forKey:kKey2];
NSLog(@"dictionary value end -------------------------------");
NSMutableDictionary *dictionaryKey1 = [NSMutableDictionary dictionary];
[dictionaryKey1 setObject:kValue1 forKey:person1];
NSMutableDictionary *dictionaryKey2 = [NSMutableDictionary dictionary];
[dictionaryKey2 setObject:kValue2 forKey:person2];
NSLog(@"dictionary key end -------------------------------");
重写hash方法:
- (NSUInteger)hash {
NSUInteger hash = [super hash];
NSLog(@"走过 hash");
return hash;
}
打印结果:
array end -------------------------------
走过 hash
走过 hash
走过 hash
走过 hash
set end -------------------------------
dictionary value end -------------------------------
走过 hash
走过 hash
走过 hash
走过 hash
dictionary key end -------------------------------
hash方法只有在对象加入到NSSet和设置NSDictionary的key时调用。
NSSet
struct __CFSet {
CFRuntimeBase _base;
CFIndex _count; /* number of values */
CFIndex _capacity; /* maximum number of values */
CFIndex _bucketsNum; /* number of slots */
uintptr_t _marker;
void *_context; /* private */
CFIndex _deletes;
CFOptionFlags _xflags; /* bits for GC */
const void **_keys; /* can be NULL if not allocated yet */
};
通过数据结构,发现set内部使用指针数组保存keys。
基于不同的初始化,hash值存在不同的运算,如下源码可知。
static CFIndex __CFSetFindBucketsXX(CFSetRef set, const void *key) {
CFHashCode keyHash = (CFHashCode)key;
const CFSetCallBacks *cb = __CFSetGetKeyCallBacks(set);
CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, set->_context) : (CFHashCode)key;
const void **keys = set->_keys;
CFIndex probe = keyHash % set->_bucketsNum;
}
添加value时,回先判断key值是否存在,如果存在则什么都不做。所以set可以重复保存数据。
通过计算获取到的hash值获取value所在hash表的位置,如果发生冲突了采用开放定址法将指针++ ,来解决哈希冲突。
void CFSetAddValue(CFMutableSetRef set, const void *key) {
// 通过 match、nomatch 判断Set是否存在key
CFIndex match, nomatch;
__CFSetFindBuckets2(set, key, &match, &nomatch);
if (kCFNotFound != match) {
// 存在key,则什么都不做
} else {
// 不存在,则添加到set中
CF_OBJC_KVO_WILLCHANGE(set, key);
CF_WRITE_BARRIER_ASSIGN(keysAllocator, set->_keys[nomatch], newKey);
set->_count++;
CF_OBJC_KVO_DIDCHANGE(set, key);
}
}
static void __CFSetFindBuckets2(CFSetRef set, const void *key, CFIndex *match, CFIndex *nomatch) {
const CFSetCallBacks *cb = __CFSetGetKeyCallBacks(set);
// 获取hash值
CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, set->_context) : (CFHashCode)key;
const void **keys = set->_keys;
uintptr_t marker = set->_marker;
CFIndex probe = keyHash % set->_bucketsNum;
CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
CFIndex start = probe;
*match = kCFNotFound;
*nomatch = kCFNotFound;
for (;;) {
uintptr_t currKey = (uintptr_t)keys[probe];
// 如果hash值对应的是空闲区域,那么标记nomatch,返回不存在key
if (marker == currKey) { /* empty */
if (nomatch) *nomatch = probe;
return;
} else if (~marker == currKey) { /* deleted */
if (nomatch) {
*nomatch = probe;
nomatch = NULL;
}
} else if (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))cb->equal, (void *)currKey, key, set->_context))) {
// 标记match,返回存在key
*match = probe;
return;
}
// 没有匹配,说明发生了冲突,那么将数组下标后移,知道找到空闲区域位置
probe = probe + probeskip;
if (set->_bucketsNum <= probe) {
probe -= set->_bucketsNum;
}
if (start == probe) {
return;
}
}
}
新增元素时,如果超过了阈值会调用扩容的方法。扩容后会重新计算hash值。
// 新增元素的时候会判断
void CFSetAddValue(CFMutableSetRef set, const void *key) {
...
if (set->_count == set->_capacity || NULL == set->_keys) {
// 调用扩容
__CFSetGrow(set, 1);
}
...
}
// 扩容
static void __CFSetGrow(CFMutableSetRef set, CFIndex numNewValues) {
// 保存旧值key的数据
const void **oldkeys = set->_keys;
CFIndex idx, oldnbuckets = set->_bucketsNum;
CFIndex oldCount = set->_count;
CFAllocatorRef allocator = __CFGetAllocator(set), keysAllocator;
void *keysBase;
set->_capacity = __CFSetRoundUpCapacity(oldCount + numNewValues);
set->_bucketsNum = __CFSetNumBucketsForCapacity(set->_capacity);
set->_deletes = 0;
void *buckets = _CFAllocatorAllocateGC(allocator, set->_bucketsNum * sizeof(const void *), (set->_xflags & __kCFSetWeakKeys) ? AUTO_MEMORY_UNSCANNED : AUTO_MEMORY_SCANNED);
// 扩容key
CF_WRITE_BARRIER_BASE_ASSIGN(allocator, set, set->_keys, buckets);
keysAllocator = allocator;
keysBase = set->_keys;
if (NULL == set->_keys) HALT;
if (__CFOASafe) __CFSetLastAllocationEventName(set->_keys, "CFSet (store)");
// 重新计算key的hash值,存放到新数组中
for (idx = set->_bucketsNum; idx--;) {
set->_keys[idx] = (const void *)set->_marker;
}
if (NULL == oldkeys) return;
for (idx = 0; idx < oldnbuckets; idx++) {
if (set->_marker != (uintptr_t)oldkeys[idx] && ~set->_marker != (uintptr_t)oldkeys[idx]) {
CFIndex match, nomatch;
__CFSetFindBuckets2(set, oldkeys[idx], &match, &nomatch);
CFAssert3(kCFNotFound == match, __kCFLogAssertion, "%s(): two values (%p, %p) now hash to the same slot; mutable value changed while in table or hash value is not immutable", __PRETTY_FUNCTION__, oldkeys[idx], set->_keys[match]);
if (kCFNotFound != nomatch) {
CF_WRITE_BARRIER_BASE_ASSIGN(keysAllocator, keysBase, set->_keys[nomatch], oldkeys[idx]);
}
}
}
CFAssert1(set->_count == oldCount, __kCFLogAssertion, "%s(): set count differs after rehashing; error", __PRETTY_FUNCTION__);
_CFAllocatorDeallocateGC(allocator, oldkeys);
}
NSDictionary
字典的数据结构如下,它由两个指针数组分别保存keys和values。
struct __CFDictionary {
CFRuntimeBase _base;
CFIndex _count; /* number of values */
CFIndex _capacity; /* maximum number of values */
CFIndex _bucketsNum; /* number of slots */
uintptr_t _marker;
void *_context; /* private */
CFIndex _deletes;
CFOptionFlags _xflags; /* bits for GC */
const void **_keys; /* can be NULL if not allocated yet */
const void **_values; /* can be NULL if not allocated yet */
};
同样也是使用开放定址法来解决哈希冲突问题。如果使用拉链法key与value应该是一个存储结构。与集合不同的是,如果key存在的话需要覆盖旧值,添加新值。
而且开放定址法的查找算法接近O(1)。
void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
// 通过match,nomatch来判断是否存在key
CFIndex match, nomatch;
__CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
。。。
if (kCFNotFound != match) {
// key已存在,覆盖newValue
CF_OBJC_KVO_WILLCHANGE(dict, key);
CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[match], newValue);
CF_OBJC_KVO_DIDCHANGE(dict, key);
} else {
// key不存在,新增value
CF_OBJC_KVO_WILLCHANGE(dict, key);
CF_WRITE_BARRIER_ASSIGN(keysAllocator, dict->_keys[nomatch], newKey);
CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[nomatch], newValue);
dict->_count++;
CF_OBJC_KVO_DIDCHANGE(dict, key);
}
}
// 查找key存储的位置
static void __CFDictionaryFindBuckets2(CFDictionaryRef dict, const void *key, CFIndex *match, CFIndex *nomatch) {
const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
// 获取hash值
CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, dict->_context) : (CFHashCode)key;
const void **keys = dict->_keys;
uintptr_t marker = dict->_marker;
CFIndex probe = keyHash % dict->_bucketsNum;
CFIndex probeskip = 1; // See RemoveValue() for notes before changing this value
CFIndex start = probe;
*match = kCFNotFound;
*nomatch = kCFNotFound;
for (;;) {
uintptr_t currKey = (uintptr_t)keys[probe];
// 空桶,返回nomatch,未匹配
if (marker == currKey) { /* empty */
if (nomatch) *nomatch = probe;
return;
} else if (~marker == currKey) { /* deleted */
if (nomatch) {
*nomatch = probe;
nomatch = NULL;
}
} else if (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))cb->equal, (void *)currKey, key, dict->_context))) {
// 匹配成功,返回match
*match = probe;
return;
}
// 未匹配,发生碰撞,将数组下标后移,直到找到空闲区域位置
probe = probe + probeskip;
if (dict->_bucketsNum <= probe) {
probe -= dict->_bucketsNum;
}
if (start == probe) {
return;
}
}
}
因为字典中key-value是一一对应的关系,所以要保证keys和values数组的长度要一致。所以扩容的时候需要一起扩容。
// setValue时判断
void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
...
if (dict->_count == dict->_capacity || NULL == dict->_keys) {
__CFDictionaryGrow(dict, 1);
}
...
}
// 扩容
static void __CFDictionaryGrow(CFMutableDictionaryRef dict, CFIndex numNewValues) {
// 保存旧值
const void **oldkeys = dict->_keys;
const void **oldvalues = dict->_values;
CFIndex idx, oldnbuckets = dict->_bucketsNum;
CFIndex oldCount = dict->_count;
CFAllocatorRef allocator = __CFGetAllocator(dict), keysAllocator, valuesAllocator;
void *keysBase, *valuesBase;
dict->_capacity = __CFDictionaryRoundUpCapacity(oldCount + numNewValues);
dict->_bucketsNum = __CFDictionaryNumBucketsForCapacity(dict->_capacity);
dict->_deletes = 0;
...
CF_WRITE_BARRIER_BASE_ASSIGN(allocator, dict, dict->_keys, _CFAllocatorAllocateGC(allocator, 2 * dict->_bucketsNum * sizeof(const void *), AUTO_MEMORY_SCANNED));
dict->_values = (const void **)(dict->_keys + dict->_bucketsNum);
keysAllocator = valuesAllocator = allocator;
keysBase = valuesBase = dict->_keys;
if (NULL == dict->_keys || NULL == dict->_values) HALT;
...
// 重新计算keys数据的hash值,存放到新的数组中
for (idx = dict->_bucketsNum; idx--;) {
dict->_keys[idx] = (const void *)dict->_marker;
dict->_values[idx] = 0;
}
if (NULL == oldkeys) return;
for (idx = 0; idx < oldnbuckets; idx++) {
if (dict->_marker != (uintptr_t)oldkeys[idx] && ~dict->_marker != (uintptr_t)oldkeys[idx]) {
CFIndex match, nomatch;
__CFDictionaryFindBuckets2(dict, oldkeys[idx], &match, &nomatch);
CFAssert3(kCFNotFound == match, __kCFLogAssertion, "%s(): two values (%p, %p) now hash to the same slot; mutable value changed while in table or hash value is not immutable", __PRETTY_FUNCTION__, oldkeys[idx], dict->_keys[match]);
if (kCFNotFound != nomatch) {
CF_WRITE_BARRIER_BASE_ASSIGN(keysAllocator, keysBase, dict->_keys[nomatch], oldkeys[idx]);
CF_WRITE_BARRIER_BASE_ASSIGN(valuesAllocator, valuesBase, dict->_values[nomatch], oldvalues[idx]);
}
}
}
...
}
dictionary之所以采用这种设计,其一出于查询性能的考虑;其二dictionary在使用过程中总是会很快的被释放,不会长期占用内存。
AssociatedObject关联对象
关联对象它实现了不通过继承来增加属性的需求。通过源码可以发现关联对象内部使用了嵌套map的结构实现了对象的扩展属性管理。也是采用了开放定址法。
void _object_set_associative_reference(id object, void *key, id value, uintptr_t policy) {
/// 获取associated object全局map
AssociationsManager manager;
AssociationsHashMap &associations(manager.associations());
/// DISGUISE宏定义获取对象的唯一值,等同于hash方法
disguised_ptr_t disguised_object = DISGUISE(object);
if (new_value) {
AssociationsHashMap::iterator i = associations.find(disguised_object);
if (i != associations.end()) {
/// 结果不等于未匹配end()
ObjectAssociationMap *refs = i->second;
ObjectAssociationMap::iterator j = refs->find(key);
if (j != refs->end()) {
old_association = j->second;
j->second = ObjcAssociation(policy, new_value);
} else {
(*refs)[key] = ObjcAssociation(policy, new_value);
}
} else {
/// 对象未绑定过任何属性,新增map存储
ObjectAssociationMap *refs = new ObjectAssociationMap;
associations[disguised_object] = refs;
(*refs)[key] = ObjcAssociation(policy, new_value);
_class_setInstancesHaveAssociatedObjects(_object_getClass(object));
}
} else {
AssociationsHashMap::iterator i = associations.find(disguised_object);
/// 结果不等于未匹配end()
if (i != associations.end()) {
ObjectAssociationMap *refs = i->second;
ObjectAssociationMap::iterator j = refs->find(key);
if (j != refs->end()) {
old_association = j->second;
refs->erase(j);
}
}
}
}
ObjectAssociationMap是被上面嵌套的dictionary,这个结构存储了实际绑定的属性值。在我们调用objc_setAssociatedObject的时候,会将传入的key和value存储在这里面。
开放定址法在大量数据存储时,会造成大量空间占用。为什么要使用这种方案呢?因为虽然苹果使用了一个全局的AssociationsHashMap对象存储了全部的关联对象,但在对象dealloc时会移除这些数据,同一时间占用的内存也是可接受的。
@sychronized
@sychronized 采用了hash+linked实现结构,参照源码,实际上使用了拉链法解决碰撞问题。在代码编译时,转换成了以下函数调用:
int objc_sync_enter(id obj);
int objc_sync_exit(id obj);
相比一般拉链法的设计,@sychronized增加了缓存机制,下面是关键结构:
typedef struct SyncData {
struct SyncData* nextData;
id object;
int threadCount;
recursive_mutex_t mutex;
} SyncData;
typedef struct {
SyncData *data;
OSSpinLock lock;
char align[64 - sizeof (OSSpinLock) - sizeof (SyncData *)];
} SyncList __attribute__((aligned(64)));
#define COUNT 16
#define HASH(obj) ((((uintptr_t)(obj)) >> 5) & (COUNT - 1))
#define LOCK_FOR_OBJ(obj) sDataLists[HASH(obj)].lock
#define LIST_FOR_OBJ(obj) sDataLists[HASH(obj)].data
static SyncList sDataLists[COUNT];
在代码@synchronized(x)中一开始有一个结构体 struct SyncData,这个结构体中包括object就是传入的对象以及和x关联的锁mutex。结构体中还包括nextData这是明显的链表特征。threadCount记录对象被锁线程使用的数量,当threadCount=0的时候,可以拿出来复用,赋值给其他对象。
链表SyncList,里面有头节点SyncData,防止多线程修改链表头结点的自旋锁 OSSpinLock。这里可以看出@synchronized(x)是使用拉链法解决冲突的,因此设计了链表。
下面来看下hash算法HASH(obj),将对象的指针传入,然后向右位移5,和COUNT-1进行与运算,这样结果不会超过数组长度。那么下面两个宏就很好理解了LOCK_FOR_OBJ和LIST_FOR_OBJ,传入的对象进行HASH运算,算出0-15的一个index,然后数组直接指针偏移以O(1),直接拿出数据,如果不同对象放在同一个index,冲突就在一条链表中,继续遍历链表拿数据。
为什么同样是使用全局存储的方式@synchronized和associated采用的方式不一样。
其实主要是根据存储数据的生命周期和特性所决定的:
- 开放定址法的存储属性基本是和key所属对象相关联的,一旦key所属对象发生变化时,其所存储的数据大概率也是要发生修改的。因此即便是开放定址法在使用全局实现时,对象释放时同样会清空所存储的内容,因此总体来说内存占用并不会过高。
- 拉链法对于碰撞的处理方式更为简单,不用担心数据的堆积现象。另外如果存储的数据是通用类型数据,可以被反复利用。比如@synchronized是存储的锁是一种无关业务的实现结构,程序运行时多个对象使用同一个锁的概率相当的高,有效的节省了内存。
weak的实现
每次准备面试的时候背八股文的时候都说,weak修饰的对象是弱引用,引用计数不会+1,在释放的时候会自动置为nil。用weak修饰的对象,会以对象的指针为key,weak指针为value放在weak表中。释放的时候,找到通过对象地址找到weak指针,然后置为nil。这次有时间努力地学习了一下原理。
当然weak表也是用哈希表实现的,所以放到这篇一起介绍。
objc_initWeak方法
Person *object = [Person alloc];
id __weak objc = object;
当我们将对象赋值给weak修饰的对象时,会调用objc_initWeak方法。
该方法主要参数
- location: weak指针地址,存储指针的地址,这样便可以在最后将其指向的对象置为nil。
- newObj:引用的对象,就是例子中的obj。
id objc_initWeak(id *location, id newObj)
{
if (!newObj) {
*location = nil;
return nil;
}
return storeWeak<DontHaveOld, DoHaveNew, DoCrashIfDeallocating>
(location, (objc_object*)newObj);
}
objc_initWeak方法内部主要调用了storeWeak方法。
storeWeak
storeWeak的实现:
// Template parameters.
enum HaveOld { DontHaveOld = false, DoHaveOld = true };
enum HaveNew { DontHaveNew = false, DoHaveNew = true };
enum CrashIfDeallocating {
DontCrashIfDeallocating = false, DoCrashIfDeallocating = true
};
template <HaveOld haveOld, HaveNew haveNew,
CrashIfDeallocating crashIfDeallocating>
static id
storeWeak(id *location, objc_object *newObj)
{
assert(haveOld || haveNew);
if (!haveNew) assert(newObj == nil);
Class previouslyInitializedClass = nil;
id oldObj;
SideTable *oldTable;
SideTable *newTable;
// Acquire locks for old and new values.
// Order by lock address to prevent lock ordering problems.
// Retry if the old value changes underneath us.
retry:
if (haveOld) { // 如果weak ptr之前弱引用过一个obj,则将这个obj所对应的SideTable取出,赋值给oldTable
oldObj = *location;
oldTable = &SideTables()[oldObj];
} else {
oldTable = nil; // 如果weak ptr之前没有弱引用过一个obj,则oldTable = nil
}
if (haveNew) { // 如果weak ptr要weak引用一个新的obj,则将该obj对应的SideTable取出,赋值给newTable
newTable = &SideTables()[newObj];
} else {
newTable = nil; // 如果weak ptr不需要引用一个新obj,则newTable = nil
}
// 加锁操作,防止多线程中竞争冲突
SideTable::lockTwo<haveOld, haveNew>(oldTable, newTable);
// location 应该与 oldObj 保持一致,如果不同,说明当前的 location 已经处理过 oldObj 可是又被其他线程所修改
if (haveOld && *location != oldObj) {
SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
goto retry;
}
// Prevent a deadlock between the weak reference machinery
// and the +initialize machinery by ensuring that no
// weakly-referenced object has an un-+initialized isa.
if (haveNew && newObj) {
Class cls = newObj->getIsa();
if (cls != previouslyInitializedClass &&
!((objc_class *)cls)->isInitialized()) // 如果cls还没有初始化,先初始化,再尝试设置weak
{
SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
_class_initialize(_class_getNonMetaClass(cls, (id)newObj));
// If this class is finished with +initialize then we're good.
// If this class is still running +initialize on this thread
// (i.e. +initialize called storeWeak on an instance of itself)
// then we may proceed but it will appear initializing and
// not yet initialized to the check above.
// Instead set previouslyInitializedClass to recognize it on retry.
previouslyInitializedClass = cls; // 这里记录一下previouslyInitializedClass, 防止改if分支再次进入
goto retry; // 重新获取一遍newObj,这时的newObj应该已经初始化过了
}
}
// Clean up old value, if any.
if (haveOld) {
weak_unregister_no_lock(&oldTable->weak_table, oldObj, location); // 如果weak_ptr之前弱引用过别的对象oldObj,则调用weak_unregister_no_lock,在oldObj的weak_entry_t中移除该weak_ptr地址
}
// Assign new value, if any.
if (haveNew) { // 如果weak_ptr需要弱引用新的对象newObj
// (1) 调用weak_register_no_lock方法,将weak ptr的地址记录到newObj对应的weak_entry_t中
newObj = (objc_object *)
weak_register_no_lock(&newTable->weak_table, (id)newObj, location,
crashIfDeallocating);
// weak_register_no_lock returns nil if weak store should be rejected
// (2) 更新newObj的isa的weakly_referenced bit标志位
// Set is-weakly-referenced bit in refcount table.
if (newObj && !newObj->isTaggedPointer()) {
newObj->setWeaklyReferenced_nolock();
}
// Do not set *location anywhere else. That would introduce a race.
// (3)*location 赋值,也就是将weak ptr直接指向了newObj。可以看到,这里并没有将newObj的引用计数+1
*location = (id)newObj; // 将weak ptr指向object
}
else {
// No new value. The storage is not changed.
}
// 解锁,其他线程可以访问oldTable, newTable了
SideTable::unlockTwo<haveOld, haveNew>(oldTable, newTable);
return (id)newObj; // 返回newObj,此时的newObj与刚传入时相比,weakly-referenced bit位置1
}
下图可以比较清晰的描述了storeWeak的过程:
- 维护了oldTable和newTable
- 加锁处理
- 调用weak_unregister_no_lock移除旧引用 和weak_register_no_lock添加新引用 这两个方法。而这两个方法都是操作的SideTable 这样一个结构的变量 。
- 调用setWeaklyReferenced_nolock 方法修改weak新引用的对象的bit标志位
SideTable、weak_table_t、weak_entry_t
SideTable
struct SideTable {
spinlock_t slock;
RefcountMap refcnts;
weak_table_t weak_table;
}
SideTable有三个成员:
- slock: 自旋锁,用于上锁Si的Table
- refcnts:用来存储OC对象的引用计数的 hash表(仅在未开启isa优化或在isa优化情况下isa_t的引用计数溢出时才会用到)。
- weak_table 存储对象弱引用指针的hash表。是OC中weak功能实现的核心数据结构。
weak_table_t
struct weak_table_t {
weak_entry_t *weak_entries;
size_t num_entries;
uintptr_t mask;
uintptr_t max_hash_displacement;
};
weak_table_t:
- weak_entries : hash数组,用来存储弱引用对象的相关信息
- num_entries:hash数组中的元素个数
- mask:hash数组长度-1,会参与hash计算。(注意,这里是hash数组的长度,而不是元素个数。比如,数组长度可能是64,而元素个数仅存了2个)
- max_hash_displacement:可能会发生的hash冲突的最大次数,用于判断是否出现了逻辑错误(hash表中的冲突次数绝不会超过改值)
weak_entry_t
weak_entry_t结构也是一个hash结构,其存储的元素是弱引用对象指针的地址。
定长数组inline_referrers的引用个数最大值为4。
动态数组的默认长度是8,这里要考虑到entry->mask取值,一定是:0x111, 0x1111, 0x11111, ... ,因为数组每次都是*2增长,即8, 16, 32
#define WEAK_INLINE_COUNT 4
#define REFERRERS_OUT_OF_LINE 2
struct weak_entry_t {
DisguisedPtr<objc_object> referent; // 被弱引用的对象
// 引用该对象的对象列表,联合。 引用个数小于4,用inline_referrers数组。 用个数大于4,用动态数组weak_referrer_t *referrers
union {
struct {
weak_referrer_t *referrers; // 弱引用该对象的对象指针地址的hash数组
uintptr_t out_of_line_ness : 2; // 是否使用动态hash数组标记位
uintptr_t num_refs : PTR_MINUS_2; // hash数组中的元素个数
uintptr_t mask; // hash数组长度-1,会参与hash计算。
uintptr_t max_hash_displacement; // 可能会发生的hash冲突的最大次数,用于判断是否出现了逻辑错误
};
struct {
// out_of_line_ness field is low bits of inline_referrers[1]
weak_referrer_t inline_referrers[WEAK_INLINE_COUNT];
};
};
bool out_of_line() {
return (out_of_line_ness == REFERRERS_OUT_OF_LINE);
}
weak_entry_t& operator=(const weak_entry_t& other) {
memcpy(this, &other, sizeof(other));
return *this;
}
weak_entry_t(objc_object *newReferent, objc_object **newReferrer)
: referent(newReferent) // 构造方法,里面初始化了静态数组
{
inline_referrers[0] = newReferrer;
for (int i = 1; i < WEAK_INLINE_COUNT; i++) {
inline_referrers[i] = nil;
}
}
};
- weak_entry_t是一个联合体,在联合体内部有定长数组inline_referrers和动态数组weak_referrer_t存储弱引用对象的指针地址。
- out_of_line()通过这个方法判断是哪种存储方式。
- 当指针数少于WEAK_INLINE_COUNT时,使用定长数组。超过使用动态数组。
到这里我们知道了啥?
weak底层主要调用了storeWeak(),在这个方法中,维护了两个sidetable,带调用weak_unregister_no_lock 和weak_register_no_lock 这两个方法添加和移除弱引用。
弱引用表是一个哈希表,key是对象指针,value是弱引用指针地址的数组。
weak_register_no_lock 添加弱引用
参数解释:
- weak_table:weak表
- referent_id: 对象地址
- *referrer_id: weak指针地址
- crashIfDeallocating: 是否正在析构
这个方法主要做个几件事:
- 如果referent_id是空或采用了TaggedPointer计数方式,直接返回,不做任何操作
- 正在析构会抛异常
- 不能被弱引用,返回nil
- 调用 weak_entry_for_referent方法,根据对象地址查找weak_entry,然后调用append_referrer将weak指针地址加到数组中。
id
weak_register_no_lock(weak_table_t *weak_table, id referent_id,
id *referrer_id, bool crashIfDeallocating)
{
objc_object *referent = (objc_object *)referent_id;
objc_object **referrer = (objc_object **)referrer_id;
// 如果referent为nil 或 referent 采用了TaggedPointer计数方式,直接返回,不做任何操作
if (!referent || referent->isTaggedPointer()) return referent_id;
// 确保被引用的对象可用(没有在析构,同时应该支持weak引用)
bool deallocating;
if (!referent->ISA()->hasCustomRR()) {
deallocating = referent->rootIsDeallocating();
}
else {
BOOL (*allowsWeakReference)(objc_object *, SEL) =
(BOOL(*)(objc_object *, SEL))
object_getMethodImplementation((id)referent,
SEL_allowsWeakReference);
if ((IMP)allowsWeakReference == _objc_msgForward) {
return nil;
}
deallocating =
! (*allowsWeakReference)(referent, SEL_allowsWeakReference);
}
// 正在析构的对象,不能够被弱引用
if (deallocating) {
if (crashIfDeallocating) {
_objc_fatal("Cannot form weak reference to instance (%p) of "
"class %s. It is possible that this object was "
"over-released, or is in the process of deallocation.",
(void*)referent, object_getClassName((id)referent));
} else {
return nil;
}
}
// now remember it and where it is being stored
// 在 weak_table中找到referent对应的weak_entry,并将referrer加入到weak_entry中
weak_entry_t *entry;
if ((entry = weak_entry_for_referent(weak_table, referent))) { // 如果能找到weak_entry,则讲referrer插入到weak_entry中
append_referrer(entry, referrer); // 将referrer插入到weak_entry_t的引用数组中
}
else { // 如果找不到,就新建一个
weak_entry_t new_entry(referent, referrer);
weak_grow_maybe(weak_table);
weak_entry_insert(weak_table, &new_entry);
}
// Do not set *referrer. objc_storeWeak() requires that the
// value not change.
return referent_id;
}
weak_entry_for_referent 取元素
static weak_entry_t *
weak_entry_for_referent(weak_table_t *weak_table, objc_object *referent)
{
assert(referent);
weak_entry_t *weak_entries = weak_table->weak_entries;
if (!weak_entries) return nil;
size_t begin = hash_pointer(referent) & weak_table->mask; // 这里通过 & weak_table->mask的位操作,来确保index不会越界
size_t index = begin;
size_t hash_displacement = 0;
while (weak_table->weak_entries[index].referent != referent) {
index = (index+1) & weak_table->mask;
if (index == begin) bad_weak_table(weak_table->weak_entries); // 触发bad weak table crash
hash_displacement++;
if (hash_displacement > weak_table->max_hash_displacement) { // 当hash冲突超过了可能的max hash 冲突时,说明元素没有在hash表中,返回nil
return nil;
}
}
return &weak_table->weak_entries[index];
}
append_referrer添加元素
- 添加元素的时候,需要先确定是定长数组还是动态数组,如果weak_entry尚未使用动态数组则直接添加到数组中即可。
- 如果inline_referrers已经满了,则需要转型到到动态数组
- 如果动态数组“负载因子”大于3/4,需要动态扩容。
- 采用开放定址法,发生哈希冲突时,将index++
static void append_referrer(weak_entry_t *entry, objc_object **new_referrer)
{
if (! entry->out_of_line()) { // 如果weak_entry 尚未使用动态数组,走这里
// Try to insert inline.
for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
if (entry->inline_referrers[i] == nil) {
entry->inline_referrers[i] = new_referrer;
return;
}
}
// 如果inline_referrers的位置已经存满了,则要转型为referrers,做动态数组。
// Couldn't insert inline. Allocate out of line.
weak_referrer_t *new_referrers = (weak_referrer_t *)
calloc(WEAK_INLINE_COUNT, sizeof(weak_referrer_t));
// This constructed table is invalid, but grow_refs_and_insert
// will fix it and rehash it.
for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
new_referrers[i] = entry->inline_referrers[I];
}
entry->referrers = new_referrers;
entry->num_refs = WEAK_INLINE_COUNT;
entry->out_of_line_ness = REFERRERS_OUT_OF_LINE;
entry->mask = WEAK_INLINE_COUNT-1;
entry->max_hash_displacement = 0;
}
// 对于动态数组的附加处理:
assert(entry->out_of_line()); // 断言: 此时一定使用的动态数组
if (entry->num_refs >= TABLE_SIZE(entry) * 3/4) { // 如果动态数组中元素个数大于或等于数组位置总空间的3/4,则扩展数组空间为当前长度的一倍
return grow_refs_and_insert(entry, new_referrer); // 扩容,并插入
}
// 如果不需要扩容,直接插入到weak_entry中
// 注意,weak_entry是一个哈希表,key:w_hash_pointer(new_referrer) value: new_referrer
// 细心的人可能注意到了,这里weak_entry_t 的hash算法和 weak_table_t的hash算法是一样的,同时扩容/减容的算法也是一样的
size_t begin = w_hash_pointer(new_referrer) & (entry->mask); // '& (entry->mask)' 确保了 begin的位置只能大于或等于 数组的长度
size_t index = begin; // 初始的hash index
size_t hash_displacement = 0; // 用于记录hash冲突的次数,也就是hash再位移的次数
while (entry->referrers[index] != nil) {
hash_displacement++;
index = (index+1) & entry->mask; // index + 1, 移到下一个位置,再试一次能否插入。(这里要考虑到entry->mask取值,一定是:0x111, 0x1111, 0x11111, ... ,因为数组每次都是*2增长,即8, 16, 32,对应动态数组空间长度-1的mask,也就是前面的取值。)
if (index == begin) bad_weak_table(entry); // index == begin 意味着数组绕了一圈都没有找到合适位置,这时候一定是出了什么问题。
}
if (hash_displacement > entry->max_hash_displacement) { // 记录最大的hash冲突次数, max_hash_displacement意味着: 我们尝试至多max_hash_displacement次,肯定能够找到object对应的hash位置
entry->max_hash_displacement = hash_displacement;
}
// 将ref存入hash数组,同时,更新元素个数num_refs
weak_referrer_t &ref = entry->referrers[index];
ref = new_referrer;
entry->num_refs++;
}
weak_unregister_no_lock 移除引用
调用weak_unregister_no_lock方法将旧的weak指针地址移除。
- 先在table中entry
- 找到后将referrer从entry中移除
- 移除后需要判断entry是否还有值
- 如果没有将entry从table中移除
void
weak_unregister_no_lock(weak_table_t *weak_table, id referent_id,
id *referrer_id)
{
objc_object *referent = (objc_object *)referent_id;
objc_object **referrer = (objc_object **)referrer_id;
weak_entry_t *entry;
if (!referent) return;
if ((entry = weak_entry_for_referent(weak_table, referent))) { // 查找到referent所对应的weak_entry_t
remove_referrer(entry, referrer); // 在referent所对应的weak_entry_t的hash数组中,移除referrer
// 移除元素之后, 要检查一下weak_entry_t的hash数组是否已经空了
bool empty = true;
if (entry->out_of_line() && entry->num_refs != 0) {
empty = false;
}
else {
for (size_t i = 0; i < WEAK_INLINE_COUNT; i++) {
if (entry->inline_referrers[i]) {
empty = false;
break;
}
}
}
if (empty) { // 如果weak_entry_t的hash数组已经空了,则需要将weak_entry_t从weak_table中移除
weak_entry_remove(weak_table, entry);
}
}
到这里我们知道了啥?
知道了weak_register_no_lock添加弱引用,weak_unregister_no_lock移除弱引用,这两个方法的具体实现。
引用计数不会+1,只是在weak_table中添加entry。
dealloc
_objc_rootDealloc
当对象的引用计数为0时,底层会调用_objc_rootDealloc方法对对象进行释放,而在_objc_rootDealloc方法里面会调用rootDealloc方法。
inline void
objc_object::rootDealloc()
{
if (isTaggedPointer()) return; // fixme necessary?
if (fastpath(isa.nonpointer &&
!isa.weakly_referenced &&
!isa.has_assoc &&
!isa.has_cxx_dtor &&
!isa.has_sidetable_rc))
{
assert(!sidetable_present());
free(this);
}
else {
object_dispose((id)this);
}
}
- 首先判断对象是否是Tagged Pointer,如果是则直接返回。
- 如果对象是采用了优化的isa计数方式,且同时满足对象没有被weak引用!isa.weakly_referenced、没有关联对象!isa.has_assoc 、没有自定义的C++析构方法!isa.has_cxx_dtor、没有用到SideTable来引用计数!isa.has_sidetable_rc则直接快速释放。
- 调用object_dispose方法释放。
object_dispose
- 如果有自定义的C++析构方法,则调用C++析构函数。
- 如果有关联对象,则移除关联对象并将其自身从Association Manager的map中移除。
- 调用clearDeallocating 方法清除对象的相关引用。
void *objc_destructInstance(id obj)
{
if (obj) {
// Read all of the flags at once for performance.
bool cxx = obj->hasCxxDtor();
bool assoc = obj->hasAssociatedObjects();
// This order is important.
if (cxx) object_cxxDestruct(obj);
if (assoc) _object_remove_assocations(obj);
obj->clearDeallocating();
}
return obj;
}
clearDeallocating
- 判断是否开启了isa优化,如果未开启需要清理引用计数表
- 如果isa有辅助引用计数或有weak引用,调用clearDeallocating_slow方法
inline void
objc_object::clearDeallocating()
{
if (slowpath(!isa.nonpointer)) {
// Slow path for raw pointer isa.
sidetable_clearDeallocating();
}
else if (slowpath(isa.weakly_referenced || isa.has_sidetable_rc)) {
// Slow path for non-pointer isa with weak refs and/or side table data.
clearDeallocating_slow();
}
assert(!sidetable_present());
}
NEVER_INLINE void
objc_object::clearDeallocating_slow()
{
assert(isa.nonpointer && (isa.weakly_referenced || isa.has_sidetable_rc));
SideTable& table = SideTables()[this]; // 在全局的SideTables中,以this指针为key,找到对应的SideTable
table.lock();
if (isa.weakly_referenced) { // 如果obj被弱引用
weak_clear_no_lock(&table.weak_table, (id)this); // 在SideTable的weak_table中对this进行清理工作
}
if (isa.has_sidetable_rc) { // 如果采用了SideTable做引用计数
table.refcnts.erase(this); // 在SideTable的引用计数中移除this
}
table.unlock();
}
- clearDeallocating_slow方法中如果isa有weak引用,调用weak_clear_no_lock对weak_table进行清理工作
weak_clear_no_lock
- 获取动态和定长数组,并且获取数组个数
- 遍历数组,取出weak指针地址,并设置为nil。
- 将entry从weak表中删除。
void
weak_clear_no_lock(weak_table_t *weak_table, id referent_id)
{
objc_object *referent = (objc_object *)referent_id;
weak_entry_t *entry = weak_entry_for_referent(weak_table, referent); // 找到referent在weak_table中对应的weak_entry_t
if (entry == nil) {
/// XXX shouldn't happen, but does with mismatched CF/objc
//printf("XXX no entry for clear deallocating %p\n", referent);
return;
}
// zero out references
weak_referrer_t *referrers;
size_t count;
// 找出weak引用referent的weak 指针地址数组以及数组长度
if (entry->out_of_line()) {
referrers = entry->referrers;
count = TABLE_SIZE(entry);
}
else {
referrers = entry->inline_referrers;
count = WEAK_INLINE_COUNT;
}
for (size_t i = 0; i < count; ++i) {
objc_object **referrer = referrers[i]; // 取出每个weak ptr的地址
if (referrer) {
if (*referrer == referent) { // 如果weak ptr确实weak引用了referent,则将weak ptr设置为nil,这也就是为什么weak 指针会自动设置为nil的原因
*referrer = nil;
}
else if (*referrer) { // 如果所存储的weak ptr没有weak 引用referent,这可能是由于runtime代码的逻辑错误引起的,报错
_objc_inform("__weak variable at %p holds %p instead of %p. "
"This is probably incorrect use of "
"objc_storeWeak() and objc_loadWeak(). "
"Break on objc_weak_error to debug.\n",
referrer, (void*)*referrer, (void*)referent);
objc_weak_error();
}
}
}
weak_entry_remove(weak_table, entry); // 由于referent要被释放了,因此referent的weak_entry_t也要移除出weak_table
}
到此我知道了啥?
知道了dealloc后,weak修饰的对象是怎么置为nil的。
objc_loadWeakRetained
当需要调用weak修饰的对象时,会调用objc_loadWeakRetained方法来对weak对象retain。
之前编译器会将weak修饰的对象加入到自动释放池中,现在是直接release。
{
id __weak obj1 = obj;
NSLog(@"%@", obj1);
}
/* iOS5及之前编译器做法 */
id obj1;
objc_initWeak(&obj1, obj);
id tmp = objc_loadWeakRetained(&obj1);
objc_autorelease(tmp);//错误!!!mistake
NSLog(@"%@", tmp);
objc_destroyWeak(&obj1);
/* 现在的编译器做法*/
id obj = objc_msgSend(NSObject, "new");
id obj1;
objc_initWeak(&obj1, obj);
id tmp = objc_loadWeakRetained(obj1);//objc_loadWeakRetained would increment the reference count to ensure that tmp is alive in the NSLog statement.
NSLog(@"%@", obj1);
objc_release(tmp);
objc_destroyWeak(&obj1);
objc_storeStrong(&obj, 0);//release
当需要调用weak修饰的对象时:
- 首先调用initWeak方法获取weak对象
- 调用objc_loadWeakRetained
- 首先判断是否是isTaggedPointer,如果是直接返回对象
- 判断isa是否有hasCustomRR,retain/release/autorelease/retainCount/_tryRetain/_isDeallocating/retainWeakReference/allowsWeakReference返回true,一般情况我们都不会重写这些方法,因此会返回false,取反就为true
- 执行if (! obj->rootTryRetain()) {result = nil;}尝试对象进行retain
- retain成功返回对象,失败返回nil
/*
Once upon a time we eagerly cleared *location if we saw the object
was deallocating. This confuses code like NSPointerFunctions which
tries to pre-flight the raw storage and assumes if the storage is
zero then the weak system is done interfering. That is false: the
weak system is still going to check and clear the storage later.
This can cause objc_weak_error complaints and crashes.
So we now don't touch the storage until deallocation completes.
*/
id
objc_loadWeakRetained(id *location)
{
id obj;
id result;
Class cls;
SideTable *table;
retry:
// fixme std::atomic this load
obj = *location;
if (!obj) return nil;
if (obj->isTaggedPointer()) return obj;
table = &SideTables()[obj];
table->lock();
if (*location != obj) {
table->unlock();
goto retry;
}
result = obj;
cls = obj->ISA();
if (! cls->hasCustomRR()) {
// Fast case. We know +initialize is complete because
// default-RR can never be set before then.
assert(cls->isInitialized());
if (! obj->rootTryRetain()) {
result = nil;
}
}
else {
// Slow case. We must check for +initialize and call it outside
// the lock if necessary in order to avoid deadlocks.
if (cls->isInitialized() || _thisThreadIsInitializingClass(cls)) {
BOOL (*tryRetain)(id, SEL) = (BOOL(*)(id, SEL))
class_getMethodImplementation(cls, SEL_retainWeakReference);
if ((IMP)tryRetain == _objc_msgForward) {
result = nil;
}
else if (! (*tryRetain)(obj, SEL_retainWeakReference)) {
result = nil;
}
}
else {
table->unlock();
_class_initialize(cls);
goto retry;
}
}
table->unlock();
return result;
}
realease调用时间:
- 在ARC中编译器会在weak对象操作的下面插入一条release语句
- 在MRC中,获取weak指向的对象时,并不会直接调用objc_loadWeakRetained,而是会调用objc_loadWeak,此方法的实现如下:利用自动释放池,对retain的对象进行release操作
学习链接
集合NSSet、字典NSDictionary的底层实现原理
更深层次的了解iOS内存管理
iOS开发 之 不要告诉我你真的懂isEqual与hash!
hash
NSDictionary和NSMutableArray底层原理(哈希表和环形缓冲区)
weak的实现原理
详解获取weak对象的过程
从一个crash理解weak的延迟释放