95

What is the reason why we cannot always use a HashMap, even though it is much more efficient than ArrayList or LinkedList in add,remove operations, also irrespective of the number of the elements.

I googled it and found some reasons, but there was always a workaround for using HashMap, with advantages still alive.

  • 11
    `Lists` and `Maps` are two *completely* different data structures, with different operations and invariants. Can you explain the context/requirements you're thinking of where both would be acceptable solutions? – Mark Peters Nov 02 '11 at 04:26
  • 3
    Apparently you've never needed to keep a set of things *in a particular order* ... – Brian Roach Nov 02 '11 at 04:31
  • 59
    Downvote, why? I think this is a proper question. Shows lack of knowlegde though, but on SO question should not be downvoted for showing lack of knowledge. In fact a question is always a result of lack of knowledge. –  Nov 02 '11 at 04:56

4 Answers4

102

Lists represent a sequential ordering of elements. Maps are used to represent a collection of key / value pairs.

While you could use a map as a list, there are some definite downsides of doing so.

Maintaining order:

  • A list by definition is ordered. You add items and then you are able to iterate back through the list in the order that you inserted the items. When you add items to a HashMap, you are not guaranteed to retrieve the items in the same order you put them in. There are subclasses of HashMap like LinkedHashMap that will maintain the order, but in general order is not guaranteed with a Map.

Key/Value semantics:

  • The purpose of a map is to store items based on a key that can be used to retrieve the item at a later point. Similar functionality can only be achieved with a list in the limited case where the key happens to be the position in the list.

Code readability Consider the following examples.

    // Adding to a List
    list.add(myObject);         // adds to the end of the list
    map.put(myKey, myObject);   // sure, you can do this, but what is myKey?
    map.put("1", myObject);     // you could use the position as a key but why?

    // Iterating through the items
    for (Object o : myList)           // nice and easy
    for (Object o : myMap.values())   // more code and the order is not guaranteed

Collection functionality Some great utility functions are available for lists via the Collections class. For example ...

    // Randomize the list
    Collections.shuffle(myList);

    // Sort the list
    Collections.sort(myList, myComparator);
starball
  • 20,030
  • 7
  • 43
  • 238
polster
  • 1,353
  • 1
  • 8
  • 6
  • LinkedLists are often said to be bad because of performance issues. I frequently use LinkedLists over ArrayLists because of element ordering. Would it be better (for performance and memory) if I used HashMaps with positions as keys? – Cesar Castro Oct 18 '13 at 19:05
34

Lists and Maps are different data structures. Maps are used for when you want to associate a key with a value and Lists are an ordered collection.

Map is an interface in the Java Collection Framework and a HashMap is one implementation of the Map interface. HashMap are efficient for locating a value based on a key and inserting and deleting values based on a key. The entries of a HashMap are not ordered.

ArrayList and LinkedList are an implementation of the List interface. LinkedList provides sequential access and is generally more efficient at inserting and deleting elements in the list, however, it is it less efficient at accessing elements in a list. ArrayList provides random access and is more efficient at accessing elements but is generally slower at inserting and deleting elements.

jazzdawg
  • 564
  • 5
  • 10
2

I will put here some real case examples and scenarios when to use one or another, it might be of help for somebody else:

HashMap

When you have to use cache in your application. Redis and membase are some type of extended HashMap. (Doesn't matter the order of the elements, you need quick ( O(1) ) read access (a value), using a key).

LinkedList

When the order is important (they are ordered as they were added to the LinkedList), the number of elements are unknown (don't waste memory allocation) and you require quick insertion time ( O(1) ). A list of to-do items that can be listed sequentially as they are added is a good example.

vhbazan
  • 1,240
  • 1
  • 17
  • 26
1

The downfall of ArrayList and LinkedList is that when iterating through them, depending on the search algorithm, the time it takes to find an item grows with the size of the list.

The beauty of hashing is that although you sacrifice some extra time searching for the element, the time taken does not grow with the size of the map. This is because the HashMap finds information by converting the element you are searching for, directly into the index, so it can make the jump.

Long story short... LinkedList: Consumes a little more memory than ArrayList, low cost for insertions(add & remove) ArrayList: Consumes low memory, but similar to LinkedList, and takes extra time to search when large. HashMap: Can perform a jump to the value, making the search time constant for large maps. Consumes more memory and takes longer to find the value than small lists.

Simon Walker
  • 56
  • 5