This is the third article in the series of autumn tips. The first two articles have not received much response. If this article is of any help to you, please give it a thumbs up and forward, Risby
Recently preparing for the interview of friends can pay attention to my column – help autumn recruit, I hope to help you
Related information Sharing
- Summary of Java basic knowledge
- 2021 Gold three silver four Java post interview summary
- First-line Internet company Java interview core knowledge points
First, set class
Origin of collection:
Object oriented language to things are reflected in the form of objects, in order to facilitate the operation of multiple objects, it is necessary to store objects, collection is the most common way to store objects.
Collection features:
1. a container for storing objects. (The container itself is an object, stored in the heap memory, which holds the address of the object) 2, the length of the collection is variable. 3. Primitive data type values cannot be stored in collections. (Only store objects)
Quick question: What if you want to use collections to store basic data types?
Case and unbox. Example: al. Add (5); Add (new Integer(5));
The difference between collections and arrays:
Although arrays can also store objects, but the length is fixed, collection length is variable.
Arrays can store primitive data types; collections can store objects only.
Composition and classification of set framework :(dotted lines are interfaces)
Here are some of the top-level interfaces in the collection framework.
2. Collection interface
Collection subinterface and common implementation classes:
The Collection interface
-
| – the List interface: orderly (deposit and take out the order of the same), element has index (Angle), element can be repeated.
-
| – Vector: internal array data structure, are synchronous. Add delete, query is very slow! 100% extension (rarely used)
-
| – ArrayList: internal array data structure, is out of sync.
Instead of Vector, the query speed is fast and the speed of adding and deleting is slow. 50% longer. (The query starts from the first element in the container, because the memory space of the array is continuous, so the query is fast; In addition and deletion, the memory address of all elements must be changed, so the addition and deletion are slow.
-
| – LinkedList: internal data structure is a linked list * * * *, is out of sync. Elements can be added and removed very quickly. (Similarly, linked list memory space is discontinuous, so the query is slow; Add or delete only need to change the point of a single pointer, so fast;)
-
| – Set interface: disorderly, elements cannot be repeated. The methods in the Set interface are the same as Collection.
-
| – HashSet: internal data structure is a hash table, is out of sync.
-
| – LinkedHashSet: internal data structure is a hash table and linked list, there is a sequence of HashSet.
-
| – TreeSet: the internal data structure is ordered binary tree, its role is to provide an orderly Set collection, is out of sync.
The List interface:
One of the most common features of LinkedList is the ability to manipulate corner tags. The list collection can be used to add, delete, change or check elements.
The difference between a Set and a List
1. The Set interface instance stores unordered and non-repetitive data. The List interface instance stores ordered, repeatable elements < essential difference >.
2. Set retrieval efficiency is low, deletion and insertion efficiency is high, insertion and deletion will not cause element position change.
3. A List is similar to an array. It can grow dynamically based on the size of the stored data. It is efficient to find elements, but inefficient to insert and delete elements, because it causes other elements to change positions.
ArryList and Vector are variable-length arrays:
When the array of default length is not enough to store, a new array is created. Copy the contents of the original array to the new array, and append the new element to the end of the copied array, if not enough. Where,ArryList is increased by 50%, while Vector is increased by 100%.
ArryList is thread-safe, Vector is thread-safe:
The efficiency of Arrylist is much higher than that of Vector because the judgment of whether there is a lock or not will affect the efficiency. And any common container is not synchronous because synchronization is inefficient.
A small example of an ArryList access object:
Person p1 = new Person("lisi1",21); ArrayList al = new ArrayList(); al.add(p1); al.add(new Person("lisi2",22)); al.add(new Person("lisi3",23)); al.add(new Person("lisi4",24)); Iterator it = al.iterator(); while(it.hasNext()){ // System.out.println(((Person) it.next()).getName()+"::"+((Person) it.next()).getAge()); Next () moves once, printing "lisi1::22 lisi3::24". Person p = (Person) it.next(); System.out.println(p.getName()+"--"+p.getAge()); }Copy the codeThe HashSet overrides the hashCode and equals methods to ensure element uniqueness
How do you ensure that the elements of a HashSet are unique? Object uniqueness is achieved through the object’s hashCode and equals methods:
- -> If the hashCode value of the object is different, then the equals method is not checked, and the hash table is stored directly.
- -> If the objects’ hashCode values are the same, then check again whether the equals method of the objects is true:
If true, the element is the same and does not exist; If false, it is treated as a different element and stored.
Remember: If an object is to be stored in a HashSet collection, the object must override the hashCode and equals methods.
In general, if you define a class that produces many objects, such as people, students, and books, you will need to override equals and hashCode to establish whether the objects are the same or not.
Example: Store a Person object in a HashSet collection. If the name and age are the same, they are the same person and the same element.
import java.util.HashSet; import java.util.Iterator; class Person { private String name; private int age; public Person(String name, int age) { this.name = name; this.age = age; } @Override public int hashCode() { // System.out.println(this+"....... hashCode"); return name.hashCode() + age * 27; } @override public Boolean equals(Object obj) {if (this == obj) return true; if (! (obj instanceof Person) throw new ClassCastException(" type error "); // System.out.println(this+".... equals....." +obj); Person p = (Person) obj; return this.name.equals(p.name) && this.age == p.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; } public String toString() { return name + ":" + age; } } public class HashSetTest { public static void main(String[] args) { HashSet hs = new HashSet(); /* * The data structure of the HashSet is a hash table, so when storing elements, * uses the hashCode method of the elements to determine their positions. If the positions are identical, then equals is used to determine whether they are identical. * */ hs.add(new Person("lisi4", 24)); hs.add(new Person("lisi7", 27)); hs.add(new Person("lisi1", 21)); hs.add(new Person("lisi9", 29)); hs.add(new Person("lisi7", 27)); Iterator it = hs.iterator(); while (it.hasNext()) { Person p = (Person) it.next(); System.out.println(p); }}}Copy the codeRunning results:
lisi1:21
lisi9:29
lisi4:24
lisi7:27
Copy the codeTreeSet’s Two ways to judge element uniqueness (How to order)
TreeSet defaults to determining element uniqueness by:
According to the comparison method of Conpare interface, whether the return result of conpareTo is 0, yes, that is, the same element, does not exist.
Below, we give two custom ways to determine the uniqueness of elements:
A:
Make elements compare themselves, that is, by the attributes in the elements. This approach requires the element to implement the Comparable interface, overriding the compareTo method.
Example: Store the Person object in the TreeSet collection. If the name and age are the same, they are the same person and the same element.
import java.util.Iterator; import java.util.TreeSet; class Person implements Comparable { public String name; public int age; public Person() { super(); } public Person(String name, int age) { super(); this.name = name; this.age = age; } public String toString() { return name + ":" + age; } @Override public int compareTo(Object o) { Person p = (Person) o; /* int temp = this.age - p.age; return temp == 0 ? this.name.compareTo(p.name) : temp; // if (this.age > p.age) // return 1; // if (this.age < p.age) // return -1; // else { // return this.name.compareTo(p.name); // } } public static void main(String[] args) { TreeSet<Person> ts = new TreeSet<Person>(); ts.add(new Person("zhangsan", 22)); ts.add(new Person("lisi", 27)); ts.add(new Person("wangermazi", 21)); ts.add(new Person("zhaosi", 25)); Iterator it = ts.iterator(); while (it.hasNext()) { Person person = (Person) it.next(); System.out.println(person.toString()); }}}Copy the codeRunning results:
wangermazi:21
zhangsan:22
zhaosi:25
lisi:27
Copy the codeAs you can see, after overwriting the compareTo method, the elements are sorted according to the age attribute.
Method 2 :(develop this, master the use of the comparator)
Let the collection compare itself. Write a Comparator. Define a class that implements the Comparator interface and overwrites the compare method. The class object is then passed as an argument to the constructor of the TreeSet collection.
Elements are no longer required to implement the Conparable interface.
Step1 – create a comparedbyname. Java class and override the compare method:
import java.util.Comparator; public class ComparedByName implements Comparator { @Override public int compare(Object o1, Object o2) { // TODO Auto-generated method stub Person p1 = (Person) o1; Person p2 = (Person) o2; int temp = p1.name.compareTo(p2.name); return temp == 0 ? p1.age - p2.age : temp; }}Copy the codeStep2 – Pass the comparator class object as an argument to the constructor of the TreeSet collection:
import java.util.Iterator; import java.util.TreeSet; class Person implements Comparable { public String name; public int age; public Person() { super(); } public Person(String name, int age) { super(); this.name = name; this.age = age; } public String toString() { return name + ":" + age; } @Override public int compareTo(Object o) { Person p = (Person) o; /* int temp = this.age - p.age; return temp == 0 ? this.name.compareTo(p.name) : temp; // if (this.age > p.age) // return 1; // if (this.age < p.age) // return -1; // else { // return this.name.compareTo(p.name); // } } public static void main(String[] args) { TreeSet<Person> ts = new TreeSet<Person>(new ComparedByName()); ts.add(new Person("zhangsan", 22)); ts.add(new Person("lisi", 27)); ts.add(new Person("wangermazi", 21)); ts.add(new Person("zhaosi", 25)); Iterator it = ts.iterator(); while (it.hasNext()) { Person person = (Person) it.next(); System.out.println(person.toString()); }}}Copy the codeRunning results:
lisi:27
wangermazi:21
zhangsan:22
zhaosi:25
Copy the codeThis time our comparator sorts by the element attribute name, and the overwrite compareTo method sorts by age.
As you can see, when both methods exist, they are sorted according to the comparator’s method.
Consider: How can FIFO and FIFO be implemented in this way?
Let the comparator return either 1 or -1.
Iterator interface
An iterator that iterates over a Collection, which is the common interface for fetching elements from all Collection containers.
The iterator object depends on the concrete container, and because each container has a different data structure, the iterator object is implemented internally in the concrete container. (Inner class, can see the specific container source)
The implementation method is not important to the container user, as long as the object of the implementation’s iterator is retrieved from the container, that is, the iterator() method, instead of new. (the Iterator ite = list. The Iterator ())
Quick tip: The difference between while and for when using iterators
Iterator<String> ite=list.iterator(); While (ite.hasnext ())// determine the value after the next element {system.out.println (ite.next()); Iterator<String> ite=list.iterator(); for(Iterator it = coll.iterator(); it.hasNext(); ) { System.out.println(it.next()); }Copy the codeIn the first way, the iterator remains in memory after the while loop ends and can continue to be used.
In the second method, the iterator disappears after the for loop ends, clearing up memory. The second method is common in development.
A subinterface of Iterator
| – a ListIterator interface (list iterator)
Application Scenarios:
As the name implies, can only be used with List iterators.
In the process of using iterators iterative need to use the method of a set of elements, abnormal ConcurrentModificationException, specific look at the following example.
Code for abnormal situation:
Iterator it = list.iterator(); while(it.hasNext()){ Object obj = it.next(); / / Java. Util. ConcurrentModificationException / / in the process of using the iterator elements in the collection method is used to add () operation, abnormal. // ListIterator, a subinterface of the Iterator interface, can be used to perform more operations on elements in an iteration. if(obj.equals("abc2")){ list.add("abc9"); } else System.out.println("next:"+obj); } System.out.println(list);Copy the codeSolution code:
public static void main(String[] args) { List list = new ArrayList(); list.add("abc1"); list.add("abc2"); list.add("abc3"); System.out.println("list:"+list); ListIterator it = list.listIterator(); // Get the list iterator object // It can be used to add, delete, change and check elements in the process of iteration. While (it.hasnext ()){Object obj = it.next(); if(obj.equals("abc2")){ it.add("abc9"); //ListIterator provides the add method}}Copy the code4. Map interface
The Map interface is similar to the Set interface and can be learned by comparison, such as the comparator in TreeMap.
Map: Adds a pair of elements at a time, Collection adds one element at a time.
A Map is also called a two-column Collection, and a Collection is also called a single-column Collection.
In fact, map sets store key-value pairs. The uniqueness of keys must be ensured in map sets.
Common methods:
1, add
- Value PUT (key,value): Returns the previous value associated with the key, or null if not.
2, remove
- Void clear(): clears the map set.
- Value remove(key): Displays the key-value pair based on the specified key.
3, judge
- Boolean containsKey(key): Specifies whether to contain the key
- Boolean containsValue(value): Specifies whether to contain the value
- boolean isEmpty(); Whether is empty
4, get
Value get(key): Retrieves a value by key, or returns null if there is no key. Of course, you can determine whether the specified key is included by returning null.
Int size(): Gets the number of key-value pairs.
A HashMap is a Hashtable. A Hashtable is a Hashtable.
- | – Hashtable: internal structure is a hash table, are synchronous. Null is not allowed as a key, null as a value.
- | – Properties: used to store the key value of type configuration file information, can be combined and IO technology.
- | – HashMap: internal structure is a hash table, is not synchronized. Null is allowed as key and NULL as value.
- | – TreeMap: internal structure is a binary tree, is not synchronized. You can sort the keys in the Map collection.
Map iteration method:
The Map itself has no iterators.
Method 1: Using the values() method of the Map interface, return a Collection of values contained in the Map (values that are not unique),
It then iterates through Collecion’s iterator. (Value only, Key not required)
public class MapDemo { public static void main(String[] args) { Map<Integer,String> map = new HashMap<Integer,String>(); method_2(map); } public static void method_2(Map<Integer,String> map){ map.put(8,"zhaoliu"); map.put(2,"zhaoliu"); map.put(7,"xiaoqiang"); map.put(6,"wangcai"); Collection<String> values = map.values(); Iterator<String> it2 = values.iterator(); while(it2.hasNext()){ System.out.println(it2.next()); }}}Copy the codeMethod 2: Obtain the Set Set of all keys in the map through keySet method (Key and Set are unique).
Get each key through the iterator of Set, and then get the corresponding value of each key through the GET method of Map Set.
Set<Integer> keySet = map.keySet();
Iterator<Integer> it = keySet.iterator();
while(it.hasNext()){
Integer key = it.next();
String value = map.get(key);
System.out.println(key+":"+value);
}
Copy the codeMethod 3: Use the internal interface of Map, map. Entry
, and use iterator.
Through the entrySet() method of a Map, the key and value mappings are stored as objects in the Set collection.
The type of mapping is map.Entry (marriage certificate).
The map. Entry object’s getKey and getValue are used to obtain the keys and values.
Set<Map.Entry<Integer, String>> entrySet = map.entrySet();
Iterator<Map.Entry<Integer, String>> it = entrySet.iterator();
while(it.hasNext()){
Map.Entry<Integer, String> me = it.next();
Integer key = me.getKey();
String value = me.getValue();
System.out.println(key+":"+value);
}
Copy the codeMethod 4: Iterate over keys and values with map.entryset () (recommended, especially if the volume is large)
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
Copy the codeComparison in map (Baidu interview question)
How to sort by value in HashMap
Similar to the use of the comparator in Set, we implement the comparator as an inner class. Simple examples cover a lot of ground.
1 public class HashMapTest {2 public class HashMapTest {2 3 Private static class ValueComparator implements Comparator< map. Entry<Character, String>> { 4 @Override 5 public int compare(Map.Entry<Character, String> entryA, Map.Entry<Character, String> entryB) {6 // compare, compareTo, compareTo; 7 return entryA.getValue().compareTo(entryB.getValue()); 8 } 9 } 10 11 public static void main(String[] args) { 12 Map<Character, String> map = new HashMap<>(); 13 map.put('c', "3"); 14 map.put('a', "5"); 15 map.put('b', "1"); 16 map.put('d', "2"); 17 System.out.println("Before Sort:"); 18 for (Map.Entry<Character, String> mapping : map.entrySet()) { 19 System.out.println(mapping.getKey() + ":" + mapping.getValue()); 20 } 21 22 List<Map.Entry<Character, String>> list = new ArrayList<>(map.entrySet()); List.addall (map.entryset ()); 24 ValueComparator vc = new ValueComparator(); 25 Collections.sort(list, vc); 26 27 System.out.println("After Sort:"); 28 for (Map.Entry<Character, String> mapping : list) { 29 System.out.println(mapping.getKey() + ":" + mapping.getValue()); 30} 31} 32}Copy the codeCollections and Arrays
Collections is a utility class for the Collections framework, where the methods are static.
Example 1: Sort by the length of the string in positive or reverse order.
You can use collections.reverseOrder () anywhere you want to use a comparator.
Java comparatorBylEngth.java:
import java.util.Comparator;
public class ComparatorByLength implements Comparator<String> {
@Override
public int compare(String o1, String o2) {
int temp = o1.length() - o2.length();
return temp==0?o1.compareTo(o2): temp;
}
}
Copy the codeThe Demo:
Public static void demo_3() {// reverse implementation /* * TreeSet<String> ts = new TreeSet<String>(new Comparator<String>() { @Override public int compare(String o1, String o2) { int temp = o2.compareTo(o1); return temp; }}); */ TreeSet<String> treeset = new TreeSet<String>(new ComparatorByLength()); treeset.add("abc"); treeset.add("hahaha"); treeset.add("zzz"); treeset.add("aa"); treeset.add("cba"); System.out.println(treeset); TreeSet<String> ts = new TreeSet<String>(Collections.reverseOrder(new ComparatorByLength())); Add (" ABC "); ts.add("hahaha"); ts.add("zzz"); ts.add("aa"); ts.add("cba"); System.out.println("after reverse:\t" + ts); } public static void main(String[] args) {demo_3(); }<em id="__mceDel" style="background-color: rgba(255, 255, 255, 1); font-family: "PingFang SC", "Helvetica Neue", Helvetica, Arial, sans-serif; font-size: 14px"><br></em>Copy the codeThe results
Example 2: Sort with the collections.sort () utility class:
public static void demo_2() { List<String> list = new ArrayList<String>(); list.add("abcde"); list.add("cba"); list.add("aa"); list.add("zzz"); list.add("cba"); list.add("nbaa"); System.out.println(list); Collections.sort(list); System.out.println("after sort:\n" + list); Collections.sort(list, Collections.reverseOrder()); System.out.println("after reverse sort:\n" + list); int index = Collections.binarySearch(list, "cba"); System.out.println("index=" + index); // Get the maximum value. String max = Collections.max(list, new ComparatorByLength()); System.out.println("maxLength=" + max); } public static void main(String[] args) { demo_2(); }Copy the codeThe results
[abcde, cba, aa, zzz, cba, nbaa]
after sort:
[aa, abcde, cba, cba, nbaa, zzz]
after reverse sort:
[zzz, nbaa, cba, cba, abcde, aa]
index=2
maxLength=abcde
Copy the codeExample 3: Lock a set that is not synchronized. There are too many methods to list. Check the API for yourself. (Grasp, the interview will ask)
Returns a synchronous (thread-safe) set supported by the specified set. |
A little bit about the idea of locking sets.
List list = new ArrayList(); // Unsynchronized list. list=MyCollections.synList(list); Class MyCollections{/** * return a locked list ** / public static list synList(list list){return new MyList(list); } private class implements List{private List implements List; private static final Object lock = new Object(); MyList(List list){ this.list = list; } public boolean add(Object obj){ synchronized(lock) { return list.add(obj); } } public boolean remove(Object obj){ synchronized(lock) { return list.remove(obj); }}}}Copy the codeExample 4: Arrays.aslist () method to convert sets to Arrays
Application scenario: Array methods are limited and need to be used to manipulate array elements.
Note 1:
The length of an array is fixed, so the add and remove methods (add() and remove()) for collections are not available.
The Demo:
public static void demo_1() { String[] arr = { "abc", "haha", "xixi" }; List<String> list = Arrays.asList(arr); boolean b1 = list.contains("xixi"); System.out.println("list contains:" + b1); // list.add("hiahia"); / / cause UnsupportedOperationException System. Out. Println (list); }Copy the codeThe results
list contains:true
[abc, haha, xixi]
Copy the codeNote 2:
If the elements in the array are objects (wrapper type), then the elements in the array are stored as collection elements directly when converted to a collection. (Like the Demo above)
If the elements in the array are primitive data types, the array is stored as elements in the collection. (Such as the following Demo)
The Demo:
Public static void demo_2() {/* * If the elements of an array are objects, the elements of the array are stored as members of the collection. * * If the elements in the array are primitive-type values, the array is stored as an element in the collection. * */ int[] arr = { 31, 11, 51, 61 }; List<int[]> list = Arrays.asList(arr); System.out.println(list); System.out.println(" array length: "+ list.size()); }Copy the codeThe results
The length of the [[I@659e0bfd] array is 1Copy the codeAs can be seen from the result, when the element in the array is int, the element in the collection is the entire array, and the length of the collection is 1 instead of 4.
** Example 5: Turn an array into a collection using the list.toarray () method **
Application scenario: The operation methods of elements in a collection are limited and cannot be added or deleted.
Note: the toArray method requires passing in an array of the specified type. How to define the length of the array?
If the size of the array defined is smaller than the size of the collection, the method creates an array of the same type and size as the collection.
If the array length is greater than the size of the collection, the method uses the specified array, storing the elements in the collection, and defaults to NULL elsewhere.
Therefore, the length of the array is generally defined as the size of the collection.
The Demo:
public class ToArray { public static void main(String[] args) { List<String> list = new ArrayList<String>(); list.add("abc1"); list.add("abc2"); list.add("abc3"); String[] arr = list.toArray(new String[list.size()]); System.out.println(Arrays.toString(arr)); }}Copy the codeExample 6: Foreach statement
Application scenario: Traversal a number group or Collection a single column Collection.
Foreach can simplify the code for traversing an array just to get the elements in the array. It is recommended to use a traditional for loop if you want to manipulate the array markers.
Format:
For (type variables: set Collection * * | array) {
}
The Demo:
Public class ForEachDemo {public static void main(String[] args) {public static void main(String[] args) {int[] arr = {3, 1, 5, 7, 4}; for (int i : arr) { System.out.println(i); } List<String> List = new ArrayList<String>(); list.add("abc1"); list.add("abc2"); list.add("abc3"); for (String s : list) { System.out.println(s); } // Map traversal // Can I use advanced for traversal map collection? Cannot be used directly, but can be used by converting a map to a single-column set. Map<Integer, String> map = new HashMap<Integer, String>(); map.put(3, "zhagsan"); map.put(1, "wangyi"); map.put(7, "wagnwu"); map.put(4, "zhagsansan"); for (Integer key : map.keySet()) { String value = map.get(key); System.out.println(key + "::" + value); } for (Map.Entry<Integer, String> me : map.entrySet()) { Integer key = me.getKey(); String value = me.getValue(); System.out.println(key + ":" + value); Iterator<String> it = list.iterator(); while (it.hasNext()) { System.out.println(it.next()); }}}Copy the codePrevious hot articles:
- Summary of Java basic knowledge
- Performance Tuning Series topics (JVM, MySQL, Nginx, and Tomcat)
- From being kicked out to 5 offers of 30K+, I have come a long way
- 100 Java project parsing, with source code and learning documentation!
end