C#中的哈希表和列表 [英] Hashtable and List in C#

问题描述

大家好，

我有一个愚蠢的问题.
在c#中，Hashtable和List这两个数据结构中的哪一个比另一个更快(快速访问)?

Hi everybody,

I''ve a stupid question.
In c#, which of the two data structure Hashtable and List is faster(fast access) than the other? Is there any data structure faster than them?

推荐答案

它完全取决于操作集.如果仅添加元素，通过索引访问它们或使用foreach或for循环对其进行迭代，则List将是最快的(如果不时调整大小，其速度将比纯数组快).如果您需要搜索元素，尤其是在数据集很大的情况下，那么按键搜索Hashtable最快.速度接近O(1)(请参见 http://en.wikipedia.org/wiki/Big_O_notation [ ^ ].)

在现实生活中，最佳容器的选择可能并非易事.您不应为设计选择容器，而应在设计数据结构和代码时考虑到收集类的质量.在许多情况下，出于性能考虑，您可能需要应用数据冗余.


让我这样说:如果一种收集类型可能总是比其他收集类型更快，那么人们只会开发一种完美"的收集类型而从不使用其他收集类型.

—SA

It totally depends on the set of operations dominating your run-time. If you only add elements, access them by index or iterate them using foreach or for loops, the List will be the fastest (and faster than the plain array if you resize if from time to time). If you need to search elements, especially if the data set is big, Hashtable is the fastest if you search by key; the speed is nearly O(1) (see http://en.wikipedia.org/wiki/Big_O_notation[^].)

In real-life situation the selection of the best containers can be non-trivial. You should not select containers for the design, you should design you data structures and code taking into account the qualities of the collection classes. In many situations, you may need to apply data redundancy for the sake of performance.


Let me put it in this way: if one type of collection could be always faster then others, people would develop just one "perfect" collection type and never used others.

—SA

其他域中的某些库规范(例如C ++ STL)为添加，删除，访问，排序，内存消耗，提供的容器及其迭代器的内存布局等.

由于.Net/C#并非高性能环境，因此似乎没有那么集中精力.至少我不了解.Net世界中对容器的系统分析和保证.

如果您需要知道哪个容器对您的应用程序更快，那么最好对其进行度量.在C#中，您有几个标准容器(请参阅系统. Collections.Generic [ ^ ]和系统.集合 [ ^ ]命名空间.
除此之外，您还拥有C#本机对象数组(例如string[]).

一般而言:

• 哈希表(Directory<...>个对象)平均用于线性访问时间(假设您的对象具有不错的哈希键)，但没有排序功能，在最坏的情况下，您有当所有散列键都崩溃时，性能会下降.
• List<...>对象在随机访问和末尾添加方面具有良好的性能，但对于搜索(例如，检查)不利如果列表中包含某些条目).它们适用于具有定义顺序的通用存储元素和随机访问.
• 其他更专门的容器专注于其他方面(例如，添加时排序，Set操作，快速操作(如随机位置插入和删除) ，在一端快速添加并在另一端提取，在一端快速添加并提取等)

Some library specifications in other domains (like the C++ STL) provide clear guarantees on performance figures on add, remove, access, sort, memory consumption, memory layout, etc. of the provided containers and their iterators.

Since .Net/C# is not a high-performance environment, this seems to be lesser of a focus. At least I don''t know of a systematic analysis and guarantees of containers in the .Net world.

If you need to know which container is faster for your application, you best measure it. You have several standard containers at hand in C# (see System.Collections.Generic[^] and System.Collections[^] namespaces.
Beside that, you have the C# native object arrays (e.g. string[]).

General speaking:

• Hash tables (Directory<...> objects) are for linear access time in average (assuming you have a decent hash key for your objects), but you have no ordering and in worst case, you have bad performance when all hash key collaps to all the same.
• List<...> objects have good performance for random access and adding at the end, but are bad for searching (e.g. check if the list contains some entry). They are good for general purpose storing elements that have a defined order and for random access.
• Other more specialized containers focus on other aspects (e.g. sorted while adding, Set operations, fast manipulation like random location insertion and deletion, fast adding at one end and extracting at the other end, fast adding and extracting at one end, etc.)

List<string> GetHugeData()
{
    return (from record in db.MyHugeTable
            select record.Text
           ).ToList();
}





...
if (GetHugeData().Count > 0)
{
    ...
}

IQueryable<string> GetHugeData()
{
    return from record in db.MyHugeTable
           select record.Text;
}
bool HasElements<T>(IQueryable<T> it)
{
    return it != null
        && it.GetEnumerator().MoveNext();
}

...
if (HasElements(GetHugeData()))
{
    ...
}

如果您具有LINQ to Object或LINQ to XML，则应使用IEnumerable<...>而不是IQueryable<...>.

干杯
Andi

If you have LINQ to Object or LINQ to XML, you would use IEnumerable<...> instead of IQueryable<...>.

Cheers
Andi

哈希表更快.但是，了解Hashtable逻辑有时可能会更加复杂(尽管C#会抽象出大部分内容).

哈希表不支持泛型.
如果您正在寻找通用的哈希表，请使用字典.

Hashtables are faster. However, understanding Hashtable logic can sometimes be more complex (although C# would abstract most of that).

Hashtables do not support generics.
If you are looking for a generic Hashtable, use a Dictionary.

这篇关于C#中的哈希表和列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！