分析实现-一对一设计
一对一one to one并不是某种业务上的具体需求，它仅仅是一种数据存储上的设计。one to one要求一个变量能且最多只能匹配一个变量，这听着很绕口，举个常见的结构例子就是key-value匹配。不同的编程语言提供了高层级的key-value存储结构，例如dictionary字典，被这些高层级的存储结构宠坏了的我们不知是否思考过这么一个问题：
dictionary是怎么通过key来存储或者移除匹配的value的
应用程序的数据存储只存在连续存储和非连续存储这两种方式，并且非连续存储需要使用额外的内存来存储下一个数据的信息，因此非连续存储的内存开销是大于连续存储方式的。在dictionary的存储结构中，key和value可以完全不同且没有丝毫的关联性，这是否意味着字典会采用非连续存储的结构设计并且使用了大量的额外内存呢？又或者存在某种设计，使得即便是完全不同的数据，也能实现连续的存储呢？
从排序说起
如果你已经了解过桶排序或者哈希表，那么可以跳过本节继续阅读。
桶排序
在代码设计中，空间和时间是两个非常重要的概念，前者表示代码运行过程中，需要占用的内存大小。后者表示运行这段代码，CPU需要处理多少个时钟周期。实现同样一个功能需要的空间和时间并不是固定的，通常来说，前者相比后者要廉价的多。因此在实现需求的时候，我们可以适当的放弃一些空间来换取更快的执行效率。桶排序是一种典型的空间换时间算法，它采用一种十分取巧的方式，让排序时间可以达到O(N)的水平。
创建
N个空桶，N为排序数组中最大值加一。然后遍历排序数组，以元素值为下标，将其放入对应的桶中
出于读者大多数为iOSer的考虑，我将使用OC代码来描述桶排序。首先存在一个需要排序的无序正整数数组，我们遍历这个数组，然后创建一堆空桶：
NSUInteger bucketCount = 0;
NSArray<NSNumber *> *nums = @[@(10), @(8), @(3), @(9), @(3), @(1), @(4), @(6), @(7), @(5)];
for (NSNumber *num in nums) {
if (bucketCount < num.unsignedIntegerValue + 1) {
bucketCount = num.unsignedIntegerValue + 1;
}
}
NSMutableArray<NSNumber *> *buckets = @[].mutableCopy;
for (NSUInteger idx = 0; idx < bucketCount; idx++) {
[buckets addObject: @0];
}
因为桶排序的思想是：数组中每一个元素都能成为桶列表的下标，所以桶列表的长度必须为最大值加一才能避免数组访问越界。桶列表被初始化后，每一个桶的值都是0，表示该桶的数量为0个。然后对原数组进行一次遍历，将元素放到对应的桶中（桶内值+1）：
for (NSNumber *num in nums) {
NSUInteger count = buckets[num.unsignedIntegerValue].unsignedIntegerValue;
buckets[num.unsignedIntegerValue] = @(count + 1);
}
NSMutableArray<NSNumber *> *sortNums = @[].mutableCopy;
for (NSUInteger idx = 0; idx < buckets.count; idx++) {
NSUInteger count = buckets[idx].unsignedIntegerValue;
while (count--) {
[sortNums addObject: @(idx)];
}
}
在两次遍历之后，数组值已经将元素转换成下标顺序的存放在桶列表中，最后遍历所有桶，如果桶不为空，那么取下标，遍历后排序完成。
哈希排序
桶排序效率非常的高，但是存在一个致命的问题：内存占用过大。当需要处理的数据足够大时，计算机根本无法分配足够多的桶来完成排序。基于这一问题，哈希排序将较大的数值映射成较小的数值，成倍的减少了需要使用到的桶的数量。由于较大数值->较小数值的过程中，会导致数据精确的丢失，同一个桶可能存在多个排序数据，因此可以用数组表示每一个桶来存储多个变量。
较大数值->较小数值的转换过程我们称之为hash化。如果不同变量hash化后存在相同的结果值，我们称之为hash碰撞：
NSUInteger hashCode(NSNumber *num) {
return num.unsignedIntegerValue / 10;
}
NSUInteger bucketCount = 0;
NSArray<NSNumber *> *nums = @[@(101), @(89), @(32), @(95), @(33), @(11), @(44), @(62), @(71), @(99)];
for (NSNumber *num in nums) {
if (bucketCount < (hashCode(num) + 1)) {
bucketCount = (hashCode(num) + 1);
}
}
NSMutableArray<NSNumber *> *buckets = @[].mutableCopy;
for (NSUInteger idx = 0; idx < bucketCount; idx++) {
[buckets addObject: @[].mutableCopy];
}
for (NSNumber *num in nums) {
NSMutableArray *bucket = buckets[num.unsignedIntegerValue / 10];
[bucket addObject: num];
}
在由于同一个桶中可能存在多个待排序数据，因此在最后完成排序操作中，还需要进行额外的排序。下面略去对桶中数据重新排序的代码：
NSMutableArray<NSNumber *> *sortNums = @[].mutableCopy;
for (NSUInteger idx = 0; idx < buckets.count; idx++) {
NSMutableArray *bucket = buckets[idx];
[sortNums addObjectsFromArray: [bucket sortedArrayUsingSelector: @selector(compare:)]];
}
相较于桶排序，哈希排序在空间和时间上努力寻找一个平衡点，尽可能的保证效率。但实际上当处理数据足够大量时，哈希排序相较于其他的排序方式，并没有体现足够的优势，因此哈希在排序需求上，并不是一个好选择。但由于哈希能简化数据的特点，被广泛运用于数据存储的设计上。
字典
Foundation提供了诸多的高层级数据结构，这些数据结构基本都是对Core Foundation中的特定结构的高层次包装，比如NSDictionary对应的实现结构为__CFDictionary结构体，源码给我们提供了这一结构体的内容：
struct __CFDictionary {
CFRuntimeBase _base;
CFIndex _count;
CFIndex _capacity;
CFIndex _bucketsNum;
uintptr_t _marker;
void *_context;
CFIndex _deletes;
CFOptionFlags _xflags;
const void **_keys;
const void **_values;
};
根据数据结构可以发现dictionary内部使用了两个指针数组分别来保存keys和values，先不去讨论这两个数组的元素如何形成对应关系，已知的是dictionary采用的是连续存储的方式存储键值对，因此接下来我们将一步步了解字典是如何完成key-value的匹配过程。
hash
这里的hash指的不是上面的哈希排序或者hash化，而是一个方法。在OC中，万物皆NSObject的子孙，NSObject某种意义上来说等同于OC的上帝类，作为所有类的基类，NSObject提供了诸多接口，大多数的接口在日常开发中都不会被主动调用，比如有这么一段代码：
NSArray *nums = @[@(1), @(2), @(3), @(4), @(5)];
NSLog(@"%zd", [nums containsObject: @(1)]);
代码是为了检测在数组中是否存在@(1)这个对象，而在运行时，苹果为了提高匹配两个对象是否相同的效率，会先判断两个对象的hash方法返回值是否相等，再进行进一步的判断。hash方法一般耗时在纳秒级，这能有效的减少匹配的耗时：
- (BOOL)compareObj1: (id)obj1 withObj2: (id)obj2 {
if ([obj1 hash] == [obj2 hash]) {
return [obj1 isEqual: obj2];
}
return NO;
}
除非我们有意重新实现hash方法，否则NSObject会默认将对象的地址转换成一个非负整数返回。如果存在自定义的数据对象，数组中存在equal BUT NOT same的对象时，即便实现了isEqual接口，只要hash方法不能返回一个正确的结果，调用containsObject:总是返回NO：
+ (NSUInteger)hash {
return _objc_rootHash(self);
}
- (NSUInteger)hash {
return _objc_rootHash(self);
}
uintptr_t _objc_rootHash(id obj) {
if (UseGC) {
return _object_getExternalHash(obj);
}
return (uintptr_t)obj;
}
原则上，hash结果应该通过合理的运算来尽可能的避免冲突，比如MD5是一种相当优秀的hash化，但这并不代表hash的实现难度很高。实际上只要hash的结果能够体现出数据的特征就行了，比如字典的hash实现非常任性的返回了键值对个数：
static CFHashCode __CFDictionaryHash(CFTypeRef cf) {
CFDictionaryRef dict = (CFDictionaryRef)cf;
return dict->_count;
}
那么可以得到一个初步的结论：相等变量的hash结果总是相同的，不相等变量的hash结果有可能相同。在继续之前，我们再明确一个概念：
hash化是一个取得变量特征的过程，这个过程可以是取出变量的特征，也可以是一个计算
从dictionary的结构中可以看到keys大概率是一个数组，那么当对象完成hash化运算，这个计算结果要如何和数组实现位置匹配？由于存储结构的特性，计算机的hash化几乎总是返回一个非负整数，因此这个匹配过程就变得相当简单——相同的数值的求余结果总是相同的。下面将通过字典的key的匹配过程来论证这点，基于不同的初始化，这个hash化存在两种运算。代码忽略其他逻辑：
static CFIndex __CFDictionaryFindBucketsXX(CFDictionaryRef dict, const void *key) {
/// 创建字典时传入__kCFDictionaryHasNullCallBacks声明key无法进行hash运算，直接使用对象地址作为keyHash
CFHashCode keyHash = (CFHashCode)key;
/// 创建字典时传入其他配置，key存在hash实现代码，使用hash函数的结果值作为keyHash
CFHashCode keyHash = cb->hash ? (CFHashCode)INVOKE_CALLBACK2(((CFHashCode (*)(const void *, void *))cb->hash), key, dict->_context) : (CFHashCode)key;
const void **keys = dict->_keys;
CFIndex probe = keyHash % dict->_bucketsNum;
......
}
上述代码中INVOKE_CALLBACK2表示调用接收2个参数的函数指针。通过源码我们看到了dictionary的更多实现细节，也可以发现hash化其实不是一个困难的处理。
开放定址法
实现合理的hash化过程是一对一的基本要求，一旦每一个变量拥有了自己的hash特征，那就需要思考下一个重要问题：
不同对象发生
hash碰撞要采用什么方式解决？
在上文介绍哈希排序时，解决hash碰撞的方式是将发生碰撞的多个元素放到一个容器中，这个容器通常使用链表结构，这种解决方案被称作拉链法。试想一下，假如dictionary也采用这种方案解决冲突，为了能匹配到正确的数据，必然要使用一个复合结构存储key和value的数据，然后碰撞发生时遍历容器查找匹配的key-value：
从设计结构上来看，这个方案能够解决hash碰撞的匹配问题。但拉链法会将key和value包装成一个结构存储，而dictionary的结构拥有keys和values这两个数组，说明了这两个数据是被分开存储的，所以使用这个方案的可能性不高。而且拉链法存在一个问题：
数据过多时，由于需要遍历容器，匹配效率低。另外桶列表长度如果不够大时，会加剧匹配的损耗
官方文档声明过dictionary的查找时间接近O(1)，这意味着keyHash的位置只对应一个数据，而拉链法是无法保证这一点的，因此可以排除这种实现方案。这时候，开放定址法就闪亮登场了：在发生冲突时，将存储位置向后移动一位，直到空桶位置，然后将数据放入空桶中：
虽然数据存储的位置不一定是计算出来的keyHash位置，但是符合一个keyHash位置只会存储一个数据，达到了O(1)的查找效率。不过开放定址法依旧存在一个问题：
由于数据会占用彼此的存储位置，通列表很容易就存满数据，新增数据不再能找到空桶存放
为了解决这个问题，使用开放定址法的结构通常允许在通列表的数量达到了某个阈值，通常是通列表长度的80%使用量时，对通列表进行一次扩充grow，然后重新计算数据的keyHash放入新桶中：
开放定址法可以通过动态扩充通列表长度解决了满桶无法插入的问题，也符合O(1)的查询速度，但同样随着数据量的增加，数据会明显的集中在某一段连续区域，称作堆积现象。基本可以确定dictionary就是采用这种解决方式来实现keyHash的数据存放问题。通过阅读setValue的实现，也可以印证这个设计。下面代码已除去了无关逻辑：
/// set value for key
void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
/// 假如字典中存在key，match返回keyHash的存储位置
/// 假如字典中不存在key，nomatch存储插入key的存储位置
CFIndex match, nomatch;
__CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
......
if (kCFNotFound != match) {
/// 字典中已经存在key，修改操作
CF_OBJC_KVO_WILLCHANGE(dict, key);
......
CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[match], newValue);
CF_OBJC_KVO_DIDCHANGE(dict, key);
} else {
/// 字典中不存在key，新增操作
......
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) {
/// 对key进行hash化，获取keyHash
const CFDictionaryKeyCallBacks *cb = __CFDictionaryGetKeyCallBacks(dict);
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;
CFIndex start = probe;
*match = kCFNotFound;
*nomatch = kCFNotFound;
for (;;) {
uintptr_t currKey = (uintptr_t)keys[probe];
/// 如果keyHash对应的桶是空桶，那么标记nomatch，返回未匹配
if (marker == currKey) {
if (nomatch) *nomatch = probe;
return;
} else if (~marker == currKey) {
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 = probe;
return;
}
/// 如果未匹配，说明发生了冲突，那么将桶下标向后移动，直到找到空桶位置
probe = probe + probeskip;
if (dict->_bucketsNum <= probe) {
probe -= dict->_bucketsNum;
}
if (start == probe) {
return;
}
}
}
由于dictionary采用的非key + value的复合结构进行存储数据，而是分别使用两个数组存储，所以在匹配到keyHash的位置时，这个位置同样也是value的位置，因此keys和values拥有一样的长度才能保证能够匹配上数据。dictionary的结构内部，使用_capacity表示当前通列表的扩充阈值，当count数量达到这个长度时，扩充数组：
/// 桶列表扩充阈值
static const uint32_t __CFDictionaryCapacities[42] = {
4, 8, 17, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349,
15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498,
3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324,
228826127, 370248451, 599074578, 969323029, 1568397607, 2537720636U
};
/// 桶列表长度
static const uint32_t __CFDictionaryBuckets[42] = {
5, 11, 23, 41, 67, 113, 199, 317, 521, 839, 1361, 2207, 3571, 5779, 9349, 15121,
24473, 39607, 64081, 103681, 167759, 271429, 439199, 710641, 1149857, 1860503, 3010349,
4870843, 7881193, 12752029, 20633237, 33385273, 54018521, 87403763, 141422317, 228826121,
370248451, 599074561, 969323023, 1568397599, 2537720629U, 4106118251U
};
/// 匹配下一个扩充阈值
CF_INLINE CFIndex __CFDictionaryRoundUpCapacity(CFIndex capacity) {
CFIndex idx;
for (idx = 0; idx < 42 && __CFDictionaryCapacities[idx] < (uint32_t)capacity; idx++);
if (42 <= idx) HALT;
return __CFDictionaryCapacities[idx];
}
/// 匹配下一个桶列表长度
CF_INLINE CFIndex __CFDictionaryNumBucketsForCapacity(CFIndex capacity) {
CFIndex idx;
for (idx = 0; idx < 42 && __CFDictionaryCapacities[idx] < (uint32_t)capacity; idx++);
if (42 <= idx) HALT;
return __CFDictionaryBuckets[idx];
}
/// set value for key
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) {
/// 保存当前keys和values的数据，计算出新的长度
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;
......
/// 扩充keys和values数组
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]);
}
}
}
......
}
另外，还有一个有趣的marker属性，它在字典创建时被设置成0xa1b1c1d3，这个地址值用来表示被删除或已清空的项目，属于用户无法使用的地址。对应的，marker和~marker分别表示空桶和被清空两个状态，这两个值都会使得nomatch被填充，处理逻辑基本一致。但可能是为了兼容后续版本可能会对remove后的逻辑进行更改，于是苹果预留了~marker这一个值：
void CFDictionaryRemoveValue(CFMutableDictionaryRef dict, const void *key) {
/// 查找keyHash
CFIndex match;
if (0 == dict->_count) return;
if (__kCFDictionaryHasNullCallBacks == __CFBitfieldGetValue(((const CFRuntimeBase *)dict)->_info, 3, 2)) {
match = __CFDictionaryFindBuckets1a(dict, key);
} else {
match = __CFDictionaryFindBuckets1b(dict, key);
}
if (kCFNotFound == match) return;
/// 清除key和value，并标记keyHash位为~marker
const void *oldkey = dict->_keys[match];
CFAllocatorRef allocator = CFGetAllocator(dict);
CF_OBJC_KVO_WILLCHANGE(dict, oldkey);
if (vcb->release) {
INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[match], dict->_context);
}
dict->_keys[match] = (const void *)~dict->_marker;
dict->_values[match] = 0;
dict->_count--;
CF_OBJC_KVO_DIDCHANGE(dict, oldkey);
if (cb->release) {
INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))cb->release), __CFGetAllocator(dict), oldkey, dict->_context);
}
/// 判断是否需要缩小通列表
dict->_deletes++;
if ((__kCFDictionaryMutable == __CFDictionaryGetType(dict)) && (dict->_bucketsNum < 4 * dict->_deletes || (512 < dict->_capacity && 3.236067 * dict->_count < dict->_capacity))) {
__CFDictionaryGrow(dict, 0);
} else {
if (match < dict->_bucketsNum - 1 && dict->_keys[match + 1] == (const void *)dict->_marker) {
while (0 <= match && dict->_keys[match] == (const void *)~dict->_marker) {
dict->_keys[match] = (const void *)dict->_marker;
dict->_deletes--;
match--;
}
}
}
}
碰撞处理
如果事情有变坏的可能，不管这种可能性有多小，它总会发生。
hash碰撞总是不可避免的，上述介绍了包括拉链法和开放定址法两种处理碰撞的手段。此外还有再哈希法以及建立公共溢出区两种方案，后者将冲突数据存放到一个公共的数据区，具体实现方案并不清楚，也没见过这种方案。
再哈希法
再哈希法是另一种类似于开放定址法的方案，其思路是假如当前hash化的结果发生碰撞，使用另一个hash化方案，直至计算出不冲突的hash结果或者扩充列表为止：
#define unused_ptr 0xa1b1c1d3
int hashCode1(int num) {
return num / 10;
}
int hashCode2(int num) {
return num / 6;
}
......
void storeValue(void**nums, const void *key) {
bool match = false;
__storeValue(nums, key, hashCode1, &match);
if (match) { return; }
__storeValue(nums, key, hashCode2, &match);
if (match) { return; }
......
}
void __storeValue(void **nums, void *key, int(*hash_func)(int), bool *match) {
int hashCode = ((int(*)(void))(((hash_obj *)key)->hash))();
int keyHash = hash_func(hashCode);
*match = (nums[keyHash] == unused_ptr);
if (*match) {
nums[keyHash] = key;
}
}
上面是rehash的一种方式：对key进行多个hash运算，每次得到不同的hashCode。另一种方式是基于hashCode计算出另外一个hashCode，甚至可以这么说，开放定址法就是采用对hashCode自增运算的再哈希法。再哈希法同样是一个keyHash只保存一个数据。但这种方案有太多的不足之处：
- 需要多个
hash化算法支持，相比起单纯移动keyHash的做法，性能更差 - 在尝试所有
hash结果后依旧冲突时，会grow列表，实际上列表使用率可能低于预期
拥有开放定址法相似的操作，但在性能和设计上都是劣势，因此再哈希法实际上是一种鲜有人用的解决方案，实现一对一方案时可以不考虑这种方案。另外，目前为止开放定址法似乎在三种方案中最优，它的缺点也非常明显：
- 由于扩充几乎是翻倍
grow，多次扩充后可能会存在大量的空桶，浪费空间 - 删除元素时，为了影响后续元素查找，需要对删除位置做特殊处理，实现逻辑上更复杂
dictionary之所以采用这种设计，其一出于查询性能的考虑；其二dictionary在使用过程中总是会很快的被释放，不会长期占用内存。
associated object
关联对象associated object是iOS开发常用的机制之一，它实现了不通过继承来增加属性这种需求。通过阅读objc-references源码，可以发现关联对象内部使用了嵌套dictionary的结构实现了对象的扩展属性管理，也就是使用开放定址法的解决方案。下面代码去除了无关存储的逻辑：
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);
}
}
}
}
函数中使用了大量的C++代码，考虑到部分读者可能没接触过C++语法，对部分关键方法调用和逻辑判断做下解释：
-
AssociationsHashMap是一个dictionary，以对象hash结果存储了一个dictionary，用OC的泛型声明来看，就是一个NSDictionary<id, NSDictionary *>的结构变量，这个变量是全局的。 -
ObjectAssociationMap是被上面嵌套的dictionary，这个结构存储了实际绑定的属性值。在我们调用objc_setAssociatedObject的时候，会将传入的key和value存储在这里面。
我在上面说过，开放定址法在大量数据存储时，会造成大量的空间占用，为什么associated object采用全局对象的情况下依旧使用这种方案。这是因为虽然苹果使用了一个全局的AssociationsHashMap对象存储了全部的关联对象，但在对象dealloc时会移除这些数据，同一时间占用的内存也是可接受的：
void _object_remove_assocations(id object) {
vector< ObjcAssociation,ObjcAllocator<ObjcAssociation> > elements;
{
AssociationsManager manager;
AssociationsHashMap &associations(manager.associations());
if (associations.size() == 0) return;
disguised_ptr_t disguised_object = DISGUISE(object);
AssociationsHashMap::iterator i = associations.find(disguised_object);
if (i != associations.end()) {
ObjectAssociationMap *refs = i->second;
for (ObjectAssociationMap::iterator j = refs->begin(), end = refs->end(); j != end; ++j) {
elements.push_back(j->second);
}
delete refs;
associations.erase(i);
}
}
for_each(elements.begin(), elements.end(), ReleaseValue());
}
当然，个人觉得之所以这么设计的最重要的原因可能是苹果的工程师偷懒，不想花时间再设计一个结构，直接使用现有结构。至于为什么不用__CFDictionary而是unordered_map，莫非苹果工程师觉得自家的设计没有C++的强？
@synchronized
在上篇文章中我提到过@synchronized采用了hash + linked list的实现结构，源码参见objc-sync，实际上就是拉链法来解决碰撞问题。在代码编译时，这个语句会被转换成成对的两个函数调用：
int objc_sync_enter(id obj);
int objc_sync_exit(id obj);
相比起一般的拉链法的设计，@synchronized增加了一个缓存机制，下面是使用到的关键结构：
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)中，宏定义HASH(obj)会将对象的地址进行hash化获取存储位置。threadCount表示当前SyncData被使用的线程数，如果这个值为0，说明锁未被使用，可以进行复用，关于@synchronized更多的知识点，可以通过下方的扩展阅读了解更多。
总结
为什么同样是使用全局存储的实现方式下，
@synchronized采用的是拉链法，而associate object采用的是开放定址法
其实最重要的一点是存储数据的生命周期和特性所决定的：
-
开放定址法的存储属性基本是和key所属对象相关联的，一旦key所属对象发生变化时，其所存储的数据大概率也是要发生修改的。因此即便是开放定址法在使用全局实现时，对象释放时同样会清空所存储的内容，因此总体来说内存占用并不会过高。 -
拉链法对于碰撞的处理方式更为简单，不用担心数据的堆积现象。另外如果存储的数据是通用类型数据，可以被反复利用。比如@synchronized是存储的锁是一种无关业务的实现结构，程序运行时多个对象使用同一个锁的概率相当的高，有效的节省了内存。
17年总结才写完没多久，转眼又一个月过去了，不得不感慨时间过得太快。由于年前是最忙碌的一段时间，过年又想好好玩玩，本文将大概率是3月前的最后一篇文章，先对读者们说声新年快乐。
扩展阅读
如何设计并实现一个线程安全的 Map ？(上篇)
如何设计并实现一个线程安全的 Map ？(下篇)
关于 @synchronized，这儿比你想知道的还要多