.NET数据结构：ArrayList，List，HashTable，Dictionary，SortedList，SortedDictionary - 速度，内存以及何时使用？ [英] .NET data structures: ArrayList, List, HashTable, Dictionary, SortedList, SortedDictionary -- Speed, memory, and when to use each?

问题描述

.NET具有很多复杂的数据结构。不幸的是，其中一些是非常相似的，我并不总是确定何时使用一个，何时使用另一个。我的大部分C＃和Visual Basic书籍都在一定程度上谈到他们，但他们从来没有真正了解任何真实的细节。

Array，ArrayList，List有什么区别？ ，Hashtable，Dictionary，SortedList和SortedDictionary？

哪些是可列举的（IList - 可以做'foreach'循环）？哪些使用键/值对（IDict）？

内存占用？插入速度？检索速度？

有没有其他数据结构值得一提？

我还在寻找更多的细节内存使用量和速度（Big-O符号）。

解决方案

我的头顶：

• Array * - 代表一个老式的内存数组 - 类似于正常的类型[] 数组。可以枚举。不能自动增长。我会假设非常快速的插入和恢复速度。




• ArrayList - 自动增长数组。增加更多的开销。可以枚举，可能比正常数组慢，但仍然很快。这些在.NET中使用很多。




• 列表 - 我的一个喜爱 - 可以与泛型，所以你可以有一个强类型的数组，例如列表< string> 。除此之外，它非常像 ArrayList




• Hashtable - 普通旧哈希表。 O（1）到O（n）最坏的情况。可以枚举值和键属性，并执行键/值对




• 字典 - 与上述相同只有通过泛型进行强类型化，例如 Dictionary< string，string>




• SortedList - 一个排序的通用列表。放慢插入，因为它必须弄清楚放在哪里。可以枚举，可能是一样的检索，因为它不必诉诸，但删除将比一个简单的旧列表慢。

我经常使用列表和字典 - 一旦你开始使用它们强类型仿制的，真的很难回到标准的非泛型。

还有很多其他数据结构 - 有$ code> KeyValuePair 您可以使用它来做一些有趣的事情，有一个 SortedDictionary ，这也是有用的。

.NET has a lot of complex data structures. Unfortunately, some of them are quite similar, and I'm not always sure when to use one and when to use another. Most of my C# and Visual Basic books talk about them to a certain extent, but they never really go into any real detail.

What's the difference between Array, ArrayList, List, Hashtable, Dictionary, SortedList, and SortedDictionary?

Which ones are enumerable (IList -- can do 'foreach' loops)? Which ones use key/value pairs (IDict)?

What about memory footprint? Insertion speed? Retrieval speed?

Are there any other data structures worth mentioning?

I'm still searching for more details on memory usage and speed (Big-O notation).

解决方案

Off the top of my head:

• Array* - represents an old-school memory array - kind of like a alias for a normal type[] array. Can enumerate. Can't grow automatically. I would assume very fast insert and retrival speed.

• ArrayList - automatically growing array. Adds more overhead. Can enum., probably slower than a normal array but still pretty fast. These are used a lot in .NET

• List - one of my favs - can be used with generics, so you can have a strongly typed array, e.g. List<string>. Other than that, acts very much like ArrayList

• Hashtable - plain old hashtable. O(1) to O(n) worst case. Can enumerate the value and keys properties, and do key/val pairs

• Dictionary - same as above only strongly typed via generics, such as Dictionary<string, string>

• SortedList - a sorted generic list. Slowed on insertion since it has to figure out where to put things. Can enum., probably the same on retrieval since it doesn't have to resort, but deletion will be slower than a plain old list.

I tend to use List and Dictionary all the time - once you start using them strongly typed with generics, its really hard to go back to the standard non-generic ones.

There are lots of other data structures too - there's KeyValuePair which you can use to do some interesting things, there's a SortedDictionary which can be useful as well.

这篇关于.NET数据结构：ArrayList，List，HashTable，Dictionary，SortedList，SortedDictionary - 速度，内存以及何时使用？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！