NSDictionary和NSMutableArray底层原理（

作者: Mr_Baymax | 来源:发表于2019-03-05 11:30 被阅读0次

前言

1.NSDictionary底层是哈希表，下面会介绍具体是用拉链法还是开放定址法线性探测来解决冲突？由于Apple给的查询复杂度可以快至O(1)，那么为什么是O(1)，底层是如何通过空间换取时间的？

2.NSArray是线性连续内存，这个很好理解。但是NSMutableArray是可以插入和删除的，那么如何做到高效？就比如插入，如何做到尽可能少的移动或者不移动插入元素后其他元素的内存？实现数据结构原理是什么？

NSDictionary底层原理

哈希表详解以及Topk算法

原作者介绍了桶排序和桶排序（哈希排序）

桶排序是典型的空间换时间，可以让排序时间打到O(n)

创建N个空桶，N为排序数组中最大值加一。然后遍历排序数组，以元素值为下标，将其放入对应的桶中
如果少量数据，可以根据数组里面的最大值+1创建出那么多空桶，然后遍历，根据索引在空桶的值上累加，最后遍历空桶（已装载），根据值遍历出对应的下标。

虽然这样做效率非常高，但是如果数据过大，内存吃不消，这样就有了哈希排序的介绍。例如一组数据，我们可以根据hash算法后取模的值进行空桶排列，但是如果两个值例如 101和11 % 10都是余1，会被放入同一个桶里面，这样就会有需要二次排列。虽然这个排序效率并不高，因此哈希化就变成了数据存储的一种设计。

字典介绍

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结果应该通过合理的运算来尽可能的避免冲突，比如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;
    ......
}

但是hash过程中必定会出现冲突，如何来处理冲突？

开放定址法

在上文介绍哈希排序时，解决hash碰撞的方式是将发生碰撞的多个元素放到一个容器中，这个容器通常使用链表结构，这种解决方案被称作拉链法。试想一下，假如dictionary也采用这种方案解决冲突，为了能匹配到正确的数据，必然要使用一个复合结构存储key和value的数据，然后碰撞发生时遍历容器查找匹配的key-value：

image.png
从设计结构上来看，这个方案能够解决hash碰撞的匹配问题。但拉链法会将key和value包装成一个结构存储，而dictionary的结构拥有keys和values这两个数组，说明了这两个数据是被分开存储的，所以使用这个方案的可能性不高。而且拉链法存在一个问题：

桶数量不多的情况下，拉链衍生出来的链表会非常庞大，需要二次遍历，匹配损耗一样很大，这样等于没有优化一样。官方都说了查找算法接近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;
        }
    }
}

我们刚才在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] = {
    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]);
            }
        }
    }
    ......
}

除了上述提到的拉链和开放定址，还有再哈希以及建立公共溢出区域来解决冲突。

apple都用了，开放定址法应该是在三种方案中最优，它的缺点也非常明显：

由于扩充几乎是翻倍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在使用过程中总是会很快的被释放，不会长期占用内存。

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

AssociationsHashMap是一个dictionary，以对象hash结果存储了一个dictionary，用OC的泛型声明来看，就是一个NSDictionary<id, NSDictionary *>的结构变量，这个变量是全局的。
ObjectAssociationMap是被上面嵌套的dictionary，这个结构存储了实际绑定的属性值。在我们调用objc_setAssociatedObject的时候，会将传入的key和value存储在这里面。

开放定址法在大量数据存储时，会造成大量的空间占用，为什么associated object采用全局对象的情况下依旧使用这种方案。这是因为虽然苹果使用了一个全局的AssociationsHashMap对象存储了全部的关联对象，但在对象dealloc时会移除这些数据，同一时间占用的内存也是可接受的：

@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采用的是拉链法，而associate object采用的是开放定址法

其实最重要的一点是存储数据的生命周期和特性所决定的：

开放定址法的存储属性基本是和key所属对象相关联的，一旦key所属对象发生变化时，其所存储的数据大概率也是要发生修改的。因此即便是开放定址法在使用全局实现时，对象释放时同样会清空所存储的内容，因此总体来说内存占用并不会过高。
拉链法对于碰撞的处理方式更为简单，不用担心数据的堆积现象。另外如果存储的数据是通用类型数据，可以被反复利用。比如@synchronized是存储的锁是一种无关业务的实现结构，程序运行时多个对象使用同一个锁的概率相当的高，有效的节省了内存。

好像weak对应的引用计数根据对象地址维护了一张哈希表，这里由于weak指向的对象在释放的时候，根据对象地址的哈希函数地址计算出对应在哈希表中的index，然后找到存到的指针（链表结构），然后都置为nil。内存释放的时候采用哈希结构，可以更更快找到对应地址对应的weak指针。我猜测是拉链法实现的

以上就是NSDictionary的内部原理介绍

内部结构keys和values两个对应的数组（一一对应），hash函数通过key的值计算出哈希表的index，然后对应插入，下次访问的时候直接在此计算key的hash函数index，直接按照连续控件的访问顺序访问下标即可拿出数据，因此把无序和庞大的数据进行了空间哈希表对应，下次查找复杂度接近于O(1)，但是不断扩容的空间就是其弊端，因此开放地址法最好存储的是临时需要，尽快释放的资源例如字典参数和associated object，拉链法就保证了资源的可控性，像这种@synchronized锁就可以根据地址拉链出一条对应的使用线程即可，随时使用。

NSMutableArray底层原理

c数组问题

普通c数组，归根接地就是一段能被方便读写的连续内存控件。

使用一段线性内存空间的一个最明显的缺点是，在下标 0 处插入一个元素时，需要移动其它所有的元素，即 memmove 的原理：

image

同样地，假如想要保持相同的内存指针作为首个元素的地址，移除第一个元素需要进行相同的动作：

image

当数组非常大时，这样很快会成为问题。显而易见，直接指针存取在数组的世界里必定不是最高级的抽象。C 风格的数组通常很有用，但 Obj-C 程序员每天的主要工作使得它们需要 NSMutableArray 这样一个可变的、可索引的容器。

上面文章中介绍了如何反汇编出来源码，下面通过参数来详细介绍NSMutableArray

ivars 的意思

我们来概括下每个 ivar 的意思：

_used 是计数的意思
_list 是缓冲区指针
_size 是缓冲区的大小
_offset 是在缓冲区里的数组的第一个元素索引

内存布局

最关键的部分是决定 realOffset 应该等于 fetchOffset（减去 0）还是 fetchOffset 减 _size。看着纯代码不一定能画出完美的图画，我们设想一下两个关于如何获取对象的例子。

_size > fetchOffset

这个例子中，偏移量相对较小：

image

为了获取 0 处的对象，我们计算出 fetchOffset 等于 3 + 0。因为 _size 大于 fetchOffset，realOffset 也等于 3。代码返回 _list[3] 的值。而获取 4 处的对象时，fetchOffset 等于 3 + 4，代码返回 _list[7]。

_size <= fetchOffset

当偏移量比较大时会怎样？

image

获取 0 处的对象，使得 fetchOffset 等于 7 + 0，调用方法后如期望的返回 _list[7]。然而，获取 4 处的对象时，fetchOffset 等于 7 + 4 = 11，要大于 _size。获得的 realOffset 要从 fetchOffset 减去 _size，即 11 - 10 = 1，方法返回 list[1]。

我们基本上是在做取模运算，当穿过缓存区边界时会转回缓冲区的另一端。

数据结构

正如你会猜测的，__NSArrayM 用了环形缓冲区 (circular buffer)。这个数据结构相当简单，只是比常规数组或缓冲区复杂点。环形缓冲区的内容能在到达任意一端时绕向另一端。

环形缓冲区有一些非常酷的属性。尤其是，除非缓冲区满了，否则在任意一端插入或删除均不会要求移动任何内存。我们来分析这个类如何充分利用环形缓冲区来使得自身比 C 数组强大得多。在任意一端插入或者删除，只是修改offset参数，不需要移动内存，我们访问的时候只是不和普通的数组一样index多少就是多少，这里会计算加上offset之后处理的值取数据，而不是插入头和尾巴的时候，环形结构会根据最少移动内存指针的方式插入，例如要在A和B之间插入，按照C的数组，我们需要把B到E的元素移动内存，但是环形缓冲区的设计，我们只要把A的值向前移动一个单位内存，即可，同时修改offset偏移量，就能保证最小的移动单元来完成中间插入

在两端插入或删除会相当地快

我么来思考一下一个非常简单的例子：

NSMutableArray *array = [NSMutableArray array];
for (int i = 0; i &lt; 5; i++) {
    [array addObject:@(i)];
}
[array removeObjectAtIndex:0];
[array removeObjectAtIndex:0];
NSLog(@"%@", [array explored_description]);

输出显示移除位于 0 处的对象两次后，只是简单地清除了指针并由此而移动了 _offset ivar：

Size: 6
Count: 3
Offset: 2
Storage: 0x178245ca0
[0] 0x0
[1] 0x0
[2] 0xb000000000000022
[3] 0xb000000000000032
[4] 0xb000000000000042
[5] 0x0

image

头部插入

NSMutableArray *array = [NSMutableArray array];
for (int i = 0; i &lt; 4; i++) {
    [array addObject:@(i)];
}
[array insertObject:@(15) atIndex:0];

在 0 处插入对象用了环形缓冲区魔法来将新插入的对象放置在缓存区的末端：

Size: 6
Count: 5
Offset: 5
Storage: 0x17004a560
[0] 0xb000000000000002
[1] 0xb000000000000012
[2] 0xb000000000000022
[3] 0xb000000000000032
[4] 0x0
[5] 0xb0000000000000f2

image

可以看到插入头尾只是修改offset指针而已，如果插入数据到达阀值，一样需要扩容。

最糟糕的就是中间插入和删除中间

NSMutableArray *array = [NSMutableArray array];
for (int i = 0; i &lt; 6; i++) {
    [array addObject:@(i)];
}
[array removeObjectAtIndex:3];

从输出中我们看到顶部的元素往下移动，底部为低索引（注意 [5] 处的游离指针）：

[0] 0xb000000000000002
[1] 0xb000000000000012
[2] 0xb000000000000022
[3] 0xb000000000000042
[4] 0xb000000000000052
[5] 0xb000000000000052

image

然而，当我们调用 [array removeObjectAtIndex:2] 时，底部的元素往上移动，顶部为高索引：

image

往中部插入对象有非常相似的结果。合理的解释就是，__NSArrayM 试着去最小化内存的移动，因此会移动最少的一边元素。

总结

NSMutableArray 是一个高级抽象数组，解决了 C 风格数组对应的缺点。（C数组插入的时候都会移动内存，不是O（1），用到了环形缓冲区数据结构来处理内存移动的损耗）

但是可变数组任意一端插入或删除能有固定时间的性能。而且在中间插入和删除的时候都会试着去移动最小化内存。

环形缓冲区的数据结构如果是连续数组结构，在扩容的时候难免会移动大量内存，因此用链表实现环形缓冲会更好

维基百科就是这么介绍的

NSDictionary和NSMutableArray底层原理（

前言

NSDictionary底层原理

字典介绍

hash

开放定址法

associated object

@synchronized

NSMutableArray底层原理

c数组问题

ivars 的意思

内存布局

_size > fetchOffset

_size <= fetchOffset

数据结构

在两端插入或删除会相当地快

最糟糕的就是中间插入和删除中间

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

数据结构

底层

iOS

OC底层相关