1. Characteristics of stored data: unordered and unrepeatable elements
concrete:
Take HashSet as an example:
1. Disorder: not equal to randomness. The stored data is not added in the order of array index in the underlying array, but determined according to the hash value of the data.
2. Non repeatability: ensure that the added elements cannot return true when judged by equals(). That is, only one element can be added for the same element.
2. Element adding process: (take HashSet as an example)
We add element a to the HashSet. First, we call the hashCode() method of the class where element a is located to calculate the hash value of element a,
This hash value then calculates the storage location (i.e. index location) in the underlying array of HashSet through some algorithm
Whether the array has elements at this position:
If there are no other elements at this location, element a is added successfully. -- -- > case 1
If there are other elements b (or multiple elements in the form of linked list) at this position, compare the hash values of element a and element b:
If the hash values are different, element a is added successfully. -- -- > case 2
If the hash values are the same, you need to call the equals() method of the class where element a is located:
equals() returns true, element a addition failed
If equals() returns false, element a is added successfully. -- -- > case 2
For cases 2 and 3 where the addition is successful, element a and the data already existing at the specified index position are stored in a linked list.
jdk 7: put element a into the array and point to the original element.
jdk 8: the original element is in the array and points to element a
Conclusion: seven up and eight down
HashSet bottom layer: array + linked list structure. (premise: jdk7)
3. Common methods
No new methods are defined in the Set interface, but all the methods declared in the Collection are used.
4. Common implementation classes:
|----Collection interface: single column collection, used to store objects one by one
* |---- Set interface: stores unordered and non repeatable data --> "Collection" in high school
* |---- HashSet: as the main implementation class of the Set interface; thread unsafe; null values can be stored
* |---- LinkedHashSet: as a subclass of HashSet; when traversing its internal data, it can be traversed in the order of addition
* While adding data, each data also maintains two references to record the previous data and the latter data. For frequent traversal operations, LinkedHashSet is more efficient than HashSet
* |---- TreeSet: you can sort according to the specified attributes of the added object.
5. Requirements for storage object class:
HashSet/LinkedHashSet:
Requirement: the class of data added to set (mainly HashSet and LinkedHashSet) must override hashCode() and equals()
Requirement: the rewritten hashCode() and equals() should be consistent as much as possible: equal objects must have equal hash codes
* Tip for rewriting two methods: the fields in the object used for the equals() method comparison should be used to calculate the hashCode value.
public class User implements Comparable{
private String name;
private int age;
public User() {
}
public User(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
@Override
public String toString() {
return "User{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
@Override
public boolean equals(Object o) {
System.out.println("User equals()....");
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
if (age != user.age) return false;
return name != null ? name.equals(user.name) : user.name == null;
}
@Override
public int hashCode() { //return name.hashCode() + age;
int result = name != null ? name.hashCode() : 0;
result = 31 * result + age;
return result;
}
//In descending order of name and age
@Override
public int compareTo(Object o) {
if(o instanceof User){
User user = (User)o;
// return -this.name.compareTo(user.name);
int compare = -this.name.compareTo(user.name);
if(compare != 0){
return compare;
}else{
return Integer.compare(this.age,user.age);
}
}else{
throw new RuntimeException("The types entered do not match");
}
}
}
***************************************************************************
@Test
public void test1(){
Set set = new HashSet();
set.add(456);
set.add(123);
set.add(123);
set.add("AA");
set.add("CC");
set.add(new User("Tom",12));
set.add(new User("Tom",12));
set.add(129);
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
************************************************************************
Operation results:
User equals()....
AA
CC
129
456
123
User{name='Tom', age=12}//Use of LinkedHashSet //LinkedHashSet is a subclass of HashSet. While adding data, each data also maintains two references, recording the previous one of this data //Data and the latter data. //Advantages: LinkedHashSet is more efficient than HashSet for frequent traversal operations
@Test
public void test2(){
Set set = new LinkedHashSet();
set.add(456);
set.add(123);
set.add(123);
set.add("AA");
set.add("CC");
set.add(new User("Tom",12));
set.add(new User("Tom",12));
set.add(129);
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
****************************************************************
Operation results:
User equals()....
456
123
AA
CC
User{name='Tom', age=12}
129/* 1. The data added to TreeSet must be objects of the same class. 2. Two sorting methods: natural sorting (implementing Comparable interface) and custom sorting (Comparator) 3. In natural sorting, the criteria for comparing whether two objects are the same is: compareTo() returns 0. It is no longer equal() 4. In custom sorting, the criteria for comparing whether two objects are the same is: compare() returns 0. It is no longer equal() */
@Test
public void test1(){
TreeSet set = new TreeSet();
//Failed: cannot add objects of different classes
// set.add(123);
// set.add(456);
// set.add("AA");
// set.add(new User("Tom",12));
//Example 1:
// set.add(34);
// set.add(-34);
// set.add(43);
// set.add(11);
// set.add(8);
//Example 2:
set.add(new User("Tom",12));
set.add(new User("Jerry",32));
set.add(new User("Jim",2));
set.add(new User("Mike",65));
set.add(new User("Jack",33));
set.add(new User("Jack",56));
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
*******************************************************************
Operation results:
User{name='Tom', age=12}
User{name='Mike', age=65}
User{name='Jim', age=2}
User{name='Jerry', age=32}
User{name='Jack', age=33}
User{name='Jack', age=56}//Arranged from small to large according to age
@Test
public void test2(){
Comparator com = new Comparator() {
//Arranged from small to large according to age
@Override
public int compare(Object o1, Object o2) {
if(o1 instanceof User && o2 instanceof User){
User u1 = (User)o1;
User u2 = (User)o2;
return Integer.compare(u1.getAge(),u2.getAge());
}else{
throw new RuntimeException("The data types entered do not match");
}
}
};
TreeSet set = new TreeSet(com);
set.add(new User("Tom",12));
set.add(new User("Jerry",32));
set.add(new User("Jim",2));
set.add(new User("Mike",65));
set.add(new User("Mary",33));
set.add(new User("Jack",33));
set.add(new User("Jack",56));
Iterator iterator = set.iterator();
while(iterator.hasNext()){
System.out.println(iterator.next());
}
}
************************************************************************
Operation results:
User{name='Jim', age=2}
User{name='Tom', age=12}
User{name='Jerry', age=32}
User{name='Mary', age=33}
User{name='Jack', age=56}
User{name='Mike', age=65}