==學習目標==
1、能夠了解紅黑樹
2、能夠掌握HashSet集合的特點以及使用（特點以及使用，雜湊表資料結構）
3、能夠掌握Map集合的特點以及使用（特點，常見方法，Map集合的遍歷）
4、能夠掌握HashMap集合的特點以及使用
5、能夠掌握TreeMap集合的特點以及使用
==知識點==紅黑樹HashSetMapHashMapTreeMap==知識點梳理====超詳細講義==1.紅黑樹1.1紅黑樹-概述【瞭解】1.什麼是紅黑樹
平衡二叉B樹，每一個節點可以是紅或者黑，紅黑樹不是 高度平衡 的,它的平衡是透過"自己的紅黑規則"進行實現的。
1.2 紅黑樹-紅黑規則 (瞭解) 紅黑樹的紅黑規則有哪些每一個節點或是紅色的,或者是黑色的根節點必須是黑色所有葉子節點（空的節點被稱作葉子節點）都是黑色的不能出現兩個紅色節點相連 的情況對每一個節點,從該節點到其所有後代葉節點的簡單路徑上,均包含相同數目的黑色節點1.3 紅黑樹-新增節點的預設顏色（瞭解)新增節點時,預設為紅色,效率高
1.4 紅黑樹-新增節點後，如何保證紅黑規則1 【難點】1.5 紅黑樹-新增節點後，如何保證紅黑規則2 【難點】（旋轉之後，根據規則驗證是否是紅黑樹，總結紅黑樹新增節點的規則）
1.6 紅黑樹練習-成績排序案例【重點】(共3點)
1.案例需求
用TreeSet集合儲存多個學生資訊(姓名,語文成績,數學成績,英語成績),並遍歷該集合要求: 按照總分從低到高排序程式碼實現
學生類
public class Student implements Comparable<Student> { private String name; private int chinese; private int math; private int english; public Student() { } public Student(String name, int chinese, int math, int english) { this.name = name; this.chinese = chinese; this.math = math; this.english = english; } public String getName() { return name; } public void setName(String name) { this.name = name; } public int getChinese() { return chinese; } public void setChinese(int chinese) { this.chinese = chinese; } public int getMath() { return math; } public void setMath(int math) { this.math = math; } public int getEnglish() { return english; } public void setEnglish(int english) { this.english = english; } public int getSum() { return this.chinese + this.math + this.english; } @Override public int compareTo(Student o) { // 主要條件: 按照總分進行排序 int result = o.getSum() - this.getSum(); // 次要條件: 如果總分一樣,就按照語文成績排序 result = result == 0 ? o.getChinese() - this.getChinese() : result; // 如果語文成績也一樣,就按照數學成績排序 result = result == 0 ? o.getMath() - this.getMath() : result; // 如果總分一樣,各科成績也都一樣,就按照姓名排序 result = result == 0 ? o.getName().compareTo(this.getName()) : result; return result; }}測試類
public class TreeSetDemo { public static void main(String[] args) { //建立TreeSet集合物件，透過比較器排序進行排序 TreeSet<Student> ts = new TreeSet<Student>(); //建立學生物件 Student s1 = new Student("jack", 98, 100, 95); Student s2 = new Student("rose", 95, 95, 95); Student s3 = new Student("sam", 100, 93, 98); //把學生物件新增到集合 ts.add(s1); ts.add(s2); ts.add(s3); //遍歷集合 for (Student s : ts) { System.out.println(s.getName() + "," + s.getChinese() + "," + s.getMath() + "," + s.getEnglish() + "," + s.getSum()); } }}2.TreeSet原理
2.HashSet集合2.1HashSet-基本使用【重點】1.什麼是HashSet(HashSet的特點)
底層資料結構是雜湊表存取無序不可以儲存重複元素沒有索引,不能使用普通for迴圈遍歷（get方法）2.HashSet使用-儲存字串並遍歷
package com.itheima.myhashset;import java.util.HashSet;import java.util.Iterator;/** * 新增字串並進行遍歷 */public class HashSetDemo1 { public static void main(String[] args) { HashSet<String> hs = new HashSet<>(); hs.add("hello"); hs.add("world"); hs.add("java"); hs.add("java"); hs.add("java"); hs.add("java"); hs.add("java"); hs.add("java"); Iterator<String> it = hs.iterator(); while(it.hasNext()){ String s = it.next(); System.out.println(s); } System.out.println("============================="); for (String s : hs) { System.out.println(s); } }}1.什麼是雜湊值
是JDK根據物件的地址或者屬性值，算出來的int型別的整數
2.如何獲取物件中的Hash值
Object類中有一個方法: public int hashCode():根據物件的地址值計算出來的雜湊值
3.雜湊值的特點
沒有重寫HashCode的情況：1.同種一物件多次呼叫hashCode方法返回值是一樣的
2.不同物件hashCode方法返回值不一樣
Object子類重寫hashCode方法的情況：重寫的目的是計算物件雜湊值時，按屬性值來計算，因此只要屬性值相同，不同物件的hashCode方法返回值是一樣的
package com.itheima.myhashset;/** * 計算雜湊值 */public class HashSetDemo2 { public static void main(String[] args) { Student s1 = new Student("xiaozhi",23); Student s2 = new Student("xiaomei",22); //因為在Object類中，是根據物件的地址值計算出來的雜湊值。 System.out.println(s1.hashCode());//1060830840 System.out.println(s1.hashCode());//1060830840 System.out.println(s2.hashCode());//2137211482 }}Student類
package com.itheima.myhashset;public class Student { private String name; private int age; public Student() { } 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; } //我們可以對Object類中的hashCode方法進行重寫 //在重寫之後，就一般是根據物件的屬性值來計算雜湊值的。 //此時跟物件的地址值就沒有任何關係了。 @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result; } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; }}雜湊表=陣列 + 連結串列
2.5HashSet-JDK8底層最佳化【難點】（共兩點）
1.HashSet 在JDK1.8之後的原理
節點個數少於等於8個數組 + 連結串列節點個數多於8個數組 + 紅黑樹2.HashSet 在JDK1.8版本的儲存流程
2.6HashSet集合儲存學生物件並遍歷【重點】案例需求建立一個儲存學生物件的集合，儲存多個學生物件，使用程式實現在控制檯遍歷該集合要求：學生物件的成員變數值相同，我們就認為是同一個物件程式碼實現
測試類
public class HashSetDemo2 { public static void main(String[] args) { //HashSet集合儲存自定義型別元素,要想實現元素的唯一,要求必須重寫hashCode方法和equals方法 HashSet<Student> hashSet = new HashSet<>(); Student s1 = new Student("xiaohei",23); Student s2 = new Student("xiaohei",23); Student s3 = new Student("xiaomei",22); hashSet.add(s1); hashSet.add(s2); hashSet.add(s3); for (Student student : hashSet) { System.out.println(student); } }}學生類
package com.itheima.myhashset;public class Student { private String name; private int age; public Student() { } 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 boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Student student = (Student) o; if (age != student.age) { return false; } return name != null ? name.equals(student.name) : student.name == null; } //我們可以對Object類中的hashCode方法進行重寫 //在重寫之後，就一般是根據物件的屬性值來計算雜湊值的。 //此時跟物件的地址值就沒有任何關係了。 @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result; } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; }}(共3點)
1.什麼是Map集合【記憶】
Map集合又稱為雙列集合，雙列集合中元素的內容是成對的
2.Map集合的特點 【記憶】
鍵不能重複，值可以重複
鍵與值之間是一一對應的關係
(鍵+值)這個整體我們稱之為"鍵值對"或"鍵值對物件",在Java中又叫"Entry物件"
3.如何使用Map集合
1.Map集合格式
interface Map<K,V> K：鍵的型別；V：值的型別2.如何建立Map集合物件
Map<String,String> map = new HashMap<String,String>();//使用具體實現類，採用多型形式建立4.使用Map集合儲存學生學號和姓名
package com.itheima.mapdemo1;import java.util.HashMap;import java.util.Map;/** * Map的基本使用 */public class MyMap1 { public static void main(String[] args) { Map<String,String> map = new HashMap<>(); //map.add(); map.put("itheima001","小智"); map.put("itheima002","小美"); map.put("itheima003","大胖"); System.out.println(map); }}方法介紹
示例程式碼
package com.itheima.mapdemo1;import java.util.HashMap;import java.util.Map;/** * Map的基本方法 */public class MyMap2 { public static void main(String[] args) { Map<String,String> map = new HashMap<>(); map.put("itheima001","小智"); map.put("itheima002","小美"); map.put("itheima003","大胖"); map.put("itheima004","小黑"); map.put("itheima005","大師"); //method1(map); //method2(map); //method3(map); //method4(map); //method5(map); //method6(map); //method7(map); } private static void method7(Map<String, String> map) { // int size() 集合的長度，也就是集合中鍵值對的個數 int size = map.size(); System.out.println(size); } private static void method6(Map<String, String> map) { // boolean isEmpty() 判斷集合是否為空 boolean empty1 = map.isEmpty(); System.out.println(empty1);//false map.clear(); boolean empty2 = map.isEmpty(); System.out.println(empty2);//true } private static void method5(Map<String, String> map) { // boolean containsValue(Object value) 判斷集合是否包含指定的值 boolean result1 = map.containsValue("aaa"); boolean result2 = map.containsValue("小智"); System.out.println(result1); System.out.println(result2); } private static void method4(Map<String, String> map) { // boolean containsKey(Object key) 判斷集合是否包含指定的鍵 boolean result1 = map.containsKey("itheima001"); boolean result2 = map.containsKey("itheima006"); System.out.println(result1); System.out.println(result2); } private static void method3(Map<String, String> map) { // void clear() 移除所有的鍵值對元素 map.clear(); System.out.println(map); } private static void method2(Map<String, String> map) { // V remove(Object key) 根據鍵刪除鍵值對元素 String s = map.remove("itheima001"); System.out.println(s); System.out.println(map); } private static void method1(Map<String, String> map) { // V put(K key,V value) 新增元素 //如果要新增的鍵不存在，那麼會把鍵值對都新增到集合中 //如果要新增的鍵是存在的，那麼會覆蓋原先的值，把原先值當做返回值進行返回。 String s = map.put("itheima001", "aaa"); System.out.println(s); System.out.println(map); }}方法介紹
示例程式碼
package com.itheima.mapdemo1;import java.util.HashMap;import java.util.Map;import java.util.Set;/** * Map的第一種遍歷方式 */public class MyMap3 { public static void main(String[] args) { //建立集合並新增元素 Map<String,String> map = new HashMap<>(); map.put("1號丈夫","1號妻子"); map.put("2號丈夫","2號妻子"); map.put("3號丈夫","3號妻子"); map.put("4號丈夫","4號妻子"); map.put("5號丈夫","5號妻子"); //獲取到所有的鍵 Set<String> keys = map.keySet(); //遍歷Set集合得到每一個鍵 for (String key : keys) { //透過每一個鍵key，來獲取到對應的值 String value = map.get(key); System.out.println(key + "---" + value); } }}方法介紹
示例程式碼
package com.itheima.mapdemo1;import java.util.HashMap;import java.util.Map;import java.util.Set;/** * Map的第二種遍歷方式 */public class MyMap4 { public static void main(String[] args) { //建立集合並新增元素 Map<String,String> map = new HashMap<>(); map.put("1號丈夫","1號妻子"); map.put("2號丈夫","2號妻子"); map.put("3號丈夫","3號妻子"); map.put("4號丈夫","4號妻子"); map.put("5號丈夫","5號妻子"); //首先要獲取到所有的鍵值對物件。 //Set集合中裝的是鍵值對物件（Entry物件） //而Entry裡面裝的是鍵和值 Set<Map.Entry<String, String>> entries = map.entrySet(); for (Map.Entry<String, String> entry : entries) { //得到每一個鍵值對物件 String key = entry.getKey(); String value = entry.getValue(); System.out.println(key + "---" + value); } }}1.HashMap小結
HashMap底層是雜湊表結構依賴hashCode方法和equals方法保證鍵的唯一如果鍵要儲存自定義物件,需要重寫hashCode和equals方法4.2 HashMap集合-練習【重點】（共4點，第4點是對forEache的解析）
1.案例需求
建立一個HashMap集合，鍵是學生物件(Student)，值是籍貫 (String)。儲存三個元素，並遍歷。要求保證鍵的唯一性：如果學生物件的成員變數值相同，我們就認為是同一個物件2.實現思路
定義學生類建立HashMap集合物件新增學生物件為了保證key的一致性，重寫學生類的hashCode和equals方法3.程式碼實現
學生類
package com.itheima.mapdemo1;public class Student{ private String name; private int age; public Student() { } 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 boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Student student = (Student) o; if (age != student.age) return false; return name != null ? name.equals(student.name) : student.name == null; } @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + age; return result; } @Override public String toString() { return "Student{" + "name='" + name + '\'' + ", age=" + age + '}'; }}測試類
package com.itheima.mapdemo1;import java.util.HashMap;import java.util.Map;import java.util.Set;/** * Map的練習 */public class MyMap5 { public static void main(String[] args) { HashMap<Student,String> hm = new HashMap<>(); Student s1 = new Student("xiaohei",23); Student s2 = new Student("dapang",22); Student s3 = new Student("xiaomei",22); hm.put(s1,"江蘇"); hm.put(s2,"北京"); hm.put(s3,"天津"); //第一種：先獲取到所有的鍵，再透過每一個鍵來找對應的值 Set<Student> keys = hm.keySet(); for (Student key : keys) { String value = hm.get(key); System.out.println(key + "----" + value); } System.out.println("==================================="); //第二種：先獲取到所有的鍵值對物件。再獲取到裡面的每一個鍵和每一個值 Set<Map.Entry<Student, String>> entries = hm.entrySet(); for (Map.Entry<Student, String> entry : entries) { Student key = entry.getKey(); String value = entry.getValue(); System.out.println(key + "----" + value); } System.out.println("==================================="); //第三種： hm.forEach( (Student key, String value)->{ System.out.println(key + "----" + value); } ); }}4.forEach方法解析
5.TreeMap集合5.1TreeMap-原理解析【瞭解】1.TreeMap-小結
TreeMap底層是紅黑樹結構依賴自然排序或者比較器排序,對鍵進行排序如果 鍵儲存 的是自定義物件,需要實現Comparable介面或者在建立TreeMap物件時候給出比較器排序規則5.2TreeMap集合應用案例【重點】案例需求建立一個TreeMap集合,鍵是學生物件(Student),值是籍貫(String),學生屬性姓名和年齡,按照年齡進行排序並遍歷要求按照學生的年齡進行排序,如果年齡相同則按照姓名進行排序實現思路1.建立學生類
2.建立TreeMap集合物件
3.建立學生物件
4.新增學生物件
5.遍歷輸出
程式碼實現學生類
package com.itheima.maptest;public class Student/* implements Comparable<Student>*/{ private String name; private int age; public Student() { } 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 + '}'; } /* @Override public int compareTo(Student o) { //按照年齡進行排序 int result = o.getAge() - this.getAge(); //次要條件，按照姓名排序。 result = result == 0 ? o.getName().compareTo(this.getName()) : result; return result; }*/}測試類
package com.itheima.maptest;import java.util.Comparator;import java.util.TreeMap;/** * 需求：建立一個TreeMap集合，鍵是學生物件(Student)，值是籍貫(String)。 * 學生屬性姓名和年齡，按照年齡進行排序並遍歷。 */public class Test1 { public static void main(String[] args) { TreeMap<Student,String> tm = new TreeMap<>(new Comparator<Student>() { @Override public int compare(Student o1, Student o2) { int result = o1.getAge() - o2.getAge(); result = result== 0 ? o1.getName().compareTo(o2.getName()) : result; return result; } }); Student s1 = new Student("xiaohei",23); Student s2 = new Student("dapang",22); Student s3 = new Student("xiaomei",22); tm.put(s1,"江蘇"); tm.put(s2,"北京"); tm.put(s3,"天津"); tm.forEach( (Student key, String value)->{ System.out.println(key + "---" + value); } ); }}
最新評論