Java Collections Implementations (Classes) - RichardDanielOliva/java-learning-wiki GitHub Wiki

Java Collections framework comes with many implementation classes for the interfaces. Most common implementations are ArrayList, HashMap and HashSet. Java 1.5 included Concurrent implementations; for example ConcurrentHashMap and CopyOnWriteArrayList. Usually Collection classes are not thread-safe and their iterator is fail-fast. In this section, we will learn about commonly used collection classes.

The Java Collections Framework provides several general-purpose implementations of the core interfaces:

  • For the Set interface, HashSet is the most commonly used implementation.
  • For the List interface, ArrayList is the most commonly used implementation.
  • For the Map interface, HashMap is the most commonly used implementation.
  • For the Queue interface, LinkedList is the most commonly used implementation.
  • For the Deque interface, ArrayDeque is the most commonly used implementation.

Each of the general-purpose implementations provides all optional operations contained in its interface.

Set Implementations

The Set interface defines a collection that cannot contain duplicate elements. This interface contains only the methods inherited from Collection by adding the restriction that duplicate elements are prohibited. It is important to point out that, in order to check whether elements are duplicate elements or not, it is necessary that these elements have correctly implemented the equals and hashCode methods. To check if two Set are equal, it will be checked if all the elements that compose them are equal no matter in the order that these elements occupy.

Within the Set interface there are several types of implementations made within the Java platform. We are going to analyze each one of them:

  • HashSet: this implementation stores the elements in a hash table. It is the implementation with the best performance of all but does not guarantee any order at the time of performing iterations. It is the most used implementation due to its performance and because, generally, we don't care about the order that the elements occupy. This implementation provides constant times in basic operations as long as the hash function correctly disperses the elements within the hash table. It is important to define the initial size of the table as this size will mark the performance of this implementation.
  • TreeSet: this implementation stores the elements sorted according to their values. It is much slower than HashSet. The stored elements must implement the Comparable interface. This implementation guarantees, always, a log(N) performance in the basic operations, due to the tree structure used to store the elements.
  • LinkedHashSet: this implementation stores the elements according to the insertion order. It is simply a little more expensive than HashSet.

List Implementations

The List interface defines a succession of elements. Unlike the Set interface, the List interface does support duplicate elements. In addition to the methods inherited from Collection, it adds methods that allow the following points to be improved:

Positional access to elements: manipulates elements according to their position in the list.

  • Item search: searches for a specific item in the list and returns its position.

  • Iteration on elements: improves the default Iterator.

  • Operation range: allows you to perform certain operations on ragos of elements within the list itself.

  • Within the List interface there are several types of implementations carried out within the Java platform. We are going to analyze each one of them:

  • ArrayList: this is the typical implementation. It is based on a resizable array that increases in size as the collection of elements grows. It is the one with the best performance over most situations.

  • LinkedList: this implementation allows you to improve performance on certain occasions. This implementation is based on a double-linked list of elements, with each element having a pointer to the previous and next element.

Map Implementations

The Map interface associates keys with values. This interface cannot contain duplicate keys and each of these keys can only have a maximum value associated with it.

Within the Map interface there are several types of implementations carried out within the Java platform. Let's analyze each of them:

  • HashMap: this implementation stores the keys in a hash table. It is the implementation with the best performance of all but does not guarantee any order at the time of performing iterations. This implementation provides constant times in basic operations as long as the hash function correctly disperses the elements within the hash table. It is important to define the initial size of the table as this size will mark the performance of this implementation.
  • TreeMap: this implementation stores the keys sorted according to their values. It is much slower than HashMap. The stored keys must implement the Comparable interface. This implementation guarantees, always, a log(N) performance in the basic operations, due to the tree structure used to store the elements.
  • LinkedHashMap: this implementation stores the keys according to the insertion order. It is simply a little more expensive than HashMap.

References

https://www.journaldev.com/1260/collections-in-java-tutorial https://docs.oracle.com/javase/tutorial/collections/implementations/index.html https://www.arquitecturajava.com/java-collections-list-vs-set/ https://www.adictosaltrabajo.com/2015/09/25/introduccion-a-colecciones-en-java/