1. Collections in Java
Collection classes in Java are the most frequently used and most convenient classes in Java programming. As a container class, the collection class can store any type of data, and of course it can also store specified types in combination with generics (but generics are only valid during the compilation period and will be erased at runtime). What is stored in the collection class is only a reference to the object, not a reference to the object itself. The capacity of the collection class can be dynamically expanded during operation, and also provides many convenient methods, such as finding the union and intersection of the collection.
2. Collection class structure
Collections in Java include multiple data structures, such as linked lists, queues, hash tables, etc. In terms of the inheritance structure of a class, it can be divided into two categories. One is inherited from the Collection interface. This type of collection includes collection classes such as List, Set and Queue. The other class is inherited from the Map interface, which mainly includes collection classes related to hash tables. Let’s take a look at the inheritance structure diagrams of these two categories:
1. List, Set and Queue
The green dotted line in the figure represents implementation, the green solid line represents inheritance between interfaces, and the blue solid line represents inheritance between classes.
(1) List: We use more Lists, including ArrayList and LinkedList. The difference between these two is also very obvious, which can be seen from their names. The underlying ArrayList is implemented through arrays, so its random access speed is relatively fast, but the efficiency is relatively low for cases where frequent additions and deletions are required. For LinkedList, the underlying layer is implemented through linked lists, so the addition and deletion operation is easier to complete, but the efficiency of random access is relatively low.
Let's first look at the insertion efficiency of both:
package com.paddx.test.collection;import java.util.ArrayList;import java.util.LinkedList;public class ListTest {public static void main(String[] args) {for(int i=;i<;i++){}long start = System.currentTimeMillis();LinkedList<Integer> linkedList = new LinkedList<Integer>();for(int i=;i<;i++){linkedList.add(,i);}long end = System.currentTimeMillis();System.out.println(end - start);ArrayList<Integer> arrayList = new ArrayList<Integer>();for(int i=;i<;i++){arrayList.add(,i);}System.out.println(System.currentTimeMillis() - end);}}Here are the results of local execution:
twenty three
1227
It can be seen that in this case, the insertion efficiency of LinkedList is much higher than that of ArrayList, of course this is a relatively extreme situation. Let’s compare the efficiency of random access between the two:
package com.paddx.test.collection;import java.util.ArrayList;import java.util.LinkedList;import java.util.Random;public class ListTest {public static void main(String[] args) {Random random = new Random();for(int i=;i<;i++){}LinkedList<Integer> linkedList = new LinkedList<Integer>();for(int i=;i<;i++){linkedList.add(i);}ArrayList<Integer> arrayList = new ArrayList<Integer>(); for(int i=;i<;i++){arrayList.add(i);} long start = System.currentTimeMillis(); for(int i=;i<;i++){int j = random.nextInt(i+);int k = linkedList.get(j);} long end = System.currentTimeMillis();System.out.println(end - start);for(int i=;i<;i++){int j = random.nextInt(i+);int k = arrayList.get(j);}System.out.println(System.currentTimeMillis() - end);}}Here is the result of my execution:
5277
6
It is obvious that ArrayList's random access efficiency is several orders of magnitude higher than LinkedList. Through these two pieces of code, we should be able to know more clearly the difference between LinkedList and ArrayList and the adaptation scenarios. As for Vector, it is a thread-safe version of ArrayList, while Stack corresponds to the stack data structure. These two are used less frequently, so I won't give an example here.
(2)Queue: Generally, it can be done directly using LinkedList. It can also be seen from the above class diagram that LinkedList inherits from Deque, so LinkedList has the function of a double-ended queue. PriorityQueue is characterized by providing a priority for each element, and elements with high priority will be given priority from the queue.
(3)Set: The main difference between Set and List is that Set does not allow elements to be repeated, while List can allow elements to be repeated. To judge the repetition of elements, we need to decide based on the object's hash method and equals method. This is also why we usually override the hashCode method and equals method for element classes in a collection. Let’s take an example to see the difference between Set and List, as well as the role of the hashcode method and equals method:
package com.paddx.test.collection;import java.util.ArrayList;import java.util.HashSet;import java.util.Set;public class SetTest {public static void main(String[] args) {Person p1 = new Person("lxp",10);Person p2 = new Person("lxp",10);Person p3 = new Person("lxp",20);ArrayList<Person> list = new ArrayList<Person>();list.add(p1);System.out.println("-------------");list.add(p2);System.out.println("----------------");list.add(p3);System.out.println("List size=" + list.size());System.out.println("---------------");Set<Person> set = new HashSet<Person>();set.add(p1);System.out.println("------------");set.add(p2);System.out.println("-------------");set.add(p3);System.out.println("Set size="+set.size());}static class Person{private String name;private int age;public Person(String name, int age) {this.name = name;this.age = age;}@Overridepublic boolean equals(Object o) {System.out.println("Call equals();name="+name);if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;Person person = (Person) o;return name.equals(person.name);}@Overridepublic int hashCode() {System.out.println("Call hashCode(),age="+age);return age;}}} The execution results of the above code are as follows:
------------
------------
List size=3
----Divide line----
Call hashCode(),age=10
------------
Call hashCode(),age=10
Call equals();name=lxp
------------
Call hashCode(),age=20
Set size=2
From the results, no additional operations are performed when the element is added to the List and can be repeated. Before joining Set, you need to execute the hashCode method first. If the returned value already exists in the set, you need to continue to execute the equals method. If the result returned by the equals method is also true, it proves that the element already exists, and the new element will be overwritten by the old element. If the returned hashCode value is different, you will directly add the set. Remember here that for elements in a collection, elements with different hashCode values must be unequal, but for elements with unequal have the hashCode values may be the same.
The difference between HashSet and LinkedHashSet is that the latter can ensure that the order of elements inserted into the set is consistent with the order of output. The difference between TresSet is that its sort is sorted in Comparator, and by default, it is arranged in ascending order in the natural order of characters.
(4) Iterable: From this figure, you can see that the Collection class inherits from Iterable. The function of this interface is to provide element traversal, that is, all collection classes (except Map-related classes) provide element traversal functions. Iterable contains Iterator's iterator, and its source code is as follows. If you are familiar with the iterator mode, it should be easy to understand.
public interface Iterator<E> {boolean hasNext();E next();void remove();}2. Map:
The biggest advantage of Map type collection is that its search efficiency is relatively high, and the time complexity of O(1) can be achieved ideally. The most commonly used Map is HashMap. The difference between LinkedHashMap and HashMap is that the former can ensure that the order of elements inserted into the set is consistent with the output order. The difference between these two and TreeMap is that TreeMap is sorted according to key values. Of course, its underlying implementation also has essential differences. For example, the underlying layer of HashMap is a hash table, while the underlying layer of TreeMap is a tree. Let's now look at the difference between TreeMap and LinkedHashMap:
package com.paddx.test.collection;import java.util.Iterator;import java.util.LinkedHashMap;import java.util.Map;import java.util.TreeMap;public class MapTest {public static void main(String[] args) {Map<String,String> treeMap = new TreeMap<String,String>();Map<String,String> linkedMap = new LinkedHashMap<String, String>();treeMap.put("b",null);treeMap.put("c",null);treeMap.put("a",null);for (Iterator<String> iter = treeMap.keySet().iterator();iter.hasNext();){System.out.println("TreeMap="+iter.next());}System.out.println("----------分割线---------");linkedMap.put("b",null);linkedMap.put("c",null);linkedMap.put("a",null);for (Iterator<String> iter = linkedMap.keySet().iterator();iter.hasNext();){System.out.println("LinkedHashMap="+iter.next());}}} Run the above code and the execution result is as follows:
TreeMap=a
TreeMap=b
TreeMap=c
-------------------------
LinkedHashMap=b
LinkedHashMap=c
LinkedHashMap=a
From the running results, it is obvious that the difference between TreeMap and LinkedHashMap is clearly seen. The former is output by string sorting, while the latter is output by insertion order. Careful readers can find that the difference between HashMap and TreeMap is consistent with the previously mentioned differences between HashSet and TreeSet. When conducting source code analysis in the future, we can see that HashSet and TreeSet are essentially implemented through HashMap and TreeMap respectively, so their differences are naturally the same. HashTable is rarely used now. The main difference from HashMap is that HashTable is thread-safe, but due to its low efficiency, HashMap is usually used. In a multi-threaded environment, CurrentHashMap is usually used instead.
3. Summary
This article only introduces the Java collection framework and its inheritance relationship as a whole. In addition to the above classes, collections also provide two tool classes: Collections and Arrays. In addition, the sorting in the collection is closely related to Comparable and Comparator. In a subsequent article, the above-mentioned class implementation source code in JDK will be analyzed in detail.