何时在 LinkedList 或 ArrayList 上使用 HashMap，反之亦然

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.

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,

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.

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.