YouTipJava Collections
Before Java 2, Java provided ad-hoc classes such as: Dictionary, Vector, Stack, and Properties to store and manipulate groups of objects.
Although these classes are all very useful, they lack a central, unified theme. Because of this, the way you use Vector is quite different from how you use Properties.
The Collections Framework was designed to meet several goals.
* The framework must be high-performance. The implementations for the fundamental collections (dynamic arrays, linked lists, trees, and hash tables) must also be efficient.
* The framework must allow different types of collections to work in a similar fashion and with high interoperability.
* The framework must be easy to extend and/or adapt.
To achieve these goals, the entire collections framework is designed around a set of standard interfaces. You can use the standard implementations of these interfaces, such as: **LinkedList**, **HashSet**, and **TreeSet**, etc., or you can implement your own collections through these interfaces.
!(#)
As you can see from the above collections framework diagram, the Java collections framework primarily consists of two types of containers: one is a Collection, which stores a collection of elements, and the other is a Map, which stores key/value pair mappings. The Collection interface has 3 subtypes: List, Set, and Queue, which are followed by some abstract classes, and finally the concrete implementation classes. Common ones include (#), (#), (#), LinkedHashSet, (#), LinkedHashMap, etc.
The collections framework is a unified architecture for representing and manipulating collections. All collections frameworks contain the following:
* **Interfaces:** These are abstract data types that represent collections. For example, Collection, List, Set, and Map. The reason for having multiple interfaces is to represent different types of collections that can be manipulated in different ways.
* **Implementations (Classes):** These are the concrete implementations of the collection interfaces. In essence, they are reusable data structures, such as: ArrayList, LinkedList, HashSet, and HashMap.
* **Algorithms:** These are methods that perform useful computations on objects that implement the collection interfaces, such as searching and sorting. These algorithms are polymorphic because the same method can work on different implementations of the appropriate interface.
In addition to the collections, the framework also defines several Map interfaces and classes. Maps store key/value pairs. Although Maps are not collections, they are fully integrated into the collections framework.
### The Collections Framework Hierarchy is shown in the figure below
!(#)
The Java Collections Framework provides a set of high-performance, convenient interfaces and classes. The Java collections framework is located in the java.util package, so you need to import the package when using the collections framework.
* * *
## Collection Interfaces
The collections framework defines several interfaces. This section provides an overview of each interface:
| No. | Interface Description |
| --- | --- |
| 1 | **Collection Interface** Collection is the most basic collection interface. A Collection represents a group of Objects, its elements. Java does not provide direct implementations of the Collection interface, but provides implementations of its sub-interfaces (like List and Set). The Collection interface stores a group of unique, unordered objects. |
| 2 | **List Interface** List is an ordered Collection. It allows precise control over where each element is inserted. You can access elements in a List by their index (the element's position in the List, similar to an array's index). The index of the first element is 0, and duplicate elements are allowed. The List interface stores a group of unique, ordered (insertion order) objects. |
| 3 | **Set** Set has an interface identical to Collection, but with different behavior. Set does not store duplicate elements. The Set interface stores a group of unique, unordered objects. |
| 4 | **SortedSet** Extends Set to maintain elements in a sorted order. |
| 5 | **Map** Map stores a group of key-value objects, providing a mapping from a key (index) to a value. |
| 6 | **Map.Entry** Describes an element (a key/value pair) within a Map. It is an inner interface of Map. |
| 7 | **SortedMap** Extends Map so that the keys are maintained in ascending order. |
| 8 | **Enumeration** This is a legacy interface and method defined by it, which allows you to enumerate (get one at a time) the elements of an object collection. This legacy interface has been replaced by Iterator. |
### Differences between Set and List
* 1. Set interface instances store unordered, non-duplicate data. List interface instances store ordered, duplicate elements.
* 2. Set has low retrieval efficiency but high deletion and insertion efficiency. Insertion and deletion do not cause changes in element positions. ****.
* 3. List is similar to an array; it can grow dynamically, automatically increasing its length based on the actual data stored. It has high search efficiency but low insertion and deletion efficiency, as these operations cause changes in the positions of other elements. ****.
* * *
## Collection Implementation Classes (Collection Classes)
Java provides a set of standard collection classes that implement the Collection interface. Some are concrete classes that can be used directly, while others are abstract classes that provide partial implementations of the interfaces.
The standard collection classes are summarized in the following table:
| No. | Class Description |
| --- | --- |
| 1 | **AbstractCollection** Implements most of the Collection interface. |
| 2 | **AbstractList** Extends AbstractCollection and implements most of the List interface. |
| 3 | **AbstractSequentialList** Extends AbstractList, providing sequential access to its elements rather than random access. |
| 4 | (#) This class implements the List interface, allowing null elements. It is primarily used to create linked list data structures. This class is not synchronized. If multiple threads access a List concurrently, you must implement your own synchronization. The solution is to construct a synchronized List when creating it. For example: `List list=Collections.synchronizedList(new LinkedList(...));` LinkedList has low search efficiency. |
| 5 | (#) This class also implements the List interface, implementing a resizable array. It provides better performance for random access and iteration. This class is also not synchronized and should not be used in multi-threaded environments. ArrayList grows by 50% of its current length and has low insertion and deletion efficiency. |
| 6 | **AbstractSet** Extends AbstractCollection and implements most of the Set interface. |
| 7 | (#) This class implements the Set interface, backed by a hash table. It does not allow duplicate elements, does not guarantee the order of elements, and allows one null element. |
| 8 | **LinkedHashSet** A hash table and linked list implementation of the Set interface, with predictable iteration order. |
| 9 | **TreeSet** This class implements the Set interface and can perform operations like sorting. |
| 10 | **AbstractMap** Implements most of the Map interface. |
| 11 | (#) HashMap is a hash table that stores key-value mappings. This class implements the Map interface, stores data based on the key's HashCode, and provides fast access. It allows at most one null key and does not support synchronization. |
| 12 | **TreeMap** Extends AbstractMap and uses a tree structure. |
| 13 | **WeakHashMap** Extends AbstractMap, using a hash table with weak keys. |
| 14 | **LinkedHashMap** Extends HashMap, maintaining a doubly-linked list across all entries. |
| 15 | **IdentityHashMap** Extends AbstractMap, using reference-equality when comparing keys. |
The classes defined in the java.util package have been discussed in previous tutorials, as shown below:
| No. | Class Description |
| --- | --- |
| 1 | **Vector** This class is very similar to ArrayList, but it is synchronized and can be used in multi-threaded environments. It allows setting a default growth increment, and the default expansion is 2 times the original size. |
| 2 | **Stack** Stack is a subclass of Vector and implements a standard last-in-first-out (LIFO) stack. |
| 3 | **Dictionary** Dictionary is an abstract class used to store key/value pairs, similar in function to the Map class. |
| 4 | **Hashtable** Hashtable is a subclass of the Dictionary class, located in the java.util package. |
| 5 | **Properties** Properties extends Hashtable, representing a persistent set of properties. Each key and its corresponding value in the property list is a String. |
| 6 | **BitSet** A BitSet class creates a special type of array to hold bit values. The BitSet array size grows as needed. |
* * *
## Collection Algorithms
The collections framework defines several algorithms that can be applied to collections and maps. These algorithms are defined as static methods in the collections classes.
Some methods may throw a ClassCastException when attempting to compare incompatible types. They may throw an UnsupportedOperationException when attempting to modify an unmodifiable collection.
The collections framework defines three static variables: EMPTY_SET, EMPTY_LIST, and EMPTY_MAP. These variables are all unmodifiable.
| No. | Algorithm Description |
| --- | --- |
| 1 | (#) Here is a list of all algorithm implementations. |
* * *
## How to Use Iterators
Generally, you will want to iterate over the elements in a collection. For example, displaying each element in a collection.
Typically, arrays are traversed using a for loop or an enhanced for loop. These two methods can also be used with the collections framework. However, there is another method: using an iterator to traverse the collections framework. An iterator is an object that implements the (#) interface or the ListIterator interface.
An iterator allows you to loop through and obtain or remove elements from a collection. ListIterator extends Iterator to allow bidirectional traversal of a list and modification of elements.
| No. | Iterator Method Description |
| --- | --- |
| 1 | (#) Here, through examples, all methods provided by the Iterator and ListIterator interfaces are listed. |
### Traversing an ArrayList
## Example
```java
import java.util.*;
public class Test{
public static void main(String[]args){
Listlist=new ArrayList();
list.add("Hello");
list.add("World");
list.add("HAHAHAHA");
for(String str : list){
System.out.println(str);
}
String[]strArray=new String[list.size()];
list.toArray(strArray);
for(int i=0;i<strArray.length;i++){
System.out.println(strArray);
}
Iteratorite=list.iterator();
while(ite.hasNext()){
System.out.println(ite.next());
}
}
}
**Analysis:**
All three methods are used to traverse an ArrayList collection. The third method uses an iterator, which eliminates the worry of exceeding the collection's length during traversal.
### Traversing a Map
## Example
```java
import java.util.*;
public class Test{
public static void main(String[]args){
Mapmap = new HashMap();
map.put("1", "value1");
map.put("2", "value2");
map.put("3", "value3");
System.out.println("Via Map.keySetIterate over keyandvalue:");
for(String key : map.keySet()){
System.out.println("key= "+ key + " and value= " + map.get(key));
}
System.out.println("Via Map.entrySetUseiteratorIterate over keyandvalue:");
Iterator<Map.Entry>it = map.entrySet().iterator();
while(it.hasNext()){
Map.Entryentry = it.next();
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
System.out.println("Via Map.entrySetIterate over keyandvalue");
for(Map.Entryentry : map.entrySet()){
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
System.out.println("Via Map.values()Iterate over all values, but cannot iterate over keys");
for(String v : map.values()){
System.out.println("value= " + v);
}
}
}
* * *
## How to Use Comparators
TreeSet and TreeMap store elements in sorted order. However, the exact sorting order is precisely defined by a Comparator.
This interface allows us to sort a collection in different ways.
| No. | Comparator Method Description |
| --- | --- |
| 1 | (#) Here, through examples, all methods provided by the Comparator interface are listed. |
* * *
## Summary
The Java Collections Framework provides programmers with pre-wrapped data structures and algorithms to manipulate them.
A collection is an object that can hold references to other objects. The collection interfaces declare the operations that can be performed on each type of collection.
The classes and interfaces of the collections framework are in the java.util package.
When any object is added to a collection, it is automatically converted to the Object type. Therefore, when retrieving it, a type cast is necessary.