I need a data structure to store users which should be retrieved by id. I noticed there are several classes that implement the Map interface. Which one should be my default choice? They all seem quite equivalent to me.
Asked
Active
Viewed 2,691 times
6 Answers
10
Probably it depends on how many users you plan to have and if you will need them ordered or just getting single items by id.
HashMap uses hash codes to store things so you have constant time for put and get operations but items are always unordered.
TreeMap instead uses a binary tree so you have log(n) time for basic operations but items are kept ordered in the tree.
I would use HashMap because it's the simpler one (remember to give it a suitable initial capacity). Remember that these datastructures are not synchronized by default, if you plan to use it from more than one thread take care of using ConcurrentHashMap.
A middle approach is the LinkedHashMap that uses same structure as HashMap (hashcode and equals method) but it also keeps a doubly linked list of element inserted in the map (mantaining the order of insertion). This hybrid has ordered items (ordered in sense of insertion order, as suggested by comments.. just to be precise but I had already specified that) without performance losses of TreeMap.
Jack
- 131,802
- 30
- 241
- 343
-
LinkedHashMap will be better than TreeMap for traversing all keys, but will be worse for single lookups; TreeMap gains you *much* faster single lookups in larger data sets. – Dean J Jan 04 '10 at 15:53
-
"This hybrid has ordered items" That depends on what you considered ordered. TreeMap keeps all the elements ordered by an external criteria. LinkedHashMap keeps them ordered by insertion order. – Powerlord Jan 04 '10 at 15:55
-
Actually TreeMap is log(n) for put/get while LinkedHashMap is constant time so I don't think you are right. LinkedHashMap is an HashMap that has also a list.. nothing more, nothing less. The main difference is that TreeMap keeps item ordered by value while LinkedHashMap keeps them ordered by insertion order.. – Jack Jan 04 '10 at 15:56
6
No concurrency: use java.util.HashMap
Concurrency: use java.util.concurrent.ConcurrentHashMap
If you want some control on the order used by iterators, use a TreeMap or a LinkedHashMap.
Jerome
- 8,427
- 2
- 32
- 41
-
1
-
1
-
@Jerome: That depends on if he's going to iterate all the users at some point. TreeMap is the only one that will return them in the correct order. – Powerlord Jan 04 '10 at 15:43
-
2
If they all seem equivalent then you haven't read the documentation. Sun's documentation is pretty much as terse as it gets and provides very important points for making your choices.
Start here.
Kwadz
- 2,206
- 2
- 24
- 45
Mark Bolusmjak
- 23,606
- 10
- 74
- 129
-
1No, but links to the relevant documentation, along with a brief explanation of the use for each case, would work. – Robert Harvey Jan 04 '10 at 15:43
-
Reading it now. I'm sure they're not really "equivalent". I just meant that non seems more appropriate than the other for my purpose. I'm kind of new to java (and to programming) – snakile Jan 04 '10 at 15:48
-
I have added a link to Map's documentation which has links to implementations. The briefest explanations are already given by Sun. Without further details this is the best anyone can do. "Brief explanations" will omit points that are possibly important. – Mark Bolusmjak Jan 04 '10 at 15:49
-
1@john, all other things being equal, you would use the lightest-weight structure possible that is consistent with your objectives. – Robert Harvey Jan 04 '10 at 15:50
1
Your choice could be modified by how you intend to use the data structure, and where you would rather have performance - reads, or writes?
In a user-login system, my guess is that you'll be doing more reads than writes.
Timothy
- 2,457
- 19
- 15
0
(I know I already answered this once, but I feel this needs saying)
Have you considered using a database to store this information? Even if it's SQLite, it'd probably be easier than storing your user database in the program code or loading the entire dataset into memory each time.
-
I didn't consider using a database because I'm a college student who is new to programming and knows nothing about databases for now. But thanks. – snakile Jan 04 '10 at 16:03