首先下載源碼NSDictionary \ NSSet，把源碼拉到項(xiàng)目中方便查看。源碼

一、對(duì)象的哈希函數(shù)

一個(gè)對(duì)象的哈希值通過(guò)hash方法獲得，通過(guò)OC源碼可以看到OC源碼

- (NSUInteger)hash {
    return _objc_rootHash(self);
}

uintptr_t _objc_rootHash(id obj)
{
    return (uintptr_t)obj;
}

所以O(shè)C對(duì)象默認(rèn)的哈希值就是對(duì)象的地址(uintptr_t)obj
為了看懂源碼究竟在做什么，需要先看一下哈希表的原理：
筆記-數(shù)據(jù)結(jié)構(gòu)之 Hash

NSSet和NSDictionary底層都是CF...完成的，而且實(shí)現(xiàn)原理就是哈希表（數(shù)組+開(kāi)放定址法解決哈希沖突的方式）。

二、NSSet的實(shí)現(xiàn)原理

通過(guò)源碼來(lái)查看

void CFSetAddValue(CFMutableSetRef set, const void *key) {
// 上面參數(shù)key就是set中要添加的那個(gè)對(duì)象.  void *是任意類型
// 1.當(dāng) 可變的set中，_count == _capacity 時(shí)或者set為空時(shí)__CFSetGrow去擴(kuò)容 __CFSetGrow(set, 1);
    if (set->_count == set->_capacity || NULL == set->_keys) {
        __CFSetGrow(set, 1);
    }

// 2. __CFSetFindBuckets2查找集合set中key是否有match的值，返回的nomatch是可以放置的數(shù)組下標(biāo)
    __CFSetFindBuckets2(set, key, &match, &nomatch);
    if (kCFNotFound != match) {
        // 本身存在這個(gè)key，什么也沒(méi)做
    } else {
//3. 將對(duì)象的引用計(jì)數(shù)器+1
        cb = __CFSetGetKeyCallBacks(set);
        if (cb->retain) {
            newKey = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), allocator, key, set->_context);
        } else {
            newKey = key;
        }
// 4.將newKey寫入到數(shù)組_keys中的第nomatch位置。
       CF_WRITE_BARRIER_ASSIGN(keysAllocator, set->_keys[nomatch], newKey);
        set->_count++;
    }
}

上面代碼的注釋就是實(shí)現(xiàn)的步驟，由上面可知，一個(gè)集合sets中實(shí)現(xiàn)了沒(méi)有重復(fù)的值，因?yàn)楫?dāng)找到有匹配的key時(shí)什么也沒(méi)做。

• 數(shù)組的擴(kuò)容時(shí)會(huì)首先將數(shù)組容量擴(kuò)展，其次將原來(lái)數(shù)組中的key重新計(jì)算下標(biāo)放到新的數(shù)組中。
• 數(shù)組擴(kuò)容的數(shù)量按照預(yù)先定義的數(shù)量來(lái)確定, __CFSetCapacities中預(yù)先確定了怎么擴(kuò)容。4個(gè)-》8個(gè)-》17個(gè). 查看源碼可知詳情。

static const uint32_t __CFSetCapacities[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
};

三、NSDictionary的實(shí)現(xiàn)原理

NSDictionary的原理與NSSet是一樣的,只不過(guò)是用了keys數(shù)組和values數(shù)組兩個(gè)數(shù)組， 通過(guò)源碼可以看到，擴(kuò)容時(shí)是同時(shí)擴(kuò)容這兩個(gè)數(shù)組，確定下標(biāo)時(shí)，用key的下標(biāo)作為values數(shù)組中存放值時(shí)的下標(biāo)。不過(guò)在key值查找到時(shí)是只更新value而不是NSSets的什么也不做。

void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
// 1.可變的dict中，_count == _capacity 時(shí)或者dict為空時(shí)__CFDictionaryGrow去擴(kuò)容    
    if (dict->_count == dict->_capacity || NULL == dict->_keys) {
        __CFDictionaryGrow(dict, 1);
    }
// 2. __CFDictionaryFindBuckets2查找字典dict中key是否有match的值，返回的nomatch是可以放置的數(shù)組下標(biāo)
    __CFDictionaryFindBuckets2(dict, key, &match, &nomatch);

//3. 將新value的引用計(jì)數(shù)器+1
    if (vcb->retain) {
    newValue = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))vcb->retain), allocator, value, dict->_context);
    } else {
    newValue = value;
    }
    if (kCFNotFound != match) {
//4.之前是存在這個(gè)key的，先對(duì)value前值release
    if (vcb->release) {
        INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[match], dict->_context);
    }
// 5. 將新的value放到_values數(shù)組中第match個(gè)元素
    CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[match], newValue);
    } else {
//6.之前是不存在這個(gè)key的，先對(duì)newKey進(jìn)行retain，引用計(jì)數(shù)加1
    if (cb->retain) {
        newKey = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), allocator, key, dict->_context);
    } else {
        newKey = key;
    }
// 7.將newKey添加到_keys數(shù)組中nomatch位置，將newValue添加到_values數(shù)組中第nomatch位置
    CF_WRITE_BARRIER_ASSIGN(keysAllocator, dict->_keys[nomatch], newKey);
    CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[nomatch], newValue);
    dict->_count++;
    }
}

參考閱讀:
筆記-集合NSSet、字典NSDictionary的底層實(shí)現(xiàn)原理
筆記-數(shù)據(jù)結(jié)構(gòu)之 Hash