0

Possible Duplicate:
When to use HashMap over LinkedList or ArrayList and vice-versa

Since coming across Maps in Java i have been using them extensively. In particular HashMap is an excellent option for many scenarios. It seems that it trumps an ArrayList in every category - some say that iteration isn't predictable but for that we have the LinkedHashMap.

So, my question is: why not use a HashMap all the time provided we have a solid immutable key?

Additionally, is it appropriate to use a something like a HashMap for a very small (<10) number of items or is there some additional overhead I am not considering?

Community
  • 1
  • 1
Luke De Feo
  • 2,025
  • 3
  • 22
  • 40

3 Answers3

1

Use an ArrayList when your keys are sequential integers. (If they aren't based at 0, just use an offset.) It's much more efficient for access (particularly random access) and update. Otherwise, sure, HashMap (or, as you say, LinkedHashMap) are extremely useful data structures.

I believe that the default initial size for a HashMap is 16 buckets, so there's a bit of overhead for very small lists. But unless you're creating a lot of maps, it shouldn't be a factor in your coding.

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521
  • The problem with using an array list and the position as the key, is if i remove an element the other elements will replace the slot i removed completely ruining my key-value system – Luke De Feo Nov 05 '12 at 10:05
  • @Luke1111 - That's why I said _sequential_ integers. Inserts and deletes (except when restricted to the end of the array) are generally slower with array lists (O(n) instead of O(1)). Alternatively, instead of moving elements around when you delete, you can have gaps with `null` entries in the array list. – Ted Hopp Nov 05 '12 at 19:02
1

HashMap has a significant amount of overhead compared to an array (or ArrayList):

  • You need to hash the key to get an index into the backing array, then store the value and the key. This is slower and uses more memory than an array. This is more important when your key is something large or complicated, since it will take longer to hash or take more space.
  • You also need to hash the key every time you look up a value.
  • When you resize an ArrayList, you just create a new array and copy everything. When you resize a HashMap, you create a new array, then calculate the hashes all over again (so they'll be spread out through the new array).
  • HashMap's perform badly when they're full, so they generally leave something like 25% of their space empty.

These are all pretty minor, so you could get away with just using HashMaps all the time (in fact, this is what PHP seems to do), but it's wasteful to use a HashMap when you don't really need it.

A comparison might be helpful: Anything you can do with an integer, you can also do with a string, so why do we have integers? Because they're smaller and faster to work with (and provide some nice guarantees, like that they always contain a number).

Brendan Long
  • 53,280
  • 21
  • 146
  • 188
1

I use Maps all the time - it is one of the most powerful and versatile data structures. I mostly use LinkedHashMap but, when working with Strings as key I use TreeMap because of the additional benefit of having the keys sorted.

However:

  • if your key is an int and you plan to use all the keys 0..n,use an array (remember - int is more efficient than Integer). But a map is better if you have "sparse values"
  • if you need a list of unindexed items, use a linkedlist
  • if you need to store unique elements, use a set (why waste space to keep the values if you just need the keys)!

Remember - Java gives you very powerful collections (Set, Map,List) and, for each one, multiple implementations with different features - they are there for a reason.

Every data structure has its use, even if many can be implemented using a map as a backend, the most appropriate data structure is... more appropriate (and, usually, more efficient, with less overhead and providing more functionalities)

The size does not matter - 5 or 500 elements, if it looks like a map, use a map (there maybe few exceptions and corner cases where you need maximum efficiency and hard coded values are better). But if it looks like a set - use a set!

thedayofcondor
  • 3,860
  • 1
  • 19
  • 28