After a descriptive introduction, today entered the List, Set, Map the last link, first on the mind Map
Topic 1: What is a Java Collections Framework? What are the advantages?
There are collections in every programming language, and initially Java contained only Vector, Stack, HashTable, and Array collections. With the widespread use of collections, a collection framework that encompasses all collections interfaces, implementations, and algorithms has been in place since Java1.2.
The advantages of using a collection framework are as follows:
- Reduce development costs by using core collection classes rather than implementing our own.
- With the use of rigorously tested collection framework classes, code quality improves.
- You can reduce your code maintenance costs by using the collection classes that come with the JDK
- Reusability and operability.
Topic 2: What are the characteristics of generics in collections frameworks?
- Java1.5 introduced generics, which are heavily used by all collection interfaces and implementations.
- Generics allow us to provide a collection with a containable object type, so if you add any elements of other types, it will report an error at compile time
- This avoids a ClassCastException at runtime
- Generics also keep the code clean, and we don’t need to use explicit conversions and instanceOf operators
- It benefits the runtime because no type-checking bytecode instructions are generated.
List, Set, Map, Map
- First, they are all part of the Java Collections framework, and second, all three are interfaces
- List and Set inherit from the Collection interface, Map does not
- The biggest difference between a List implementation class and a Set implementation class is whether elements can be repeated. A List implementation class must be an ordered collection, while a Set implementation class can be unordered or ordered.
- Here the order and disorder are defined relative to the access order, the order of deposit is equal to the order of take out is considered to be ordered, and the unordered Set implementation class also has its own internal definition of the order, such as HashSet
- List includes ArrayList, Vector and LinkedList
- ArrayList and Vector are implemented based on arrays, and LinkedList is implemented based on bidirectional lists
- Only Vector is thread-safe
- Different data structures for arrays and bidirectionally linked lists result in different performance (see examples below)
- Set mainly has HashSet, TreeSet, LinkedHashSet three commonly used implementation classes, the difference lies in
- HashSet is based on hash table, TreeSet is based on binary tree, LinkedHashSet is inherited from HashSet, which is based on hash table and introduces bidirectional linked list
- None of them are thread safe
- The three data structures can also lead to performance differences
- The List implementation classes both implement the List interface and inherit from the AbstractList abstract class, while the Set implementation classes both implement the Set interface and inherit from the AbstractSet abstract class, so they each have their own Set of CRUD operations of the same name
- The Map interface does not inherit from the Collection interface because it makes no sense. The essence of an interface is a set of code specifications, the essence of a Map is a key-value pair, and the essence of a Collection is a set of objects.
- Map includes HashMap, TreeMap, and LinkedHashMap
- HashMap is based on hash table, TreeMap is based on binary tree, and LinkedHashMap is inherited from HashMap, which introduces bidirectional linked list on the basis of hash table
- None of them are thread safe
- The three data structures can also lead to performance differences
- The three implementation classes of Set and Map have similar properties and differences, because the underlying classes of HashSet, TreeSet and LinkedHashSet are HashMap, TreeMap and LinkedHashMap respectively.
Field measurement: performance test
Here we separately carry out single-thread performance tests for implementation classes under the same interface
ArrayList, Vector, LinkedList
public class ListDemo {
public static void main(String[] args) {
// Test only one implementation class at a time
List<Integer> list = new ArrayList<>();
//List<Integer> list = new Vector<>();
//List<Integer> list = new LinkedList<>();
test(list);
}
/** ** entry **@param list
*/
public static void test(List<Integer> list) {
testAddTime(list, 1000000);
testIndexUpTime(list);
testForEachTime(list);
testIteratorTime(list);
testIndexDownTime(list);
testReadRandomTime(list);
testRandomDelTime(list);
testRandomAddTime(list);
testRandomSetTime(list);
}
/** * Add tests ** in sequence@param list
*/
public static void testAddTime(List<Integer> list, int size) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println(list.getClass() + "Insert" + size + Total time of each element: + (endTime - startTime) + "ms");
}
/** * Iterator traverses the test **@param list
*/
public static void testIteratorTime(List<Integer> list) {
long startTime = System.currentTimeMillis();
Iterator<Integer> it = list.iterator();
while (it.hasNext()) {
Integer integer = it.next();
/ / null traverse
}
long endTime = System.currentTimeMillis();
System.out.println(list.getClass() + "Iterator traversal time: + (endTime - startTime) + "ms");
}
/** * ForEach traversal test **@param list
*/
public static void testForEachTime(List<Integer> list) {
long startTime = System.currentTimeMillis();
for (Integer i : list) {
/ / null traverse
}
long endTime = System.currentTimeMillis();
System.out.println(list.getClass() + "ForEach traverse time:" + (endTime - startTime) + "ms");
}
/** * index increments traversal test **@param list
*/
public static void testIndexUpTime(List<Integer> list) {
long startTime = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
/ / air circulation
}
long endTime = System.currentTimeMillis();
System.out.println(list.getClass() + Incremental index traversal time: + (endTime - startTime) + "ms");
}
/** * index decrement traversal test **@param list
*/
public static void testIndexDownTime(List<Integer> list) {
long startTime = System.currentTimeMillis();
for (int i = list.size() - 1; i > 0; i--) {
/ / air circulation
}
long endTime = System.currentTimeMillis();
System.out.println(list.getClass() + "Decrement index traversal time:" + (endTime - startTime) + "ms");
}
/** * Random read test **@param list
*/
public static void testReadRandomTime(List<Integer> list) {
long startTime = System.currentTimeMillis();
Random random = new Random();
Integer integer = 0;
for (int i = 0; i < 10000; i++) {
int randomInt = random.nextInt(list.size());
integer = list.get(randomInt);
}
long endTime = System.currentTimeMillis();
System.out.println(list.getClass() + "10,000 random reads time:" + (endTime - startTime) + "ms");
}
/** * Randomly delete test **@param list
*/
public static void testRandomDelTime(List<Integer> list) {
long startTime = System.currentTimeMillis();
Random random = new Random();
for (int i = 0; i < 10000; i++) {
int randomInt = random.nextInt(list.size());
list.remove(randomInt);
}
long endTime = System.currentTimeMillis();
System.out.println(list.getClass() + "Time to randomly delete 10,000 elements:" + (endTime - startTime) + "ms");
}
/** * randomly insert objects *@param list
*/
public static void testRandomAddTime(List<Integer> list){
long startTime = System.currentTimeMillis();
Random random = new Random();
for (int i = 0; i < 10000; i++) {
int randomInt = random.nextInt(list.size());
list.add(randomInt,randomInt);
}
long endTime = System.currentTimeMillis();
System.out.println(list.getClass() + "Time to randomly insert 10,000 elements:" + (endTime - startTime) + "ms");
}
/** * Randomly change the object *@param list
*/
public static void testRandomSetTime(List<Integer> list){
long startTime = System.currentTimeMillis();
Random random = new Random();
for (int i = 0; i < 10000; i++) {
int randomInt = random.nextInt(list.size());
list.set(randomInt,randomInt);
}
long endTime = System.currentTimeMillis();
System.out.println(list.getClass() + "Time to randomly change 10,000 elements:" + (endTime - startTime) + "ms"); }}Copy the codeBased on the single-variable test method, where I change only one variable at a time (same environment, same code, different implementation class only), I get the following three results
To be honest, I was a little surprised to see this result, since the results of my previous articles were based on theory prior to this official test, but the results of this test showed that LinkedList’s performance was no better than ArrayList’s. And it’s still in my collection of samples were transferred to the array, 1 million, 5 million samples were from the beginning I directly on, at the time of test to LinkedList randomization, I thought my computer card, a half-day did not give a result, test for 3 times in a row, until I put the samples were transferred to 1 million, to see the results of randomization, I then tested it five times in a row with a million samples and found that ArrayList beat LinkedList.
HashSet, TreeSet, LinkedHashSet
public class SetDemo {
public static void main(String[] args) {
/ / the random class
Random random = new Random();
// 1 million samples
int size = 1000000;
// Test only one implementation class at a time
Set<Integer> set = new HashSet<>();
//Set<Integer> set = new TreeSet<>();
//Set<Integer> set = new LinkedHashSet<>();
// Sequential insertion
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
set.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println(set.getClass() + "Insert" + size + Total time of each element: + (endTime - startTime) + "ms");
// iterator traversal
startTime = System.currentTimeMillis();
Iterator<Integer> it = set.iterator();
while (it.hasNext()) {
/ / null traverse
Integer integer = it.next();
}
endTime = System.currentTimeMillis();
System.out.println(set.getClass() + "Iterator traversal total time:" + (endTime - startTime) + "ms");
/ / ForEach traversal
startTime = System.currentTimeMillis();
for (Integer i : set) {
/ / air circulation
}
endTime = System.currentTimeMillis();
System.out.println(set.getClass() + "ForEach traversal total time: + (endTime - startTime) + "ms");
// Random update (set does not repeat, insert small update)
startTime = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
int randomInt = random.nextInt(set.size());
set.add(randomInt);
}
endTime = System.currentTimeMillis();
System.out.println(set.getClass() + "Total time of randomly updating 10000 elements:" + (endTime - startTime) + "ms");
// Delete randomly
startTime = System.currentTimeMillis();
Integer integer = 0;
for (int i = 0; i < 10000; i++) {
int randomInt = random.nextInt(set.size());
set.remove(randomInt);
}
endTime = System.currentTimeMillis();
System.out.println(set.getClass() + "Total time for randomly deleting 10000 elements:" + (endTime - startTime) + "ms"); }}Copy the code
The results fit the assumptions of previous articles, with HashSet inserts being the fastest, LinkedHashSet look-up the fastest, and TreeSet being a moderate choice.
HashMap, TreeMap, LinkedHashMap
public class MapDemo {
public static void main(String[] args) {
/ / the random class
Random random = new Random();
String emptyString = "";
// 1 million samples
int size = 1000000;
// Test only one implementation class at a time
Map<String, String> map = new HashMap<>();
//Map<String, String> map = new TreeMap<>();
//Map<String, String> map = new LinkedHashMap<>();
// Sequential insertion
long startTime = System.currentTimeMillis();
for (int i = 0; i < size; i++) {
map.put(i + emptyString, i + emptyString);
}
long endTime = System.currentTimeMillis();
System.out.println(map.getClass() + "Insert" + size + Total time of each element: + (endTime - startTime) + "ms");
// Random fetch
startTime = System.currentTimeMillis();
String valueStr = "";
for (int i = 0; i < 10000; i++) {
int randomInt = random.nextInt(map.size());
valueStr = map.get(randomInt + emptyString);
}
endTime = System.currentTimeMillis();
System.out.println(map.getClass() + "10,000 random reads time:" + (endTime - startTime) + "ms");
// Delete randomly
startTime = System.currentTimeMillis();
for (int i = 0; i < 10000; i++) {
int randomInt = random.nextInt(map.size());
map.remove(randomInt + emptyString);
}
endTime = System.currentTimeMillis();
System.out.println(map.getClass() + "Randomly delete 10,000 time:" + (endTime - startTime) + "ms");
/ / keySet
startTime = System.currentTimeMillis();
Set<String> stringSet = map.keySet();
endTime = System.currentTimeMillis();
System.out.println(map.getClass() + "KeySet conversion time:" + (endTime - startTime) + "ms");
/ / values
startTime = System.currentTimeMillis();
Collection<String> values = map.values();
endTime = System.currentTimeMillis();
System.out.println(map.getClass() + "Converting values takes time:" + (endTime - startTime) + "ms"); }}Copy the code
Doesn’t seem to make much of a difference except that TreeMap inserts slightly less efficiently
summary
At this stage, the Java container is almost finished. In fact, the test code can be further improved. For example, the memory can be checked to determine the resource consumption of different containers, and then the sample size can be increased to 3 million or 5 million. I don’t think anyone would take that many objects and put them in one container at a time, so I think a million samples is enough, and then you have complex objects as container elements that you can test. I’m using the single variable principle here, so I can’t test it all in one article.
The test code is as follows: github.com/MagicH666/J…