资料都是从网站，源码整理的。我不是结果创造者，我只是知识的搬运工
前言
1.NSDictionary底层是哈希表，下面会介绍具体是用拉链法还是开放定址法线性探测来解决冲突？
2.Apple给的查询复杂度可以快至O(1)，那么为什么是O(1)，底层是如何通过空间换取时间的?
NSDictionary底层原理
1.知识点储备
---- 哈希表详解:解析
---- TopK算法
---- 桶排序
---- 哈希排序
桶排序是典型的空间换时间，可以让排序时间达到O(n)
&如果少量数据，根据数组里面的最大值+1创建出那么多空桶，然后遍历，根据索引在空桶的值上累加，最后遍历空桶（已装载），根据值遍历出对应的下标
虽然这样做效率非常高，但是如果数据过大，内存吃不消，这样就有了哈希排序的介绍。
例如一组数据，我们可以根据hash算法后取模的值进行空桶排列，但是如果两个值例如 101和11 % 10都是余1，会被放入同一个桶里面，这样就会有需要二次排列。虽然这个排序效率并不高，因此哈希化就变成了数据存储的一种设计。
---- 哈希冲突
字典介绍
CFDictionary 链接源码
Foundation框架下提供了很多高级数据结构，这些都是对Core Foundation下的封装，例如NSDictionary就是对_CFDictionary的封装
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 */
};
根据数据结构__CFDictionary内部使用了两个指针数组_keys和_values分别来保存keys和values。
NSDictionary采用的是连续存储的方式存储键值对，因此接下来我们将一步步了解字典是如何完成key-value的匹配过程。
hash (NSObject中的方法)
NSObject 源码
NSArray(_CFArray) 源码
这里的hash指的不是上面的哈希排序或者hash化，而是NSObject 一个方法。在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结果应该通过合理的运算来尽可能的避免冲突，比如MD5是一种相当优秀的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 __CFDictionaryFindBuckets1a(CFDictionaryRef dict, const void *key) {
/// 创建字典时传入__kCFDictionaryHasNullCallBacks声明key无法进行hash运算，直接使用对象地址作为keyHash
CFHashCode keyHash = (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;
for (;;) {
uintptr_t currKey = (uintptr_t)keys[probe];
if (marker == currKey) { /* empty */
return kCFNotFound;
} else if (~marker == currKey) { /* deleted */
/* do nothing */
} else if (currKey == (uintptr_t)key) {
return probe;
}
probe = probe + probeskip;
// This alternative to probe % buckets assumes that
// probeskip is always positive and less than the
// number of buckets.
if (dict->_bucketsNum <= probe) {
probe -= dict->_bucketsNum;
}
if (start == probe) {
return kCFNotFound;
}
}
}
static CFIndex __CFDictionaryFindBuckets1b(CFDictionaryRef dict, const void *key) {
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; // See RemoveValue() for notes before changing this value
CFIndex start = probe;
for (;;) {
uintptr_t currKey = (uintptr_t)keys[probe];
if (marker == currKey) { /* empty */
return kCFNotFound;
} else if (~marker == currKey) { /* deleted */
/* do nothing */
} else if (currKey == (uintptr_t)key || (cb->equal && INVOKE_CALLBACK3((Boolean (*)(const void *, const void *, void*))cb->equal, (void *)currKey, key, dict->_context))) {
return probe;
}
probe = probe + probeskip;
// This alternative to probe % buckets assumes that
// probeskip is always positive and less than the
// number of buckets.
if (dict->_bucketsNum <= probe) {
probe -= dict->_bucketsNum;
}
if (start == probe) {
return kCFNotFound;
}
}
}
开放定址法
---- 开放定址法（线性探测）: 解析
优点：
不论哈希表中有多少数据，查找、插入、删除（有时包括删除）只需要接近常量的时间即0(1）的时间级。实际上，这只需要几条机器指令。
哈希表运算得非常快，在计算机程序中，如果需要在一秒种内查找上千条记录通常使用哈希表（例如拼写检查器)哈希表的速度明显比树快，树的操作通常需要O(N)的时间级。哈希表不仅速度快，编程实现也相对容易。
如果不需要有序遍历数据，并且可以提前预测数据量的大小。那么哈希表在速度和易用性方面是无与伦比的。
缺点：
它是基于数组的，数组创建后难于扩展，某些哈希表被基本填满时，性能下降得非常严重，所以程序员必须要清楚表中将要存储多少数据，或者准备好定期地把数据转移到更大的哈希表中，这是个费时的过程。
明白开发原理之后，我们可以看到，数据的衍生，会很容易把表存储满，这里可以就有了扩容的概念。
为了解决这个问题，使用开放定址法的结构通常允许在通列表的数量达到了某个阈值，通常是通列表长度的80%使用量时，对通列表进行一次扩充grow，然后重新计算数据的keyHash放入新桶中
开放定址法可以通过动态扩充通列表长度解决了满桶无法插入的问题，也符合O(1)的查询速度，但同样随着数据量的增加，数据会明显的集中在某一段连续区域，称作堆积现象。基本可以确定dictionary就是采用这种解决方式来实现keyHash的数据存放问题。通过阅读setValue的实现，也可以印证这个设计。
void CFDictionarySetValue(CFMutableDictionaryRef dict, const void *key, const void *value) {
/// 假如字典中存在key，match返回keyHash的存储位置
/// 假如字典中不存在key，nomatch存储插入key的存储位置
CFIndex match, nomatch;
const CFDictionaryKeyCallBacks *cb;
const CFDictionaryValueCallBacks *vcb;
const void *newKey, *newValue;
CFAllocatorRef allocator, keysAllocator, valuesAllocator;
CF_OBJC_FUNCDISPATCH2(__kCFDictionaryTypeID, void, dict, "setObject:forKey:", value, key);
__CFGenericValidateType(dict, __kCFDictionaryTypeID);
switch (__CFDictionaryGetType(dict)) {
case __kCFDictionaryMutable:
if (dict->_count == dict->_capacity || NULL == dict->_keys) {
__CFDictionaryGrow(dict, 1);
}
break;
case __kCFDictionaryFixedMutable:
break;
default:
CFAssert2(__CFDictionaryGetType(dict) != __kCFDictionaryImmutable, __kCFLogAssertion, "%s(): immutable dict %p passed to mutating operation", __PRETTY_FUNCTION__, dict);
break;
}
__CFDictionaryFindBuckets2(dict, key, &match, &nomatch);
vcb = __CFDictionaryGetValueCallBacks(dict);
allocator = __CFGetAllocator(dict);
keysAllocator = (dict->_xflags & __kCFDictionaryWeakKeys) ? kCFAllocatorNull : allocator;
valuesAllocator = (dict->_xflags & __kCFDictionaryWeakValues) ? kCFAllocatorNull : allocator;
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) {
CF_OBJC_KVO_WILLCHANGE(dict, key);
if (vcb->release) {
INVOKE_CALLBACK3(((void (*)(CFAllocatorRef, const void *, void *))vcb->release), allocator, dict->_values[match], dict->_context);
}
CF_WRITE_BARRIER_ASSIGN(valuesAllocator, dict->_values[match], newValue);
CF_OBJC_KVO_DIDCHANGE(dict, key);
} else {
CFAssert3(__kCFDictionaryFixedMutable != __CFDictionaryGetType(dict) || dict->_count < dict->_capacity, __kCFLogAssertion, "%s(): capacity exceeded on fixed-capacity dict %p (capacity = %d)", __PRETTY_FUNCTION__, dict, dict->_capacity);
cb = __CFDictionaryGetKeyCallBacks(dict);
if (cb->retain) {
newKey = (void *)INVOKE_CALLBACK3(((const void *(*)(CFAllocatorRef, const void *, void *))cb->retain), allocator, key, dict->_context);
} else {
newKey = key;
}
if (dict->_marker == (uintptr_t)newKey || ~dict->_marker == (uintptr_t)newKey) {
__CFDictionaryFindNewMarker(dict);
}
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);
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];
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 = probe;
return;
}
probe = probe + probeskip;
// This alternative to probe % buckets assumes that
// probeskip is always positive and less than the
// number of buckets.
if (dict->_bucketsNum <= probe) {
probe -= dict->_bucketsNum;
}
if (start == probe) {
return;
}
}
}
我们刚才在CFDictionary的结构体的时候看到了key和values这两个二级指针，可以基本断定为数组结构，由于是两个数组分别存储，因此，key哈希出来的数组下标地址，同样这个地址对应到values数组的下标，就是匹配到的值。因此keys和values这两个数组的长度一致才能保证匹配到数据。内部结构还有个_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] = { // primes
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]);
}
}
}
......
}
它的缺点也非常明显：
由于扩充几乎是翻倍grow，多次扩充后可能会存在大量的空桶，浪费空间
删除元素时，为了影响后续元素查找，需要对删除位置做特殊处理，实现逻辑上更复杂
NSDictionary设置的key和value，key值会根据特定的hash函数算出建立的空桶数组，keys和values同样多，然后存储数据的时候，根据hash函数算出来的值，找到对应的index下标，如果下标已有数据，开放定址法后移动插入，如果空桶数组到达数据阀值，这个时候就会把空桶数组扩容，然后重新哈希插入。这样把一些不连续的key-value值插入到了能建立起关系的hash表中，当我们查找的时候，key根据哈希值算出来，然后根据索引，直接index访问hash表keys和hash表values，这样查询速度就可以和连续线性存储的数据一样接近O(1)了，只是占用空间有点大，性能就很强悍。如果删除的时候，也会根据_maker标记逻辑上的删除，除非NSDictionary（NSDictionary本体的hash值就是count）内存被移除。我们也会根据dictionary之所以采用这种设计，其一出于查询性能的考虑；其二dictionary在使用过程中总是会很快的被释放，不会长期占用内存。
associate object 源码
开放订址
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);
}
}
}
AssociationsHashMap是一个dictionary，以对象hash结果存储了一个dictionary，用OC的泛型声明来看，就是一个NSDictionary<id, NSDictionary *>的结构变量，这个变量是全局的。
ObjectAssociationMap是被上面嵌套的dictionary，这个结构存储了实际绑定的属性值。在我们调用objc_setAssociatedObject的时候，会将传入的key和value存储在这里面。
@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)中，一开始有一个结构体定义 struct SyncData的定义，这个结构体包含一个object，就是之前传入的x对象，以及和对象x关联的锁mutex，仔细看，还有个同类型的指针nextData，这很明显是链表的特征。最后每个结构体里面还有个treadCount，这个是用来记录对象锁被线程使用的数量，当treadCount=0的时候没有线程使用，就可以拿出来复用，赋值给新的对象。链表节点对象SyncData，那么链表就是下面定义的SyncList，里面有头结点data，以及防止多线程修改链表头结点的自旋锁 OSSpinLock。这里可以看出@synchronized(x)内部存储是拉链法解决冲突的，因此设计了链表。下面来看下hash算法HASH（obj），将对象的指针传入，然后向右位移5，和COUNT-1进行与运算，这样结果不会超过数组长度，牛逼。那么下面两个宏就很好理解了LOCK_FOR_OBJ和LIST_FOR_OBJ，传入的对象进行HASH运算，算出0-15的一个index，然后数组直接指针偏移以O(1)，直接拿出数据，如果不同对象放在同一个index，冲突就在一条链表中，继续遍历链表拿数据
为什么同样是使用全局存储的实现方式下，@synchronized采用的是拉链法，而associate object采用的是开放定址法
其实最重要的一点是存储数据的生命周期和特性所决定的：
开放定址法的存储属性基本是和key所属对象相关联的，一旦key所属对象发生变化时，其所存储的数据大概率也是要发生修改的。因此即便是开放定址法在使用全局实现时，对象释放时同样会清空所存储的内容，因此总体来说内存占用并不会过高。
拉链法对于碰撞的处理方式更为简单，不用担心数据的堆积现象。另外如果存储的数据是通用类型数据，可以被反复利用。比如@synchronized是存储的锁是一种无关业务的实现结构，程序运行时多个对象使用同一个锁的概率相当的高，有效的节省了内存。
好像weak对应的引用计数根据对象地址维护了一张哈希表，这里由于weak指向的对象在释放的时候，根据对象地址的哈希函数地址计算出对应在哈希表中的index，然后找到存到的指针（链表结构），然后都置为nil。内存释放的时候采用哈希结构，可以更更快找到对应地址对应的weak指针。我猜测是拉链法实现的
以上就是NSDictionary的内部原理介绍
内部结构keys和values两个对应的数组（一一对应），hash函数通过key的值计算出哈希表的index，然后对应插入，下次访问的时候直接在此计算key的hash函数index，直接按照连续控件的访问顺序访问下标即可拿出数据，因此把无序和庞大的数据进行了空间哈希表对应，下次查找复杂度接近于O(1)，但是不断扩容的空间就是其弊端，因此开放地址法最好存储的是临时需要，尽快释放的资源例如字典参数和associated object，拉链法就保证了资源的可控性，像这种@synchronized锁就可以根据地址拉链出一条对应的使用线程即可，随时使用。
感谢：https://blog.csdn.net/Deft_MKJing/article/details/82732833
