Hashset介紹
- HashSet實際上是HashMap，底層都一樣(陣列+鏈表+紅黑樹)
- 不能有重復的元素，記住深入理解，可以添加不同的物件的，在前面的隨筆中講過了，只能有一個null
-
添加元素底層機制說明(先說結論)：
- 添加一個元素時，先得到hash值，會轉成-->索引，
- 找到存盤資料表table，看這個索引是否已經存放元素
- 如果該hash值得出的索引位置上沒有其他元素，則直接存放
- 如果有則呼叫equals比較，如果相同就放棄添加，如果沒有添加到最后
- 重要，我們可以在添加的物件中重寫equals，就是判斷的內容，主要是看equals有沒有重寫
- 添加元素的代碼分析
@SuppressWarnings({"all"})
public class HashSet01 {
public static void main(String[] args) {
Set set = new HashSet<>();
set.add("平凡晨");//成功
set.add("浪子王");//成功
set.add("路人甲");//成功
set.add("平凡晨");//失敗
System.out.println("Set = "+ set);
/**
* 1、 底層創建了的是HashMap
* public HashSet() {
* map = new HashMap<>();
* }
*
* 2、執行add()方法，并且是回傳一個布林值
* public boolean add(E e) { //e：平凡晨
* return map.put(e, PRESENT)==null; //PRESENT = new Object
* }
*
* 3、執行的是put()
* public V put(K key, V value) { //key："平凡晨" value： 因為Hashset沒有value值，存放的是Object，起到站位的作用
* return putVal(hash(key), key, value, false, true);
* }
*
* 4、往里追會(hash(key)方法 會跳到hash()方法 這個方法 會得到 key對應的hash值
* 重要重要的一句話： 里面的hash值 不等價于 hashCode()
* static final int hash(Object key) {
* int h;
* //解釋：這個方法是先判斷傳進來的key是不是空，
* // 不是空的話就得到他的hash值，無符號右移16位
* return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
* }
*
*
* 重要重要！！！！！！！！！！！！
*
* final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
* boolean evict) {
* Node<K,V>[] tab; Node<K,V> p; int n, i; //定義了一些輔助變數
*
* // 解釋：if ((tab = table) == null 把當前的table表賦給了陣列變數tab，在判斷當前的tab表是不是空
* //解釋：|| (n = tab.length) == 0) 并且判斷當前的tab的長度賦給 n 在判斷長度是不是0
* // 解釋：第一次添加tab肯定是null，所以第一次添加會進入if陳述句的代碼塊
* if ((tab = table) == null || (n = tab.length) == 0)
* //解釋：這個resize()).length其實是給陣列初始化值位12個空間，然后在賦給陣列tab ，在給到n
* n = (tab = resize()).length;
*
* //解釋：根據key ，得到hash值，去計算在tab表中的索引位置 ，并賦給p ，在判斷p 是不是null
* //如果p 等于null 就表示沒有添加過資料
* if ((p = tab[i = (n - 1) & hash]) == null)
* //解釋：創建一個Node （key = "平凡晨"，value = "https://www.cnblogs.com/ityc/p/PRESENT"）
* tab[i] = newNode(hash, key, value, null);
*
* //解釋：如果p不為空就進入else
* else {
* Node<K,V> e; K k;
*
* 解釋：如果當前索引位置對應的第一個鏈表和準備添加的key的hash值一樣
* 解釋：并且當前索引的key 和要傳進來的key 是不是同一個物件
* 解釋：或者傳進來的null不等于空，并且傳進來的key的equlas等于k
* 解釋：看傳進來的代碼有沒有重寫equal方法
* if (p.hash == hash &&
* ((k = p.key) == key || (key != null && key.equals(k))))
* e = p;
*
* 解釋：進入else if 在判斷p是不是一個紅黑樹
* 解釋：如果是一個紅黑樹就呼叫 putTreeVal 這個方法
* else if (p instanceof TreeNode)
* e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
*
* 解釋：如果 table 表的索引位置 ，已經是一個鏈表就for回圈
* 解釋：以此和鏈表上的每個元素進行比較，
* 解釋：如果鏈表有元素，并且判斷比較時，不相同就加載到有元素的鏈表的后面
* else {
* for (int binCount = 0; ; ++binCount) {
* if ((e = p.next) == null) {
* p.next = newNode(hash, key, value, null);
* 解釋：當把資料添加進來以后，就立即判斷的鏈表的結點是否已經達到八個
* 重點！！！：注意在進行紅黑樹的時候，他會判斷你當前的的陣列大小有沒有達到64個空間
* 如果沒有就先把陣列大小擴容到64
* if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
* 解釋：達到八個就轉為紅黑樹
* treeifyBin(tab, hash);
* break;
* }
*
* 解釋：如果鏈有元素，并且判斷比較時，相同，則就brak
* 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 = https://www.cnblogs.com/ityc/p/e.value;
* if (!onlyIfAbsent || oldValue =https://www.cnblogs.com/ityc/p/= null)
* e.value = https://www.cnblogs.com/ityc/p/value;
*
* afterNodeAccess(e);
* return oldValue;
* }
* }
* //添加成功就會++modCount ，在判斷是不是應該擴容 ，回傳一個null
* ++modCount;
* if (++size > threshold)
* resize();
* afterNodeInsertion(evict);
* return null;
* }
*/
}
} -
Hashset擴容和紅黑樹機制(總結)
- HashSet底層HashMap，第一添加的時候，table陣列擴容到16，臨界值時16*加載因子(0.75)，也就是16*0.75 = 12 ，臨界值就是12
- 如果table陣列使用到臨界值12就會擴容，16*2 = 32，新的臨界值就是32*0.75 = 24，依此類推
- 如果一條鏈表達到8時，會先把tabel陣列擴容到64，在轉化成紅黑樹，如果沒有到64，不轉紅黑樹，知道到達64為止
LinkedHashSet的說明
LinkedHashSet是Hashset的子類
LinkedHashSet底層是LinkedHashMap底層維護的是陣列+雙向鏈表
LinkedHashSet根據元素的hashCode值來決定元素的存盤位置，同時使用鏈表維護元素的次序(圖)，這使得元素看起來是以插入順序保存的，
LinkedHashset不允許元素重復
TreeSet
- 核心：TreeSet里面有一個構造器，傳入的是一個比較器(匿名內部類)
- 注意：tes.add( new 物件); 這個會報錯，因為會把 這個物件轉位 comparble型別，沒發轉
- Comparator是一個比較器(比較大小，也就是按照一定規則排序)，里面有一個compare的構造器需在呼叫的時候重寫，主要是return回傳值是大于0，就從大到小排序，return回傳值是小于0，就從小到大排序
-
import java.util.Comparator; import java.util.TreeSet; public class text { public static void main(String[] args) { TreeSet<Object> tes = new TreeSet<>(new Comparator<Object>() { @Override public int compare(Object o1, Object o2) { //根據字串長度比較 //注意，如果用字符的長度排序，如果有相同的長度底層原始碼 ，就直接回傳，沒有聽見進去 // return ((String) o1).length() - ((String) o2).length(); //根據字串的字母順序比較 return ((String) o1).compareTo((String) o2); } }); tes.add("java"); tes.add("lm"); tes.add("jack");//這里如果按字符長度排序 則不能添加進去，因為 tes.add("java"); 也是4 ，底層原始碼就回傳0，添加不成功 tes.add("liming"); tes.add("pingfanchen"); System.out.println("tes + " +tes);
} }
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/444305.html
標籤：Java
上一篇：資料庫與快取資料一致性解決方案
下一篇：Java的jps命令使用詳解