3

I had this discussion with co-workers before. We had to store users by id and we'd do mostly Add/Get operations on it. I proposed to use a Dictionary which seems like the logical choice. My co-worker argued that the Dictionary was pointless in that case because we didn't have many users (Maybe 150).

I proposed the dictionary because I know, in theory, that it's the best data structure for this scenario. In the case where I have 150 users (that's an arbitrary number), is there really a performance difference between the O(1) access of a Dictionary and the O(n) access of a List?

He proposed the List because the Dictionary seemed useless in that case.

We ended up using the Dictionary because if the application was to grow, we'd have more users and the Dictionary would prove useful.

Though the question remained, are there scenarios where we shouldn't consider which data structures to use?

  • 6
    tl;dr coworker is weird – Lightness Races in Orbit Dec 3 '15 at 20:29
  • @LightnessRacesinOrbit I already had that feeling :p I had troubles with him very often when it came to design stuff other than CRUD operations – IEatBagels Dec 3 '15 at 20:32
  • 4
    I can't find it at the moment, but someone actually studied this on C#, and the cutover point from a list to a Dictionary or Hash Table is somewhere between 3 and 7 items. The number is much lower than I would have thought. – Robert Harvey Dec 3 '15 at 20:36
  • 2
    Here it is: dotnetperls.com/dictionary-time. – Robert Harvey Dec 3 '15 at 20:38
  • 1
    @TopinFrassi: Well then I think that's pretty much your answer :P – Lightness Races in Orbit Dec 3 '15 at 20:46
4

Your coworker have a strange logic. A dictionary might not have a performance-benefit if the number of items is small, but that does not mean that there is any benefit to using a list instead!

If the number of operations is small then the performance difference is probably unimportant either way, so you should choose the data structure which is simplest to work with for the task at hand. If you want to store users by id, a dictionary seem like the natural choice.

3

In this case, a dictionary is more appropriate but there are really two considerations here:

  1. How do you identify the data?

  2. How do you add or remove the data?

A list accesses by index. This is simply the ordering of the elements in the data structure. A dictionary or hash table adds another layer by using a key, and its hash is the index into the underlying array.

In your case you need a structure where you can use user IDs to access the data. What would you rather do?

This:

dictionary.get(userId);

Or this:

for (User u : users) {
  if (userId == u.userId) {
    return u;
  }
}

It makes more sense to get a user by ID rather than searching the whole list (it is O(n)) for it.

The other consideration is how you add or remove data. This goes back to the whole "array list v linked list" discussion that is taught in any undergraduate CS program so I will omit that here. The other detail to keep in mind is that it is appropriate for dictionaries, too: you can implement them with an array (hash table) or a tree. Each has benefits and drawbacks and is more efficient at different types of mutations and accesses.


Note that at no time does "how much data will there be" enter into the equation. Typically, the above concerns drive the data structure selection, not the quantity of data. The only time this should be an issue is if there is so much data it cannot all fit into memory at once.

  • 1
    So the concern for the right data structure should always be present if I understood correctly? – IEatBagels Dec 3 '15 at 20:26
  • @TopinFrassi: Definitely. – Lightness Races in Orbit Dec 3 '15 at 20:27
  • 3
    I would sound a note of caution, however, that if the truly appropriate data structure for the job is substantially more complex to provision/use/maintain than a slightly less appropriate alternative, and the less appropriate alternative has a worse Big-Oh, but your input data is always going to remain small, it's still worth considering the less appropriate alternative. It's not true to say that size never factors into it. However, this is a whole new level of discussion that should be applied only after the basic wisdom and only when you really know what you're doing and why. – Lightness Races in Orbit Dec 3 '15 at 20:28
  • @LightnessRacesinOrbit Thanks that's a very valuable comment (answer-worthy?). – IEatBagels Dec 3 '15 at 20:36
  • 1
    @TopinFrassi: cba tbh - sounds like Robert's got the makings of a similar one though – Lightness Races in Orbit Dec 3 '15 at 20:46
2

Aside from performance, you should also consider the principle of least surprise for future programmers: if lookup is being done by item rather than by index, but a list is being used, this is a surprising design choice and if I'm reading the code, it leads me to waste time to figure out why it's implemented in this way.

I might think: "Does it need to be ordered somewhere?" "Is it being sorted?" "Was it meant to be ordered but that wasn't implemented yet? Was it supposed to be implemented but the dev forgot to do that?".

In other words it increases the wtf/per minute rate, which is one way to measure quality of code.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.