Java?HashSet添加?遍歷元素源碼分析
更新時間：2022年07月08日 15:40:54 作者：趙妹兒
這篇文章主要為大家詳細介紹了HashSet、HashMap底層添加、遍歷元素的機制，追蹤并分析源碼，文中的示例代碼講解詳細，希望對大學有所幫助
HashSet 類圖
HashSet 簡單說明
1.HashSet 實現(xiàn)了 Set 接口
2.HashSet 底層實際上是由 HashMap 實現(xiàn)的
public HashSet() {
map = new HashMap<>();
}
3.可以存放 null，但是只能有一個 null
4.HashSet 不保證元素是有序的(即不保證存放元素的順序和取出元素的順序一致)，取決于 hash 后，再確定索引的結(jié)果
5.不能有重復的元素
HashSet 底層機制說明
HashSet 底層是 HashMap，HashMap 底層是 數(shù)組 + 鏈表 + 紅黑樹
模擬數(shù)組+鏈表的結(jié)構(gòu)
/**
* 模擬 HashSet 數(shù)組+鏈表的結(jié)構(gòu)
*/
public class HashSetStructureMain {
public static void main(String[] args) {
// 模擬一個 HashSet(HashMap) 的底層結(jié)構(gòu)
// 1. 創(chuàng)建一個數(shù)組，數(shù)組的類型為 Node[]
// 2. 有些地方直接把 Node[] 數(shù)組稱為 表
Node[] table = new Node[16];
System.out.println(table);
// 3. 創(chuàng)建節(jié)點
Node john = new Node("john", null);
table[2] = jhon; // 把節(jié)點 john 放在數(shù)組索引為 2 的位置
Node jack = new Node("jack", null);
jhon.next = jack; // 將 jack 掛載到 jhon 的后面
Node rose = new Node("rose", null);
jack.next = rose; // 將 rose 掛載到 jack 的后面
Node lucy = new Node("lucy", null);
table[3] = lucy; // 將 lucy 放在數(shù)組索引為 3 的位置
System.out.println(table);
}
}
// 節(jié)點類 存儲數(shù)據(jù)，可以指向下一個節(jié)點，從而形成鏈表
class Node{
Object item; // 存放數(shù)據(jù)
Node next; // 指向下一個節(jié)點
public Node(Object item, Node next){
this.item = item;
this.next = next;
}
}
HashSet 添加元素底層機制
HashSet 添加元素的底層實現(xiàn)
1.HashSet 底層是 HashMap
2.當添加一個元素時，會先得到 待添加元素的 hash 值，然后將其轉(zhuǎn)換成一個 索引值
3.查詢存儲數(shù)據(jù)表(Node 數(shù)組) table，看當前 待添加元素 所對應的 索引值 的位置是否已經(jīng)存放了 其它元素
4.如果當前 索引值 所對應的的位置不存在 其它元素，就將當前 待添加元素 放到這個 索引值 所對應的的位置
5.如果當前 索引值 所對應的位置存在 其它元素，就調(diào)用 待添加元素.equals(已存在元素) 比較，結(jié)果為 true，則放棄添加；結(jié)果為 false，則將 待添加元素 放到 已存在元素 的后面(已存在元素.next = 待添加元素)
HashSet 擴容機制
1.HashSet 的底層是 HashMap，第一次添加元素時，table 數(shù)組擴容到 cap = 16，threshold(臨界值) = cap * loadFactor(加載因子 0.75) = 12
2.如果 table 數(shù)組使用到了臨界值 12，就會擴容到 cap * 2 = 32，新的臨界值就是 32 * 0.75 = 24，以此類推
3.在 Java8 中，如果一條鏈表上的元素個數(shù) 到達 TREEIFY_THRESHOLD(默認是 8)，并且 table 的大小 >= MIN_TREEIFY_CAPACITY(默認是 64)，就會進行 樹化(紅黑樹)
4.判斷是否擴容是根據(jù) ++size > threshold，即是否擴容，是根據(jù) HashMap 所存的元素個數(shù)(size)是否超過臨界值，而不是根據(jù) table.length() 是否超過臨界值
HashSet 添加元素源碼
/**
* HashSet 源碼分析
*/
public class HashSetSourceMain {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add("java");
hashSet.add("php");
hashSet.add("java");
System.out.println("set = " + hashSet);
// 源碼分析
// 1. 執(zhí)行 HashSet()
/**
* public HashSet() { // HashSet 底層是 HashMap
* map = new HashMap<>();
* }
*/
// 2. 執(zhí)行 add()
/**
* public boolean add(E e) { // e == "java"
* // HashSet 的 add() 方法其實是調(diào)用 HashMap 的 put()方法
* return map.put(e, PRESENT)==null; // (static) PRESENT = new Object(); 用于占位
* }
*/
// 3. 執(zhí)行 put()
// hash(key) 得到 key(待存元素) 對應的hash值，并不等于 hashcode()
// 算法是 h = key.hashCode()) ^ (h >>> 16
/**
* public V put(K key, V value) {
* return putVal(hash(key), key, value, false, true);
* }
*/
// 4. 執(zhí)行 putVal()
// 定義的輔助變量：Node<K,V>[] tab; Node<K,V> p; int n, i;
// table 是 HashMap 的一個屬性，初始化為 null；transient Node<K,V>[] table;
// resize() 方法，為 table 數(shù)組指定容量
// p = tab[i = (n - 1) & hash] 計算 key的hash值所對應的 table 中的索引位置，將索引位置對應的 Node 賦給 p
/**
* final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
* boolean evict) {
* Node<K,V>[] tab; Node<K,V> p; int n, i; // 輔助變量
* // table 就是 HashMap 的一個屬性，類型是 Node[]
* // if 語句表示如果當前 table 是 null，或者 table.length == 0
* // 就是 table 第一次擴容，容量為 16
* if ((tab = table) == null || (n = tab.length) == 0)
* n = (tab = resize()).length;
* // 1. 根據(jù) key，得到 hash 去計算key應該存放到 table 的哪個索引位置
* // 2. 并且把這個位置的索引值賦給 i；索引值對應的元素，賦給 p
* // 3. 判斷 p 是否為 null
* // 3.1 如果 p 為 null，表示還沒有存放過元素，就創(chuàng)建一個Node(key="java",value=PRESENT)，并把這個元素放到 i 的索引位置
* // tab[i] = newNode(hash, key, value, null);
* if ((p = tab[i = (n - 1) & hash]) == null)
* tab[i] = newNode(hash, key, value, null);
* else {
* Node<K,V> e; K k; // 輔助變量
* // 如果當前索引位置對應的鏈表的第一個元素和待添加的元素的 hash值一樣
* // 并且滿足下面兩個條件之一：
* // 1. 待添加的 key 與 p 所指向的 Node 節(jié)點的key 是同一個對象
* // 2. 待添加的 key.equals(p 指向的 Node 節(jié)點的 key) == true
* // 就認為當前待添加的元素是重復元素，添加失敗
* if (p.hash == hash &&
* ((k = p.key) == key || (key != null && key.equals(k))))
* e = p;
* // 判斷 當前 p 是不是一顆紅黑樹
* // 如果是一顆紅黑樹，就調(diào)用 putTreeVal，來進行添加
* else if (p instanceof TreeNode)
* e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
* else {
* // 如果 當前索引位置已經(jīng)形成一個 鏈表，就使用 for 循環(huán)比較
* // 將待添加元素依次和鏈表上的每個元素進行比較
* // 1. 比較過程中如果出現(xiàn)待添加元素和鏈表中的元素有相同的，比較結(jié)束，出現(xiàn)重復元素，添加失敗
* // 2. 如果比較到鏈表最后一個元素，鏈表中都沒出現(xiàn)與待添加元素相同的，就把當前待添加元素放到該鏈表最后的位置
* // 注意：在把待添加元素添加到鏈表后，立即判斷 該鏈表是否已經(jīng)到達 8 個節(jié)點
* // 如果到達，就調(diào)用 treeifyBin() 對當前這個鏈表進行數(shù)化(轉(zhuǎn)成紅黑樹)
* // 注意：在轉(zhuǎn)成紅黑樹前，還要進行判斷
* // if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
* // resize();
* // 如果上面條件成立，先對 table 進行擴容
* // 如果上面條件不成立，才轉(zhuǎn)成紅黑樹
* 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;
* }
* }
* // e 不為 null ，說明添加失敗
* if (e != null) { // existing mapping for key
* V oldValue = e.value;
* if (!onlyIfAbsent || oldValue == null)
* e.value = value;
* afterNodeAccess(e);
* return oldValue;
* }
* }
* ++modCount;
* // 擴容：說明判斷 table 是否擴容不是看 table 的length
* // 而是看 整個 HashMap 的 size(即已存元素個數(shù))
* if (++size > threshold)
* resize();
* afterNodeInsertion(evict);
* return null;
* }
*/
}
}
HashSet 遍歷元素底層機制
HashSet 遍歷元素底層機制
1.HashSet 的底層是 HashMap，HashSet 的迭代器也是借由 HashMap 來實現(xiàn)的
2.HashSet.iterator() 實際上是去調(diào)用 HashMap 的 KeySet().iterator()
public Iterator<E> iterator() {
return map.keySet().iterator();
}
3.KeySet() 方法返回一個 KeySet 對象，而 KeySet 是 HashMap 的一個內(nèi)部類
public Set<K> keySet() {
Set<K> ks = keySet;
if (ks == null) {
ks = new KeySet();
keySet = ks;
}
return ks;
}
4.KeySet().iterator() 方法返回一個 KeyIterator 對象，KeyIterator 是 HashMap 的一個內(nèi)部類
public final Iterator<K> iterator() { return new KeyIterator(); }
5.KeyIterator 繼承了 HashIterator(HashMap的內(nèi)部類) 類，并實現(xiàn)了 Iterator 接口，即 KeyIterator、HashIterator 才是真正實現(xiàn) 迭代器 的類
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
6.當執(zhí)行完 Iterator iterator = HashSet.iterator; 之后，此時的 iterator 對象中已經(jīng)存儲了一個元素節(jié)點
- 怎么做到的？
- 回到第 4 步，
KeySet().iterator()方法返回一個KeyIterator對象 new KeyIterator()調(diào)用KeyIterator的無參構(gòu)造器- 在這之前，會先調(diào)用其父類
HashIterator的無參構(gòu)造器 - 因此，分析
HashIterator的無參構(gòu)造器就知道發(fā)生了什么
/**
* Node<K,V> next; // next entry to return
* Node<K,V> current; // current entry
* int expectedModCount; // for fast-fail
* int index; // current slot
* HashIterator() {
* expectedModCount = modCount;
* Node<K,V>[] t = table;
* current = next = null;
* index = 0;
* if (t != null && size > 0) { // advance to first entry
* do {} while (index < t.length && (next = t[index++]) == null);
* }
* }
*/
next、current、index都是HashIterator的屬性Node<K,V>[] t = table;先把Node數(shù)組talbe賦給tcurrent = next = null;current、next都置為nullindex = 0;index置為0do {} while (index < t.length && (next = t[index++]) == null);這個do-while會在table中遍歷Node結(jié)點- 一旦
(next = t[index++]) == null不成立 時，就說明找到了一個table中的Node結(jié)點 - 將這個節(jié)點賦給
next，并退出當前do-while循環(huán) - 此時
Iterator iterator = HashSet.iterator;就執(zhí)行完了 - 當前
iterator的運行類型其實是HashIterator，而HashIterator的next中存儲著從table中遍歷出來的一個Node結(jié)點
7.執(zhí)行 iterator.hasNext
此時的 next 存儲著一個 Node，所以并不為 null，返回 true
public final boolean hasNext() {
return next != null;
}
8.執(zhí)行 iterator.next()
I.Node<K,V> e = next; 把當前存儲著 Node 結(jié)點的 next 賦值給了 e
II.(next = (current = e).next) == null 判斷當前結(jié)點的下一個結(jié)點是否為 null
- (a). 如果當前結(jié)點的下一個結(jié)點為
null，就執(zhí)行do {} while (index < t.length && (next = t[index++]) == null);，在table數(shù)組中遍歷，尋找table數(shù)組中的下一個Node并賦值給next - (b). 如果當前結(jié)點的下一個結(jié)點不為
null，就將當前結(jié)點的下一個結(jié)點賦值給next，并且此刻不會去table數(shù)組中遍歷下一個Node結(jié)點
III.將找到的結(jié)點 e 返回
IV.之后每次執(zhí)行 iterator.next() 都像 (a)、(b) 那樣去判斷遍歷，直到遍歷完成
HashSet 遍歷元素源碼
/**
* HashSet 源碼分析
*/
public class HashSetSourceMain {
public static void main(String[] args) {
HashSet hashSet = new HashSet();
hashSet.add("java");
hashSet.add("php");
hashSet.add("java");
System.out.println("set = " + hashSet);
// HashSet 迭代器實現(xiàn)原理
// HashSet 底層是 HashMap，HashMap 底層是 數(shù)組 + 鏈表 + 紅黑樹
// HashSet 本身沒有實現(xiàn)迭代器，而是借由 HashMap 來實現(xiàn)的
// 1. hashSet.iterator() 實際上是去調(diào)用 HashMap 的 keySet().iterator()
/**
* public Iterator<E> iterator() {
* return map.keySet().iterator();
* }
*/
// 2. KeySet() 方法返回一個 KeySet 對象，而 KeySet 是 HashMap 的一個內(nèi)部類
/**
* public Set<K> keySet() {
* Set<K> ks = keySet;
* if (ks == null) {
* ks = new KeySet();
* keySet = ks;
* }
* return ks;
* }
*/
// 3. KeySet().iterator() 方法返回一個 KeyIterator 對象，KeyIterator 是 HashMap的一個內(nèi)部類
/**
* public final Iterator<K> iterator() { return new KeyIterator(); }
*/
// 4. KeyIterator 繼承了 HashIterator(HashMap的內(nèi)部類) 類，并實現(xiàn)了 Iterator 接口
// 即 KeyIterator、HashIterator 才是真正實現(xiàn) 迭代器的類
/**
* final class KeyIterator extends HashIterator
* implements Iterator<K> {
* public final K next() { return nextNode().key; }
* }
*/
// 5. 當執(zhí)行完 Iterator iterator = hashSet.iterator(); 后
// 此時的 iterator 對象中已經(jīng)存儲了一個元素節(jié)點
// 怎么做到的？
// 回到第 3 步，KeySet().iterator() 方法返回一個 KeyIterator 對象
// new KeyIterator() 調(diào)用 KeyIterator 的無參構(gòu)造器
// 在這之前，會先調(diào)用 KeyIterator 父類 HashIterator 的無參構(gòu)造器
// 因此分析 HashIterator 的無參構(gòu)造器就知道發(fā)生了什么
/**
* Node<K,V> next; // next entry to return
* Node<K,V> current; // current entry
* int expectedModCount; // for fast-fail
* int index; // current slot
* HashIterator() {
* expectedModCount = modCount;
* Node<K,V>[] t = table;
* current = next = null;
* index = 0;
* if (t != null && size > 0) { // advance to first entry
* do {} while (index < t.length && (next = t[index++]) == null);
* }
* }
*/
// 5.0 next, current, index 都是 HashIterator 的屬性
// 5.1 Node<K,V>[] t = table; 先把 Node 數(shù)組 table 賦給 t
// 5.2 current = next = null; 把 current 和 next 都置為 null
// 5.3 index = 0; index 置為 0
// 5.4 do {} while (index < t.length && (next = t[index++]) == null);
// 這個 do{} while 循環(huán)會在 table 中 遍歷 Node節(jié)點
// 一旦 (next = t[index++]) == null 不成立時，就說明找到了一個 table 中的節(jié)點
// 將這個節(jié)點賦給 next，并退出當前 do while循環(huán)
// 此時 Iterator iterator = hashSet.iterator(); 就執(zhí)行完了
// 當前 iterator 的運行類型其實是 HashIterator，而 HashIterator 的 next 中存儲著從 table 中遍歷出來的一個 Node節(jié)點
// 6. 執(zhí)行 iterator.hasNext()
/**
* public final boolean hasNext() {
* return next != null;
* }
*/
// 6.1 此時的 next 存儲著一個 Node，所以并不為 null，返回 true
// 7. 執(zhí)行 iterator.next()，其實是去執(zhí)行 HashIterator 的 nextNode()
/**
* final Node<K,V> nextNode() {
* Node<K,V>[] t;
* Node<K,V> e = next;
* if (modCount != expectedModCount)
* throw new ConcurrentModificationException();
* if (e == null)
* throw new NoSuchElementException();
* if ((next = (current = e).next) == null && (t = table) != null) {
* do {} while (index < t.length && (next = t[index++]) == null);
* }
* return e;
* }
*/
// 7.1 Node<K,V> e = next; 把當前存儲著 Node 節(jié)點的 next 賦值給了 e
// 7.2 (next = (current = e).next) == null
// 判斷當前節(jié)點的下一個節(jié)點是否為 null
// a. 如果當前節(jié)點的下一個節(jié)點為 null
// 就執(zhí)行 do {} while (index < t.length && (next = t[index++]) == null);
// 再 table 數(shù)組中 遍歷，尋找 table 數(shù)組中的下一個 Node 并賦值給 next
// b. 如果當前節(jié)點的下一個節(jié)點不為 null
// 就將當前節(jié)點的下一個節(jié)點賦值給 next，并且此刻不會去 table 數(shù)組中遍歷下一個 Node 節(jié)點
// 7.3 將找到的節(jié)點 e 返回
// 7.4 之后每次執(zhí)行 iterator.next()，都像 a、b 那樣去判斷遍歷，直到遍歷完成
Iterator iterator = hashSet.iterator();
while (iterator.hasNext()) {
Object next = iterator.next();
System.out.println(next);
}
}
}到此這篇關(guān)于Java HashSet添加 遍歷元素源碼分析的文章就介紹到這了,更多相關(guān)HashSet添加 遍歷元素內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
在進行浮點數(shù)的加減運算時,直接使用+和-可能會引入精度誤差,為了比較浮點數(shù),可以使用Double的compareTo()方法,或者通過定義一個容差值（Epsilon）來判斷兩個浮點數(shù)是否相等,此外,Double.compare()方法也能比較兩個double值2024-10-10
這篇文章主要介紹了mybatis是如何集成到spring的,將mybatis集成到spring之后，就可以被spring的ioc容器托管，再也不用自己創(chuàng)建SqlSessionFactory?、打開SqlSession等操作，本文結(jié)合實例代碼給大家介紹的非常詳細，需要的朋友可以參考下2023-05-05
Mybatis逆向工程是一個自動生成Mybatis Mapper接口、XML文件和Java實體類的工具,可以提高開發(fā)效率,避免手動編寫大量的重復代碼，本文主要介紹了Mybatis創(chuàng)建逆向工程的步驟，感興趣的可以了解一下2023-10-10
SpringBoot默認的內(nèi)嵌容器是Tomcat，也就是我們的程序?qū)嶋H上是運行在Tomcat里的，所以與其說SpringBoot可以處理多少請求，到不如說Tomcat可以處理多少請求，這篇文章主要介紹了SpringBoot可以同時處理多少請求,需要的朋友可以參考下2023-02-02
Mybatis-Plus中的MetaObjectHandler組件的使用
MetaObjectHandler是Mybatis-Plus中一個實用組件,專門用于自動處理實體對象中的特定字段,如創(chuàng)建時間、更新時間、創(chuàng)建人和修改人等,該接口允許開發(fā)者在不修改業(yè)務代碼的情況下,實現(xiàn)自動填充功能,極大地簡化了代碼的復雜性,感興趣的可以了解一下2024-10-10
這篇文章主要給大家介紹了關(guān)于Java單鏈表反轉(zhuǎn)的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-04-04
關(guān)于Javaweb的轉(zhuǎn)發(fā)和重定向詳解
這篇文章主要介紹了關(guān)于Javaweb的轉(zhuǎn)發(fā)和重定向詳解,請求的轉(zhuǎn)發(fā),是指服務器收到請求后,從一個服務器端資源跳轉(zhuǎn)到同一個服務器端另外一個資源的操作,需要的朋友可以參考下2023-05-05
jxls2.4.5如何動態(tài)導出excel表頭與數(shù)據(jù)
這篇文章主要介紹了jxls2.4.5如何動態(tài)導出excel表頭與數(shù)據(jù)問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-08-08
這篇文章主要介紹了Java8?函數(shù)式編程stream流使用詳解的相關(guān)資料,需要的朋友可以參考下2023-07-07
眾所周知小程序的openid相當重要,它是用戶的唯一標識id,牽扯的支付,登錄,授權(quán)等,下面這篇文章主要給大家介紹了關(guān)于如何獲取微信用戶openid的相關(guān)資料,需要的朋友可以參考下2023-02-02