Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

People also ask

When should a HashMap be used instead of an ArrayList?

Memory Consumption ArrayList stores the elements only as values and maintains internally the indexing for every element. While HashMap stores elements with key and value pairs that means two objects. So HashMap takes more memory comparatively.

When would you use a HashMap?

Using HashMap makes sense only when unique keys are available for the data we want to store. We should use it when searching for items based on a key and quick access time is an important requirement. We should avoid using HashMap when it is important to maintain the same order of items in a collection.

When would you choose to use ArrayList over LinkedList?

LinkedList should be used where modifications to a collection are frequent like addition/deletion operations. LinkedList is much faster as compare to ArrayList in such cases. In case of read-only collections or collections which are rarely modified, ArrayList is suitable.

Why does HashMap use LinkedList inside it instead of ArrayList?

because it means that the normal trade-off between LinkedList and ArrayList does not apply. The normal trade-off is: ArrayList uses less space, but insertion and removal of a selected element is O(N) in the worst case. LinkedList uses more space, but insertion and removal of a selected element1 is O(1) .


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);  

Hope this helps,


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.


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.


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.