JAVA資料結構之Set集合
一、Set集合概論和特點
Set集合特點
- 不包含重復元素的集合
- 沒有帶索引的方法,所以不能使用普通for回圈遍歷
Set集合是一個介面,不能物體化,所以若要物體化,則需要找到它的實作類——HashSet
二、HashSet
該類實作Set介面,由哈希表(實際為HashMap實體)支持, 對集合的迭代順序不作任何保證; 特別是,它不能保證訂單在一段時間內保持不變, 這個類允許null元素,
遍歷字串演示
package Set;
import java.util.HashSet;
import java.util.Set;
public class SetDemo {
public static void main(String[] args) {
Set<String> set = new HashSet<String>();
// 增加資料
set.add("Hello");
set.add("World");
set.add("java");
//增強for回圈輸出
for (String s : set){
System.out.println(s);
}
}
}
輸出結果
java
Hello
World
輸入資料的時候,按照的順序是Hello、World、java,但是輸出的順序是java、Hello、World,因此這個例子就驗證了HashSet對集合的迭代順序不作任何保證
因此,HashSet的特點是
- 底層資料結構是哈希表
- 對集合的迭代不作任何保證,也就是說不保證存盤和取出來的元素順序一樣
- 沒有帶索引方法,所以不可能用for回圈遍歷
- 由于是Set集合,所以不包含重復元素的集合
三、HashSet集合保證元素唯一性的原始碼分析
package Set;
import java.util.HashSet;
import java.util.Set;
public class SetDemo {
public static void main(String[] args) {
Set<String> set = new HashSet<String>();
// 增加資料
set.add("Hello");
set.add("World");
set.add("java");
//增強for回圈輸出
for (String s : set){
System.out.println(s);
}
}
}
//------------------------------------------------
/*
原始碼
比如添加字串Hello
*/
//1、傳輸引數過來,e就是"Hello",呼叫一個put方法,然后回傳
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
//2、在put方法中,先呼叫一個hash方法,計算出key(也就是add方法里面的引數e)的哈希值
//4、接收到hash方法回傳的"Hello"的哈希值后,然后呼叫putVal方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//3、key(也就是add方法中的e)通過hashCode方法,計算出key的哈希值,回傳到put方法中
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//5、這是的形參hash就是指"Hello"的哈希值,而key就是"Hello"
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//6、如果這個哈希表未初始化,就對其初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//7、根據物件的哈希值計算物件的存盤位置,如果該位置為null(說明有元素),則存盤元素(new一個結點存盤進去)
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
/*
8、通過前面比較如果執行到這里,說明該存盤位置有元素,那么就比較存入的元素和以前的元素的哈希值
這是一個短路運算子,如果前面為false,那么后面不會執行
8.1、如果這兩個哈希值不同,那么回傳false,if不成立,繼續向下執行,把元素添加到集合
8.2、如果哈希值相同,那么會執行(k = p.key) == key || (key != null && key.equals(k)))
首先進行物件的比較(比較地址),如果兩個地址值相同,那么說明這兩個是同一個元素,
如果地址值不相同,那就呼叫equal方法,判斷這兩個元素的內容是否一樣(兩個元素哈希值一樣),如果一樣則 不存入集合,如果不一樣,那么則把元素添加到集合中
*/
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//這個else if先不用看
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
簡單概括來說就是以下幾步
- 先如果兩個元素存盤位置不相同,那么直接把元素添加到集合即可
- 如果兩個元素存盤位置相同,那么比較兩個元素的哈希值
- 如果兩個元素的哈希值不一樣,那么存盤進去
- 如果兩個元素的哈希值一樣,那么比較兩個元素的內容
- 如果兩個元素的內容一樣,那么不添加進集合
- 如果兩個元素的內容不一樣,那么不用添加進集合
HashSet集合之所以可以一個位置存盤多個元素,那是因為HashSet集合整體是陣列結構,而每個位置上是鏈式結構,所以一個位置能存盤多個元素
四、哈希值
哈希值:是JDK根據物件地址或者字串或者數字算出來的int型別的數值
因此在Object類中有一個方法可以獲取物件的哈希值
- public int hashCode() :回傳物件的哈希碼值
哈希值的特點在代碼中體現
package CodeDemo;
/*
學生物件類
*/
public class Student {
private int age;
private String name;
public Student(){}
public Student(int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}
package CodeDemo;
public class CodeDemo {
public static void main(String[] args) {
Student s1 = new Student(18, "劉德華");
Student s2 = new Student(18, "劉德華");
Student s3 = new Student(20, "周星馳");
//同一物件多次呼叫hashCode()方法回傳的哈希值是相同的
System.out.println(s1.hashCode());
System.out.println(s1.hashCode());
System.out.println("----------------------");
//默認情況下,不同物件的哈希值是不同的
//可以通過方法重寫,可以實作不同物件的哈希值相同
System.out.println(s2.hashCode());
System.out.println(s3.hashCode());
System.out.println("----------------------");
//不同的字串對應的哈希值也是不同的
System.out.println("Hello".hashCode());
System.out.println("World".hashCode());
System.out.println("----------------------");
//但相同的字串對應的哈希值是相同的
System.out.println("JAVA".hashCode());
System.out.println("JAVA".hashCode());
System.out.println("----------------------");
//不同漢字的哈希值可能一樣
System.out.println("重地".hashCode());
System.out.println("通話".hashCode());
System.out.println("中秋".hashCode());
}
}
運行結果
149928006
149928006
----------------------
713338599
168423058
----------------------
69609650
83766130
----------------------
2269730
2269730
----------------------
1179395
1179395
651582
五、HashSet學生實體應用
需求:創建一個存盤學生物件的集合,存盤多個學生物件,使用程式遍歷
要求:學生物件的成員變數值相同,認為是同一個物件
思路
- 定義學生類
- 創建HashSet集合物件
- 創建學生物件
- 把學生添加到集合
- 遍歷集合(增強for)
- 在學生類中重寫兩個方法(hashCode()和equals())
代碼實作
package CodeDemo;
/*
學生類
*/
import java.util.Objects;
public class Student {
private int age;
private String name;
public Student(){}
public Student(int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Student{" +
"age=" + age +
", name='" + name + '\'' +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return age == student.age &&
Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(age, name);
}
}
package CodeDemo;
/*
測驗類
*/
import java.util.HashSet;
import java.util.Iterator;
public class HashDemo {
public static void main(String[] args) {
Student s1 = new Student(19, "成龍");
Student s2 = new Student(20, "劉德華");
Student s3 = new Student(20, "劉德華");
HashSet<Student> hashSet = new HashSet<Student>();
hashSet.add(s1);
hashSet.add(s2);
hashSet.add(s1);
hashSet.add(s3);
for (Student s : hashSet){
System.out.println(s);
}
Iterator<Student> iterator = hashSet.iterator();
while (iterator.hasNext()){
Student s = iterator.next();
System.out.println(s);
}
}
}
運行結果
Student{age=19, name='成龍'}
Student{age=20, name='劉德華'}
Student{age=19, name='成龍'}
Student{age=20, name='劉德華'}
為什么要重寫hashCode方法呢???
那是因為hashcode重寫的好還可以提升hashset的效率
六、LinkedHashSet集合概述和特點
特點
- 哈希表和鏈式實作的Set介面,具有可預測的迭代次序
- 由鏈式保證元素有序,也就是說元素的存盤和取出順序是一致的
- 由哈希表保證元素唯一,也就是說沒有重復的元素
package CodeDemo;
import java.util.LinkedHashSet;
public class LinkDemo {
public static void main(String[] args) {
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();
linkedHashSet.add("Hello");
linkedHashSet.add("World");
linkedHashSet.add("java");
linkedHashSet.add("Hello");
for (String s : linkedHashSet){
System.out.println(s);
}
}
}
Hello
World
java
七、TreeSet集合概述和特點
TreeSet集合特點
TreeSet 會呼叫集合元素的 compareTo(Object obj) 方法來比較元素之間的大小關系,然后將集合元素按升序排列
-
元素有序,但是這里的順序值得不是存盤和取出順序,而是按照一定的規則進行排序,具體排序方式取決于構造方法
TreeSet():根據其元素的自然排序進行排序(自然排序是指ABCD這樣的順序)
TreeSet(Comparator comparator):根據指定的比較器進行排序
-
沒有帶索引的方法,所以不能使用普通的for回圈遍歷
-
由于是Set集合,所以不包含重復元素的集合
package CodeDemo;
import java.util.TreeSet;
public class TreeDemo {
public static void main(String[] args) {
//創建集合物件
//集合存盤的是物件(參考型別),所以存盤整數應該存盤Inerger
TreeSet<Integer> tree = new TreeSet<Integer>();
//添加資料
tree.add(10);
tree.add(100);
tree.add(1000);
tree.add(10);
tree.add(1);
for (int num : tree){
System.out.println(num);
}
}
}
輸出結果
1
10
100
1000
由結果可見,輸出的資料沒有重復的資料
并且輸入的順序是10、100、1000、1,但是輸出的順序是1、10、100、1000,所以可證明TreeSet( )根據其元素的自然排序進行排序.
八、自然排序Comparable的使用
從例子中體會其作用
- 存盤學生物件并遍歷,創建TreeSet集合使用無參構造方法
- 要求:按照年齡從小到大排序,年齡相同時,按照姓名的字母順序排序
package CodeDemo;
/*
學生類
*/
import java.util.Objects;
public class Student implements Comparable<Student> {
private int age;
private String name;
public Student(){}
public Student(int age, String name) {
this.age = age;
this.name = name;
}
public int getAge() {
return age;
}
public void setAge(int age) {
this.age = age;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
@Override
public String toString() {
return "Student{" +
"age=" + age +
", name='" + name + '\'' +
'}';
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return age == student.age &&
Objects.equals(name, student.name);
}
@Override
public int hashCode() {
return Objects.hash(age, name);
}
@Override
public int compareTo(Student o) {
//return 0; 表示相同
//return 1; 表示從小到大排序
//return -1; 表示從大到小排序
//按照年齡從小到大排序
int num = this.age - o.age;
//年齡相同時候,按照姓名字母順序排序
int num2 = num == 0? this.name.compareTo(o.name) : num;
return num2;
}
}
package CodeDemo;
import java.util.TreeSet;
public class ComparableDemo {
public static void main(String[] args) {
//創建集合物件
TreeSet<Student> treeSet = new TreeSet<Student>();
//創建學生物件
Student s1 = new Student(19, "小明");
Student s2 = new Student(20, "小紅");
Student s3 = new Student(20, "小白");
//添加到集合中
treeSet.add(s1);
treeSet.add(s2);
treeSet.add(s3);
treeSet.add(s1);
for (Student s : treeSet){
System.out.println(s);
}
}
}
n’n’n
運行結果
Student{age=19, name='小明'}
Student{age=20, name='小白'}
Student{age=20, name='小紅'}
結論
- 用TreeSet集合存盤自定義物件,無參構造方法使用的是自然排序對元素進行排序
- 自然排序,就是讓元素所有的類實作Comparable介面,重寫compareTo(T o)方法
- 重寫方法時,一定要注意排序規則必須按照要求的主要條件和次要條件來寫
九、比較器排序Comparator
TreeSet(Comparator<? super E> comparator) | 構造一個新的,空的樹集,根據指定的比較器進行排序, |
|---|
為了方便,這里可以運用匿名內部類的知識去解決
package TEXT;
/*
學生類
*/
public class Student {
private String name;
private int age;
public Student(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 "Student{" +
"name='" + name + '\'' +
", age=" + age +
'}';
}
}
package TEXT;
import java.util.Comparator;
import java.util.TreeSet;
public class Demo {
public static void main(String[] args) {
//創建集合物件
TreeSet<Student> treeSet = new TreeSet<Student>(new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
int num = o1.getAge() - o2.getAge();
int num2 = num == 0? o1.getName().compareTo(o2.getName()) : num;
return num2;
}
});
//創建學生物件
Student s1 = new Student("小明", 19);
Student s2 = new Student("小紅", 20);
Student s3 = new Student("小白", 20);
//添加到集合中
treeSet.add(s1);
treeSet.add(s2);
treeSet.add(s3);
treeSet.add(s1);
for (Student s : treeSet){
System.out.println(s);
}
}
}
運行結果
Student{name='小明', age=19}
Student{name='小白', age=20}
Student{name='小紅', age=20}
結論
- 用TreeSet集合存盤自定義物件,帶參構造方法使用是比較器排序對元素進行排序的
- 比較器排序,就是讓集合構造方法接收Comparator的實作類物件重寫compare(T o1, T o2)方法
- 重寫方法時,一定要注意排序規則必須按照要求的主要條件和次要條件來寫
轉載請註明出處,本文鏈接:https://www.uj5u.com/houduan/319700.html
標籤:java
上一篇:使用python進行視頻圖片提取
