The Java collections framework consists of the classes and interfaces that implement a collection data structure. Collections are similar to arrays in that respect as they can hold references to objects and can be managed as a group. The difference is that arrays require their capacity being defined before they can be used, while collections can increase and decrease their size automatically as needed. One just adds or removes an object reference to a collection, and the collection changes its size accordingly. Another difference is that the collections cannot have their elements to be primitive types such as short, int, or double. If you need to store such type values, the elements must be of a corresponding wrapper type such as Short, Integer, or Double, for example.
Java collections support various algorithms of storing and accessing the elements of a collection: an ordered list, a unique set, a dictionary called a map in Java, a stack, a queue, and some others. All the classes and interfaces of Java collections framework belong to the java.util package of Java Class Library. The java.util package contains the following:
- The interfaces that extend the Collection interface: List, Set, Queue to name the most popular ones
- The classes that implement the previously listed interfaces: ArrayList, HashSet, Stack, LinkedList, and some other
- The Map interface and its sub-interfaces: ConcurrentMap, SortedMap, to a name a couple
- The classes that implement the Map-related interfaces: HashMap, HashTable, TreeMap, to name the three most frequently used
To review all the classes and interfaces of java.util package would require a dedicated book. So, in this section, we will just have a brief overview of the three main interfaces: List, Set, and Map—and one implementation class for each of them—ArrayList, HashSet, and HashMap. We start with methods that are shared by List and Set interfaces. The principal difference between List and Set is that Set does not allow duplication of the elements. Another difference is that List preserves the order of the elements and also allows them to be sorted.
To identify an element inside a collection, the equals() method is used. To improve performance, the classes that implement Set interface often use the hashCode() method too. It allows to quickly calculate an integer (called hash value or hash code) that is most of the time (but not always) unique for each element. The elements with the same hash value are placed in the same bucket. While establishing whether there is already a certain value in the set, it is enough to check the internal hash table and see whether such a value has already been used. If not, the new element is unique. If yes, then the new element can be compared (using equals() method) with each of the elements with the same hash value. Such a procedure is faster than comparing a new element with each element of the set one by one.
That is why we often see that the name of the classes has "Hash" prefix, indicating that the class uses the hash value, so the element must implement the hashCode() method. While doing this, you must make sure that it is implemented so that every time equals() method returns true for two objects, the hash values of these two objects returned by the hashCode() method are equal too. Otherwise, all the just described algorithm of using the hash value will not work.
And finally, before talking about the java.util interfaces, a few words about generics.