HashMap之keyset()方法底層原理解讀
HashMap之keyset() 方法底層原理
獲取HashMap所有的鍵，通常調(diào)用方法keyset()即可返回所有的key集合。
那么keyset()的工作原理是什么？它真的會維護一個Set嗎，當Map的鍵值對發(fā)生變化，就來更新這個Set?
如果真的是這樣，那么HashMap的性能將會大打折扣，并且存儲空間的消耗也會翻倍。
其實，HashMap采用了一種比較巧妙的方式實現(xiàn)keyset。
源碼如下：
? ? public Set<K> keySet() {
? ? ? ? Set<K> ks = keySet;
? ? ? ? if (ks == null) {
? ? ? ? ? ? ks = new LinkedKeySet();
? ? ? ? ? ? keySet = ks;
? ? ? ? }
? ? ? ? return ks;
? ? }
?
? ? final class LinkedKeySet extends AbstractSet<K> {
? ? ? ? public final int size() ? ? ? ? ? ? ? ? { return size; }
? ? ? ? public final void clear() ? ? ? ? ? ? ? { LinkedHashMap.this.clear(); }
? ? ? ? public final Iterator<K> iterator() {
? ? ? ? ? ? return new LinkedKeyIterator();
? ? ? ? }
? ? ? ? public final boolean contains(Object o) { return containsKey(o); }
? ? ? ? public final boolean remove(Object key) {
? ? ? ? ? ? return removeNode(hash(key), key, null, false, true) != null;
? ? ? ? }
? ? ? ? public final Spliterator<K> spliterator() ?{
? ? ? ? ? ? return Spliterators.spliterator(this, Spliterator.SIZED |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Spliterator.ORDERED |
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Spliterator.DISTINCT);
? ? ? ? }
? ? ? ? public final void forEach(Consumer<? super K> action) {
? ? ? ? ? ? if (action == null)
? ? ? ? ? ? ? ? throw new NullPointerException();
? ? ? ? ? ? int mc = modCount;
? ? ? ? ? ? for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after)
? ? ? ? ? ? ? ? action.accept(e.key);
? ? ? ? ? ? if (modCount != mc)
? ? ? ? ? ? ? ? throw new ConcurrentModificationException();
? ? ? ? }
? ? }當我們調(diào)用keyset方法時，會先判斷keyset是否已經(jīng)初始化，如果沒有，則new LinkedKeySet 對象，然后更新成員變量keyset，下次再調(diào)用時，則直接返回已經(jīng)初始化的LinkedKeySet對象引用，不再初始化LinkedKeySet對象。
分析LinkedKeySet，發(fā)現(xiàn)該內(nèi)部類只有無參的構(gòu)造方法，并且構(gòu)造方法僅僅new 了一個空對象，并沒有給Set集合初始化值，那么keyset值從哪兒來呢？
往下看，LinkedKeySet內(nèi)部類有個方法iterator()，是集合類接口Set聲明的iterator方法的一個具體實現(xiàn)，該方法會new一個迭代器。
當我們做增強for循環(huán)時會調(diào)用該迭代器，該迭代器會遍歷HashMap的各個節(jié)點，拿到key。
? ? final class LinkedKeyIterator extends LinkedHashIterator
? ? ? ? implements Iterator<K> {
? ? ? ? public final K next() { return nextNode().getKey(); }
? ? }還有一個問題，當我們debug的時候，我們會發(fā)現(xiàn)，keyset()方法返回的set集合并非一個空集合，里面是有數(shù)據(jù)的，這是為什么呢？
原因是IDEA在debug時會默認調(diào)用toString()方法，所以我們debug看到的信息其實調(diào)用了父AbstractCollection的toString()方法。
包括我們通過System.out.println(set)打印數(shù)據(jù)的時候，都會調(diào)用這個toString方法。
? ? public String toString() {
? ? ? ? Iterator<E> it = iterator();
? ? ? ? if (! it.hasNext())
? ? ? ? ? ? return "[]";
?
? ? ? ? StringBuilder sb = new StringBuilder();
? ? ? ? sb.append('[');
? ? ? ? for (;;) {
? ? ? ? ? ? E e = it.next();
? ? ? ? ? ? sb.append(e == this ? "(this Collection)" : e);
? ? ? ? ? ? if (! it.hasNext())
? ? ? ? ? ? ? ? return sb.append(']').toString();
? ? ? ? ? ? sb.append(',').append(' ');
? ? ? ? }
? ? }HashMap的values()、entrySet()方法也是如此。
HashMap (jdk1.8) keySet()方法詳細注釋
hashMap通過keyset遍歷時，先調(diào)用keySet()方法，該方法返回hashMap中存儲的key的集合ks, 然后再執(zhí)行內(nèi)部類 final class KeySet 中的iterator()，iterator()返回一個HashMap.KeyIterator()對象。
KeyIterator對象繼承HashIterator且實現(xiàn) Iterator<K>
HashIterator的構(gòu)造方法初始化時會把table中存儲的元素賦值給臨時node類型變量t,并通過循環(huán)
do {} while (index < t.length && (next = t[index++]) == null);找到table中的第一個不為空的元素的前一個元素，賦值給next，。
KeyIterator對象實現(xiàn) Iterator<K>接口的next方法，這樣就能實現(xiàn)table中元素的遍歷 HashIterator 中的nextNode()方法可以找到table中的第一個不為空的元素的前一個元素，賦值給next。
keySet()注釋
?/*
? ? * hashMap通過keyset遍歷時，先調(diào)用keySet()方法，該方法返回hashMap中存儲的key的集合ks,
? ? 然后再執(zhí)行內(nèi)部類 final class KeySet extends AbstractSet<K>中的iterator()，iterator()
? ? 返回一個HashMap.KeyIterator()對象，KeyIterator對象繼承HashIterator且實現(xiàn) Iterator<K>
? ? ? HashIterator的構(gòu)造方法初始化時會把table中存儲的元素賦值給臨時node類型變量t,并通過循環(huán)
? ? ? ? do {} while (index < t.length && (next = t[index++]) == null);找到table中的第一個
? ? ? ? 不為空的元素的前一個元素，賦值給next，
? ? KeyIterator對象實現(xiàn) Iterator<K>接口的next方法，這樣就能實現(xiàn)table中元素的遍歷
? ? * HashIterator 中的nextNode()方法可以找到table中的第一個不為空的元素的前一個元素，賦值給next，
? ? * */
?? ? ?public Set<K> keySet() {
? ? ? ? Set<K> ks = keySet; //keySet是hashMap的父類AbstractMap的成員變量，創(chuàng)建Set類型的ks對象，把keySet賦值給ks;
? ? ? ? if (ks == null) { //如果ks為空，創(chuàng)建一個KeySet對象，賦值給ks
? ? ? ? ? ? ks = new KeySet();
? ? ? ? ? ? keySet = ks; ?//把ks再賦值賦值給成員變量keySet
? ? ? ? }
? ? ? ? return ks; ? ? ? //返回ks
? ? }KetSet內(nèi)部類
/*
? ? * 定義一個不可變類KeySet，繼承AbstractSet，重寫它父類的父類AbstractCollection中的size()、
? ? * clear()\ iterator()\contains(Object o)\remove(Object key)\
? ? * spliterator()\forEach(Consumer<? super K> action) 方法
? ? ?* */
? ? final class KeySet extends AbstractSet<K> {
? ? ? ? public final int size() ? ? ? ? ? ? ? ? { return size; } //返回hashMap的成員變量size的長度
? ? ? ? public final void clear() ? ? ? ? ? ? ? { HashMap.this.clear(); }//調(diào)用hashMap的clear方法，this表示調(diào)用clear()方法的hashMap對象
? ? ? ? public final Iterator<K> iterator() ? ? { return new HashMap.KeyIterator(); }//創(chuàng)建一個KeyIterator對象，該對象繼承HashIterator，implements Iterator<K>中的next方法，其它方法為啥不用實現(xiàn)？
? ? ? ? public final boolean contains(Object o) { return containsKey(o); }//調(diào)用hashMap的 containsKey(o)方法
? ? ? ? public final boolean remove(Object key) {
? ? ? ? ? ? return removeNode(hash(key), key, null, false, true) != null; //調(diào)用hashMap的 removeNode()方法
? ? ? ? }
? ? ? ? public final Spliterator<K> spliterator() {
? ? ? ? ? ? return new HashMap.KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
? ? ? ? }//返回一個KeySpliterator對象，KeySpliterator 繼承 HashMapSpliterator<K,V>implements Spliterator<K>，調(diào)用父類的構(gòu)造方法初始化對象
? ? ? ? //KeySpliterator的方法中調(diào)用它的父類HashMapSpliterator中的構(gòu)造方法初始化對象
? ? ? ?public final void forEach(Consumer<? super K> action) {
? ? ? ? ? ? Node<K,V>[] tab; //定義Node類型的數(shù)組tab
? ? ? ? ? ? if (action == null)//如果action為空，拋出空指針異常
? ? ? ? ? ? ? ? throw new NullPointerException();
? ? ? ? ? ? if (size > 0 && (tab = table) != null) { //如果size大于0，把table賦值給tab,tab不為空
? ? ? ? ? ? ? ? int mc = modCount;//定義mc變量，把modCount賦值給mc,modCount記錄hashMap修改次數(shù)
? ? ? ? ? ? ? ? for (Node<K, V> e : tab) { //遍歷tab
? ? ? ? ? ? ? ? ? ? for (; e != null; e = e.next) //循環(huán)條件e不為空，有next節(jié)點
? ? ? ? ? ? ? ? ? ? ? ? action.accept(e.key);//調(diào)用Consumer中的accept(),傳入key
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (modCount != mc) //如果modCount不等于mc，說明有其它線程修改這個hashMap,拋出異常
? ? ? ? ? ? ? ? ? ? throw new ConcurrentModificationException();
? ? ? ? ? ? }
? ? ? ? }
? ? }KeyIterator實現(xiàn)Iterator接口
Iterator接口里面有boolean hasNext() 、E next()、 void remove()、void forEachRemaining()方法，為啥只重寫next方法？
HashIterator里面重寫了boolean hasNext() 、E next()、 void remove()，但是void forEachRemaining()在HashIterator和KeyIterator中都沒有重寫，沒想明白是為啥？
? final class KeyIterator extends HashMap.HashIterator
? ? ? ? implements Iterator<K>{
?
? ? @Override
? ? public K next() {
? ? ? ? return null;
? ? }
}總結(jié)
以上為個人經(jīng)驗，希望能給大家一個參考，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了Springboot實現(xiàn)VNC的反向代理,搭建過程也很簡單，通過注冊bean攔截指定URL路徑進行自定義操作，具體實例代碼跟隨小編一起看看需要的朋友可以參考下2021-09-09
下面小編就為大家?guī)硪黄狫ava基礎(chǔ)的幾道練習題(分享)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧，希望可以幫到你2021-07-07
這篇文章主要介紹了解決Nacos集群啟動失敗:java版本問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06
elasticsearch的zenDiscovery和master選舉機制原理分析
這篇文章主要介紹了elasticsearch的zenDiscovery和master選舉機制原理分析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-04-04
下面小編就為大家?guī)硪黄猨ava同步鎖的正確使用方法(必看篇)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
本文詳細介紹了MySqlConnector的核心功能,包括數(shù)據(jù)變更捕獲、KafkaConnect兼容性、配置管理、版本信息、連接器任務創(chuàng)建、配置驗證、數(shù)據(jù)庫連接建立和連接器配置創(chuàng)建等,感興趣的可以了解一下2024-10-10
這篇文章主要為大家詳細介紹了java代碼實現(xiàn)俄羅斯方塊，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-06-06
本文主要介紹了Springboot利于第三方服務進行ip定位獲取省份城市，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-07-07
SpringBoot+MyBatis簡單數(shù)據(jù)訪問應用的實例代碼
這篇文章主要介紹了SpringBoot+MyBatis簡單數(shù)據(jù)訪問應用的實例代碼,需要的朋友可以參考下2017-05-05
SpringCloud基于SpringAMQP實現(xiàn)消息隊列及原理解析
Spring AMQP作為Spring框架的一部分,是一套用于支持高級消息隊列協(xié)議（AMQP）的工具,這篇文章主要介紹了SpringCloud基于SpringAMQP實現(xiàn)消息隊列及原理解析,需要的朋友可以參考下2024-04-04