The Java Collection API provides some column classes and interfaces to help us store and manage object collections. In fact, collections in Java work like an array, but the size of the collection can be changed dynamically, and collections also provide more advanced functions. With the JavaCollection API, we don’t need to write collection classes ourselves. Most Java collection classes are located in java.util package, and some concurrency-related collection classes are located in the java.util.concurrent package. Here are some of the collection classes provided by the Java API.
1. Overview of Java Collections
There are two categories of collections in Java, namely:
1. Collection
2. Map
The collection of the Collection class can be understood as mainly storing single objects, while the collection of the Map class mainly stores key-value objects. These two categories can be taken for granted to correspond to two interfaces, namely Collection接口and Map接口. The following picture lists the inheritance tree of these two interfaces:
From the above picture, we can see that the Collection interface has derived three branches, namely:
1. List
2. Set
3. Queue
Map is relatively simple, with only one branch. Below we will introduce each implementation class of Java Collection in detail.
Note: To distinguish Collection and Collections, Collections is an interface to the collection, and Collections is a tool class, which provides some static methods to facilitate us to operate collection instances, both of which are located in the java.util package.
2. First introduce from the Collection interface
The following figure is a screenshot of the source code of the Collection interface. From the abstract methods in the interface, we can see that it defines a common method for a general collection:
- Add and delete an element
- Determine whether the element exists
- Get the size of the collection
- Iterate over a collection
2.1 Collection's List interface
The List interface inherits from the Collection interface. Its characteristic is that the objects in it are ordered and each object has a unique index. We can search for an element through this index, and the objects in the List are allowed to be repeated, which is similar to an array. For List interface, the Java API provides the following implementation:
- java.util.ArrayList
- java.util.LinkedList
- java.util.Vector
- java.util.Stack
Of course, there are some implementations in the java.util.concurrent package, which will be described in detail in another article.
ArrayList is the most commonly used collection, and its internal implementation is an array , and the size of ArrayList can be dynamically expanded. The random access efficiency for elements is high, and the time complexity of access is O(1) . The operation efficiency from the tail is high, and the time complexity is O(1) just like random access. If it is operated from the head, the efficiency will be relatively low, because when inserting or deleting from the head, all the following elements need to be moved, and the time complexity is O(ni) (n represents the number of elements, and i represents the position of the element).
LinkList: As can be seen from the above figure, it not only inherits the List interface, but also inherits the Deque interface (it will be introduced later). LinkList is a data structure based on a linked list, and each node saves pointers to the previous and next nodes. LinkList is relatively inefficient for random access because it requires indexing from scratch, so its time complexity is O(i) . However, for the addition and deletion of elements, LinkList is efficient because only the front and back pointers need to be modified, and its time complexity is O(1) .
Vector: From the screenshots of the Vector and ArrayList source code, they inherit the interfaces exactly the same. Therefore, Vector can be regarded as a thread-safe ArrayList, which is also implemented based on arrays , but almost all collection operations are added with the synchronized keyword.
Stack: The above is a screenshot of the Stack class source code. We see that the Stack class actually inherits from Vector. Stack just adds several methods based on Vector to provide the characteristics of the stack (Last In First Out LIFO). Stack's feature is that when added, new elements will be added to the top, and when removed, the top elements will be removed first. This data structure is mainly used as some special data processing processes, such as language compilation, XML parsing, etc.
2.2 Collection Set interface
Set and List interface are also inherited from the Collection interface, and are also an implementation of collections. The biggest difference between them is that objects in Set are not allowed to be repeated . For Set interfaces, the Java API provides the following implementation:
- java.util.EnumSet
- java.util.HashSet
- java.util.LinkedHashSet
- java.util.TreeSet
The functions of these classes are slightly different, and the differences are mainly reflected in the order of the iteration of objects and the efficiency of insertion and search.
The implementation of HashSet is very simple, and it is an HashMap inside, but it does not guarantee the order of elements.
The implementation of LinkedHashSet is also very simple, and it uses a LinkedHashMap internally. Because LinkedHashMap maintains a bidirectional linked list internally to maintain order, the characteristic of LinkedHashSet is that the elements in it are ordered, and the order of element iteration is the order of their insertion. The reinsertion of elements will not affect the order of the original elements.
TreeSet: From the inheritance relationship in the figure above, you must first understand NavigableSet TreeSet SortedSet interfaces.
SortedSet Interface
public interface SortedSet<E> extends Set<E> { Comparator<? super E> comparator(); SortedSet<E> subSet(E fromElement, E toElement); SortedSet<E> headSet(E toElement); SortedSet<E> tailSet(E fromElement); E first(); } From the above interface definition, the SortedSet interface is a subinterface of the Set. In addition to the general Set characteristics, its elements are ordered internally. The order of internal elements depends on the ordering rules of the elements, that is, the order of elements depends on the implementation of the element's comparable interface or a comparator comparator . For the difference between comparable and comparator, please refer to: https://www.VeVB.COM/article/93973.htm
NavigableSet interface
public interface NavigableSet<E> extends SortedSet<E> { NavigableSet<E> descendingSet(); Iterator<E> descendingIterator(); SortedSet<E> headSet(E toElement); SortedSet<E> tailSet(E fromElement); SortedSet<E> subSet(E fromElement, E toElement); ceiling(), floor(), higher(), and lower() ...}From the NavigableSet interface definition, it is a subinterface of SortedSet and provides some navigation methods. As for the meaning of these navigation methods, you can check Java Doc.
Therefore, the characteristic of TreeSet is that its internal elements are ordered and there are many navigation methods to implement. From the first part of the Java collection class overview, we know that Set has a sub-interface SortedSet , and SortedSet has a sub-interface NavigableSet interface. The Java API only implements SortedSet and NavigableSet interfaces, which is TreeSet .
2.3 Collection's Queue interface
The Queue interface inherits from the Collection interface, which also represents an ordered queue. However, the biggest feature of this queue is that the newly inserted element is located at the tail of the queue and the removed object is located at the head of the queue, which is similar to the queue that checks out in the supermarket.
We already know from the Java collection overview in Section 1 that the Queue interface also has a sub-interface Deque. Let's take a look at the definition of these two interfaces by the Java API:
Queue interface:
public interface Queue<E> extends Collection<E> { boolean add(E e); boolean offer(E e); E remove(); E poll(); E peek();}Deque interface:
public interface Deque<E> extends Queue<E> { void addFirst(E e); void addLast(E e); E removeFirst(); E removeFirst();}From the definitions of these two interfaces, I think everyone has seen some clues. The Queue interface defines the operation method of a general queue, while Deque is a double-ended queue .
For Queue interfaces, the Java API provides two implementations:
- java.util.LinkedList (also implements the Deque interface)
- java.util.PriorityQueue
LinkedList: The previous List chapter has mentioned that it is a standard queue.
PriorityQueue: The order in the queue is similar to TreeSet, depending on the ordering rules of the elements, that is, the implementation of the elements to the comparable interface or a comparator comparator.
For the Deque interface, there is another implementation besides the LinkList class:
- java.util.ArrayDeque
ArrayDeque: As can be seen from the name, its internal implementation is an array.
3. Java collection map
From the first part of the Java collection class overview, we know that Map does not inherit from the Collection interface, but is located in a parallel position with the Collection interface. Therefore, the behavior of Map is very different from the behavior of Collection introduced above. The main feature of Map is that the elements it stores are key-value pairs. Let's take a look at the definition of the Map interface:
public interface Map<K,V> { V put(K key, V value); boolean containsKey(Object key); Set<Map.Entry<K, V>> entrySet(); int hashCode(); V get(Object key); Set<K> keySet(); ... }For Map interfaces, the Java API provides the following implementations:
- java.util.HashMap
- java.util.Hashtable
- java.util.EnumMap
- java.util.IdentityHashMap
- java.util.LinkedHashMap
- java.util.Properties
- java.util.TreeMap
- java.util.WeakHashMap
Among them, the most commonly used are HashMap and TreeMap.
The key and value in HashMap are both disordered. The internal implementation of HashMap is worth studying. For details, please refer to the internal implementation of HashMap
HashTable can be regarded as a heavyweight implementation of HashMap. Most of the methods are added with the synchronized keyword, which is thread-safe. Another difference between HashTable and HashMap is that both HashMap's key-value are allowed to be null, while HashTable不.
LinkedHashMap is also a HashMap, but a two-way linked list is maintained internally to maintain order. LinkedHashSet internal implementation is used to use LinkedHashMap.
The key and value in TreeMap can not only maintain order, but are similar to TreeSet and PriorityQueue . The iterative order of key and value in TreeMap depends on their respective sorting rules.
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.