Click here to Skip to main content
12,445,931 members (70,834 online)
Rate this:
 
Please Sign up or sign in to vote.
See more: C#
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 17-May-11 15:09pm
Updated 17-May-11 15:10pm
v2
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 1

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
  Permalink  
v6
Comments
Karthik. A 18-May-11 0:30am
   
nice answer, good that you included real life views, my 5!
SAKryukov 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
SAKryukov 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.
SAKryukov 18-May-11 1:02am
   
Thank you Abhinav. Let me see...
--SA
Kim Togo 18-May-11 2:37am
   
Good answer SA. 5.
SAKryukov 18-May-11 2:58am
   
Thank you, Kim.
--SA
Andreas Gieriet 28-Oct-12 17:22pm
   
My 5! Good answer as always!
My addition: if performance is really an issue, he should first measure to get evidence on that in his very constellation of usage. E.g. I did observe on several occasions that data are held in containers instead of accessed on request only by IEnumerable<...>..., etc.
Cheers
Andi
Sergey Alexandrovich Kryukov 28-Oct-12 20:42pm
   
Thank you, Andi.
I understand your point; it's is very good, but I'm not sure OP can understand it -- it's somewhat cryptic, may need some explanations...
--SA
Andreas Gieriet 29-Oct-12 5:03am
   
Hello Sergey,
see my solution #5. I decided to detail my "cryptic" statement in a solution rather to have a lenghtly comment here.
Cheers
Andi
Sergey Alexandrovich Kryukov 29-Oct-12 11:00am
   
I hope it was a good idea to do so. Let me see...
--SA
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 5

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
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()))
{
    ...
}

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

Cheers
Andi
  Permalink  
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
Rate this: bad
 
good
Please Sign up or sign in to vote.

Solution 2

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.
  Permalink  
Comments
SAKryukov 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.
SAKryukov 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)

  Print Answers RSS
Top Experts
Last 24hrsThis month


Advertise | Privacy | Mobile
Web01 | 2.8.160811.3 | Last Updated 29 Oct 2012
Copyright © CodeProject, 1999-2016
All Rights Reserved. Terms of Service
Layout: fixed | fluid

CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100