. net有很多复杂的数据结构。不幸的是,其中一些非常相似,我不总是确定什么时候使用一个,什么时候使用另一个。我的大多数c#和VB书籍都在一定程度上讨论了它们,但它们从来没有真正深入任何细节。
数组、数组列表、列表、哈希表、字典、排序列表和排序字典之间的区别是什么?
哪些是可枚举的(IList -可以做'foreach'循环)?哪些使用键/值对(IDict)?
内存占用呢?插入速度?检索速度?
还有其他值得一提的数据结构吗?
我还在寻找内存使用和速度的更多细节(大o符号)
. net有很多复杂的数据结构。不幸的是,其中一些非常相似,我不总是确定什么时候使用一个,什么时候使用另一个。我的大多数c#和VB书籍都在一定程度上讨论了它们,但它们从来没有真正深入任何细节。
数组、数组列表、列表、哈希表、字典、排序列表和排序字典之间的区别是什么?
哪些是可枚举的(IList -可以做'foreach'循环)?哪些使用键/值对(IDict)?
内存占用呢?插入速度?检索速度?
还有其他值得一提的数据结构吗?
我还在寻找内存使用和速度的更多细节(大o符号)
当前回答
泛型集合和非泛型集合之间存在微妙和不那么微妙的差异。它们只是使用了不同的底层数据结构。例如,Hashtable保证了一个写入器-多个读取器而不需要同步。字典没有。
其他回答
泛型集合将比非泛型集合执行得更好,特别是在遍历许多项时。这是因为装箱和开箱不再发生。
它们在智能感知上拼得很好。只需输入System.Collections。或者System.Collections.Generics(首选),你会得到一个可用的列表和简短描述。
如果可能的话,使用泛型。这包括:
List而不是ArrayList 字典而不是哈希表
哈希表/字典是O(1)性能,这意味着性能不是大小的函数。知道这一点很重要。
编辑:在实践中,哈希表/字典<>查找的平均时间复杂度是O(1)。
我能想到的是:
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.
我倾向于一直使用List和Dictionary——一旦开始使用带有泛型的强类型,就很难再回到标准的非泛型了。
还有很多其他的数据结构,比如KeyValuePair,你可以用它做一些有趣的事情,还有SortedDictionary,它也很有用。