15

I'm writing a service where performance is essential, and I'm not sure what is the fastest thing. I have a few Objects (50-200) which each have an ID in them (ints, e.g. 84397 or 23845). Would it be faster to have a Dictionary, a List of KeyValue Pairs or a List with the indexes set to the IDs with the rest having null values or an array with the same idea?

SBoss
  • 8,845
  • 7
  • 28
  • 44
  • 2
    Have you tried to run a simple test application? – Neil Knight Nov 29 '11 at 07:27
  • 2
    I've started it, but I thought asking would be more efficient (for future askers and me). – SBoss Nov 29 '11 at 07:29
  • 4
    Which operations you have to do with those objects? Search by key? Search for values? Many inserts? Removing keys? – Marco Nov 29 '11 at 07:29
  • In the case you're using arrays - what is the maximum ID you have? How ofter you'll increase array size? – Vitaliy Nov 29 '11 at 07:31
  • Read value by key (random times), update value by key (every second), a few inserts (every few seconds). Maximum ID is not fixed. – SBoss Nov 29 '11 at 07:32
  • Faster wrt to what? Faster lookup? Removal? Addition? Updation? Insertion? Enumeration? Lesser memory overhead so that other programs run smoother? Faster to write? Sorry voting to close. – nawfal May 25 '14 at 10:25

4 Answers4

21

It depends on which operation you want to execute. Let's assume that you want to find an object with a given ID.

  • The huge array approach is fastest: Accessing myArray[84397] is a constant-time operation O(1). Of course, this approach requires the most memory.
  • The dictionary is almost as fast but requires less memory, since it uses a hash table internally.
  • The list of pairs approach is the slowest, since you might have to traverse the whole list to find your entry, which yields O(n) complexity.

Thus, in your situation, I would choose the dictionary, unless the marginally better performance of the huge array is really relevant in your case.

Heinzi
  • 167,459
  • 57
  • 363
  • 519
  • Thanks for the help, I'll use the dictionary (assuming marginally means something like 1ms faster). – SBoss Nov 29 '11 at 08:35
  • You wrote "dictionary requires less memory" - didn't you mean to write it requires MORE memory, since it uses a hash table internally? – BornToCode Jun 23 '14 at 11:42
  • 4
    @BornToCode: It requires less memory than the previous option, the huge array. The huge array requires *maximumID* storage places, whereas the dictionary only requires around *someConstant*numberOfElements* storage places. – Heinzi Jun 23 '14 at 12:47
8

Dictionary<TKey, TValue> uses a hash table internally so I think it would be the fastest one.

David Schwartz
  • 1,956
  • 19
  • 28
Haris Hasan
  • 29,856
  • 10
  • 92
  • 122
  • 2
    +1 This is precisely why `Dictionary` exists. – James Nov 29 '11 at 07:30
  • 2
    Would a HashTable itself be better? – SBoss Nov 29 '11 at 07:33
  • 2
    @SBoss - The generic dictionary does not use a `HashTable` internally, so no. A `HashTable` is considerably slower when you use ValueTypes, like you plan on doing with your `int`. – Christopher Currens Nov 29 '11 at 07:46
  • 3
    A `Dictionary` uses a hash table, but does not use the `HashTable` class. – Gabe Nov 29 '11 at 07:47
  • @Gabe - Yes. I now realize I wasn't clear about that. Thanks for the clarification. – Christopher Currens Nov 29 '11 at 07:52
  • @SBoss Performance for both HashTable and Dictionary would be very similar but there is one major difference ` Dictionary is a generic type, Hashtable is not. That means you get type safety with Dictionary, because you can't insert any random object into it, and you don't have to cast the values you take out.` – Haris Hasan Nov 29 '11 at 08:31
  • @DavidSchwartz, you can't just [completely change someone's post](http://stackoverflow.com/review/suggested-edits/4247992). Make your own answer if you have one. – gunr2171 Mar 06 '14 at 17:45
2

Dictionary versus List Lookup time

Also, for a more detailed explaination of the different collections, check out this question.

Community
  • 1
  • 1
Neil Knight
  • 47,437
  • 25
  • 129
  • 188
0

You can use Hashtables as well. Dictionary internally using it anyway. but dictionary has an advantage that it is a GENERIC type which gives you type safety.

here is different thread Dictionary Vs HashTable I hope it helps you decide.

Praveen

Community
  • 1
  • 1
PraveenLearnsEveryday
  • 595
  • 1
  • 5
  • 13