Dr.*_*len 4 c# arraylist data-structures
构建arraylist时使用了什么数据结构,因为我们能够在其上动态添加/删除值.
我假设它使用链接列表,但在做了一些谷歌后,我发现它使用矢量..但没有更多的细节.
Han*_*ant 14
在现代处理器上,内存缓存是王道.有效地使用高速缓存产生巨大的差异,当程序访问其内容未被高速缓存的地址时,处理器可以容易地停顿数百个周期,等待非常慢的存储器总线提供数据.
按顺序访问内存时访问内存效率最高.一个字节在缓存中可用的几率是最大的,它很可能出现在同一缓存行中.假设您按顺序索引数组元素,这使得数组成为最有效的集合对象.
因此,除LinkedList之外的所有.NET集合类都使用数组来存储数据.包括散列集合(Hashtable,Dictionary,Hashset),它们使用数组数组.包括ArrayList.应该避免使用LinkedList,因为它的缓存局部性很差,除非在随机已知位置进行廉价插入和删除是主要问题.
数组的一个问题是它们的大小是固定的,这使得很难实现自动调整大小的集合,比如ArrayList.这是通过故意浪费地址空间来解决的.只要数组填满容量,就会重新分配数组并复制元素.重新分配是以前大小的两倍,您可以从Capacity属性中观察到这一点.虽然这听起来很昂贵,但算法是分摊O(1)并且操作系统中的虚拟内存子系统确保您实际上不支付您不使用的内存.
您可以通过预先猜测容量来避免不那么便宜的复制.关于这个答案的更多细节.