NSSet、NSDictionary底层实现

Foundation框架很多都是和Core Foundation对应，例如NSSet和_CFSet相对应，NSDictionary和_CFDictionary相对应。

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，可以从源码中了解到采用的是连续存储的方式存储

在数组长度不大的情况下，链表法衍生出来的链表会非常庞大，而且需要二次遍历，匹配损耗一样很大，这样等于没有优化。官方说查找算法接近O(1)，所以肯定不是链表法，那就是开放定址法。

开放定址法可以通过动态扩容数组长度解决表存储满无法插入的问题，也符合O(1)的查询速度。在CFSet内部结构里还有个_capacity表示当前数组的扩容阈值，当count达到这个值就扩容

NSSet添加key，key值会根据特定的hash函数算出hash值，然后存储数据的时候，会根据hash函数算出来的值，找到对应的下标，如果该下标下已有数据，开放定址法后移动插入，如果数组到达阈值，这个时候就会进行扩容，然后重新hash插入。查询速度就可以和连续性存储的数据一样接近O(1)了

NSDictionary

数据结构：

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

字典则用了两个数组keys和values，说明这两个数据是被分开存储的。

同样的也是利用开放定址法来动态扩容数组来解决数组满了无法插入的问题，也可以通过setValue的实现证实这一点，下面代码已除去无关逻辑：

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插入到字典NSDictionary时，会覆盖旧值，而集合NSSet则什么都不做，保证了里面的元素不会重复。

key和value是分别存储在两个不同的数组里，这里面是如何对key、value进行绑定的呢？

首先key利用hash函数算出hash值，然后对数组的长度取模，得到数组下标的位置，同样将这个地址对应到values数组的下标，就匹配到相应的value

要保证一点，就是keys和values这两个数组的长度要一致。所以扩容的时候，需要对keys和values两个数组一起扩容

开放地址法最好存储的是临时需要，尽快的释放资源

对于字典NSDictionary设置的key和value，key值会根据特定的hash函数算出hash值，keys和values同样多，利用hash值对数组长度取模，得到其对应的下标index，如果下标已有数据，开放定址法后移插入，如果数组达到阈值，就扩容，然后重新hash插入。这样的机制就把一些不连续的key-value值插入到能建立起关系的hash表中。
查找的时候，key根据hash函数以及数组长度，得到下标，然后根据下标直接访问hash表的keys和values，这样查询速度就可以和连续线性存储的数据一样接近O(1)了。

参考

集合NSSet、字典NSDictionary的底层实现原理