Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”
This article has participated in the “Digitalstar Project” and won a creative gift package to challenge the creative incentive money.
1. Introduction to collection framework
A collection can be thought of as a container for storing object information. All collection classes are located under the java.util package.
The Java Collections Framework (JCF) is a unified and standard architecture for representing and manipulating Collections. Any collection framework consists of three big pieces: the external interface, the implementation of the interface, and the algorithm to operate on the collection.
- Interface: Is an abstract data type that represents a collection. For example, Collection, List, Set, and Map. Multiple interfaces are defined to manipulate collection objects in different ways
- Implementation (class) : Is a concrete implementation of the collection interface. In essence, they are reusable data structures, such as ArrayList, LinkedList, HashSet, HashMap.
- Algorithms: Useful calculations performed by methods in objects that implement the collection interface, such as searching and sorting. These algorithms are called polymorphic because the same method can have different implementations on similar interfaces.
The entire collection framework is designed around a set of standard interfaces. You can directly use the standard implementations of these interfaces (implementation classes), such as LinkedList, HashSet, and TreeSet, or you can implement your own collections through these interfaces.
The set framework system is shown in the figure:
The Java Collections framework consists of two main types of interfaces: collections, which store a Collection of elements, and Maps, which store key/value pair mappings.
2. Apis involved in the collection framework
Java collections can be divided into two systems: Collection and Map.
The Collection interface: Collection is the most basic Collection interface. A Collection represents a group of objects, that is, the elements of a Collection. Java does not provide classes that directly inherit from a Collection, but only subinterfaces (such as List and set) that inherit from a Collection.
- List interface: The List interface is an ordered Collection with precise control over where each element is inserted. Elements in the List can be accessed by index (element position in the List, similar to the subscript of an array). The index of the first element is 0, and the same element is allowed. The List interface stores a List of repeatable, ordered (insert order) objects.
- Set interface: A Set has exactly the same interface as a Collection, except that the behavior is different. Sets do not hold duplicate elements. The Set interface stores an unrepeatable, unordered Set of objects.
Map interface: The Map interface stores a set of key-value objects and provides mapping from key to value.
Collection interface inheritance tree: Solid lines represent inheritance and dotted lines represent implementation classes
Map interface inheritance tree: Solid line indicates inheritance, dotted line indicates implementation
3. Use of Collection interface
3.1 common methods in Collection interface
Method description and test code are as follows:
Add (Object e) to add element e to the collection
AddAll (Collection,coll1) moves elements from coll1 to the current Collection. Coll1 is empty after the move
Size (), gets the number of elements in the collection
IsEmpty () to determine whether the current collection isEmpty
Clear () to clear the elements in the collection
// Take ArrayList, the implementation class of the Collection interface
Collection coll = new ArrayList();
//add(Object e) to add element e to the collection
coll.add("AA");
coll.add(123);
coll.add(new Date());
//size(), gets the number of elements in the collection
System.out.println(coll.size());/ / 3
Collection coll1 = new ArrayList();
coll.add(456);
coll.add("CC");
//addAll(Collection,coll1), add elements from coll1 to the current coll1,coll1 will be empty
coll.addAll(coll1);/ / 5
System.out.println(coll.size());
System.out.println(coll);//[AA, 123, Tue Oct 05 21:20:16 CST 2021, 456, CC]
System.out.println(coll1);/ / []
//isEmpty() to determine whether the current collection isEmpty
System.out.println(coll.isEmpty());//false
//clear() to clear the elements in the collection
coll.clear();
System.out.println(coll.isEmpty());//true
Copy the codeContains (Object obj), determines whether the Object obj is in the current collection. Equals () of the Object obj class is called to determine this
ContainsAll (Collection<> coll1) checks whether all the elements in coll1 are in the current Collection
Custom classes:
package collection;
import java.util.Objects;
public class Person {
private String name;
private int age;
public Person(a) {}public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName(a) {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge(a) {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString(a) {
return "Person{" +
"name='" + name + '\' ' +
", age=" + age +
'} ';
}
// Override equals
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null|| getClass() ! = o.getClass())return false;
Person person = (Person) o;
returnage == person.age && Objects.equals(name, person.name); }}Copy the codeTest code:
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
// Add obj objects to the collection, requiring the obj class to override equals()
coll.add(new Person("wanli".3));
//contains(Object obj), checks whether the Object obj is in the current collection. Equals () of the Object obj class is called when checking
System.out.println(coll.contains("DD"));//true
System.out.println(coll.contains(new String("EE")));//true
System.out.println(coll.contains(new Person("wanli".3)));//true
Collection coll1 = Arrays.asList(123.456);
//containsAll(Collection<> coll1) checks whether all the elements in coll1 are in the current Collection
System.out.println(coll.containsAll(coll1));
Copy the codeRemove (Object obj), removes the obj element from the current collection
RemoveAll (Collection<> coll1) removes elements from the coll1 Collection from the current Collection
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));
//remove(Object obj) to remove the obj element from the current collection
System.out.println(coll.remove(456));//true
System.out.println(coll.remove(789));//false
System.out.println(coll.remove(new Person("wanli".3)));//true
System.out.println(coll);//[123, false, EE, DD]
//removeAll(Collection<> coll1) to remove elements from coll1 from the current Collection
Collection coll2 = new ArrayList();
coll2.add("DD");
System.out.println(coll.removeAll(coll2));//true
System.out.println(coll);//[123, false, EE]
Copy the codeRetainAll (Collection<> coll1), gets the intersection of the current Collection and coll1 and returns it to the current Collection
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
// Add obj objects to the collection, requiring the obj class to override equals()
coll.add(new Person("wanli".3));
Collection coll1 = Arrays.asList(123.456);
//retainAll(Collection<> coll1), retrieves the intersection of the current Collection and coll1 and returns it to the current Collection
System.out.println(coll.retainAll(coll1));//true
System.out.println(coll);/ / [123, 456]
Copy the codeEquals (Object obj) compares the equality of the specified Object to the collection
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));
Collection coll1 = new ArrayList();
coll1.add(123);
coll1.add(456);
coll1.add(false);
coll1.add(new String("EE"));
coll1.add("DD");
coll1.add(new Person("wanli".3));
//equals(Object obj) compares the specified objects to the collection
System.out.println(coll.equals(coll1));//true
Copy the codeHashCode (), which prints the hash value of the current object
ToArray () converts the current collection to an array
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));
//hashCode(), which prints the hash value of the current object
System.out.println(coll.hashCode());
//toArray(), which converts the current collection to an array
Object[] arr = coll.toArray();
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
// An array is converted to a collection
List<String> strings = Arrays.asList(new String[]{"AA"."BB"."CC"});
System.out.println(strings);//[AA, BB, CC]
Copy the code3.2 Traversing the Collection
3.2.1. Use Iterator to iterate over the Collection
Iterator Indicates an Iterator interface
Lterator objects are called iterators (a type of design pattern) and are used primarily to iterate over elements in a Collection. GOF defines the iterator pattern as providing a way to access elements of a container object without exposing the inner details of the object. The iterator pattern is built for containers.
The Collection interface inherits the java.lang.ilterable interface, which has an iterator() method. All Collection classes that implement the Collection interface have an iterator() method that returns an object that implements the Lterator interface.
The Lterator is only used to traverse collections. The Lterator body does not provide the ability to load objects. If you need to create an Lterator object, you must have an iterated collection.
Each call to the iterator() method results in a new iterator object. The default cursor precedes the first element of the collection.
Methods of the Iterator interface
HasNext (), returns true if the iteration has more elements.
Next (), returns the next element in the iteration.
HasNext () must be called to check before calling the next() method. If not called and the next record is invalid, calling next() directly throws NoSuchElementException.
Remove () to remove the last element returned by this iterator from the underlying collection (optional operation).
Iterator Iterator through the Collection code instance
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));
// Create an iterator object
Iterator iterator = coll.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
Copy the codeTest the remove() method
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));
Iterator iterator = coll.iterator();
while (iterator.hasNext()){
Object next = iterator.next();
if ("EE".equals(next)){
// Remove the elementiterator.remove(); }}// iterate over the collection
iterator = coll.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
Copy the code
Note:
-
The lterator can remove elements of a collection, but only through the iterator object’s remove method during traversal, not the collection object’s remove method.
-
If next() has not been called yet or if the remove method has been called since the last time next was called, a call to remove is reported as llegalStateException.
3.2.2 forEach loops through the collection
Java 5.0 provides foreach loops to iteratively access collections and arrays.
Traversal does not need to get the length of the Collection or array, and does not need to use indexes to access elements.
The underlying call to Iterator to iterate through the collection completes the operation.
Foreach can also be used to iterate over groups of numbers.
ForEach loop through the collection code example:
Collection coll = new ArrayList();
coll.add(123);
coll.add(456);
coll.add(false);
coll.add(new String("EE"));
coll.add("DD");
coll.add(new Person("wanli".3));
for (Object obj : coll) {
System.out.println(obj);
}
Copy the code4. List interface
List Interface Overview
Given the limitations of arrays in Java for storing data, we often use lists instead.
The elements of the List collection class are ordered and repeatable, and each element in the collection has its corresponding sequential index.
List Each element in the container corresponds to an integer sequence number to record its position in the container. You can access the elements in the container according to the sequence number.
The List implementation classes in JDKAPI are ArrayList, LinkedList, and Vector.
4.1. The List interface is commonly used to achieve class comparison
ArrayList, LinkedList, and Vector:
-
Same: The three classes all implement the List interface and store data in the same way: store ordered and repeatable data.
-
Vision:
- ArrayList: is the main implementation class of List interface. It is not thread safe and efficient. The bottom layer uses Object[] storage
- LinkedList: if you want to insert and delete frequently, it is efficient to use this type, and the underlying storage is two-way LinkedList
- Vector: is an older implementation of the List interface. It is thread-safe and inefficient and uses Object[] storage at the bottom
4.2 ArrayList source code analysis (JDK1.8)
// The initial capacity of the default array element
private static final int DEFAULT_CAPACITY = 10;
// A shared empty array instance for the empty instance
private static final Object[] EMPTY_ELEMENTDATA = {};
// A shared empty array instance of an empty instance of default size. We separate this from EMPTY_ELEMENTDATA to see how much expansion is required when the first element is added
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList is the array buffer in which the elements are stored. The capacity of the ArrayList is the length of the array buffer. When the first element is added, any empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA will be expanded to DEFAULT_CAPACITY.
transient Object[] elementData;
Copy the codeNo-parameter structure:
public ArrayList(a) {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Copy the codeThe no-argument construct initializes an empty array, and the array size is initialized to 10 only after the first add.
The add () method:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Check the list capacity. If it is insufficient, increase the capacity by 1. The first time add size is 0
// place the element e at size and size++
elementData[size++] = e;
return true;
}
Copy the codeEnsureCapacityInternal (int minCapacity) : minCapacity: minimum capacity required
// Add minCapacity to 1 for the first time.
private void ensureCapacityInternal(int minCapacity) {
// Check whether the array needs to be expanded
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
Copy the codeCalculateCapacity (Object[] elementData, int minCapacity) :
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// If it is the first time to add, elementData and DEFAULTCAPACITY_EMPTY_ELEMENTDATA are empty
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// return the maximum number, DEFAULT_CAPACITY = 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// The minCapacity is 10
return minCapacity;
}
Copy the codeEnsureExplicitCapacity (int minCapacity) :
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// When you add for the first time, minCapacity is 10 and elementData.length is 0
if (minCapacity - elementData.length > 0)
// Enter the capacity expansion method
grow(minCapacity);
}
Copy the codeGrow (int minCapacity) : a key method for automatic capacity expansion
private void grow(int minCapacity) {
// Get the capacity of the current array
int oldCapacity = elementData.length;
// Get the capacity of the expanded array. The new array is 1.5 times the size of the previous one
int newCapacity = oldCapacity + (oldCapacity >> 1);
// If the capacity after expansion is still smaller than the required minimum capacity
if (newCapacity - minCapacity < 0)
// Expand the capacity again to the minimum size required. When the first add is made, the initial capacity of the array is defined here
newCapacity = minCapacity;
// If the capacity after expansion exceeds the threshold, the system allocates large capacity
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// The size of the new array is determined, copy the array, copyof(original array, new array length)
elementData = Arrays.copyOf(elementData, newCapacity);
}
Copy the code4.3 Common methods of List interface
Method description:
Void add(int index, object ele): Insert ele at index position
Boolean addAll(int index,Collection eles): Adds all elements from eles starting at index
Object get(int index): Gets the element at the specified index position
Int indexOf(Object obj): Returns the position where obj first appears in the set, or -1 if not
Int lastIndexOf(object obj): Returns the position of the last occurrence of obj in the current set, or -1 if not
Object remove(int index): Removes the element at the specified index position and returns the element
Object set(int index, Object ele): Sets the element at the specified index position to ele
List subList(int fromIndex, int toIndex): Returns a subset of positions from fromIndex to toIndex, fromIndex closed and toIndex open.
Code test:
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
list.add(new Person("wanli".3));
System.out.println(list);//[123, 456, AA, Person{name='wanli', age=3}]
//void add(int index, object ele
list.add(2."BB");
System.out.println(list);// [123, 456, BB, AA, Person{name='wanli', age=3}]
// Boolean addAll(int index,Collection eles): addAll elements from eles starting at index
List<Integer> list1 = Arrays.asList(1.2.3);
list.addAll(3,list1);
System.out.println(list);//[123, 456, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]
//object get(int index): Gets the element at the specified index position
System.out.println(list.get(2));//BB
list.add(2."AA");
System.out.println(list);//[123, 456, AA, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]
//int indexOf(Object obj): Returns the position where obj first appears in the set
System.out.println(list.indexOf("AA"));/ / 2
//int lastIndexOf(object obj): Returns the last occurrence of obj in the current set
System.out.println(list.lastIndexOf("AA"));/ / 7
//Object remove(int index): Removes the element at the specified index position and returns the element
System.out.println(list);[123, 456, AA, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]
System.out.println(list.remove(1));/ / 456
System.out.println(list);[123, AA, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]
//System.out.println(list.remove(789)); / / if the element is not present, the abnormal IndexOutOfBoundsException
//Object set(int index, Object ele): set the element at the specified index position to ele, return the original element at the specified index position
list.set(0.333);
System.out.println(list);//[333, AA, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]
//List subList(int fromIndex, int toIndex) subList(int fromIndex, int toIndex)
System.out.println(list);//[333, AA, BB, 1, 2, 3, AA, Person{name='wanli', age=3}]
System.out.println(list.subList(1.4));//[AA, BB, 1]
Copy the codeGo through the List
ArrayList list = new ArrayList();
list.add(123);
list.add(456);
list.add("AA");
Iterator iterator = list.iterator();
// Iterator: Iterator
while(iterator.hasNext()){
System.out.println(iterator.next());
}
// forEach
for (Object obj: list) {
System.out.println(obj);
}
// For loop
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
Copy the code5. Set interface
Set Interface Overview
The Set interface is a subinterface of Collection, and the Set interface provides no additional methods.
A Set cannot contain identical elements. If you try to add two identical elements to the same Set, the addition fails.
Set determines whether two objects are the same not by using the == operator, but by equals().
The difference between Set and List
1. The Set interface instance stores unordered, non-repeating data. The List interface instance stores ordered, repeatable elements.
2, Set retrieval efficiency is low, delete and insert efficiency is high, insert and delete will not cause element position change < implementation class has HashSet,TreeSet>.
3. Lists, like arrays, can grow dynamically, depending on the actual size of the stored data. Find the elements with high efficiency, low insert removing efficiency, because can lead to other elements position change < ArrayList implementation class, LinkedList, the Vector >.
5.1 Commonly used Set interface implementation class comparison
Set implementation class HashSet introduction
HashSet is a typical implementation of the Set interface, and is used most of the time when working with sets. A HashSet uses the Hash algorithm to store the elements of a collection, so it has good access, find, and delete performance.
HashSet has the following characteristics:
- The order of elements cannot be guaranteed
- Hashsets are not thread-safe
- Collection elements can be null
A HashSet is unordered, that is, the order of the inserts is not recorded.
The criteria for determining the equality of two elements in a HashSet is that two objects are compared to each other using the hashCode() method and that their equals() method returns equal values.
For objects stored in a Set, the corresponding class must override the equals() and hashCode(Objectobj) methods to implement the object equality rule. That is, “Equal objects must have equal hash codes”.
Set implementation class LinkedHashSet introduction
LinkedHashSet is a subclass of HashSet
LinkedHashSet determines where elements are stored based on their hashCode value, but it also maintains the order of elements using a two-way linked list, which makes them appear to be stored in insertion order.
LinkedHashSet has slightly lower insert performance than HashSet, but good performance when iteratively accessing all elements in a Set.
LinkedHashSet does not allow collection elements to be repeated.
TreeSet introduction to the Set implementation class
TreeSet is an implementation class of the SortedSet interface. TreeSet ensures that collection elements are in sorted state.
The underlying TreeSet uses a red-black tree structure to store data
TreeSet can sort by the specified properties of the added objects
TreeSet has two sorting methods: natural sorting and custom sorting. By default, TreeSet uses natural sorting.
5.2 Understand the disorder and unrepeatability of Set
Take HashSet as an example.
disorder
HashSet set = new HashSet();
set.add(123);
set.add(798);
set.add(new Person("wanli".3));
set.add(456);
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
Person{name='wanli', age=3} 123 798 */
}
Copy the codeUnordered: Data stored in the underlying array is not added in the order of the array index, but is determined by the hash value of the data.
nonrepeatability
Create an entity class
public class User {
private String name;
private int age;
public User(a){}public User(String name, int age) {
this.name = name;
this.age = age;
}
public String getName(a) {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge(a) {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString(a) {
return "User{" +
"name='" + name + '\' ' +
", age=" + age +
'} '; }}Copy the codeExample code:
@Test
public void test1(a){
HashSet set = new HashSet();
set.add(123);
set.add(798);
set.add(new User("wanli".3));
set.add(new User("wanli".3));
set.add(456);
Iterator iterator = set.iterator();
while(iterator.hasNext()){ System.out.println(iterator.next()); }}Copy the codeIn the above code, we add two User objects to the HashSet to see the result:
Both User objects are printed because the Set can only store non-repeatable elements, indicating that the two User objects are not duplicated.
The criteria for determining the equality of two elements in a HashSet is that two objects are compared to each other using the hashCode() method and that their equals() method returns equal values.
The User implementation overrides the equals() and hashCode(Object obj) methods:
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null|| getClass() ! = o.getClass())return false;
User user = (User) o;
if(age ! = user.age)return false;
returnname ! =null ? name.equals(user.name) : user.name == null;
}
@Override
public int hashCode(a) {
intresult = name ! =null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
Copy the codeNote: For objects stored in a Set, the corresponding class must override the equals() and hashCode(Object obj) methods to implement the Object equality rule.
To see the results again:
Non-repeatability: Ensure that added elements cannot return true when checked by equals(). That is, only one of the same elements can be added to the Set.
The process of adding elements to a HashSet
When we add element A to a HashSet, we first call the hashCode() method of element A’s class to calculate the hash value of element A. The hash value then uses some algorithm to calculate the location in the underlying array of the HashSet (i.e. the index position).
Check if there are already elements at this position:
-
If there are no other elements at this location, element A is added successfully.
-
If there are other elements B (or multiple elements in a linked list) in this position, then compare the hash value of element A to element B:
- If the hash value is different, element A is added successfully.
- If the hash value is the same, then call the equLas() method of element A’s class: return true, add failed, return false, add succeeded
When element A is successfully added to the array index of an existing element, element A is stored in a linked list with the data that already exists at the specified index location. Storage mode: JDK7 head plug method, JDK8 tail plug method
5.3 Natural and customized ordering of TreeSet
Adding an element to a TreeSet requires that the object to which the element is added be of the same type.
The default implementation of natural sorting:
@Test
public void test(a){
// Add an Integer object
TreeSet set = new TreeSet();
set.add(23);
set.add(12);
set.add(5);
set.add(62);
set.add(45);
Iterator iterator = set.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
// Add a String object
TreeSet set1 = new TreeSet();
set1.add("CC");
set1.add("BB");
set1.add("TT");
set1.add("EE");
set1.add("AA");
Iterator iterator1 = set1.iterator();
while(iterator1.hasNext()){ System.out.println(iterator1.next()); }}Copy the codeView the run result:
By default, TreeSet uses natural sorting.
Natural sorting of custom class implementations
Inherit the Comparable interface in the User entity class and rewrite the compareTo method:
package collection;
public class User implements Comparable{
private String name;
private int age;
public User(a){}public User(String name, int age) {
this.name = name;
this.age = age;
}
public String getName(a) {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge(a) {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString(a) {
return "User{" +
"name='" + name + '\' ' +
", age=" + age +
'} ';
}
// Sort by name from smallest to largest
@Override
public int compareTo(Object o) {
if (o instanceof User){
User user = (User) o;
return this.name.compareTo(user.name);
}else {
throw new RuntimeException("Type exception cannot be compared"); }}}Copy the codeTest code: Add the User object to the TreeSet collection
@Test
public void test(a){
TreeSet set = new TreeSet();
set.add(new User("wanli".23));
set.add(new User("shengming".14));
set.add(new User("taoxian".36));
set.add(new User("bimo".12));
set.add(new User("neihan".35));
Iterator iterator = set.iterator();
while(iterator.hasNext()){ System.out.println(iterator.next()); }}Copy the codeView the run result:
Put two User objects of the same name and different ages into the TreeSet collection of the test code:
@Test
public void test(a){
TreeSet set = new TreeSet();
set.add(new User("wanli".23));
set.add(new User("shengming".14));
set.add(new User("taoxian".36));
set.add(new User("bimo".12));
set.add(new User("neihan".35));
set.add(new User("neihan".46));
Iterator iterator = set.iterator();
while(iterator.hasNext()){ System.out.println(iterator.next()); }}Copy the codeLook at the results again: two User objects with the same name and different ages output only one
This is because in the natural ordering of TreeSet collections, two objects are determined not by equals(), but by compareTo(). If compareTo() returns 0, the two objects are determined to be the same.
Adding a secondary judgment to the rewritten compareTo() method solves the above problem:
@Override
public int compareTo(Object o) {
if (o instanceof User){
User user = (User) o;
// Sort the names from largest to smallest
int compare = -this.name.compareTo(user.name);
// If the name is different, return it directly
if(compare ! =0) {return compare;
// If the names are the same, then sort by age from youngest to oldest
}else {
return Integer.compare(this.age, user.age); }}else {
throw new RuntimeException("Type exception cannot be compared"); }}Copy the codeIn the case of two User objects with the same name and different ages, look at the run result: two User objects with the same name and different ages are output.
TreeSet custom sorting
@Test
public void test1(a){
Comparator comparator = new Comparator() {
// Sort by age from youngest to oldest
@Override
public int compare(Object o1, Object o2) {
if (o1 instanceof User && o2 instanceof User){
User user1 = (User) o1;
User user2 = (User) o2;
return Integer.compare(user1.getAge(),user2.getAge());
}else {
throw new RuntimeException("Type exception cannot be compared"); }}};// Select custom sort. If there is no comparator, natural sort is default
TreeSet set = new TreeSet(comparator);
set.add(new User("wanli".23));
set.add(new User("shengming".14));
set.add(new User("taoxian".36));
set.add(new User("bimo".12));
set.add(new User("neihan".12));
set.add(new User("neihan".46));
Iterator iterator = set.iterator();
while(iterator.hasNext()){ System.out.println(iterator.next()); }}Copy the code
In a custom sort of TreeSet collection, compare() is used instead of equals() to determine whether two objects are the same. If compare() returns 0, the two objects are the same.
6. Map interface
Map interface: The Map interface stores a set of key-value objects and provides mapping from key to value.
6.1 comparison of commonly used Map interface implementation classes
HashMap: As the main implementation class of Map, it is not thread safe and efficient, and can store null keys and values.
LinkedHashMap: A subclass of HashMap that ensures that map elements can be traversed in the order they were added to. This is suitable for frequent traversal.
TreeMap: Sorts the key and value according to the added key and value. In this case, both natural and custom sorts only consider the key, not the value.
Hashtable: is an ancient implementation of Map, thread-safe, inefficient, cannot store null keys and values.
Properties: a subclass of Hashtable, used to handle configuration files where keys and values are strings.
Difference between HashMap and Hashtable
Compared to HashMap, Hashtable is thread-safe and does not allow null keys and values.
The default size of Hashtable is 11.
Hashtable is a hash value that uses the hashCode(key.hashcode ()) of the key directly. Unlike the static final int hash(Object key) function inside a HashMap, the key’s hashCode is disturbed as a hash value.
Hash bucket subscript for Hashtable is modular %. (because its default capacity is not 2 ^ n.). So you can’t replace modular operations with bitwise operations.)
During capacity expansion, the new capacity is twice the original capacity +1. int newCapacity = (oldCapacity << 1) + 1;
Hashtable is a subclass of Dictionary that implements the Map interface.
6.2 Key-value characteristics stored in HashMap
HashMap is the most frequently used implementation class of the Map interface. It allows null keys and null values and, like HashSet, does not guarantee the order of the mapping.
The Set of all keys in a HashMap is Set: unordered and non-repeatable. So, the classes for keys need to be overridden :equals() and lhashCode().
All values of a HashMap form a Collection: unordered and repeatable. So, the value class is overridden :equals()
HashMap A key-value pair constitutes an entry
The Set of all the entries in a HashMap is a Set: unordered and non-repeatable
A HashMap determines that two keys are equal when they return true via equals() and the hashCode values are equal.
The HashMap criterion for determining the equality of two values is that they return true via equals().
6.3 HashMap Source Code Analysis (JDK 8)
6.3.1 Underlying structure of HashMap
In JDK1.8, HashMap is composed of array + linked list + red-black tree. With the addition of red-black tree as the underlying data structure, the structure becomes more complex, but the use efficiency also becomes more efficient.
6.3.2 Data structures involved in HashMap
Linked list (single linked list)
Node is an inner class of HashMap that implements the Map.Entry interface, which is essentially a mapping (key-value pair).
Specific source code:
static class Node<K.V> implements Map.Entry<K.V> {
final int hash;/ / hash value
final K key;/ / key the key
V value;/ / value the value
Node<K,V> next;// A reference to the next key-value pair
// constructor
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey(a) { return key; }
public final V getValue(a) { return value; }
public final String toString(a) { return key + "=" + value; }
// The hash value of each node is xor of the key hashCode and the value hashCode.
public final int hashCode(a) {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
// Set the new value and return the old value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
// Check whether two nodes are equal. If both key and value are equal, return true. You can compare it with yourself
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceofMap.Entry) { Map.Entry<? ,? > e = (Map.Entry<? ,? >)o;if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false; }}Copy the codeOne of the data structures involved in HashMap is an array
// An array of stored elements. The transient keyword indicates that the attribute cannot be serialized
transient Node<K,V>[] table;
Copy the codeRed-black tree, the data structure involved in HashMap
About the characteristics of red-black trees:
Property 1. The node is red or black.
Property 2. The root node is black.
Property 3 Each leaf node (NIL node, empty node) is black.
Property 4 Two children of each red node are black. (No two consecutive red nodes on all paths from each leaf to the root)
Property 5. The path from any node to each of its leaves contains the same number of black nodes.
static final class TreeNode<K.V> extends LinkedHashMap.Entry<K.V> {
TreeNode<K,V> parent; / / the parent node
TreeNode<K,V> left;// Left child node
TreeNode<K,V> right;// Right child node
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red; // Color attributes
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
/** * returns the root of the tree containing this node */
final TreeNode<K,V> root(a) {
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
returnr; r = p; }}Copy the code6.3.3 Basic attributes of HashMap
// Default initial capacity is 16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// The maximum size of the array is 2 to the 30th
static final int MAXIMUM_CAPACITY = 1 << 30;
// Default load factor 0.75
static final float DEFAULT_LOAD_FACTOR = 0.75 f;
// Threshold for list nodes to be converted to red black tree nodes. When the list exceeds 8 nodes, it is converted to red black tree nodes
static final int TREEIFY_THRESHOLD = 8;
// The threshold of the red-black tree node to convert the list node. If the list node is less than or equal to 6, the red-black tree will be converted to a normal list
static final int UNTREEIFY_THRESHOLD = 6;
// If the internal array length is less than 64, the list will not be converted to a red-black tree, but the array will be expanded first. 64 is the minimum length of a table when turning a red-black tree
static final int MIN_TREEIFY_CAPACITY = 64;
// An array that stores elements, always a power of 2
transient Node<k,v>[] table;
// Store a set of specific elements
transient Set<map.entry<k,v>> entrySet;
// The number of key-value mappings stored
transient int size;
// Expand and change the map counter each time
transient int modCount;
// Threshold When the actual size (capacity x fill factor) exceeds the threshold, the system expands the capacity
int threshold;
// Load factor
final float loadFactor;
Copy the code6.3.4 constructors
Construct an empty HashMap with a default initial capacity (16) and a default load factor (0.75)
public HashMap(a) {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
Construct an empty HashMap with the specified initial capacity and default load factor (0.75)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
// Construct an empty HashMap with the specified initial capacity and load factor
public HashMap(int initialCapacity, float loadFactor) {
// If the specified initial capacity is less than 0, an exception is thrown
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// If the specified initial capacity is greater than the array maximum capacity, set the specified capacity to the maximum capacity 2 ^ 30
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// If the specified load factor is less than 0, an exception is thrown
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// Returns the minimum quadratic value greater than initialCapacity as the threshold
this.threshold = tableSizeFor(initialCapacity);
}
// Create a hash table and add all the elements from the other map m to the table
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
Copy the codeTableSizeFor method
// Return the smallest quadratic value greater than initialCapacity, since the array capacity must be raised to the power of 2,
static final int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
// Check whether n is out of bounds, return 2 to the n as the table threshold
return (n < 0)?1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
Copy the code6.3.5, put() and putVal() method source analysis
Put () method source code analysis
// Associate the specified value with the specified key in this mapping. If you map a map that previously contained a key, the old value is replaced.
public V put(K key, V value) {
// Get the hash value of the key,
return putVal(hash(key), key, value, false.true);
}
Copy the codeHash () algorithm source code analysis
static final int hash(Object key) {
int h;
return (key == null)?0 : (h = key.hashCode()) ^ (h >>> 16);
}
Copy the codeWe first get the hash of the key, then move the hash 16 bits to the right, then xor the hash to the original hashCode, and return the result.
The purpose of the hash method is to further obfuscate hashCode, increase its “randomness,” try to reduce hash collisions when inserting a HashMap, or in more technical terms, improve discretization performance. This method is called the “perturbation function” when someone answers.
PutVal () source code analysis
The put method inserts an element by putting val ().
// Arguments: processed hash value, key, value value
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
// Table is an array of elements, and the following resize() method is used only if the table is uninitialized or has a length of 0
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// Calculate the index of the hash value of key in the array, and assign the element corresponding to the index to p,
if ((p = tab[i = (n - 1) & hash]) == null)
// If p is null, there is no element at that location, and it is added directly to the array
tab[i] = newNode(hash, key, value, null);
// If there are already elements in that position
else {
Node<K,V> e; K k;
// Determine whether the key and hash values of p node (stored in a linked list at this time) are equal to the key-value to be added. If they are equal, then p node is the target node to be searched, and assign p node to e node
if(p.hash == hash && ((k = p.key) == key || (key ! =null && key.equals(k))))
e = p;
// If the p node is a node of the red-black tree (i.e. the hash value is not equal, i.e. the key is not equal), add the key-value pair to the red-black tree
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// Check whether the node behind the p node conflicts with the node to be added.
else {
//binCount Counts the number of nodes in the linked list
for (int binCount = 0; ; ++binCount) {
// If there are no nodes after the p node, place the node to be added after the p node.
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
// Check if the number of nodes exceeds 8. If so, call the treeifyBin method to turn the list node into a red-black tree node. -1 is because the loop starts at the next node of the P node
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// If the next node e of node P is not null, check whether the key and hash values of node E are equal to the key-value to be added. If they are equal, node E is the target node to be searched, exit the loop, no longer compare, and perform the operation of overwriting the old value with new value
if(e.hash == hash && ((k = e.key) == key || (key ! =null && key.equals(k))))
break;
// Point p to the next node, which is equivalent to moving p down to the next elementp = e; }}// If e is not empty, the target node exists, overwrites its value with the value passed in, and returns oldValue
if(e ! =null) { // existing mapping for key
V oldValue = e.value;
// If onlyIfAbsent is false or the old value is null
if(! onlyIfAbsent || oldValue ==null)
// The new value overwrites the old value
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// If the actual size is greater than the threshold, expand the capacity
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
Copy the code6.3.6 Resize () source code analysis
Resize () source code analysis
final Node<K,V>[] resize() {
// Assign the original array to oldTab, which is the capacity of the old table
Node<K,V>[] oldTab = table;
// If the expansion method is called for the first time, table is null and oldTab is also null, so oldCap is 0
int oldCap = (oldTab == null)?0 : oldTab.length;
// Threshold is assigned to oldThr. The initial value is 0. OldThr is the threshold of the old table
int oldThr = threshold;
// Define the new table capacity and the new table threshold, starting with 0
int newCap, newThr = 0;
// If the capacity of the old table is greater than 0
if (oldCap > 0) {
// If the capacity of the old table is greater than the maximum capacity (2 ^ 30), then the maximum integer is assigned to the threshold
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// If the current hash bucket array is still smaller than the maximum size after being doubled and oldCap is greater than the default value of 16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // Double the expansion threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// If the capacity of the old table and the threshold of the old table are not greater than 0, the table is not initialized
else { // zero initial threshold signifies using defaults
// assign the default initial capacity DEFAULT_INITIAL_CAPACITY = 16 to the new table capacity newCap
newCap = DEFAULT_INITIAL_CAPACITY;
// Then calculate the new table threshold assigned to newThr, threshold = load factor 0.75x default initial capacity 16 = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// Assign the threshold newThr calculated above to threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// Create a new hash bucket array of 16 lengths
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
// Assign the newly created array to the table, so when put for the first time, the size of the Node array is defined as 16
table = newTab;
// If the old table is not null, expand the capacity and copy the Node object value to the new hash bucket array
if(oldTab ! =null) {
// go through the old watch
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// If there is a node at the index, set the node on that index to null
if((e = oldTab[j]) ! =null) {
oldTab[j] = null;
// If there is only one node at the index, then the index is recalculated into the new array.
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// If the node type is a red-black tree, perform red-black tree expansion
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// If the node type is a linked list node
else { // preserve order
//loHead, loTail are the nodes of the original list with the same index
Node<K,V> loHead = null, loTail = null;
//hiHeadm, hiTail is new list node, old index + old array length
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
// Start traversing the list
do {
// Assign the current node's reference to the next node to the current node
next = e.next;
// If the hash value of node E and the length of the original hash bucket array is 0
if ((e.hash & oldCap) == 0) {
// If loTail is null
if (loTail == null)
// Assign e to loHead
loHead = e;
// If loTail is not null
else
// Assign node e to the next loTail node
loTail.next = e;
// Then assign the node e to loTail
loTail = e;
}
// If the hash value of node E and the length of the original hash bucket array is not 0
else {
// If hiTail is null
if (hiTail == null)
// Assign e to hiHead
hiHead = e;
// If hiTail is not null
else
// Assign e to the next node in hiTail
hiTail.next = e;
// Then assign e to hiTail
hiTail = e;
}
// Exit traversal condition: traversal has reached the last element
} while((e = next) ! =null);
// If loTail is not equal to null after completion of the loop
if(loTail ! =null) {
// Set lotail.next to null
loTail.next = null;
// Put the loHead in the new Hash bucket array [j]
newTab[j] = loHead;
}
// If hiTail is not null
if(hiTail ! =null) {
// Set hitail.next to null
hiTail.next = null;
// Put the hiHead in the new Hash bucket array [j+ the old hash bucket array length]
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// Return the expanded array
return newTab;
}
Copy the code6.3.7 treeifyBin() source analysis
TreeifyBin () source code analysis
Converts a linked list node at the given array index to a red-black tree node
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// If the internal array length is less than 64, the list will not be converted to red-black tree, but the array will be expanded first,MIN_TREEIFY_CAPACITY = 64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
// Calculate the index of the array based on the hash value and assign the node on the index to e, if e is not null
else if ((e = tab[index = (n - 1) & hash]) ! =null) {
//hd represents the head node, tl represents the tail node
TreeNode<K,V> hd = null, tl = null;
do {
// Change e to type TreeNode and assign it to p
TreeNode<K,V> p = replacementTreeNode(e, null);
// If the tail node is null
if (tl == null)
// set the current node p as the head node
hd = p;
else {
// set tl to the precursor of p
p.prev = tl;
// set p to the successor node of tl
tl.next = p;
}
// After the head node is set to p, p is assigned to the tail node tl, and then the next node in the linked list is set to TreeNode, and then p is assigned to p
tl = p;
// If the next node is empty, the list is traversed
} while((e = e.next) ! =null);
// Assign the index position of table to the head node of the newly converted TreeNode. If this node is not empty, the head node (HD) is used as the root node to construct the red-black tree
if((tab[index] = hd) ! =null)
// The header calls the treeify method to build a red-black treehd.treeify(tab); }}Copy the code6.3.8 Source code analysis of Treeify ()
Treeify () source code analysis
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// Assign the node (this) from which this method is called to x, starting with x, to begin traversal
for (TreeNode<K,V> x = this, next; x ! =null; x = next) {
// point the reference to the next node of x to x
next = (TreeNode<K,V>)x.next;
// Set the left and right of the x node to null
x.left = x.right = null;
// If the root node is null (indicating that the red-black tree has not been built), x is assigned to the root node
if (root == null) {
x.parent = null;// The parent of the x node is set to null
x.red = false;// Set the color of the x node to false
root = x;
}
// If the root node is not null (the red-black tree is already built, and the node is being added to the tree)
else {
// Take the key from x and store it in k
K k = x.key;
// Get the hash value of x and store it in h
inth = x.hash; Class<? > kc =null;
// If the current node x is not the root node, the traversal starts from the root node. This traversal has no bounds and can only be jumped from the inside
for (TreeNode<K,V> p = root;;) {
//dir indicates the direction (left and right) and pH indicates the hash value of the current tree node
int dir, ph;
// Retrieve the key of the current tree node and store it in pk
K pk = p.key;
// If the current tree node's hash value is greater than the hash value of the list node (this) on which the Treeify method was called
if ((ph = p.hash) > h)
// This node will be placed to the left of the current tree node
dir = -1;
// If the current tree node's hash value is less than the hash value of the list node (this) on which the Treeify method was called
else if (ph < h)
// This will be placed to the right of the current tree node
dir = 1;
// If the hash values of the two nodes are equal, compare them using Comparable and tieBreakOrder
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// Save the current tree node to XP
TreeNode<K,V> xp = p;
// If dir is greater than 0, the current list node (this/x) is to the right of the current tree node
// If the current tree node is a leaf node, execute x.parent = xp. , treat the current tree node as the parent of the current list node
// Case 2: If the current tree node is not a leaf node, start with the right child node of the current tree node
// If dir is not greater than 0, the current list node (this/x) is to the left of the current tree node
// If the current tree node is a leaf node, execute x.parent = xp. , treat the current tree node as the parent of the current list node
// Case 2: If the current tree node is not a leaf node, start with the right child node of the current tree node
if ((p = (dir <= 0)? p.left : p.right) ==null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;// The current list node is the left child of the current tree node
else
xp.right = x;// The current list node is the right child of the current tree node
//balanceInsertion insertion algorithm is a new method of structuring a red-black tree after a new node is inserted into the tree structure to ensure that the tree retains the red-black tree characteristics. Once balanced, you can move on to the next list node.
root = balanceInsertion(root, x);
break; }}}}// Make sure that if the element in the HashMap array is of type TreeNode, the TreeNode must be the root of the tree and the first of the list.
moveRootToFront(tab, root);
}
Copy the code6.3. Common methods in Map
Add, delete, modify operations:
Object PUT (Object Key,Object value): Adds or modifies the specified key-value to the current map Object
Void putAll(Map M): stores all key-value pairs in M to the current Map
Object remove(): Removes the key-value pair of the specified key and returns value
Void clear(): clears all data in the map
Test code:
Map map = new HashMap<String, Object>();
/ / add
map.put("AA".12);
map.put("BB".13);
map.put("CC".14);
/ / modify
map.put("AA".15);
System.out.println(map);//{AA=15, BB=13, CC=14}
Map map1 = new HashMap<String, Object>();
map.put("DD".16);
map.put("EE".17);
// Put all key-value pairs in map1 into the current map
map.putAll(map1);
System.out.println(map);//{AA=15, BB=13, CC=14, DD=16, EE=17}
// Remove the key-value pair for the specified key and return value
map.remove("AA");
map.remove("BB".13);
System.out.println(map);//{CC=14, DD=16, EE=17}
// Clear all data in the current map
map1.clear();
System.out.println(map1);/ / {}
Copy the codeElement query operations:
Object GET (Object key): Obtains the value corresponding to the specified key
Boolean containsKey(Object Key): Specifies whether to contain the specified key
Boolean containsValue(Object value): Specifies whether to contain the specified value
Int size(): Returns the number of key-value pairs in the map
Boolean isEmpty(): checks whether the current map isEmpty
Boolean equals(Object obj): Checks whether map and Object obj are equal
Test code:
Map map = new HashMap<String, Object>();
Map map1 = new HashMap<String, Object>();
map.put("AA".12);
map.put("BB".13);
map.put("CC".14);
map.put("DD".16);
map.put("EE".17);
// Get the value of the specified key
System.out.println(map.get("BB"));/ / 13
System.out.println(map.get("DD"));/ / 16
// Whether to contain the specified key
System.out.println(map.containsKey("AA"));//true
System.out.println(map.containsKey("FF"));//false
// Whether to include the specified value
System.out.println(map.containsValue(12));//true
System.out.println(map.containsValue(18));//false
// Return the number of key-value pairs in the map
System.out.println(map.size());/ / 5
System.out.println(map1.size());/ / 0
// Check whether the current map is empty
System.out.println(map.isEmpty());//false
System.out.println(map1.isEmpty());//true
// Determine whether map and obj are equal
Map map2 = new HashMap<String, Object>();
map2.put("AA".12);
map2.put("BB".13);
map2.put("CC".14);
map2.put("DD".16);
map2.put("EE".17);
System.out.println(map.equals(map2));//true
Copy the codeTo traverse a Map:
Set keySet(): Returns the Set of all keys
Collection Values (): Returns a Collection of all values
Set entrySet(): Returns a Set of all key-value pairs
Test code:
Map map = new HashMap<String, Object>();
map.put("AA".12);
map.put("BB".13);
map.put("CC".14);
map.put("DD".16);
map.put("EE".17);
// Return a Set of all keys
Set set = map.keySet();
// Call the iterator of Set to iterate
Iterator iterator = set.iterator();
// iterate over all keys
while (iterator.hasNext()){
System.out.println(iterator.next());//AA BB CC DD EE
}
// Return a Collection of all values
Collection values = map.values();
// Call the iterator of the Collection to iterate
Iterator iterator1 = values.iterator();
// Iterate over all values
while (iterator1.hasNext()){
System.out.println(iterator1.next());//12 13 14 15 16 17
}
// Return the Set of all key-value pairs
Set entrySet = map.entrySet();
// Call the iterator of Set to iterate
Iterator iterator2 = entrySet.iterator();
// Iterate over all key-value pairs
while (iterator2.hasNext()){
Object next = iterator2.next();
Map.Entry map1 = (Map.Entry) next;
System.out.println(map1);//AA=12 BB=13 CC=14 DD=16 EE=17
}
Copy the code6.4 TreeMap two kinds of sorting implementation
Natural order Comparable
Custom classes:
package map;
public class User implements Comparable{
private String name;
private int age;
public User(a){}public User(String name, int age) {
this.name = name;
this.age = age;
}
public String getName(a) {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge(a) {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString(a) {
return "User{" +
"name='" + name + '\' ' +
", age=" + age +
'} ';
}
@Override
public int compareTo(Object o) {
if (o instanceof User){
User user = (User) o;
// Sort the names from largest to smallest
int compare = -this.name.compareTo(user.name);
// If the name is different, return it directly
if(compare ! =0) {return compare;
// If the names are the same, then sort by age from youngest to oldest
}else {
return Integer.compare(this.age, user.age); }}else {
throw new RuntimeException("Type exception cannot be compared"); }}}Copy the codeTest code:
TreeMap<User, Integer> map = new TreeMap<>();
User user1 = new User("wanli".11);
User user2 = new User("shengming".12);
User user3 = new User("yumo".13);
map.put(user1,1);
map.put(user2,2);
map.put(user3,3);
Set<Map.Entry<User, Integer>> entrySet = map.entrySet();
Iterator<Map.Entry<User, Integer>> iterator = entrySet.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
Copy the codeCustomize the sort Comparator
Test code:
TreeMap<User, Integer> map = new TreeMap<>(new Comparator<User>() {
@Override
public int compare(User o1, User o2) {
// Sort by age
return-Integer.compare(o1.getAge(), o2.getAge()); }}); User user1 =new User("wanli".11);
User user2 = new User("shengming".12);
User user3 = new User("yumo".13);
map.put(user1,1);
map.put(user2,2);
map.put(user3,3);
Set<Map.Entry<User, Integer>> entrySet = map.entrySet();
Iterator<Map.Entry<User, Integer>> iterator = entrySet.iterator();
while (iterator.hasNext()){
System.out.println(iterator.next());
}
Copy the code7. Use of the Collections utility class
Collections is a utility class that operates on Collections of sets, lists, maps, and so on.
Collections provides a series of static methods for sorting, querying, and modifying collection elements, as well as methods for immutability and synchronization control of collection objects.
7.1. Common methods
Sort (static) :
-
Reverse (List): Reverses the order of elements in a List
-
Shuffle (List): Randomly sorts the elements in the List
-
Sort (List): Sort the elements of the specified List collection in ascending order according to their natural order
-
Sort (List, Comparator): Sorts List collection elements in the order produced by the specified Comparator
-
Swap (List, int, int): Swaps the elements at I and j in the specified List
Method test code:
ArrayList list = new ArrayList();
list.add(2);
list.add(12);
list.add(22);
list.add(31);
list.add(6);
//everse(List): reverses the order of the elements in the List
Collections.reverse(list);
System.out.println(list);//[6, 31, 22, 12, 2]
Shuffle (List): Sorts the elements in the List randomly
Collections.shuffle(list);
System.out.println(list);//[12, 6, 22, 31, 2]
//sort(List): Sort the elements of the specified List in ascending order according to their natural order
Collections.sort(list);
System.out.println(list);//[2, 6, 12, 22, 31]
//sort(List, Comparator): Sorts the List collection elements in the order produced by the specified Comparator
ArrayList list1 = new ArrayList();
User user1 = new User("wanli".3);
User user2 = new User("wanli".60);
User user3 = new User("wanli".24);
User user4 = new User("wanli".18);
list1.add(user1);
list1.add(user2);
list1.add(user3);
list1.add(user4);
Collections.sort(list1, new Comparator<User>() {
@Override
public int compare(User o1, User o2) {
// Sort by age from youngest to oldest
returnInteger.compare(o1.getAge(),o2.getAge()); }}); System.out.println(list1);//swap(List, int, int): swaps the elements at subscript I and j in the specified List
Collections.swap(list,2.3);
System.out.println(list);//[2, 6, 22, 12, 31]
Copy the codeFind and replace
-
Object Max (Collection): Returns the largest element in a given Collection based on the natural order of the elements
-
Object Max (Collection, Comparator): Returns the largest elements in a given set in the order specified by the Comparator
-
Object min(Collection): Returns the smallest element in a given Collection according to the natural order of the elements
-
Object min(Collection, Comparator): Returns the smallest elements in a given set in the order specified by the Comparator
-
Int frequency(Collection, Object): Returns the number of occurrences of the specified element in the specified Collection
-
Void copy(List dest,List SRC): Copies the contents of SRC into dest
-
Boolean replaceAll(List List, Object oldVal, Object newVal): replaceAll old List values with new values
Method test code:
List list = new ArrayList();
list.add(2);
list.add(12);
list.add(22);
list.add(22);
list.add(31);
list.add(6);
//Object Max (Collection): Returns the largest element in a given Collection according to the natural order of the elements
System.out.println(Collections.max(list));/ / 31
//Object min(Collection): Returns the smallest element in a given Collection according to the natural order of the elements
System.out.println(Collections.min(list));/ / 2
ArrayList list1 = new ArrayList();
User user1 = new User("wanli".3);
User user2 = new User("wanli".60);
User user3 = new User("wanli".24);
User user4 = new User("wanli".18);
list1.add(user1);
list1.add(user2);
list1.add(user3);
list1.add(user4);
//Object Max (Collection, Comparator): Returns the largest element in a given set in the order specified by the Comparator
System.out.println(Collections.max(list1, new Comparator<User>() {
@Override
public int compare(User o1, User o2) {
// Sort by age
return-Integer.compare(o1.getAge(), o2.getAge()); }}));//User{name='wanli', age=3}
//Object min(Collection, Comparator): Returns the smallest elements in a given set in the order specified by the Comparator
System.out.println(Collections.min(list1, new Comparator<User>() {
@Override
public int compare(User o1, User o2) {
// Sort by age
return-Integer.compare(o1.getAge(), o2.getAge()); }}));//User{name='wanli', age=60}
//int frequency(Collection, Object): returns the frequency of occurrences of the specified element in the specified Collection
System.out.println(Collections.frequency(list, 22));/ / 2
//void copy(List dest,List SRC): copies the contents of SRC into dest
List dest = Arrays.asList(new Object[list.size()]);
System.out.println(dest);//[null, null, null, null, null, null]
Collections.copy(dest,list);
System.out.println(list);//[2, 12, 22, 22, 31, 6]
System.out.println(dest);//[2, 12, 22, 22, 31, 6]
// Boolean replaceAll(List List, Object oldVal, Object newVal): replaceAll old values of List with new values
Collections.replaceAll(list,22.10);
System.out.println(list);//[2, 12, 10, 10, 31, 6]
Copy the codeSynchronization control
The Collections class provides multiple synchronizedXxx() methods that enable a specified collection to be wrapped as a thread-synchronized collection, thereby addressing thread-safety issues when the collection is concurrently accessed by multiple threads.
synchronizedList()
synchronizedSet()
synchronizedMap()
SynchronizedList () Example:
public class ListTest {
public static void main(String[] args) {
List<String> list = Collections.synchronizedList(new ArrayList<>());
for (int i = 1; i < 10; i++) {
new Thread(() -> {
list.add(UUID.randomUUID().toString().substring(0.5)); System.out.println(list); }, String.valueOf(i)).start(); }}}Copy the code