Time for another showdown. This time, it's the Java Map Interface vs the List Interface. In what cases are Maps faster than Lists?
Accessing complexity
Actually, if you don't want to entirely read this article, you should know that in
almost all cases accessing a list is faster.
When you're accessing a hashmap, you'll first create a hash representation of your key, get to the right "bucket" and then get the value from an implemented list, whereas accessing a value from an ArrayList will merely fetch the value from the list.
After this fact, you might not want to use Maps, but don't worry, there's more..
Two Entirely Different Datastructures
You should never forget that both Map and List are two entirely different datastructures, each with its own advantages.
For example, the keys for a Map aren't linear. Anything can be the key, which becomes very handy when dealing with Strings as keys.
Remember this:
If you need a List, use a list. If you need a Map, use a Map. If at any time you can pick one of both data structures - for example when dealing with consecutive Integers as keys - you're probably better off picking the ArrayList implementation.
But there's more
Remember ArrayList isn't the only List implementation! Choosing the right interface is a first step to choosing the right datastructure, but sometimes a lot of performance can be gained by using another implementation of the chosen interface.
If you frequently add elements to the beginning of a List or iterate over the List to delete elements from its interior, you should consider using LinkedList.
Lists: ArrayLists, LinkedList, Vector (synchronised list)
Maps: HashMap, TreeMap, LinkedHashMap
Finally, there's also a Set interface, used when you don't need access by key, and want to use methods like "contains()"
Sets: HashSet, TreeSet, LinkedHashSet
Comments
If you'd like to add something to this, or you want to correct me on something, feel free to leave a comment below or on my twitterpage!
@Qkyrie and David