尽管存在大对象堆碎片，为什么通用集合中的大多数数据结构都使用数组？
Why most of the data structures in generic collections use array despite of Large Object Heap fragmentation?
我可以看到 CoreCLR and CoreFx 对大多数通用集合隐式使用数组。使用数组的主要驱动因素是什么，以及它如何处理 LOH 碎片的任何副作用。
数组访问速度更快，因为它是线性存储。如果数组可以很好地解决问题，那么它们是一种更好的遍历存储，而不是总是识别下一个对象的存储位置。对于大型数据结构，这种性能优势也将得到放大。
数组应该集合是什么？
更重要的是，数组还能集合是什么？
使用集合归结为"arrays - and stuff we wrap around arrays, for ease of use.":
- 纯粹的东西（数组），确实提供了一些便利，例如 C#/.NET 中的边界检查
- 自增长数组（列表）
- 两个同步数组，允许将任何输入映射到任何元素（字典 key/value 对）
- 三个同步数组：Key、Value 和一个 Hashvalue，用于快速识别不匹配的键 (HastTable)。
在幕后 - 无论 .NET 使用指针有多么困难 - 这一切都归结为一些代码执行 C/C++ 风格的指针算法来获取下一个元素。
编辑 1：正如我在另一个地方了解到的那样，.NET 词典实际上是作为 HashLists 实现的。 HashList class 只是泛型之前的版本。对象有一个具有合理默认行为的 GetHashCode 函数，可以使用，但也可以完全覆盖。
碎片明智 "best" 将是一个引用数组。它可以与引用宽度一样小（指针或稍大），并且 GC 可以在实例周围移动以对内存进行碎片整理。当然，你会得到访问引用的轻微开销，而不是仅仅 counting/mathing 指针，所以通常这是内存与速度的权衡。然而，这可能会进入 Speed Rant Territory of detail.
编辑 2：正如 Markus Appel 在评论中指出的那样，有一些更好的方法可以避免碎片化：Linked lists。即使是那个单一的引用数组——如果你让它足够大——也会在一个不可分割的块中占用相当多的内存。所以它可能 运行 进入对象大小限制或数组索引器限制。链表两者都不会。但结果是性能与从未进行过碎片整理的磁盘有关。
泛型只是在 collections/other 处提供类型安全的便利。它避免了您必须使用可怕的 Object 作为类型，这会破坏所有编译时类型安全。 Afaik 他们没有为这种情况添加任何其他内容。 List<string> 与 StringList 的工作方式相同。
如果不小心使用数组，可能会导致碎片。但在一般情况下，性能收益大于成本。
当缓冲区用完时，集合会分配一个双倍大小的新缓冲区。如果代码插入大量项目 而没有 指定容量，这将导致 log2(N) 次重新分配。如果代码 确实 指定了一个容量，即使是 非常 粗略的近似值，也可能根本没有碎片问题。
删除是另一种代价高昂的情况，因为集合必须将已删除项目之后的项目移到左侧。
虽然一般来说，数组存储比其他存储结构提供更好的性能，无论是读取、插入 还是 分配内存。在大多数情况下，删除很少见。
例如，在链表中插入 N 个项目需要分配 N 个对象来保存该值并存储 N 个指针。每次插入都会支付该费用，而 GC 将有更多的对象需要跟踪和收集。在链表中插入 100K 个项目将分配 100K 个需要跟踪的节点对象。
对于数组，除非缓冲区用完，否则不会进行任何分配。在大多数情况下，插入意味着简单地写入缓冲区位置并更新计数。当缓冲区用完时，将进行一次重新分配和一次（昂贵的）复制操作。对于 100K 项，这是 17 次分配。在大多数情况下，这是可以接受的成本。
为了减少甚至取消分配，代码可以指定用作初始缓冲区大小的容量。即使指定 非常 粗略估计也可以大大减少分配。将 1024 指定为 100K 项目的初始容量会将重新分配减少到 7。
我可以看到 CoreCLR and CoreFx 对大多数通用集合隐式使用数组。使用数组的主要驱动因素是什么，以及它如何处理 LOH 碎片的任何副作用。
数组访问速度更快，因为它是线性存储。如果数组可以很好地解决问题，那么它们是一种更好的遍历存储，而不是总是识别下一个对象的存储位置。对于大型数据结构，这种性能优势也将得到放大。
数组应该集合是什么？
更重要的是，数组还能集合是什么？
使用集合归结为"arrays - and stuff we wrap around arrays, for ease of use.":
- 纯粹的东西（数组），确实提供了一些便利，例如 C#/.NET 中的边界检查
- 自增长数组（列表）
- 两个同步数组，允许将任何输入映射到任何元素（字典 key/value 对）
- 三个同步数组：Key、Value 和一个 Hashvalue，用于快速识别不匹配的键 (HastTable)。
在幕后 - 无论 .NET 使用指针有多么困难 - 这一切都归结为一些代码执行 C/C++ 风格的指针算法来获取下一个元素。
编辑 1：正如我在另一个地方了解到的那样，.NET 词典实际上是作为 HashLists 实现的。 HashList class 只是泛型之前的版本。对象有一个具有合理默认行为的 GetHashCode 函数，可以使用，但也可以完全覆盖。
碎片明智 "best" 将是一个引用数组。它可以与引用宽度一样小（指针或稍大），并且 GC 可以在实例周围移动以对内存进行碎片整理。当然，你会得到访问引用的轻微开销，而不是仅仅 counting/mathing 指针，所以通常这是内存与速度的权衡。然而，这可能会进入 Speed Rant Territory of detail.
编辑 2：正如 Markus Appel 在评论中指出的那样，有一些更好的方法可以避免碎片化：Linked lists。即使是那个单一的引用数组——如果你让它足够大——也会在一个不可分割的块中占用相当多的内存。所以它可能 运行 进入对象大小限制或数组索引器限制。链表两者都不会。但结果是性能与从未进行过碎片整理的磁盘有关。
泛型只是在 collections/other 处提供类型安全的便利。它避免了您必须使用可怕的 Object 作为类型，这会破坏所有编译时类型安全。 Afaik 他们没有为这种情况添加任何其他内容。 List<string> 与 StringList 的工作方式相同。
如果不小心使用数组，可能会导致碎片。但在一般情况下，性能收益大于成本。
当缓冲区用完时，集合会分配一个双倍大小的新缓冲区。如果代码插入大量项目 而没有 指定容量，这将导致 log2(N) 次重新分配。如果代码 确实 指定了一个容量，即使是 非常 粗略的近似值，也可能根本没有碎片问题。
删除是另一种代价高昂的情况，因为集合必须将已删除项目之后的项目移到左侧。
虽然一般来说，数组存储比其他存储结构提供更好的性能，无论是读取、插入 还是 分配内存。在大多数情况下，删除很少见。
例如，在链表中插入 N 个项目需要分配 N 个对象来保存该值并存储 N 个指针。每次插入都会支付该费用，而 GC 将有更多的对象需要跟踪和收集。在链表中插入 100K 个项目将分配 100K 个需要跟踪的节点对象。
对于数组，除非缓冲区用完，否则不会进行任何分配。在大多数情况下，插入意味着简单地写入缓冲区位置并更新计数。当缓冲区用完时，将进行一次重新分配和一次（昂贵的）复制操作。对于 100K 项，这是 17 次分配。在大多数情况下，这是可以接受的成本。
为了减少甚至取消分配，代码可以指定用作初始缓冲区大小的容量。即使指定 非常 粗略估计也可以大大减少分配。将 1024 指定为 100K 项目的初始容量会将重新分配减少到 7。