objective-c - NSMutableSet 是像链表一样实现的吗？

Question

既然你不能随机访问 NSMutableSet 的元素，这是否意味着它像链表一样实现？

即它会比 NSMutableArray 有更快的插入/删除吗？

Answer 1

源代码是可用的，所以你可以看看：CFSet.c。（这是 Core Foundation 的对应物NSSet，但它们基本相同。）它是一个哈希表。

但是你也应该记住，NSArray其实并不是作为数组来实现的。你可以在这里看到实现：CFArray.c。也许这篇博客文章更容易理解，虽然它有点过时（~5 年。）

Answer 2

不会。查找时间会更快，因为它会使用哈希。

Answer 3

我不是 Objective-C 程序员，但通常集合是通过哈希表实现的，它（如果正确完成）将为插入、删除和查找产生 O(1)。

从技术上讲，散列通常给你 O(M)，其中 M 是键的大小，但对于一个集合，你只需使用键对象的 id，它是恒定的，所以你回到 O(1)。

Answer 4

集合通常使用平衡二叉搜索树（例如红黑树、avl 树）来实现。