Directory
- Data structure (red-black tree)
-
- red and black rules
- Red-black tree adding node rules
- set set
- summary
-
- HashSet
- Three problems with HashSet
- LinkedHashSet
-
- summary
- TreeSet
-
- TreeSet collection default rules
- Sorting rules (first sorting method)
- Method 2
-
- practise
- Xiaolian
- Summarize
- Summary: How to choose when using collections
Data structure (red-black tree)
Red and black rules
The descendant node is, for example, 13 root nodes. 8 below 13 and 17 above are descendant leaf nodes
A simple path is a simple path, for example, from 13 to 8 to 11 to nil. But if 13 to 8 appears, then 8, then 13, then 13 to 8, this is not a simple path
Add node rules to red-black tree
set collection
public static void main(String[] args) {<!-- -->
Set<String>s=new HashSet<>();
s.add("Zhang San");
s.add("Li Si");
s.add("王五");
s.add("Lao Liu");
//Added elements cannot be repeated. If repeated, no result will be printed.
//Details: add has a return value. It will first determine whether this element has been added.
//Print
Iterator<String> iterator = s.iterator();
while (iterator.hasNext()){<!-- -->
iterator.next();
}
System.out.println(s);//[Zhang San, Li Si, Wang Wu, Lao Liu]
//Enhance for traversal
for (String s1 : s) {<!-- -->
System.out.print(s1);//Zhang San Li Si Wang Wu Lao Liu
}
System.out.print("______________");
//lambda expression
s.forEach(new Consumer<String>() {<!-- -->
@Override
public void accept(String s2) {<!-- -->
System.out.print(s2);
}
});
//lambda simplified
s.forEach(s3-> System.out.print(s3));
}
Summary
Simple memory: hash: messy->disordered; linked: chain->ordered; tree: tree->sortable
HashSet
Hash value: integer representation of the object
The probability of a hash collision is so small that it can be ignored.
public static void main(String[] args) {<!-- -->
//Create object
Student s1=new Student("Zhang San",18);
Student s2=new Student("Zhang San",18);
//System.out.println(s1.hashCode());//488970385
//System.out.println(s2.hashCode());//1209271652
//This is without overriding the hash method. The hash values calculated for different objects are different.
System.out.println(s1.hashCode());
System.out.println(s2.hashCode());
//24022538
//24022538
//The hash method has been rewritten. As long as the attribute values of different objects are the same, the calculated hash values are the same.
}
The method of hash table to ensure the uniformity of elements. When you want to add a new element, you find that there is an element at the position to be added and there are two linked lists. Compare equals one by one. If they are all different, the new one will be added. Element. If comparing the third one and finding that the third one is the same, the element to be added will be discarded
Loading factor 0.75 is the opportunity for expansion. Taking this question as an example, when the array stores 16×0.75=12 elements, the array will expand to twice its original size
When the length of the linked list is too long and exceeds 8 and the array length is greater than or equal to 64, the current linked list will automatically be converted into a red-black tree.
Three questions about HashSet
Why does HashSet have no index?
Because the underlying structure is not unique (that is, sometimes linked lists are used to store data and sometimes red-black trees are used). There are too many structures, which makes it difficult to determine the index, so the index mechanism is abandoned
What mechanism does HashSet use to ensure deduplication?Rewrite the equals method and the Hash method
Why is the order of storage and retrieval of HashSet different?Because linked lists and red-black trees may be used when storing data, so when retrieving data, they are also accessed according to their rules
The process of adding elements to HashSet2. New elements are ranked behind old elements
LinkedHashSet
Each element records the address value of the current element and the address value of the next element, so it is said to be in order
public static void main(String[] args) {<!-- -->
Student s1=new Student("Zhang San",18);
Student s2=new Student("王五",13);
Student s3=new Student("李思",14);
Student s4=new Student("Zhang San",18);
java.util.LinkedHashSet<Student>lhs=new java.util.LinkedHashSet<>();
System.out.println(lhs.add(s1));
System.out.println(lhs.add(s2));
System.out.println(lhs.add(s3));
System.out.println(lhs.add(s4));
System.out.println(lhs);
//true
//true
//true
//false
//[Student{name = Zhang San, age = 18}, Student{name = Wang Wu, age = 13}, Student{name = Li Si, age = 14}]
}
It can guarantee the order of data access
Summary
TreeSet
public static void main(String[] args) {<!-- -->
//Use TreeSet to store integers and sort them
java.util.TreeSet<Integer>ts=new java.util.TreeSet<>();
ts.add(2);
ts.add(1);
ts.add(3);
ts.add(4);
//print collection
System.out.println(ts);//[1, 2, 3, 4]
//Traverse the collection
//Iterator
Iterator<Integer> it = ts.iterator();
while(it.hasNext()){<!-- -->
Integer i = it.next();
System.out.println(i);
}
System.out.println("____________");
//Enhance for
for (Integer t : ts) {<!-- -->
System.out.println(t);
}
System.out.println("____________");
//lambda
ts.forEach(new Consumer<Integer>() {<!-- -->
@Override
public void accept(Integer integer) {<!-- -->
System.out.println(integer);
}
});
}
TreeSet collection default rules
The sorting rules compare each letter one by one. If there is one that is larger than the others below, you don’t need to read it
Sort rules (first sorting method)
If the custom object does not implement the interface, an error will be reported when sorting
To implement the interface, you need to customize the object to implement the Comparable interface. The abstract method compareTo method is rewritten under the interface. The bottom layer is to use a red-black tree comparison.
Method 2
Exercise
Helps understand when to use the first and when to use the second
It is required to store four strings, sort them by length, if they are the same length, sort them by first letter
String is sorted in order by default but does not meet the requirements. In this case, the second sorting comparator is used
public static void main(String[] args) {<!-- -->
// Sort by length, if they are the same length, sort by first letter
TreeSet<String>ts=new TreeSet<>(new Comparator<String>() {<!-- -->
@Override
//o1 represents the element currently to be added
//o2 represents an element that already exists in the red-black tree
public int compare(String o1, String o2) {<!-- -->
//Sort by length
int i=o1.length()-o2.length();
//If the lengths are the same, follow the letters
i=i==0?o1.compareTo(o2):i;
//Interpretation: Is i equal to 0? If it is equal to o, use the default compare method. If it is not equal to 0, then it is i.
return i;
}
});
ts.add("c");
ts.add("ab");
ts.add("df");
ts.add("qwer");
System.out.println(ts);
//[ab, c, df, qwer] This is the default sorting method using compareTo
System.out.println(ts);//[c, ab, df, qwer]
//This is obtained after using the second sorting method
}
Little practice
@Override
public int compareTo(Student o) {<!-- -->
int sumO=o.getChineseGrade() + o.getMathGrade() + o.getEnglishGrade();
int totalScore=this.getChineseGrade() + this.getMathGrade() + getEnglishGrade();
//totalScore represents the current total score
//sumO represents the total score of o
int i=totalScore-sumO;
i=i==0?this.chineseGrade-this.getChineseGrade():i;
//This sentence means that if the total scores are the same, compare the Chinese scores
i=i==0?this.getMathGrade()-this.getMathGrade():i;
//If the Chinese scores are the same, compare the math scores
i=i==0?this.getEnglishGrade()-this.getEnglishGrade():i;
//If the math scores are the same, compare the English scores
i=i==0?this.getAge()-this.getAge():i;
//If the English scores are the same, compare age
i=i==0?this.getName().compareTo(o.getName()):i;
//If the ages are the same, sort them alphabetically by name
return i;
}
public static void main(String[] args) {<!-- -->
//First create five student objects
Student s1=new Student("zhangsan",13,60,70,80);
Student s2=new Student("lsii",15,63,79,68);
Student s3=new Student("wangwu",11,90,75,57);
Student s4=new Student("neifan",12,46,34,34);
Student s5=new Student("hebing",16,45,56,62);
//Create which collection needs to be used here using TreeSet
TreeSet<Student>ts=new TreeSet<Student>();
ts.add(s1);
ts.add(s2);
ts.add(s3);
ts.add(s4);
ts.add(s5);
//System.out.println(ts);
//Choose a sorting method. The first default is used here.
for (Student t : ts) {<!-- -->
System.out.println(t);
}
//Student{name = neifan, age = 12, chineseGrade = 46, mathGrade = 34, englishGrade = 34}
//Student{name = hebing, age = 16, chineseGrade = 45, mathGrade = 56, englishGrade = 62}
//Student{name = lsii, age = 15, chineseGrade = 63, mathGrade = 79, englishGrade = 68}
//Student{name = zhangsan, age = 13, chineseGrade = 60, mathGrade = 70, englishGrade = 80}
//Student{name = wangwu, age = 11, chineseGrade = 90, mathGrade = 75, englishGrade = 57}
}
Summary
Summary: How to choose when using collections
