4

构建arraylist时使用什么数据结构，因为我们可以在其上动态添加/删除值。

我假设它使用链表但在做了一些谷歌之后，我发现它使用向量..但没有更多关于它的细节。

4

5 回答 5

14

在现代处理器上，内存缓存为王。有效地使用缓存会产生巨大的影响，当程序访问其内容未缓存的地址时，处理器很容易停滞数百个周期，等待非常慢的内存总线提供数据。

当您按顺序访问内存时，访问内存是最有效的。一个字节在缓存中可用的几率最大，它很可能出现在同一个缓存行中。假设您按顺序索引数组元素，这使得数组成为迄今为止最有效的集合对象。

因此，除 LinkedList 之外的所有 .NET 集合类都使用数组来存储数据。包括散列集合（Hashtable、Dictionary、Hashset），它们使用数组数组。包括数组列表。应该避免使用 LinkedList，因为它的缓存局部性非常差，除非在随机已知位置进行廉价插入和删除是主要关注点。

数组的一个问题是它们的大小是固定的，这使得很难实现自动调整大小的集合，比如 ArrayList。这是通过故意浪费地址空间来解决的。每当数组填满容量时，就会重新分配数组并复制元素。重新分配是之前大小的两倍，您可以从容量属性中观察到这一点。虽然这听起来很昂贵，但该算法的摊销成本为 O(1)，并且操作系统中的虚拟内存子系统确保您实际上不会为不使用的内存付费。

您可以通过预先猜测容量来避免不那么便宜的复制。有关此答案的更多详细信息。

于 2012-06-30T15:45:59.210 回答
2

Arraylist 在内部使用数组来存储数据并在需要时调整数组的大小。

Arraylist 的 java 实现在内部创建一个具有初始大小的数组并调整该数组的大小。

你可以在这里看到实现：http: //www.docjar.com/html/api/java/util/ArrayList.java.html

这适用于 Java，但概念与 .NET 相同。

于 2012-06-30T14:57:54.603 回答
1

从MSDN 页面：

使用大小根据需要动态增加的数组实现 IList 接口。

直接使用类而不是数组的一些好处是：

  • 它可以在任何地方使用IList
  • 在从数组中间添加/删除项目时，它会为您处理调整大小和复制
  • 它跟踪数组中的“最后一个”项目
  • 它提供了对数组中的项目进行二进制搜索的方法
于 2012-06-30T15:04:09.760 回答
1

将ArrayList值在内部存储为对象数组，并公开一些公共辅助方法以使使用数组更容易（通过IList接口公开）。

插入项目时，插入点右侧的所有元素都会向右移动，从而使插入效率低下。另一方面，追加速度很快，因为不需要移动元素（除非内部数组已达到容量，在这种情况下，它会被更大的数组替换）。

因为值在内部存储为数组，所以它提供了数组的优点（例如，如果对值进行了排序，则可以进行高效搜索）。

于 2012-06-30T15:10:07.373 回答
1

请参见此处：ArrayList 源

如前所述，它是下面的数组。

private object[] _items;

这是 Add() 方法：

public virtual int Add(object value)
{
    if (this._size == this._items.Length)
    {
        this.EnsureCapacity(this._size + 1);
    }
    this._items[this._size] = value;
    ArrayList expr_2D = this;
    ArrayList arg_2E_0 = expr_2D;
    expr_2D._version = arg_2E_0._version + 1;
    ArrayList expr_3B = this;
    ArrayList arg_3C_0 = expr_3B;
    ArrayList arg_45_0 = expr_3B;
    int expr_41 = arg_3C_0._size;
    int arg_42_0 = expr_41;
    int arg_44_0 = expr_41;
    int i = arg_42_0;
    arg_45_0._size = arg_44_0 + 1;
    return i;
}

如您所见， EnsureCapacity 被调用...最终调用 set_Capacity：

public virtual void set_Capacity(int value)
{
    if (value < this._size)
    {
        throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
    }
    if (value != this._items.Length)
    {
        if (value <= 0)
        {
            this._items = new object[4];
            goto IL_65;
        }
        object[] array = new object[value];
        if (this._size > 0)
        {
            Array.Copy(this._items, 0, array, 0, this._size);
        }
        this._items = array;
        return;
    }
    IL_65:
}

如果需要增加容量，则将整个数组复制到更大的数组中。

于 2012-06-30T15:11:14.157 回答