01.jpg

預(yù)備知識(shí)點(diǎn)

Foundation框架下提供了很多高級(jí)數(shù)據(jù)結(jié)構(gòu)楞遏，很多都是和Core Foundation下的相對(duì)應(yīng)鳍徽，例如NSSet就是和_CFSet相對(duì)應(yīng)资锰，NSDictionary就是和_CFDictionary相對(duì)應(yīng)。源碼

了解集合NSSet和字典NSDictionary的底層實(shí)現(xiàn)原理前阶祭，如果不了解Hash表數(shù)據(jù)結(jié)構(gòu)的話绷杜，建議先去了解一下
筆記-數(shù)據(jù)結(jié)構(gòu)之 Hash（OC的粗略實(shí)現(xiàn)）

hash

這里說的hash并不是之前說的hash表，而是一個(gè)方法濒募。為什么要有hash方法鞭盟？

這個(gè)問題需要從hash表數(shù)據(jù)結(jié)構(gòu)說起，首先看下如何在數(shù)組中查找某個(gè)成員

• 先遍歷數(shù)組中的成員
• 將取出的值與目標(biāo)值比較萨咳，如果相等懊缺，則返回改成員

在數(shù)組未排序的情況下疫稿，查找的時(shí)間復(fù)雜度是O(n)（n為數(shù)組長(zhǎng)度）培他。hash表的出現(xiàn)，提高了查找速度遗座，當(dāng)成員被加入到hash表中時(shí)舀凛，會(huì)計(jì)算出一個(gè)hash值，hash值對(duì)數(shù)組長(zhǎng)度取模途蒋，會(huì)得到該成員在數(shù)組中的位置猛遍。

通過這個(gè)位置可以將查找的時(shí)間復(fù)雜度優(yōu)化到O(1)，前提是在不發(fā)生沖突的情況下号坡。
這里的hash值是通過hash方法計(jì)算出來的懊烤，且hash方法返回的hash值最好唯一

和數(shù)組相比，基于hash值索引的hash表查找某個(gè)成員的過程：

• 通過hash值直接查找到目標(biāo)值的位置
• 如果目標(biāo)上有很多相同hash值成員宽堆，在利用hash表解決沖突的方式進(jìn)行查找

可以看出優(yōu)勢(shì)比較明顯腌紧，最壞的情況和數(shù)組也相差無幾。

hash方法什么時(shí)候被調(diào)用

先看下幾個(gè)例子：

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方法畜隶，方便查看hash方法是否被調(diào)用：

- (NSUInteger)hash {
    NSUInteger hash = [super hash];
    NSLog(@"走過 hash");
    return hash;
}

打印結(jié)果：

array end -------------------------------
走過 hash
走過 hash
走過 hash
走過 hash
set end -------------------------------
dictionary value end -------------------------------
走過 hash
走過 hash
走過 hash
走過 hash
dictionary key end -------------------------------

可以了解到：hash方法只在對(duì)象被添加到NSSet和設(shè)置為NSDictionary的key時(shí)被調(diào)用

NSSet添加新成員時(shí)壁肋，需要根據(jù)hash值來快速查找成員，以保證集合中是否已經(jīng)存在該成員籽慢。
NSDictionary在查找key時(shí)浸遗，也是利用了key的hash值來提高查找的效率。

關(guān)于上面知識(shí)點(diǎn)詳細(xì)可參考 iOS開發(fā) 之 不要告訴我你真的懂isEqual與hash!

這里可以得到這個(gè)結(jié)論：
相等變量的hash結(jié)果總是相同的箱亿，不相等變量的hash結(jié)果有可能相同

集合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 */
};

根據(jù)數(shù)據(jù)結(jié)構(gòu)可以發(fā)現(xiàn)set內(nèi)部使用了指針數(shù)組來保存keys跛锌，可以從源碼中了解到采用的是連續(xù)存儲(chǔ)的方式存儲(chǔ)。

基于不同的初始化届惋，hash值存在不同的運(yùn)算髓帽，簡(jiǎn)化源碼可知道：

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;
}

這個(gè)過程肯定會(huì)出現(xiàn)沖突驾茴，在筆記-數(shù)據(jù)結(jié)構(gòu)之 Hash（OC的粗略實(shí)現(xiàn)）文章中，我也說明了兩種解決沖突的方法開放定址法氢卡、鏈表法锈至。

在數(shù)組長(zhǎng)度不大的情況下，鏈表法衍生出來的鏈表會(huì)非常龐大译秦，而且需要二次遍歷峡捡，匹配損耗一樣很大，這樣等于沒有優(yōu)化筑悴。官方說查找算法接近O(1)们拙，所以肯定不是鏈表法，那就是開放定址法阁吝。

開放定址法可以通過動(dòng)態(tài)擴(kuò)容數(shù)組長(zhǎng)度解決表存儲(chǔ)滿無法插入的問題砚婆，也符合O(1)的查詢速度。
也可以通過AddValue的實(shí)現(xiàn)突勇，證實(shí)這一點(diǎn)装盯，下面代碼除去了無關(guān)的邏輯：

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值對(duì)應(yīng)的是空閑區(qū)域，那么標(biāo)記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))) {
        // 標(biāo)記match账磺，返回存在key
        *match = probe;
        return;
    }
    // 沒有匹配，說明發(fā)生了沖突痊远，那么將數(shù)組下標(biāo)后移垮抗，知道找到空閑區(qū)域位置
    probe = probe + probeskip;
    
    if (set->_bucketsNum <= probe) {
        probe -= set->_bucketsNum;
    }
    if (start == probe) {
        return;
    }
    }
}

這里涉及到的擴(kuò)容，在筆記-數(shù)據(jù)結(jié)構(gòu)之 Hash（OC的粗略實(shí)現(xiàn)）中碧聪，我也使用OC代碼具體的實(shí)現(xiàn)了冒版，上一篇實(shí)現(xiàn)的是鏈表法，其實(shí)仔細(xì)看的小伙伴就知道原理是一模一樣的矾削。在CFSet內(nèi)部結(jié)構(gòu)里還有個(gè)_capacity表示當(dāng)前數(shù)組的擴(kuò)容閾值壤玫，當(dāng)count達(dá)到這個(gè)值就擴(kuò)容，看下源碼哼凯，除去了無關(guān)邏輯：

// 新增元素的時(shí)候會(huì)判斷
void CFSetAddValue(CFMutableSetRef set, const void *key) {
        ...
    if (set->_count == set->_capacity || NULL == set->_keys) {
        // 調(diào)用擴(kuò)容
        __CFSetGrow(set, 1);
    }
    ...
}

// 擴(kuò)容
static void __CFSetGrow(CFMutableSetRef set, CFIndex numNewValues) {
    // 保存舊值key的數(shù)據(jù)
    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);
    // 擴(kuò)容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)");
    
    // 重新計(jì)算key的hash值欲间，存放到新數(shù)組中
    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);
}

可以看出，NSSet添加key断部，key值會(huì)根據(jù)特定的hash函數(shù)算出hash值猎贴，然后存儲(chǔ)數(shù)據(jù)的時(shí)候，會(huì)根據(jù)hash函數(shù)算出來的值，找到對(duì)應(yīng)的下標(biāo)她渴，如果該下標(biāo)下已有數(shù)據(jù)达址，開放定址法后移動(dòng)插入，如果數(shù)組到達(dá)閾值趁耗，這個(gè)時(shí)候就會(huì)進(jìn)行擴(kuò)容沉唠，然后重新hash插入。查詢速度就可以和連續(xù)性存儲(chǔ)的數(shù)據(jù)一樣接近O(1)了

字典NSDictionary

話不多說苛败，先看下dictionary的數(shù)據(jù)結(jié)構(gòu)：

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 */
};

是不是感覺特別的熟悉满葛，和上面的集合NSSet相比較，多了一個(gè)指針數(shù)組values罢屈。

通過比較集合NSSet和字典NSDictionary的源碼可以知道兩者實(shí)現(xiàn)的原理差不多嘀韧，而字典則用了兩個(gè)數(shù)組keys和values，說明這兩個(gè)數(shù)據(jù)是被分開存儲(chǔ)的缠捌。

同樣的也是利用開放定址法來動(dòng)態(tài)擴(kuò)容數(shù)組來解決數(shù)組滿了無法插入的問題锄贷，也可以通過setValue的實(shí)現(xiàn)證實(shí)這一點(diǎn)，下面代碼已除去無關(guān)邏輯：

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存儲(chǔ)的位置
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;
    }
    
    // 未匹配咳燕，發(fā)生碰撞，將數(shù)組下標(biāo)后移乒躺，直到找到空閑區(qū)域位置
    probe = probe + probeskip;
    
    if (dict->_bucketsNum <= probe) {
        probe -= dict->_bucketsNum;
    }
    if (start == probe) {
        return;
    }
    }
}

通過源碼可以看到招盲，當(dāng)有重復(fù)的key插入到字典NSDictionary時(shí)，會(huì)覆蓋舊值嘉冒，而集合NSSet則什么都不做曹货，保證了里面的元素不會(huì)重復(fù)。

大家都知道讳推，字典里的鍵值對(duì)key-value是一一對(duì)應(yīng)的關(guān)系顶籽，從數(shù)據(jù)結(jié)構(gòu)可以看出，key和value是分別存儲(chǔ)在兩個(gè)不同的數(shù)組里银觅，這里面是如何對(duì)key礼饱、value進(jìn)行綁定的呢？

首先key利用hash函數(shù)算出hash值，然后對(duì)數(shù)組的長(zhǎng)度取模镊绪，得到數(shù)組下標(biāo)的位置匀伏，同樣將這個(gè)地址對(duì)應(yīng)到values數(shù)組的下標(biāo)，就匹配到相應(yīng)的value蝴韭。 注意到上面的這句話够颠，要保證一點(diǎn)，就是keys和values這兩個(gè)數(shù)組的長(zhǎng)度要一致榄鉴。所以擴(kuò)容的時(shí)候摧找，需要對(duì)keys和values兩個(gè)數(shù)組一起擴(kuò)容。

// setValue時(shí)判斷
void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
    ...
    if (dict->_count == dict->_capacity || NULL == dict->_keys) {
         __CFDictionaryGrow(dict, 1);
    }
    ...
}

// 擴(kuò)容
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;
    ...
    // 重新計(jì)算keys數(shù)據(jù)的hash值牢硅，存放到新的數(shù)組中
    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]);
            }
        }
    }
    ...
}

通過上面可以看出蹬耘，字典把無序和龐大的數(shù)據(jù)進(jìn)行了空間hash表對(duì)應(yīng)，下次查找的復(fù)雜度接近于O(1)减余，但是不斷擴(kuò)容的空間就是其弊端综苔，因此開放地址法最好存儲(chǔ)的是臨時(shí)需要，盡快的釋放資源位岔。

對(duì)于字典NSDictionary設(shè)置的key和value如筛，key值會(huì)根據(jù)特定的hash函數(shù)算出hash值，keys和values同樣多抒抬，利用hash值對(duì)數(shù)組長(zhǎng)度取模杨刨，得到其對(duì)應(yīng)的下標(biāo)index，如果下標(biāo)已有數(shù)據(jù)擦剑，開放定址法后移插入妖胀，如果數(shù)組達(dá)到閾值，就擴(kuò)容惠勒，然后重新hash插入赚抡。這樣的機(jī)制就把一些不連續(xù)的key-value值插入到能建立起關(guān)系的hash表中。
查找的時(shí)候纠屋，key根據(jù)hash函數(shù)以及數(shù)組長(zhǎng)度涂臣，得到下標(biāo)，然后根據(jù)下標(biāo)直接訪問hash表的keys和values售担，這樣查詢速度就可以和連續(xù)線性存儲(chǔ)的數(shù)據(jù)一樣接近O(1)了赁遗。

__weak關(guān)鍵字的底層實(shí)現(xiàn)原理

這部分內(nèi)容在筆記-更深層次的了解iOS內(nèi)存管理里也詳細(xì)的描述了，感興趣的小伙伴族铆，可以看一下岩四。

以上知識(shí)也算是對(duì)hash表知識(shí)的總結(jié)吧，如果有正確的地方骑素，希望小伙伴們指出炫乓。