NSMutableArray背后的数据结构是什么？

Question

通常，“可变数组”类被实现为简单数组的包装器。当您添加一个元素到末尾时，包装器会分配更多的内存。这是一种常见的数据结构，各种操作的性能也很好。您可以得到 O(1) 的元素访问、O(N) 的插入和删除，或者 O(1)（平均值）的在数组末尾插入和删除。但是NSMutableArray则不同。例如，在文档中指出（我强调）：

注：大多数数组操作都需要恒定时间：访问元素、在任一端添加或删除元素以及替换元素。将元素插入数组的中间位置需要线性时间。

那么，NSMutableArray到底是什么？这个有文档记录吗？

- Rob N

---

据我所知，这并没有官方文档记录。通常有两种方法：调整大小并复制，或使用多个数组，每个数组覆盖范围的一部分。我认为苹果不想正式承诺特定的设计，以便能够重新设计。 - Hot Licks

最好看到任何实现代码的机会是从苹果的CFLite代码中搜索。在那里，至少你可以找到CFArray。 - TAKeanice

仅仅猜测：可变数组的实现方式是，在数组使用的内存块的末尾和开头都有一些空闲内存。这就是为什么在开头插入元素只需要常数时间的原因。但他们也写道，它实际上不只是一个类，所以我猜对于不同的大小可能会有不同的优化。 - TAKeanice

Answer 1

这是一个围绕着循环缓冲区的包装器。

这并没有文档记录也没有开源，但是这篇博客文章展示了令人惊叹的NSMutableArray逆向工程，我认为你会非常感兴趣。

NSMutableArray类簇由一个名为__NSArrayM的具体私有子类支持。

最大的发现是NSMutableArray不是像人们可能认为的那样对CFArray进行简单封装：因为CFArray是开源的，而且它不使用循环缓冲区，而__NSArrayM则使用了循环缓冲区。

通过阅读文章评论，似乎从iOS 4开始就是这种方式了，而在之前的SDK中，NSMutableArray实际上使用内部的CFArray，并且甚至没有__NSArrayM。

正如我上面提到的博客文章所述：

数据结构

正如你可能已经猜到的，__NSArrayM使用了循环缓冲区。 这种数据结构非常简单，但比普通数组/缓冲区稍微复杂一些。当到达任何一端时，循环缓冲区的内容都可以绕回。

循环缓冲区具有一些非常酷的特性。特别地，除非缓冲区已满，否则从任一端插入/删除都不需要移动任何内存。

objectAtIndex:的伪代码如下：

- (id)objectAtIndex:(NSUInteger)index {
    if (_used <= index) {
        goto ThrowException;
    }

    NSUInteger fetchOffset = _offset + index;
    NSUInteger realOffset = fetchOffset - (_size > fetchOffset ? 0 : _size);

    return _list[realOffset];

ThrowException:
    // exception throwing code
}

其中 ivars 定义如下：

• _used: 数组中元素的数量
• _list: 循环缓冲区的指针
• _size: 缓冲区的大小
• _offset: 数组在缓冲区中的第一个元素的索引

---

再次声明，以上所有信息均来自 Bartosz Ciechanowski 的博客文章，本人不对其信息负责。

- Gabriele Petronella

---

@MartinR 引用我引用的博客文章作者的话说：我惊讶地发现NSArray和NSMutableArray与CFArray没有任何共同之处。 - Gabriele Petronella

@MartinR 最值得注意的是，CFArray 没有使用循环缓冲区。 - Gabriele Petronella

当然。如果您查看我提供的文章，它还进行了一些测试，结果表明，在NSMutableArray的两端插入和删除操作都可以在常数时间内完成，使其适用于作为队列使用。 - Gabriele Petronella

"CFArray是C数据结构，因此不能成为NSArray的子类" - 这两者之间存在无缝桥接的原因。Objective-C对象和类本质上都是C结构体。至少这两种类型的“公共”部分布局是相同的。另外，尝试运行这个 - 我有NSMutableArray，所以在我的Mac上，CFArray实际上是NSMutableArray的具体子类。这并不意味着它们的实现不能不同，但是请注意你的措辞。 - user3447428

我记得bbum在SO的评论中提到，令人惊讶的是，“桥接到”的方向在过去几年中发生了变化 - 一些？大多数？CF现在实际上是用ObjC实现的。然而，我不清楚这与开源CF的关系如何。 - jscs

Answer 2

进行了一些测量：从一个空数组开始，添加了100,000次@"Hello"，然后又删除了100,000次。不同的模式：在末尾、开头、中间、靠近开头（如果可能，在索引20处）和靠近结尾（如果可能，在距离结尾20个索引处），还有一种是在靠近开头和结尾之间交替进行。以下是100,000个对象的时间（在Core 2 Duo上测量）：

Adding objects = 0.006593 seconds
Removing objects at the end = 0.004674 seconds
Adding objects at the start = 0.003577 seconds
Removing objects at the start = 0.002936 seconds
Adding objects in the middle = 3.057944 seconds
Removing objects in the middle = 3.059942 seconds
Adding objects close to the start = 0.010035 seconds
Removing objects close to the start = 0.007599 seconds
Adding objects close to the end = 0.008005 seconds
Removing objects close to the end = 0.008735 seconds
Adding objects close to the start / end = 0.008795 seconds
Removing objects close to the start / end = 0.008853 seconds

因此，每次添加/删除的时间与数组开始或结束的距离成比例，以较近的那个为准。在中间添加元素是很昂贵的。您不必完全在末尾工作；删除接近开头/结尾的元素也非常便宜。

建议将其实现为循环列表的细节被省略了：最后一个和第一个数组元素之间存在可变大小的间隙。随着添加/删除数组元素，该间隙的大小会发生变化。当间隙消失并添加更多对象时，需要分配更多的内存并移动对象指针；当间隙变得太大时，可以缩小数组并移动对象指针。一个简单的改变（允许间隙位于任何位置，而不仅仅是在最后一个和第一个元素之间）将允许在任何位置进行快速更改（只要是相同的位置），并且将使“瘦身”数组的操作更快。

- gnasher729

---

你的结果证实了文档中所述，但那不是问题（据我理解）。 - Martin R

这与规范完全一致。在两端进行常数时间插入/删除，显然会以中间插入/删除性能不佳为代价。话虽如此，我不明白这如何回答原始问题。 - Gabriele Petronella

那么为什么会有这个问题呢？只是出于好奇吗？还是想了解性能特征？优化的黄金法则：如果你没有测量，那就不算数。顺便说一句，没有充分的理由认为MacOS X或iOS中的实现与开源实现相同。它也不完全是一个循环缓冲区，因为循环缓冲区可以轻松处理在缓冲区任何位置进行插入/删除，例如在中间。 - gnasher729

@gansher729 问题是NSMutableArray背后的数据结构是什么。循环缓冲区来自于实际实现的逆向工程，而不是开源代码（Foundation没有可用的开源代码），所以这里没有人做出那样的假设。 - Gabriele Petronella

建议的实现方式是循环列表。不对。循环列表和循环缓冲区不是同一回事。前者是一个链表，其中最后一个元素指向第一个元素。而缓冲区是一块内存，在循环缓冲区中，偏移量定义了数据开始的位置。 - vikingosegundo