Table of Contents
- Initial capacity
- The defect of asList
- Avoid using primitive data type arrays to convert to lists
- The list generated by asList is not operable
- The defect of subList
- SubList returns just a view
- After subList generates sublists, do not attempt to manipulate the original list
- It is recommended to use subList for local lists
- Keep compareTo and Equals in sync
- Refer to the article
This article has references to a number of quality technology blogs, which can be found at the bottom of the article
Today we’ll explore some of the technical details of Java collection classes. It is mainly to explain and supplement some knowledge points which are easy to be omitted and misunderstood. Please understand that it may not be comprehensive.
Initial capacity
Collections are one of the things that we use a lot in Java programming, it’s like the ocean, it’s like a universal container, it contains everything, and the ocean, it’s a universal container, it can get infinitely bigger (if it’s allowed). When the volume of the sea becomes very large, its initial capacity becomes very important, because it takes a lot of manpower, material resources and financial resources to dig and expand the sea.
In the same way, the initial capacity of a Collection is extremely important. So: For known scenarios, specify the initial capacity for the collection.
public static void main(String[] args) { StudentVO student = null; long begin1 = System.currentTimeMillis(); List<StudentVO> list1 = new ArrayList<>(); for(int i = 0 ; i < 1000000; i++){ student = new StudentVO(i,"chenssy_"+i,i); list1.add(student); } long end1 = System.currentTimeMillis(); System.out.println("list1 time: "+ (end1-begin1)); long begin2 = System.currentTimeMillis(); List<StudentVO> list2 = new ArrayList<>(1000000); for(int i = 0 ; i < 1000000; i++){ student = new StudentVO(i,"chenssy_"+i,i); list2.add(student); } long end2 = System.currentTimeMillis(); System.out.println("list2 time: "+ (end2-begin2)); }Copy the codeList1 does not request an initial capacity, while List2 does request an initial capacity of 1000000. The result is as follows:
List1 time: 1638 List2 time: 921Copy the codeFrom the above results we can see that list2 is about twice as fast as List1. As LZ mentioned earlier, the expansion mechanism of ArrayList is resource-intensive. Let’s start with the add method for ArrayList:
public boolean add(E e) { ensureCapacity(size + 1); elementData[size++] = e; return true; } public void ensureCapacity(int minCapacity) { modCount++; Int oldCapacity = elementData.length; If (minCapacity > oldCapacity) {Object oldData[] = elementData; // newCapacity = oldCapacity * 1.5 + 1 int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; ElementData = array.copyof (elementData, newCapacity); }}Copy the codeEach time an element is added to the ArrayList, it checks whether the current capacity of the ArrayList has reached a critical point, and if it has reached a critical point, it expands by 1.5 times. However, scaling up an ArrayList and copying arrays to create new arrays is expensive. Therefore, if we know the usage scenarios of the set and the general range of the set in advance, we had better specify the initial capacity, so that the utilization of resources will be better. Especially under the premise of large data volume, efficiency improvement and resource utilization will be more advantageous.
The defect of asList
In the actual development process, we often use asList to convert arrays into lists. This method is very convenient to use, but the asList method has several drawbacks:
Avoid using primitive data type arrays to convert to lists
There is an interesting drawback when using an array of eight primitive types to convert to a list. Take a look at the following procedure:
Public static void main(String[] args) {int[] ints = {1,2,3,4,5}; List list = Arrays.asList(ints); System.out.println("list'size: "+ list.size()); } -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- - the outPut: list 'size: 1Copy the codeWhat happens when the program doesn’t get a 5 as expected but a 1? First look at the source code:
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
Copy the codeThe parameter that asList takes is a variable length parameter of a generic type. We know that primitive data types are uncodified, that is, the eight primitive types cannot be used as parameters of asList. To be used as generic parameters, we must use their corresponding wrapper types. But why isn’t there an error in this instance?
Because the instance takes an array of type int as its argument, in Java an array is an object that can be genericized. So there is no error in this example. Since the example takes an entire array of ints as a generic parameter, the asList conversion will only have a list of ints. As follows:
Public static void main(String[] args) {int[] ints = {1,2,3,4,5}; List list = Arrays.asList(ints); System.out.println("list type :" + list.get(0).getClass()); System.out.println("list.get(0) == ints: "+ list.get(0).equals(ints)); }Copy the codeOutPut: list type :class [I list.get(0) == ints: true] outPut: list type :class [I list.get(0) == ints: true
Public static void main(String[] args) {Integer[] ints = {1,2,3,4,5}; List list = Arrays.asList(ints); System.out.println("list'size: "+ list.size()); System.out.println("list.get(0) :" + list.get(0).getClass()); Println ("list.get(0) == ints[0] : "+ list.get(0).equals(ints[0])); } ---------------------------------------- outPut: List 'size: 5 List.get (0) type :class java.lang.Integer list.get(0) == ints[0] : trueCopy the codeThe list generated by asList is not operable
Let’s make one more small change to the above example:
Public static void main(String[] args) {Integer[] ints = {1,2,3,4,5}; List list = Arrays.asList(ints); list.add(6); }Copy the codeInts converts to list via asList, and then adds an element via add. This example couldn’t be simpler, but what about the result? Play what we expect:
Exception in thread "main" java.lang.UnsupportedOperationException
at java.util.AbstractList.add(Unknown Source)
at java.util.AbstractList.add(Unknown Source)
at com.chenssy.test.arrayList.AsListTest.main(AsListTest.java:10)
Copy the codeOperation result necessarily throw UnsupportedOperationException exception, the exception said the list does not support the add method. How could a list not support the Add method? Is the JDK stuck in the head? AsList asList asList asList
public static <T> List<T> asList(T... a) {
return new ArrayList<>(a);
}
Copy the codeAsList takes the parameters and creates a new ArrayList. Don’t worry, read on:
private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable{ private static final long serialVersionUID = -2764017481108945198L; private final E[] a; ArrayList(E[] array) { if (array==null) throw new NullPointerException(); a = array; } / /... }Copy the codeArrayList: java.util.ArrayList: java.util.
This inner class provides methods such as size, toArray, get, set, indexOf, and contains. Methods such as add and remove that alter the result of a list are inherited from the AbstractList parent class. It is directly throw UnsupportedOperationException anomaly:
public boolean add(E e) {
add(size(), e);
return true;
}
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
public E remove(int index) {
throw new UnsupportedOperationException();
}
Copy the codeAs you can see from this code, the list returned by asList is nothing more than a list in disguise and does not have the basic property of a list (lengthening). The list is an immutable list of length, and the list returned can only be as long as the array of parameters passed in. So: : Do not try to change the list returned by asList, or you will reap the consequences.
The defect of subList
We often use the subString method to segment String objects, and we can also use subList, subMap and subSet to segment List, Map and Set, but there are some defects in this segmentation.
SubList returns just a view
First, let’s take a look at the following example:
public static void main(String[] args) { List list1 = new ArrayList(); list1.add(1); list1.add(2);
List2 List<Integer> list2 = new ArrayList<Integer>(list1); List3 List<Integer> list3 = list1.sublist (0, list1.size()); // modify list3 list3.add(3); System.out.println("list1 == list2: "+ list1.equals(list2)); System.out.println("list1 == list3: "+ list1.equals(list3)); }Copy the codeSubList > subList > subList > subList > subList > subList > subList > subList > subList > subList > subList > subList > subList > subList > subList > subList > subList , list1 = = list3? .
Since list3 adds a new element, it must be equal to list1, and list2 should be equal to list1, so the result should be:
List1 == list2: true List1 == list3: falseCopy the codeFirst, let’s look at subList source code, regardless of whether the result is correct or not:
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
Copy the codeThe subListRangeCheck method is to check whether fromIndex and toIndex are valid. If so, return a subList object directly. Note that the new object is passed with this parameter, which is very important because it represents the original list.
/** * class AbstractList, Private class SubList implements AbstractList RandomAccess {private final AbstractList implements RandomAccess parent; Private final int parentOffset; private final int offset; int size;
Constructor SubList(AbstractList<E> parent, int offset, int fromIndex, int toIndex) {this.parent = parent; this.parentOffset = fromIndex; this.offset = offset + fromIndex; this.size = toIndex - fromIndex; this.modCount = ArrayList.this.modCount; } //set method public E set(int E E) {rangeCheck(index); checkForComodification(); E oldValue = ArrayList.this.elementData(offset + index); ArrayList.this.elementData[offset + index] = e; return oldValue; } public E get(int index) {rangeCheck(index); checkForComodification(); return ArrayList.this.elementData(offset + index); } public void add(int index, E E) {rangeCheckForAdd(index); checkForComodification(); parent.add(parentOffset + index, e); this.modCount = parent.modCount; this.size++; } //remove method public E remove(int index) {rangeCheck(index); checkForComodification(); E result = parent.remove(parentOffset + index); this.modCount = parent.modCount; this.size--; return result; }}Copy the codeSubLsit is an inner class of ArrayList that, like ArrayList, inherits AbstractList and implements RandomAccess. It also provides get, set, add, remove and other common list methods. But its constructor is a bit special, and there are two things to note in the constructor:
1, this. Parent = parent; Parent is the list passed in earlier, meaning this.parent is a reference to the original list.
2, this. Offset = offset + fromIndex; this.parentOffset = fromIndex; . It even passes modCount (the fail-fast mechanism) in the constructor.
We then look at the get method, in the get method return ArrayList. Enclosing elementData (offset + index);
This code makes it clear that get returns the element at offset + index. The same goes for the add method:
parent.add(parentOffset + index, e); this.modCount = parent.modCount; Remove method
E result = parent.remove(parentOffset + index); this.modCount = parent.modCount;
True, here we can see the subList also AbstractList subList back subclasses, and its methods such as get, set, the add and remove are made operation on the original list, it does not like the subString to generate a new object.
So subList returns only a view of the original list, and all of its operations will ultimately apply to the original list.
So from the analysis here we can conclude that the above result should be exactly the opposite of our above answer:
List1 == list2: false List1 == list3: true
After subList generates sublists, do not attempt to manipulate the original list
The subList subList is just a view of the original list. If we manipulate the subList, its effects will be reflected on the original list. But what happens if we manipulate the original list?
public static void main(String[] args) { List list1 = new ArrayList(); list1.add(1); list1.add(2);
List3 List<Integer> list3 = list1.sublist (0, list1.size()); // modify list1 list1.add(3); System.out.println("list1'size: "+ list1.size()); System.out.println("list3'size: "+ list3.size()); }Copy the codeIf there were no surprises in this instance, both lists would have been of size 3, but instead we get something like this:
List1 'size: 3 Exception in thread "main" java.util.ConcurrentModificationException at java.util.ArrayList$SubList.checkForComodification(Unknown Source) at java.util.ArrayList$SubList.size(Unknown Source) at com.chenssy.test.arrayList.SubListTest.main(SubListTest.java:17)Copy the codeList1 normal output, but list3 throw ConcurrentModificationException, read my another blog colleagues very much for the exception, certainly fail – fast? It’s the fail-fast mechanism, and in the Fail-fast mechanism, LZ spent a lot of time talking about this exception, so LZ won’t talk about this exception here. Let’s look at the size method:
public int size() {
checkForComodification();
return this.size;
}
Copy the codeThe size method will first pass the checkForComodification validation and then return this.size.
private void checkForComodification() { if (ArrayList.this.modCount ! = this.modCount) throw new ConcurrentModificationException(); }Copy the codeThe method shows that when the original list modCount and enclosing modCount will throw ConcurrentModificationException are not equal.
We also know that modCount “inherits” modCount from the original list during new, and only modifies modCount when the list (sublist) is modified (acting first on the original list and then on the sublist).
In this case, we are operating on the original list. The modCount of the original list does not reflect the modCount of the sublist, so this exception is raised.
In the case of a sublist view, it is dynamically generated, so do not manipulate the original list after it is generated, otherwise the view will inevitably become unstable and throw exceptions. The best way to do this is to set the original list to read-only and manipulate the sublists as necessary:
// Use subList to generate a list like list1, list3
List<Integer> list3 = list1.subList(0, list1.size());
Copy the code// Set list1 to read-only
list1 = Collections.unmodifiableList(list1);
Copy the codeIt is recommended to use subList for local lists
One of the most common problems in development is getting a bunch of data and having to delete some data. For example, if we have a list with 1000 records and we need to delete the data at 100-200, we might do something like this:
for(int i = 0 ; i < list1.size() ; i++){ if(i >= 100 && i <= 200){ list1.remove(i); /* * There is a problem with this code, the list remove will fill in the following elements, * so you need to do a simple operation on I, of course, this is not the problem discussed here. * /}}Copy the codeThis is probably the way most of us deal with it, but there is a better way to use subList. As LZ explained earlier, all sublist operations are reflected in the original list. So the following line of code is done:
list1.subList(100, 200).clear();
Copy the codeSimple yet gorgeous ！！！！！
Keep compareTo and Equals in sync
We often use the Comparable interface in Java to implement sorting, where compareTo is the method that implements the interface. We know that compareTo returns 0 for two objects equal, positive for greater, and negative for less. Equals also determines whether two objects are equal. Is there a correlation between them?
public class Student implements Comparable<Student>{ private String id; private String name; private int age; public Student(String id,String name,int age){ this.id = id; this.name = name; this.age = age; } public boolean equals(Object obj){ if(obj == null){ return false; } if(this == obj){ return true; } if(obj.getClass() ! = this.getClass()){ return false; } Student student = (Student)obj; if(! student.getName().equals(getName())){ return false; } return true; } public int compareTo(Student student) { return this.age - student.age; } /** omit getter, setter */}Copy the codeThe Student class implements the Comparable interface and equals method, where compareTo is compared against age and equals is compared against name.
public static void main(String[] args){ List<Student> list = new ArrayList<>(); list.add(new Student("1", "chenssy1", 24)); list.add(new Student("2", "chenssy1", 26)); Collections.sort(list); // Sort Student Student = new Student("2", "chenssy1", 26); Int index1 = list.indexof (student); int index2 = Collections.binarySearch(list, student); System.out.println("index1 = " + index1); System.out.println("index2 = " + index2); }Copy the codeThe normal thinking is that the two indexes should be the same, since they are retrieving the same object, but unfortunately, the result is:
index1 = 0 index2 = 1
Why the difference? This is because indexOf and binarySearch are implemented differently.
IndexOf is implemented based on equals as long as equals returns TRUE that the same element has been found.
BinarySearch is based on the compareTo method, and when compareTo returns 0, the element is considered found.
We overwrite the compareTo and equals methods in our Student implementation, but we compare compareTo and equals based on age and name.
You might get a different result based on the comparison. So now that we know why, we can modify: we can keep the comparisons consistent.
For the compareTo and equals methods we can summarize as: CompareTo checks whether elements are equal in a sort, and equals checks whether elements are equal. Since one determines the sort position and the other determines the equality, it is important to ensure that when the sort position is the same, equals should also be equal.
The way to make them equal is that they should be attached to the same condition. Equals should be equal when Compareto is equal, equals should not be equal when Compareto is not equal, and Compareto determines the order based on certain attributes.
Refer to the article
www.cnblogs.com/galibujianb…
Blog.itpub.net/69906029/vi…
www.cnblogs.com/itxiaok/p/1…