Click here to Skip to main content
15,867,568 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
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?
Posted
Updated 17-May-11 15:10pm
v2

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.

[EDIT]
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
 
Share this answer
 
v6
Comments
Karthik. A 18-May-11 0:30am    
nice answer, good that you included real life views, my 5!
Sergey Alexandrovich Kryukov 18-May-11 0:43am    
Thank you very much. It's not even "real live views", this is a "medical fact" -- it depends.
--SA
RAJI @Codeproject 18-May-11 0:47am    
good reply.my 5
Sergey Alexandrovich Kryukov 18-May-11 1:02am    
Thank you, Raji,
--SA
Abhinav S 18-May-11 0:54am    
Good reply. 5.
However, please see my answer too.
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.)


You see, that there are a few general purpose containers and several special purpose containers that serve a specific set of operations well (under given circumstances) and not so well in the other cases.

Decide on what your main application of the container is and use the most appropriate container for that. If performance is not sufficient, measure the performance drain and only then decide on a remedy.

Beside containers, you have the option to avoid containers in many situations.

If you work with LINQ, check out for not needed .ToList() and similar calls.
LINQ bases on defered evaluation of element sequences (also known iterators). I.e. if you query database data through LINQ, you always get deferred evaluation. If you implement such queries "carelessly", you get unneeded data access which may cost a lot of execution time, e.g.


"careless"more performant
C#
List<string> GetHugeData()
{
    return (from record in db.MyHugeTable
            select record.Text
           ).ToList();
}





...
if (GetHugeData().Count > 0)
{
    ...
}
C#
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()))
{
    ...
}


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

Cheers
Andi
 
Share this answer
 
v4
Comments
Sergey Alexandrovich Kryukov 29-Oct-12 11:04am    
Well, yes, now it should be way more clear than the comment, and I think this is useful as an example of a more detailed analysis. If performance of a container is a bottleneck or is critical otherwise, it makes sense to perform thorough time measurements and try to devise test data to model real-life situations closely.

Certainly, my 5 for the answer.
--SA
Andreas Gieriet 29-Oct-12 11:26am    
Thanks for your 5!
Cheers
Andi
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.
 
Share this answer
 
Comments
Sergey Alexandrovich Kryukov 18-May-11 1:06am    
Good note about generic. I cannot agree hash tables are faster -- not always. I'm pretty much sure I could make a case where the List will be faster at least slightly (well, you saw my answer). Understanding effort should not matter -- we human should use our cognitive abilities instead of accuracy and speed in routine work we're not designed for. My vote is 4.
--SA
Abhinav S 18-May-11 1:19am    
Working with a list would always be easier.
Thanks for the 4.
Sergey Alexandrovich Kryukov 18-May-11 3:02am    
Sure. As to the speeds, I added an [EDIT] to my answer...
--SA

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900