c# - 为什么.NET中队列的底层实现要用数组？

Question

<分区>

Answer 1

出于同样的原因，许多其他数据结构，如堆栈、哈希表、邻接表等，都是使用数组而不是链表来实现的:

• 使用事实上的标准大小调整策略，即指数增长，即使您从一个空数组开始并插入几百万个项目，您也只需要两打调整大小操作。前几个调整大小操作只会复制几个字节。
• 尤其是队列很少无限制地增长，因此您基本上可以避免调整大小。
• 不只是更紧凑一点，普通值类型(int)的引用类型的双向链表整整比等价数组大三倍，甚至不用per-object考虑分配开销。如果我们诚实并考虑到这些因素，我们必须为每个节点添加一个或两个单词的 header ，因此它更像是大 4 倍或 5 倍。这使阵列可能存在的任何过度分配相形见绌。
• 由于是连续的，数组几乎可以无限地更好地利用各种缓存。这几乎会影响您可以在队列上执行的任何操作，除了询问其大小，包括调整大小。
• 必须分配所有这些列表节点并进行垃圾收集。虽然分代 GC 应该使分配相当便宜并且应该很容易地挑选只在队列中花费很少时间的节点，但它仍然有很多不必要的工作，如果队列很大或很少使用，许多节点在之前的次要 GC 中幸存下来被从队列的末尾弹出，就是这样。