13. Assembly
13.1 concept of set
-
Collection is a series of classes provided by java, which can be used to store multiple objects dynamically. (a collection can only hold objects)
-
The difference between a set and an array is that the size of the set is variable, and the element type is not limited, as long as it is a reference type. (basic data types cannot be stored in the collection, but wrapper classes of basic data types can be stored.)
-
Collection classes all support generics, which is a data security usage.
13.2 frame diagram of collection
[the external chain image transfer fails. The source station may have an anti-theft chain mechanism. It is recommended to save the image and upload it directly (img-TtZsaOAt-1628752538732)(C:\Users\DELL\Desktop(.png)]
Detailed description:
On the whole, collections are divided into two families: Collection and Map
-
Collection: single column collection (storing the address of a single object).
-
Map: double column set (storing key value pairs - [key, value]).
In the framework, there are three other branches: Iterator, Comparator, and Collections
- Iterator: iterator designed for service Collection and its subclasses.
- Comparator: comparator, used to compare objects when storing objects in a collection.
- Collection s: a tool class that provides static methods to operate on Collections.
13.3 Collection
13.3. 1 Interface Overview
The Collection interface defines the methods of accessing objects. There are two very important sub interfaces, List and Set.
List interface: the stored elements are in order and duplicate collection interfaces are allowed.
Set interface: the stored elements are out of order, and duplicate set interfaces are not allowed.
Note:
Disorder is not random, but the storage address obtained by hash value + hash algorithm. When traversing the output, it has a specific order.
13.3. 2 common methods in interface
- int size(); Returns the number of elements in this collection
- boolean isEmpty(); Determine whether this collection contains elements. (yes: false; No: true)
- boolean contains(Object obj); Determines whether this collection contains the specified element.
- boolean contains(Collection c); Determines whether this collection contains all elements in the specified collection.
- boolean add(Object element); Add elements to this collection.
- boolean addAll(Collection c); Adds all elements in the specified collection to this collection
- boolean remove(Object element); Removes the specified element from this collection.
- boolean removeAll(Collection c); Remove all elements in this collection that are also included in the specified collection.
- void clear(); Remove all elements in the collection.
- boolean retainAll(Collection c); Only those elements in this collection that are also included in the specified collection are retained.
- Iterator iterator(); Returns the iterator that iterates over the elements of this collection.
- Object[] toArray(); Convert this collection into an array.
13.3.3 List—ArrayList
Bottom layer: one-dimensional array.
Based on the methods defined by Collection, the List interface also defines many operation methods for subscripts.
Implementation example of Collection basic method:
ArrayList<String> list = new ArrayList<>();
//Add element
list.add("aaa");
list.add("bbb");
list.add("ccc");
//Gets the number of elements
System.out.println("The number of elements in the current collection is:"+list.size());
ArrayList<String> list2 = new ArrayList<>();
//Use the Collections tool to implement multiple additions to a collection.
Collections.addAll(list2, "111","222","333");
//Inserts all elements of the new collection at the end of the collection
list.addAll(list2);
//Determine whether the collection contains an element
System.out.println("Does the current collection have elements eee: "+list.contains("eee"));
//Determines whether the current collection contains all elements of a collection
System.out.println("Whether the current collection contains all the elements of the new collection:"+list.containsAll(list2));
//Empty collection
//list.clear();
System.out.println("The number of elements in the current collection is:"+list.size());
list.remove("222");
//Delete de intersection
LinkedList<Object> newList2 = new LinkedList<>();
Collections.addAll(newList2, "333","555");
list.removeAll(newList2);
//Preserve intersection
LinkedList<Object> newList3 = new LinkedList<>();
Collections.addAll(newList3, "111","aaa");
list.retainAll(newList3);
Implementation example of new method for List:
ArrayList<String> list = new ArrayList<>();
//Add element
list.add("aaa");
list.add("bbb");
list.add("ccc");
//Sets the element on the specified subscript
list.set(1, "ddd");
//Inserts an element at the specified subscript
list.add(1, "eee");
ArrayList<String> list2 = new ArrayList<>();
//Use the Collections tool to implement multiple additions to a collection.
Collections.addAll(list2, "111","222","333");
//Inserts all elements of the new collection at the specified subscript of the collection
list.addAll(2, list2);
//Gets the subscript of the element in the collection
System.out.println("The subscript of element 111 in the current set is:"+list.indexOf("111"));
//Delete according to element subscript / content
list.remove(4);
//Gets the elements between the specified subscripts and generates a new collection
List<String> list3 = list.subList(2, 4);
Traversal method:
System.out.println("---------------");
//Iterator traversal
Iterator<String> iterator = list3.iterator();
while(iterator.hasNext()){//Judge whether the next element pointed to by the current iteration exists.
System.out.println(iterator.next()); //Returns the next element in the iteration and moves the iteration pointer down.
}
System.out.println("---------------");
//foreach traversal
for (String string : list) {
System.out.println(string);
}
System.out.println("---------------");
//for loop traversal
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
Iterator iterator:
Common methods:
hasNext(); Judge whether there is an element at the next position pointed by the current iteration.
next(); Returns the next element in the iteration and moves the iteration pointer down.
(these two methods are often used for traversal. See 13.3.3. Above for examples.)
remove()； Delete the element corresponding to the current iteration. (can delete collection elements during traversal)
Example:
ArrayList<String> list = new ArrayList<>();
Collections.addAll(list, "aa","bb","cc","dd");
Iterator<String> it = list.iterator();
while(it.hasNext()){
String str=it.next();
if(str=="bb"){
it.remove();
}
}
for (String string : list) {
System.out.println(string);
}
/*
aa
cc
dd
*/
Note:
If you use list during the iteration remove(str); If you delete it, an error will be reported.
Reason: during iteration, the Iterator will get the operand of the current collection and assign this operand to the internal operand. And it will be compared during each iteration. If list Remove() method, the operand of the collection will be incremented by 1, resulting in inconsistency with the internal operand and an exception.
When the method remove in the Iterator is used to delete (essentially the remove method of the called Collection), the operands of the collection will still be increased by 1, but the internal operands will also be updated in time. This can ensure the consistency of data and prevent the occurrence of dirty data.
ListIterator iterator:
ListIterator Iterator: an interface class that specifically serves the List interface and its implementation class, implemented from Iterator.
Common methods:
Common methods of Iterator: see above
hasPrevious()； Determine whether there are iteratable elements in front.
previous(); Returns the previous element pointed to by the iteration and moves it up.
set(); Replace the element pointed to by the current iteration with this element
add(); Add the element at the iteration location
listIterator(int index); Iterate from subscript
Example (flashback the contents of the output List collection):
LinkedList<String> list = new LinkedList<>();
list.add("111");
list.add("222");
list.add("333");
list.add("444");
ListIterator<String> it1 = list.listIterator(list.size());
while(it1.hasPrevious()){
System.out.println(it1.previous());
}
/*
444
333
222
111
*/
Example (using the add and set methods)
ArrayList<String> list = new ArrayList<>();
Collections.addAll(list, "aa","bb","cc","dd");
ListIterator<String> it = list.listIterator();
while(it.hasNext()){
String str=it.next();
if(str=="bb"){
it.add("11");
}
if(str=="cc"){
it.set("CC");
}
}
for (String string : list) {
System.out.println(string);
}
/*
aa
bb
11
CC
dd
*/
Extension 1: generics
The practice of data security specifies what data types the collection should store
Use of generics in Collections:
In the above example, ArrayList = new ArrayList < > (); Specifies that only String type objects can be loaded in the list collection. If the loaded object types are incompatible, an error will be reported.
Simple use of generic qualification: (create A parent class, B child class: inherit class A)
//?: Any type
public ArrayList<?> method01(){
ArrayList<String> list = new ArrayList<>();
return list;
}
//? extends A
//?: Represents a subclass or class a of A
public ArrayList<? extends A> method02(){
//ArrayList<B> list = new ArrayList<>();
ArrayList<A> list = new ArrayList<>();
return list;
}
//? super A
//?: Represents the parent or class a of A
public ArrayList<? super A> method03(){
//ArrayList<Object> list = new ArrayList<>();
ArrayList<A> list = new ArrayList<>();
return list;
}
Extension 2: foreach traversal
The bottom layer of foreach traversal is implemented by iterators
String e;
for(Iterator<String> it = list.iterator();it.hasNext();System.out.println(e)){
e = it.next();
}
13.3.4 List—LinkedList
Bottom layer: bidirectional linked list
LinkedList is completely compatible with ArrayList in the use of methods (reason: it implements the List interface at the same time). The only difference is that LinkedList has two more modes due to the underlying linked List structure.
-
Queue mode: first in first out, (removeFirst(); Method)
LinkedList<String> list = new LinkedList<>(); list.add("111"); list.add("222"); list.add("333"); list.add("444"); Iterator<String> it = list.iterator(); while(it.hasNext()){ System.out.println(list.removeFirst()); } /* 111 222 333 444 */ -
Stack mode: first in, last out, (removeLast(); Method)
LinkedList<String> list = new LinkedList<>(); list.add("111"); list.add("222"); list.add("333"); list.add("444"); Iterator<String> it = list.iterator(); while(it.hasNext()){ System.out.println(list.removeLast()); } /* 444 333 222 111 */
Note: due to the different underlying structures of ArrayList and LinkedList, if you need to query multiple times, use ArrayList. If you need to delete and add multiple times, using LinkedList is more efficient.
13.3.5 List - Vector (deprecated)
13.3.5.1 Vector
Understand: Vector is a collection class at the veteran level, which is in jdk1 0 was put into use at the beginning, and then in jdk1 2 began to launch the collection framework.
In terms of method use, Vector implements the List interface, which can implement all methods of List, but some old methods are retained.
For example:
addElement()//Add element
removeElement(); //Delete element
v.removeElementAt();//Delete element by subscript
//ergodic
Enumeration<String> elements = v.elements();
while(elements.hasMoreElements()){
String nextElement = elements.nextElement();
System.out.println(nextElement);
}
13.2.5.2 Stack
Inherit Vector, multi stack mode (first in, last out)
Use example:
Stack<String> stack = new Stack<>();
//Add element - pushes the element to the top of the stack
stack.push("aa");
stack.push("bb");
stack.push("cc");
stack.push("dd");
stack.push("ee");
System.out.println("Distance from stack top(Start with 1): " + stack.search("bb"));
//4
while(!stack.empty()){
//Gets the first element at the top of the stack and returns
//String element = stack.peek();
//Delete the first element at the top of the stack and return
String element = stack.pop();
System.out.println(element);
}
/*
ee
dd
cc
bb
aa
*/
13.3.6 Set—HashSet
Bottom layer: one dimensional array (hash table)
When loading an element, HashSet will add the hash value of the element + its own hash algorithm to obtain the address stored in the hash table. Therefore, when the loaded elements are the same, the calculated address is also the same. At this time, HashSet considers this to be the same object and will not add it.
Because of this, the storage position of the elements added by HashSet in the array is not fixed (for people), and the output is output according to the array in turn, so its order is equal to disorder.
Usage methods (Methods in all Collection interfaces):
Common examples:
HashSet<String> set = new HashSet<>();
//Add element
set.add("aaa");
set.add("bbb");
set.add("ccc");
//Gets the number of elements
System.out.println("The number of elements in the current collection is:"+set.size());
HashSet<String> set2 = new HashSet<>();
//Use the Collections tool to implement multiple additions to a collection.
Collections.addAll(set2, "111","222","333");
//Inserts all elements of the new collection at the end of the collection
set.addAll(set2);
//Inserts all elements of the new collection at the specified subscript of the collection
//Determine whether the collection contains an element
System.out.println("Does the current collection have elements eee: "+set.contains("eee"));
//Determines whether the current collection contains all elements of a collection
System.out.println("Whether the current collection contains all the elements of the new collection:"+set.containsAll(set2));
System.out.println("The number of elements in the current collection is:"+set.size());
//Delete according to element subscript / content
set.remove(4);
set.remove("222");
System.out.println("---------------");
//Traversal set
for (String string : set) {
System.out.println(string);
}
13.3.7 Set—LinkedHashSet
Bottom layer: bidirectional linked list (in addition to the element content, it also stores the front and rear Node addresses and Node classes)
Features: weight removal + order
In the LinkedHashSet, the storage method of elements is still the same as that of the HashSet. The hash value + hash algorithm is used to calculate the storage location address. However, in the LinkedHashSet, not only the elements are stored, but also the head and tail nodes of the elements are stored in the LinkedHashSet. During the traversal, they will be traversed from the root node in the order in which the elements are loaded, so it is orderly.
The common method is the same as HashSet
13.3.8 Set—SorteSet—TreeSet
Bottom layer: self balanced sorted binary tree (red black tree)
Note: elements loaded using the TreeSet set must implement a comparison method.
There are two common methods: built-in comparator and external comparator
- Built in comparator (implement the interface comparable < >, and override the compareTo method in the class that needs to load the TreeSet Collection):
Simple example (student class):
public class Student implements Comparable<Student>{
private String name;
private int age;
//Construction method
public Student() {
}
public Student(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Student other = (Student) obj;
if (age != other.age)
return false;
if (name == null) {
if (other.name != null)
return false;
} else if (!name.equals(other.name))
return false;
return true;
}
@Override
public String toString() {
return "Student [name=" + name + ", age=" + age + "]";
}
//Overridden compareTo method, sorted by age
@Override
public int compareTo(Student o) {
return this.age-o.age;
}
}
Note: the compareTo method rewritten here, when the age is the same, will be considered as the same element by the TreeSet set and will not be added, so we use different ages to see the effect when testing.
Method test:
TreeSet<Student> set = new TreeSet<>();
set.add(new Student("Xiao Ming",20));
set.add(new Student("Xiao Hong",18));
set.add(new Student("Xiao Gang",27));
set.add(new Student("Xiaonan",19));
set.add(new Student("Xiao Hui",21));
for (Student student : set) {
System.out.println(student);
}
/*
Student [name=Xiao Hong, age=18]
Student [name=Xiaonan, age=19]
Student [name=Xiao Ming, age=20]
Student [name=Xiao Hui, age=21]
Student [name=Xiao Gang, age=27]
*/
-
External comparator (when using the TreeSet collection, create an anonymous internal class externally and override the compare method):
Simple example:
//Create collection object TreeSet<Student> set = new TreeSet<>(new Comparator<Student>() { @Override public int compare(Student o1, Student o2) { //Sort here in reverse order of age return o2.getAge()-o1.getAge(); } }); set.add(new Student("Xiao Ming",20)); set.add(new Student("Xiao Hong",18)); set.add(new Student("Xiao Gang",27)); set.add(new Student("Xiaonan",19)); set.add(new Student("Xiao Hui",21)); set.add(new Student("Small chapter",21)); //The collection is no longer added because it is considered "the same element" for (Student student : set) { System.out.println(student); } /* Student [name=Xiao Gang, age=27] Student [name=Xiao Hui, age=21] Student [name=Xiao Ming, age=20] Student [name=Xiaonan, age=19] Student [name=Xiao Hong, age=18] */Note: the priority of external comparator is higher than that of built-in comparator!!
Resource expansion (websites that understand binary trees): https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
13.4 Map
13.4.1 HashMap
Bottom layer: one dimensional array
Features: store key value pairs, de duplication + unordered (when adding elements, the storage address is also obtained by using hash value and hash algorithm. When traversing the array in turn, it is unordered.)
Note:
-
The calculated address is only calculated through the Key, which has nothing to do with value. All value values can be repeated, but the Key cannot be repeated.
-
The Map does not have an iterator. When traversal is required:
1. You can use keySet(); Method, extract all keys into the Set set, and then obtain the value value through the iterator.
2. You can use the entrySet() method to return the set < entry < string, integer > > object and then traverse it.
Examples of common usage:
HashMap<String ,Integer> map = new HashMap<>();
//Add element
map.put("aa", 21);
map.put("bb", 22);
map.put("cc", 23);
map.put("dd", 21);
map.put("ee", 20);
map.put("ff", 21);
//Add a new collection to the collection
HashMap<String, Integer> map2 = new HashMap<>();
map2.put("gg", 10);
map2.put("hh", 10);
map2.put("ii", 10);
map2.put("jj", 10);
map.putAll(map2);
//Add element: if there is a key, it will not be added, and the value in the collection will be returned
System.out.println(map.putIfAbsent("aa", 20)); //21
System.out.println(map.putIfAbsent("adc", 20)); //null
//Empty collection
// map.clear();
//Get the corresponding value through the key
Integer integer2 = map.get("aa");
System.out.println(integer2); //21
System.out.println(""+map.getOrDefault("sf", 404));//If there is no key, the default value is returned
//Determine whether there are elements in the collection
System.out.println(map.isEmpty());//Existing element: false; Does not exist: true
//Delete element
map.remove("abc");//Pass key value
map.remove("bb", 22); //Judge by key+value
map.remove("cc", 22); //Judge by key+value
//replace
//If the replacement is successful, the value before the replacement is returned
System.out.println("Replace 1:"+map.replace("aa", 100));
//If the replacement is unsuccessful, null is returned
System.out.println("Replace 2:"+map.replace("ggb", 100));
//put replace: if there is the same key, replace value and return the original value.
System.out.println("Replace 3:"+map.put("ff", 100));
/*
Replace 1:21
Replace 2:null
Replace 3:21
*/
//Gets the number of elements in the collection
System.out.println("Number of collection elements:"+map.size());
//Get all value values
Collection<Integer> values = map.values();
System.out.println(values);
//Traversal 1 -- keySet()
//Extract all key s into the Set set, and obtain the value value through the iterator
System.out.println("-------------------");
Set<String> set = map.keySet();
for (String key : set) {
Integer integer = map.get(key);
System.out.println(key+"----"+integer);
}
System.out.println("-------------------");
//Traversal 2 -entrySet()
Set<Entry<String, Integer>> entrySet = map.entrySet();
for (Entry<String, Integer> entry : entrySet) {
System.out.println(entry);
}
/*
dd=21
ff=100
hh=10
jj=10
aa=100
cc=23
ee=20
gg=10
ii=10
adc=20
*/
13.4.2 LinkedHashMap
Bottom layer: bidirectional linked list
Features: store key value pairs, de duplication + order
(compare ArrayList and LinkedList)
13.4.3 ConcurrentHashMap
Bottom layer: one dimensional array
Features: store key value pairs, de duplication + disorder + thread safety (high efficiency - local locking)
The usage method is the same as HashMap, but it has thread safety features.
13.4.4 Hastable (deprecated)
Bottom layer: one dimensional array
Features: store key value pairs, de duplication + disorder + thread safety (low efficiency - Method locking)
The use method is the same as HashMap. Although it has thread safety characteristics, it is inefficient and has been abandoned.
13.4.5 TreeMap
Usage example (see 13.3.8 above for Student class):
Call internal comparator
//See the Student class for the internal comparator. The sorting method uses age sorting
TreeMap<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o2.getAge()-o1.getAge();
}
});
map.put(new Student("Xiao Ming",20),20);
map.put(new Student("Xiao Hong",18),20);
map.put(new Student("Xiao Gang",27),20);
map.put(new Student("Xiaonan",19),20);
map.put(new Student("Xiao Hui",21),20);
Set<Entry<Student,Integer>> entrySet = map.entrySet();
for (Entry<Student, Integer> entry : entrySet) {
System.out.println(entry);
}
/*
Student [name=Xiaohong, age=18]=20
Student [name=Xiaonan, age=19]=20
Student [name=Xiao Ming, age=20]=20
Student [name=Xiao Hui, age=21]=20
Student [name=Xiao Gang, age=27]=20
*/
Call external comparator
//Call the external comparator (the comparator is sorted in reverse age order)
TreeMap<Student, Integer> map = new TreeMap<>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o2.getAge()-o1.getAge();
}
});
map.put(new Student("Xiao Ming",20),20);
map.put(new Student("Xiao Hong",18),20);
map.put(new Student("Xiao Gang",27),20);
map.put(new Student("Xiaonan",19),20);
map.put(new Student("Xiao Hui",21),20);
Set<Entry<Student,Integer>> entrySet = map.entrySet();
for (Entry<Student, Integer> entry : entrySet) {
System.out.println(entry);
}
/*
Student [name=Xiao Gang, age=27]=20
Student [name=Xiao Hui, age=21]=20
Student [name=Xiao Ming, age=20]=20
Student [name=Xiaonan, age=19]=20
Student [name=Xiaohong, age=18]=20
*/
Comprehensive comparison between Map sets:
HashMap: stores key value pairs, which are out of order. null keys are allowed. Threads are unsafe
LinkedHashMap: store key value pairs in order. null keys are allowed. Threads are unsafe
Hashtable: storing key value pairs is out of order. null keys are not allowed. It is thread safe (locking directly in the method is inefficient). It has been discarded
ConcurrentHashMap: storing key value pairs is out of order. null keys are not allowed. It is thread safe (local locking, high efficiency)