How to use java data structure to write code
Array data structure
Initialization of arrays
public static void main(String[] args) {
int[] arrays = new int[5]; // Define and open up an array of length 3
// You can write the above code in two sentences
int[] array = null; // Declare a variable of length int [] that takes up a chunk of memory and does not allocate an initial value.
array = new int[5]; // Create an array of length 5 and assign the address of the array to the variable arrays.
}(Regardless of the type of array used, the array identifier is actually just a reference pointing to a real object created in the heap, Int[] A =new int[10];new is instantiated, opens up memory space, elements of the basic data type are assigned initial values, and the length of the array cannot be changed after it is set up, but still Can be reassigned)
There are two variables defined as follows:
1 int[] zero = new int[0];
2 int[] nil = null;
What is the difference between the two definitions?
zero An array of length 0, we call it "empty array", empty array is also an object, only contains the number of elements 0.
nil is an empty reference to an array type.
Assuming that a method returns an array, if it returns null, the calling method must first determine whether it returns NULL to further process the returned array, and if it returns an empty array, no null reference checking is required. In view of this, when the method of returning an array has no result, we usually return an empty array instead of null, which is more convenient for the function caller.
Attachment:
Why do you define an array A and then report nullpoint erexception with A. length < 1? Just define an array, without instantiation, just like you and your wife took a name for your child before you wanted a child, that is, a, but when you were asked about your child for several months, you must have answered. Don't come out, because your wife is not pregnant, so it's empty.
Conversion of Arrays and Sets
To convert an integer array to a collection, you must use the original type. It is not possible to convert int [] directly into a collection, because the parameters of the asList() method must be objects. You should first convert int [] into Integer []. The same is true for arrays of other primitive types, which must first be converted into arrays of corresponding wrapper class types.
Array to list
Arrays.asList() returns a fixed-size list supported by a specified array. So you can't do Add, Remove, etc.
List = new Array List (Arrays. asList (userid)); this is all right.
public class Array {
public static void main(String[] args) {
String[] str = new String[]{"zyy", "zxx", "zww"};
List<String> list = new ArrayList<>(Arrays.asList(str));
//List<String> list = new ArrayList<>(Arrays.asList("zyy", "zxx", "zww"));
list.add("whh");
System.out.println("ArrayList Does it include:" + list.contains("whh"));
Set<String> set = new HashSet<>(Arrays.asList(str));
System.out.println("aggregate set Does it include:" + set.contains("wyy"));
}
}
public static void main(String[] args) {
String[] userid = {"aa","bb","cc"};
List<String> userList = new ArrayList<String>();
Collections.addAll(userList, userid);
System.out.println(userList.toString());
}
list rotation array
Object[] objs = strList.toArray();
If you want to become a String array, you need to type strongly.
String[] strs = (String[]) strList.toArray(new String[0]);
You can also specify size:
String[] strs = strList.toArray(new String[strList.size()]);
public static void main(String[] args) {
List<String> list = new ArrayList<String>();
list.add("1");
list.add("2");
String[] arr = (String[]) list.toArray(new String[list.size()]);
System.out.println(arr.toString());
}
How to see if an array contains an element
public static void main(String[] args) {
String[] str = new String[]{"zyy", "zxx", "zww"};
System.out.println("Does the string contain:" + Arrays.toString(str).contains("zyy"));
System.out.println("Does the string contain:" + Arrays.toString(str).contains("wyx"));
}
The binary Search () method of the Array class - - searching a specified array with a binary search method - - returning the index value of the element to be searched - - applies to all types of Arrays
---- Arrays must be sorted before invocation (through sort() method) -- If the array contains multiple elements with specified values, there is no guarantee which one is found.
1)Arrays.binarySearch(Object[], Object key);
If key is included in the array, return the index value; otherwise return "- 1" or "-" (insertion point)
Insertion point: The point at which the search key will be inserted into the array, that is, the first element index greater than this key
2)Arrays.binarySearch(Object[], int fromIndex,int toIndex,Object key);
The search ranges from fromIndex to (toIndex-1)
Exception: If the specified range is greater than or equal to the length of the array, an ArrayIndexOutOfBoundsException exception is reported
public static void main(String[] args) {
String str[] = new String[]{"ab","cd","ef","gh"};
Arrays.sort(str); //Arrays must be sorted first
int index1 = Arrays.binarySearch(str,"cd");
int index2 = Arrays.binarySearch(str,"de");
//Return to insertion point
int index3 = Arrays.binarySearch(str,0,2,"cd");
System.out.println(index1);
System.out.println(index2);
System.out.println(index3);
}
Replacement Array
public static void main(String[] args) {
int arr1[] = new int[5];
int arr2[] = new int[5];
Arrays.fill(arr1,7); //Fill in and replace arrays with the same value
Arrays.fill(arr2,0,3,7); //Designated scope
System.out.println(arr1.toString());
System.out.println(arr2.toString());
}
Merge arrays
System provides a static method, arraycopy(), which we can use to replicate between arrays.
Its function prototype is:
public static void arraycopy(Object src,int srcPos,Object dest,int destPos,int length)1
src: Source array;
srcPos: The starting position of the source array to be copied;
dest: Destination array;
destPos: The starting position of the destination array placement;
Length: The length of the copy.
Note: Both src and dest must be arrays of the same type or convertible type.
public static void main(String[] args) {
Integer[] a = { 1, 2, 3, 4, 5 };
Integer[] b = { 6, 7, 8, 9, 10 };
Integer[] c = new Integer[a.length + b.length];
System.arraycopy(a, 0, c, 0, a.length);
System.arraycopy(b, 0, c, a.length, b.length);
System.out.println(c.toString());
}
public static void main(String[] args) {
//Array defined as length 5
int scores[]=new int[]{57,81,68,75,91};
//Define a new array to copy five elements from the scores array
//At the same time, three memory spaces are reserved for future development and use.
int[] newScores=(int[])Arrays.copyOf(scores,8);
System.out.println("\n The new replicated array is as follows:"+newScores.toString());
}
public static void main(String[] args) {
int scores[]=new int[]{57,81,68,75,91,66,75,84};
//Copy the first five elements of the source array into the newScores array
int newScores[]=(int[])Arrays.copyOfRange(scores,0,5);
System.out.println("\n The new replicated array is as follows:");
System.out.println("\n The new replicated array is as follows:"+newScores.toString());
}
public static void main(String[] args) {
//Define the source array, length 8
Integer scores[]=new Integer[]{100,81,68,75,91,66,75,100};
//Copy arrays to cast Object type to int []type
Integer newScores[]=(Integer[])scores.clone();
System.out.println("\n The new replicated array is as follows:"+newScores.toString());
}
Array sorting
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
public class TestArraySort {
public static void main(String[] args) {
Integer[] a = {9, 8, 7, 2, 3, 4, 1, 0, 6, 5};
//Descending order and descending order
Arrays.sort(a,Collections.reverseOrder());
System.out.println(a.toString());
//Default ascending order
Arrays.sort(a);
System.out.println(a.toString());
//Comparator sort
Arrays.sort(a,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o2-o1;
}
});
System.out.println(a.toString());
}
}
Set and Mapping Data Structure
| Interface | Subinterface | Is there order? | Allow element duplication |
|---|---|---|---|
| Collection | no | ||
| List | ArrayList | no | yes |
| LinkedList | no | yes | |
| Vector | no | yes | |
| Set | AbstractSet | no | no |
| HashSet | no | no | |
| TreeSet | Yes (with binary sort trees) | no | |
| Map | AbstractMap | no | Using key-value to map and store data, key must be unique and value can be repeated |
| HashMap | no | ||
| TreeMap | Yes (with binary sort trees) | Using key-value to map and store data, key must be unique and value can be repeated |
List collection
Common operations of Arraylist
import java.util.ArrayList;
import java.util.Iterator;
public class ArrayListTest {
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Integer> mylist = new ArrayList<Integer>();
// Aralist before adding any number
System.out.print(mylist.size());
mylist.add(1);
mylist.add(2);
mylist.add(3);
mylist.add(4);
mylist.add(5);
mylist.add(6);
System.out.print(mylist.size());
// There are three ways to traverse
System.out.println();
// Traversing through index values
for (int i = 0; i < mylist.size(); i++) {
System.out.print(mylist.get(i) + " ");
}
System.out.println();
// Traversing through the for loop remember the enhanced for loop we talked about?
for (Integer num : mylist) {
System.out.print(num + " ");
}
System.out.println();
// Traverse through iterators
System.out.println("Traverse through iterators");
Iterator<Integer> it = mylist.iterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
// Here are two ways to arraylist to array
// The first is
Integer[] integer1 = new Integer[mylist.size()];
mylist.toArray(integer1);
// Second
Integer[] integer2 = mylist.toArray(new Integer[0]);
// Here are some common operations
mylist.add(6);
mylist.remove(1);// Remove something at an index
mylist.remove((Object) 3);// Remove an object
System.out.println("Does it contain 5" + mylist.contains(5));// Determine whether it contains 5
mylist.clear();// empty
System.out.println("Is it empty?" + mylist.isEmpty());// Determine whether it contains 5
}
}
The ArrayList array returned is a fixed-length list, and we can only view or modify it, but we can't add or delete it.
From the source code, we find that there is no such method as add() or remove(), if we add or delete it, we will call the corresponding method of its parent AbstractList, and the method tracing the parent will eventually throw an Unsupported OperationException exception. As follows:
1 String[] str = {"a","b","c"};
2 List<String> listStr = Arrays.asList(str);
3 listStr.set(1, "e");//Modifications can be made
4 System.out.println(listStr.toString());//[a, e, c]
5 listStr.add("a");//Adding elements will cause errors in java.lang.Unsupported OperationException Given array data, how to quickly get a List list that can be added, deleted and modified
1 String[] str = {"a","b","c"};
2 List<String> listStr = new ArrayList<>(Arrays.asList(str));
3 listStr.add("d");
4 System.out.println(listStr.size());//4set and add operations
public static void main(String[] args) {
ArrayList<String> arrayList=new ArrayList<String>();
arrayList.add("Zhang San");
arrayList.add("Li Si");
pringArrayList(arrayList);
// Insert the specified element into the specified location in this list.
arrayList.add(1,"Xiao Zhangsan");
pringArrayList(arrayList);
// Replace the element at the specified location in this list with the specified element.
arrayList.set(2, "Xiao Li Si");
pringArrayList(arrayList);
// Remove elements from this list at specified locations.
arrayList.remove(0);
pringArrayList(arrayList);
}import java.util.ArrayList;
public class test1 {
public static void main(String[] args) {
ArrayList<String> list1 =new ArrayList<String>();
//Add elements like dynamic arrays
list1.add("a");
list1.add("b");
list1.add("c");
list1.add("d");
System.out.println(list1);
//Adding elements at specified locations
list1.add(4, "e");
System.out.println(list1);
//Adding all elements of an array to another array
ArrayList<String> list2 =new ArrayList<String>();
list2.add("f");
System.out.println(list2);
//Add all the elements in Array 1 to Array 2
list2.addAll(list1);
System.out.println(list2);
//Get the second element in list2
System.out.println("lit2 The second element in"+list2.get(1));
//Traversing through all elements in list2
for(int i=0;i<=list2.size()-1;i++){
System.out.println(list2.get(i));
}
//Add all the elements in Array 1 to the pointer in Array 2
list2.addAll(0, list1);
System.out.println(list2);
//Delete elements at specified locations in an array
list2.remove(1);
System.out.println(list2);
//Delete the specified content
list2.remove("b");
//Delete multiple elements
list2.removeAll(list1);//All elements that exist in list21 will be deleted
System.out.println(list2);
//Clear the list collection
list1.clear();
System.out.println("@@"+list1);
//Modify list collection
list2.set(0, "B");
System.out.println(list2);
}
}
subList interception set
The function is to return the element view between the subscripts starting from the fromIndex (including) and the subscripts ending from the toIndex (excluding). As follows:
1 ArrayList<String> list = new ArrayList<>();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5
6 List<String> subList = list.subList(0, 1);
7 for(String str : subList){
8 System.out.print(str + " ");//a
9 }Here comes the SubList class, which is also an internal class in ArrayList.
Note: The view of the original collection is returned, that is, if you modify or add operations to the collection from the subList, the same operation will happen to the original collection.
1 ArrayList<String> list = new ArrayList<>();
2 list.add("a");
3 list.add("b");
4 list.add("c");
5
6 List<String> subList = list.subList(0, 1);
7 for(String str : subList){
8 System.out.print(str + " ");//a
9 }
10 subList.add("d");
11 System.out.println(subList.size());//2
12 System.out.println(list.size());//4. The length of the original set also increasesIf you want to come out of a collection independently, the solutions are as follows:
List<String> subList = new ArrayList<>(list.subList(0, 1));
Notes on deleting elements for loops
Delete all data with string b in the set
The underlying structure of ArrayList is the array type. The data structure of ArrayList is characterized by moving forward all the index of the following elements when one element is deleted, while the pointer of the for loop moves down, so the next element is omitted.
The solution is to call back the pointer once when deleting:
for (int i = 0; i < list.size(); i++) {
if("b".equals(list.get(i))) {
list.remove(i);
i--;
}
}public static void main(String[] args) {
List<String> list=new ArrayList<>();
list.add("b");
list.add("e");
list.add("b");
list.add("c");
Iterator it=list.iterator();
while(it.hasNext()) {
if("b".equals(it.next())) {
// Using the remove() method in the iterator, you can delete elements.
it.remove();
}
}
System.out.println(list.toString());
}
java8 streams delete elements in Collections
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
public class Demo {
public static void main(String[] args) {
List<String> strList2 = new ArrayList<>();
strList2.add("a");
strList2.add("ab");
strList2.add("ac");
strList2.add("ad");
strList2.forEach(System.out::print);
System.out.println();
strList2.removeIf(s -> s.equals("a"));
strList2.forEach(System.out::print);
System.out.println();
strList2 = strList2.stream().filter( s -> !s.equals("ac")).collect(Collectors.toList());
strList2.forEach(System.out::print);
System.out.println();
//Let strList2 retain only the data in the strList, which is the intersection of two sets.
List<String> strList = Arrays.asList("a", "b", "aa", "ab", "ba");
strList2.retainAll(strList);
strList2.forEach(System.out::print);
}
}
Common operations of LinkedList
Copies of collections
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
public class LinkedListTest {
public static void main(String[] args) {
LinkedList<String> lList = new LinkedList<String>();
lList.add("1");
lList.add("2");
lList.add("3");
lList.add("4");
lList.add("5");
//deep copy
List<String> dic = new ArrayList<String>(Arrays.asList(new String[lList.size()]));
Collections.copy(dic,lList);
List<String> dest1 = new ArrayList<String>();
Collections.addAll(dest1, new String[lList.size()]);
Collections.copy(dest1, lList);
//shallow copy
List<String> newList = new ArrayList<String>();
newList.addAll(lList);
List<String> newList1 = new ArrayList<String>(lList);
System.out.println("The first element of the list is : " + lList.getFirst());
System.out.println("The last element of the list is : " + lList.getLast());
lList.removeFirst();
lList.removeLast();
System.out.println(lList.toString());
System.out.println(dic.toString());
System.out.println(dest1.toString());
System.out.println(newList.toString());
System.out.println(newList1.toString());
//Delete list elements by scope
dic.subList(2, 5).clear();
System.out.println(dic.toString());
//Find element location
System.out.println(newList.indexOf("2"));
System.out.println(newList.lastIndexOf("2"));
}
}
LikedList is commonly used to simulate data structures such as stacks or queues.
LinkedList simulation stack
public class TestLinkedList {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
while(!queue.isEmpty()) {
Integer poll = queue.poll();
System.out.println(poll);
}
Deque<Integer> deque = new LinkedList<>();
deque.push(1);
deque.push(2);
deque.push(3);
deque.push(4);
deque.push(5);
deque.push(6);
while(!deque.isEmpty()) {
Integer pop = deque.pop();
System.out.println(pop);
}
Deque<Integer> deque2 = new LinkedList<>();
deque2.offerLast(1);
deque2.offerLast(2);
deque2.offerLast(3);
deque2.offerLast(4);
deque2.offerLast(5);
deque2.offerLast(6);
while(!deque2.isEmpty()) {
Integer pop = deque2.pollLast();
System.out.println(pop);
}
}
}Output:
Sometimes we need all the paths between two points in the output graph, which is implemented by stacking.
private List<List<Integer>> path(int w){
List<List<Integer>> retlist = new ArrayList<>();
for(int[] tempForm:totalList) {
List<Integer> list = new ArrayList<>();
Deque<Integer> deque = new LinkedList<>(); //Analog stack
int p = w;
while(p!=-1) {
deque.push(p);//The last node to arrive is like a stack, and the starting node is finally put on the stack.
p = tempForm[p];
}
while(!deque.isEmpty()) {
list.add(deque.pop());//First output the starting node, and finally output the node to be reached.
}
retlist.add(list);
}
return retlist;
}
void showPath(int w) {
assert hasPath(w);
List<List<Integer>> path = path(w);
for(int i=0;i<path.size();i++) {
for(int j=0;j<path.get(i).size();j++) {
System.out.println(path.get(i).get(j));
if(j!=path.get(i).size()-1)
System.out.print(" -> ");
else
System.out.println();
}
}
}
private void DFS(int i,int toIndex) {
// TODO Auto-generated method stub
visited[i] = true;
if(i==toIndex) {
visited[i] = false;
return;
}
for(int item :graph.adj(i)) {
if(!visited[item]) {
form[item] = i; //The record came from that point.
if(item==toIndex) {
visited[i] = false;
int[] temp = Arrays.copyOf(form, form.length);
totalList.add(temp);
}
DFS(item,toIndex);
//form[item] = i;
/*if(item==toIndex) {
int[] temp = Arrays.copyOf(form, form.length);
totalList.add(temp);
Arrays.fill(form, -1);
}*/
}
}
visited[i] = false;
form[i] = -1;
}LinkedList Analog Queue Implementation Width First
Queue<Integer> queue = new LinkedList<Integer>();
3 5 1 2 1 3 1 4 1 5 7 1 3 1 2 1 4 4 6 2 5 3 7 6 1 2 2 3 4 5 3 4 5 6
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class ShortestPath {
static LinkedList<Integer>[] totallist;
static int[] rootLength;
static boolean[] visited;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int test_case = 1;test_case<=T;test_case++) {
int N = sc.nextInt();
int M = N-1;
totallist = new LinkedList[N];
rootLength = new int[N];
visited = new boolean[N];
for(int i=0;i<N;i++) {
totallist[i]=new LinkedList<Integer>();
rootLength[i] = -1;
}
for(int i=0;i<M;i++) {
int s = sc.nextInt();
int e = sc.nextInt();
totallist[s-1].add(e-1);
}
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(0);
visited[0] = true;
rootLength[0] = 0;
while(!queue.isEmpty()) {
Integer top = queue.remove();
for(Integer item:totallist[top]) {
if(!visited[item]) {
queue.add(item);
visited[item]= true;
rootLength[item] = rootLength[top]+1;
}
}
}
Arrays.sort(rootLength);
int max = rootLength[rootLength.length-1];
System.out.println(max+1);
}
}
}Set collection
Set: Elements are out of order (the order of storage and retrieval is not necessarily the same), and elements cannot be repeated.
—— HashSet: The underlying data structure is a hash table. Threads are not safe. Not synchronized.
How does HashSet guarantee element uniqueness?
hashCode and equals are two methods of elements.
If the HashCode value of the element is the same, it will be judged whether equals is true.
If the hashcode value of the element is different, equals will not be called.
Note that the hashcode and equals methods of the element are the methods to determine whether the element exists or not and to delete it.
-TreeSet:
Ordered storage: TreeSet threads are insecure and can sort elements in Set collections
The uniqueness of elements is guaranteed by compare To or comparison method, and elements are stored in the form of binary trees.
set collections are often used for de-duplication
Common operations of HashSet
HashSet is a collection implemented by HashMap. Elements are disordered and cannot be repeated.
import java.util.HashSet;
import java.util.Set;
public class SetTest {
public static void main(String[] args) {
Set<Integer> set = new HashSet<Integer>();
Set<Integer> set2 = new HashSet<Integer>();
for(int i = 0;i<10;i++){
set.add(i);
set2.add(i);
}
//To weigh, there will only be a group of 0-9 in the end.
set.addAll(set2);
System.out.println(set.toString());
//containsAll returns true if the elements in the collection are the same as those in the specified collection
//contains returns true if the specified element exists in the collection, and false if it does not exist.
System.out.println(set.contains(4)+" "+set.containsAll(set2));
//remove deletes the element specified in the collection, and if the element returns true in the collection, the deletion is successful
System.out.println(set.remove((Object)4));
System.out.println(set.toString());
//removeAll deletes elements in a collection that match the elements of the specified collection. If one element of the specified collection returns true in the operated collection, the deletion will be successful; if none of the elements of the specified collection returns false in the collection, the deletion will fail.
System.out.println(set2.removeAll(set));
System.out.println(set2.toString());
}
}
Common operations of TreeSet
TreeSet is the only implementation class of the SortedSet interface, and TreeSet ensures that the collection elements are sorted. TreeSet supports two sorts, natural sort and custom sort, where natural sort is the default sort. Objects of the same class should be added to TreeSet.
Natural Sorting
Natural sorting uses the CompareTo (Object obj) method of sorting elements to compare the size relationships between elements, and then arranges elements in ascending order.
Java provides a Comparable interface, which defines a compareTo(Object obj) method, which returns an integer value and implements the object of the interface to compare sizes.
If the obj1.compareTo(obj2) method returns 0, it means that the two objects being compared are equal. If a positive number is returned, it means that obj1 is larger than obj2, and if it is negative, it means that obj1 is smaller than obj2.
If we always return true for the equals method of the two objects, the compareTo method of the two objects should return 0.
Customized Sorting
Natural sorting is arranged in ascending order according to the size of set elements. If you want to customize the sorting, you should use Comparator interface to implement the int compare(T o1,T o2) method.
Data in Treeset is automatically ordered and null values are not allowed. HashSet collection elements can be null, but can only be put in one null
TreeSet does not support fast random traversal, it can only traverse through iterators!
import java.util.Iterator;
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
TreeSet set = new TreeSet();
set.add("aaa");
set.add("aaa");
set.add("bbb");
set.add("eee");
set.add("ddd");
set.add("ccc");
// Sequential traversal of TreeSet
ascIteratorThroughIterator(set) ;
// Inverse traversal of TreeSet
descIteratorThroughIterator(set);
// Traverse the TreeSet through for-each. No recommendation! This method needs to convert Sets to arrays first
foreachTreeSet(set);
}
// Sequential traversal of TreeSet
public static void ascIteratorThroughIterator(TreeSet set) {
System.out.print("\n ---- Ascend Iterator ----\n");
for(Iterator iter = set.iterator(); iter.hasNext(); ) {
System.out.printf("asc : %s\n", iter.next());
}
}
// Inverse traversal of TreeSet
public static void descIteratorThroughIterator(TreeSet set) {
System.out.printf("\n ---- Descend Iterator ----\n");
for(Iterator iter = set.descendingIterator(); iter.hasNext(); )
System.out.printf("desc : %s\n", (String)iter.next());
}
// Traverse the TreeSet through for-each. No recommendation! This method needs to convert Sets to arrays first
private static void foreachTreeSet(TreeSet set) {
System.out.printf("\n ---- For-each ----\n");
String[] arr = (String[])set.toArray(new String[0]);
for (String str:arr)
System.out.printf("for each : %s\n", str);
}
}
Common API
import java.util.TreeSet;
public class TreeSetTest {
public static void main(String[] args) {
String val;
TreeSet tSet = new TreeSet();
tSet.add("aaa");
tSet.add("aaa");
tSet.add("bbb");
tSet.add("eee");
tSet.add("ddd");
tSet.add("ccc");
// Floor
System.out.printf("floor bbb: %s\n", tSet.floor("bbb"));
// Lower (less than)
System.out.printf("lower bbb: %s\n", tSet.lower("bbb"));
// Ceiling (greater than or equal to)
System.out.printf("ceiling bbb: %s\n", tSet.ceiling("bbb"));
System.out.printf("ceiling eee: %s\n", tSet.ceiling("eee"));
// Ceiling (greater than)
System.out.printf("higher bbb: %s\n", tSet.higher("bbb"));
// subSet()
System.out.printf("subSet(aaa, true, ccc, true): %s\n", tSet.subSet("aaa", true, "ccc", true));
System.out.printf("subSet(aaa, true, ccc, false): %s\n", tSet.subSet("aaa", true, "ccc", false));
System.out.printf("subSet(aaa, false, ccc, true): %s\n", tSet.subSet("aaa", false, "ccc", true));
System.out.printf("subSet(aaa, false, ccc, false): %s\n", tSet.subSet("aaa", false, "ccc", false));
// headSet()
System.out.printf("headSet(ccc, true): %s\n", tSet.headSet("ccc", true));
System.out.printf("headSet(ccc, false): %s\n", tSet.headSet("ccc", false));
// tailSet()
System.out.printf("tailSet(ccc, true): %s\n", tSet.tailSet("ccc", true));
System.out.printf("tailSet(ccc, false): %s\n", tSet.tailSet("ccc", false));
// Delete and return the first element
val = (String)tSet.pollFirst();
System.out.printf("pollFirst=%s, set=%s\n", val, tSet);
// Delete and return the last element
val = (String)tSet.pollLast();
System.out.printf("pollLast=%s, set=%s\n", val, tSet);
}
}
Mapping data structure
Map
—— HashMap: The underlying is the hash table data structure, which allows null values and null keys to be used. This collection is not synchronous. Instead of hashtable, jdk1.2. has high efficiency.
—— TreeMap: The bottom layer is the binary tree data structure. Threads are not synchronized. It can be used to sort keys in a map set.
Map: put/get/remove.
HashMap/HashTable: Hash lists, like Array Lists, are implemented in arrays, which can cause performance degradation if they exceed the initial capacity.
2. LinkedHashMap: It inherits from HashMap, but realizes the linked list structure by rewriting the nested class HashMap.Entry, which has the same capacity problem.
3, Properties: is the inherited HashTable.
The Difference between HashMap and Hashtable
* HashMap is almost equivalent to Hashtable, except that HashMap is non-synchronized and can accept null(HashMap can accept null's key and value, but Hashtable can't).
HashMap is non-synchronized, while Hashtable is synchronized, which means that Hashtable is thread-safe, and multiple threads can share a Hashtable; without proper synchronization, multiple threads cannot share HashMap. Java 5 provides Concurrent HashMap, which is a replacement for HashTable and is more scalable than HashTable.
Another difference is that the Iterator of HashMap is a fail-fast iterator, while the enumerator iterator of Hashtable is not a fail-fast iterator. So when other threads change the structure of HashMap (adding or removing elements), a Concurrent ModificationException will be thrown, but the removal () method of the iterator itself will not throw a Concurrent ModificationException exception. But this is not a certain behavior, depending on JVM. This is also the difference between Enumeration and Iterator.
Because Hashtable is thread-safe and synchronized, it is slower than HashMap in a single-threaded environment. If you don't need synchronization and only need a single thread, using HashMap performs better than Hashtable.
HashMap does not guarantee that the order of elements in a Map is constant over time.
Sort by key or value
public class TestMap {
public static void main(String[] args) {
HashMap<Integer,String> map = new HashMap<>();
map.put(1,"Spider-Man");
map.put(3,"Iron Man");
map.put(3,"Batman");
//The iterator traverses the Map set, noting that iterator.next() can only be used once
HashMap<Integer,String> temp=new HashMap<>();
Iterator<Entry<Integer, String>> iterator = map.entrySet().iterator();
while(iterator.hasNext()) {
Entry<Integer, String> next = iterator.next();
Integer item = next.getKey();
String value = next.getValue();
System.out.println(item+"="+value);
}
//entrySet() traverses the entire map object
Set<Entry<Integer, String>> entrySet = map.entrySet();
for(Map.Entry<Integer, String> entry :map.entrySet()) {
System.out.println("key= " + entry.getKey() + " and value= " + entry.getValue());
}
//keySet() traverses all key s
Set<Integer> keySet = map.keySet();
for(Integer item :keySet) {
String value = map.get(item);
temp.put(item, value);
}
map.clear();
map.putAll(temp);
System.out.println(map);
//values() traverses all value s
Collection<String> values = map.values();
for(String value :values) {
System.out.println("value= " + value);
}
//map comparators sort by value or key
Set<Entry<Integer, String>> entrySet2 = map.entrySet();
List<Map.Entry<Integer, String>> list = new ArrayList<>(entrySet2); //First, turn to list collection
Collections.sort(list, new Comparator<Map.Entry<Integer, String>>() {
@Override
public int compare(Entry<Integer, String> o1, Entry<Integer, String> o2) {
// TODO Auto-generated method stub
/*return o2.getValue().compareTo(o1.getValue());*/ //Inversion according to value
return o2.getKey().compareTo(o1.getKey()); //// Default ascending order according to key inversion
}
});
for(Entry<Integer, String> mapping:list) { //Traversing list sets
System.out.println(mapping.getKey()+":"+mapping.getValue());
}
}
}
Output:
Supplementary lambda expression comparator
Set<Entry<Integer, String>> entrySet2 = map.entrySet();
List<Map.Entry<Integer, String>> list = new ArrayList<>(entrySet2); //First, turn to list collection
Collections.sort(list,(O1,O2)->O1.getValue().compareTo(o2.getValue()));
for(Entry<Integer, String> mapping:list) { //Traversing list sets
System.out.println(mapping.getKey()+":"+mapping.getValue());
}Other methods
import java.util.HashMap;
import java.util.Map;
public class HashMapTest {
public static void main(String [] args) {
Map<Integer, String> map = new HashMap<Integer, String>();
map.put(1, "Barcelona");
map.put(2, "RealMadrid");
map.put(3, "ManchesterUnited");
map.put(4, "AC milan");
map.put(5, null);
map.put(null, null);
//Map. put (null,'Chelsea'); and // can run keys that are empty (if the keys are the same, the latter overrides the former)
System.out.println(map);
System.out.print(map.keySet()+" "); //All keys in a collection are returned as Set sets
System.out.println();
System.out.print(map.values()+" "); //All keys in a collection are returned as Collection collections
System.out.println();
System.out.println("Collection size:"+map.size());
System.out.println("Does it contain the key?:"+map.containsKey(2));//Return boolean
System.out.println("Does it contain this value?:"+map.containsValue("Barcelona"));//Return boolean
System.out.println(map.isEmpty()); //If no key-value mapping is included, true is returned
map.remove(5); //Delete mapping relationships
System.out.println(map);
HashMap hashMap = new HashMap();
hashMap.put("1", "demo1");
hashMap.put("2", "demo2");
Object obj = hashMap.clone();
System.out.println("hashMap copy"+obj);
HashMap hm = (HashMap)obj;
System.out.println(hm.get("1"));
hm.remove("1");
System.out.println(hm.toString());
}
}
Four traversal methods of HashMap
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;
public class HashMapTest {
public static void main(String[] args) {
Map<String,String> map=new HashMap<String,String>();
map.put("1", "value1");
map.put("2", "value2");
map.put("3", "value3");
map.put("4", "value4");
//The first kind: common use, secondary value
System.out.println("\n adopt Map.keySet ergodic key and value: ");
for(String key:map.keySet())
{
System.out.println("Key: "+key+" Value: "+map.get(key));
}
//Second
System.out.println("\n adopt Map.entrySet Use iterator ergodic key and value: ");
Iterator map1it=map.entrySet().iterator();
while(map1it.hasNext())
{
Map.Entry<String, String> entry=(Entry<String, String>) map1it.next();
System.out.println("Key: "+entry.getKey()+" Value: "+entry.getValue());
}
//Third: Recommendation, especially when the capacity is large
System.out.println("\n adopt Map.entrySet ergodic key and value");
for(Map.Entry<String, String> entry: map.entrySet())
{
System.out.println("Key: "+ entry.getKey()+ " Value: "+entry.getValue());
}
//Fourth
System.out.println("\n adopt Map.values()Traveling through all value，But not traversal key");
for(String v:map.values())
{
System.out.println("The value is "+v);
}
}
}
TreeMap
import java.util.Map.Entry;
import java.util.Set;
import java.util.SortedMap;
import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;
public class TreeMapTest {
public static void main(String[] args) {
TreeMap treeMap = new TreeMap();
treeMap.put("1", "demo1");
treeMap.put("2", "demo2");
treeMap.put("3", "demo3");
treeMap.put("4", "demo4");
System.out.println("treeMap Elements in a collection"+treeMap);
TreeMap tmMap = new TreeMap(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
// TODO Auto-generated method stub
return o2.compareTo(o1);//Reverse order
}
});
tmMap.put("1", "demo1");
tmMap.put("2", "demo2");
tmMap.put("3", "demo3");
System.out.println("tmMap Elements in a collection"+tmMap);
//Returns all the keys of the collection and is in reverse order
Set set = treeMap.descendingKeySet();
System.out.println("Returns all of the collection Key，And it's in reverse order."+" "+set);
//Return the set in reverse order
Map map = treeMap.descendingMap();
System.out.println(map);
//Returns the element of the smallest Key in the collection
Entry firstentry = treeMap.firstEntry();
System.out.println("Return the smallest set Key Elements of"+" "+firstentry);
//Returns the key of the smallest Key in the collection
Object firstKey = treeMap.firstKey();
System.out.println("Return the smallest set Key Of key"+" "+firstKey);
//Returns an element whose specified Key is greater than or equal to the minimum value, and if not, returns null.
Entry entry = treeMap.ceilingEntry("2.5");
System.out.println(entry.getKey()+"==="+entry.getValue());
entry = treeMap.ceilingEntry("4");
System.out.println(entry);
// Returns the key whose specified Key is greater than or equal to the minimum value, and if not, returns null.
Object obj = treeMap.ceilingKey("2.5");
System.out.println("Returns the specified Key Greater than or equal to the minimum value Key"+" "+obj);
obj = treeMap.ceilingKey("5");
System.out.println("Returns the specified Key Greater than or equal to the minimum value Key"+" "+obj);
//Contrary to the ceilingEntry() method, it returns the largest Key element less than or equal to the key.
Entry floorEntry = treeMap.floorEntry("2.5");
System.out.println("Return less than or equal to key Maximum Key Elements of"+" "+floorEntry);
//Returns the key of the largest key less than or equal to the key
Object floorKey = treeMap.floorKey("2.5");
System.out.println("Return less than or equal to key Maximum Key Of key"+" "+floorKey);
//Returns all elements whose Key is less than toKey
SortedMap headMap = treeMap.headMap("2.5");
System.out.println("Return Key less than toKey All elements"+" "+headMap);
//When inclusive is true, it returns all elements whose Key is less than or equal to toKey.
SortedMap headMap1 = treeMap.headMap("2",true);
System.out.println("Return Key Less than or equal to toKey All elements"+" "+headMap1);
SortedMap headMap2 = treeMap.headMap("2",false);
System.out.println("Return Key Less than or equal to toKey All elements"+" "+headMap2);
//Returns an element whose Key is greater than the key
Entry entryKey = treeMap.higherEntry("2");
System.out.println("Return Key greater than key Elements of"+" "+entryKey);
//Returns all keys whose Key is greater than the key
Object key = treeMap.higherKey("2");
System.out.println("Return Key greater than key Of Key"+" "+key);
//Returns the largest element of Key
Entry lastEntry = treeMap.lastEntry();
System.out.println("Return Key The biggest element"+" "+lastEntry);
//Returns the largest element less than key
Entry lowerEntry = treeMap.lowerEntry("2.5");
System.out.println("Return less than key Maximum element"+" "+lowerEntry);
//It depends on true or false to intercept elements from fromKey to toKey in a collection, or whether they intercept themselves.
Map map2 = treeMap.subMap("1", true,"4",false);
System.out.println("Interception set Key from fromKey reach toKey Elements of"+" "+map2);
//To intercept elements from fromKey to toKey in a collection, including fromKey, excluding toKey
Map map3 = treeMap.subMap("1","4");
System.out.println(map3);
//Intercept all elements whose Key is greater than or equal to fromKey
SortedMap tailMap = treeMap.tailMap("2");
System.out.println("Intercept Key Greater than or equal to fromKey All elements"+" "+tailMap);
SortedMap tailMap2 = treeMap.tailMap("2",false);
System.out.println("Intercept Key greater than fromKey All elements "+" "+tailMap2);
//Delete the smallest key element
treeMap.pollFirstEntry();
System.out.println("delete key The smallest element"+" "+treeMap);
//Delete the element with the largest Key
treeMap.pollLastEntry();
System.out.println("Delete maximum Key Elements of"+" "+treeMap);
}
}
