HashMap之keyset()方法的底層原理是什么

這篇文章主要講解了“HashMap之keyset()方法的底層原理是什么”，文中的講解內(nèi)容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“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)部類只有無參的構造方法，并且構造方法僅僅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的構造方法初始化時會把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的構造方法初始化時會把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)用父類的構造方法初始化對象
        //KeySpliterator的方法中調(diào)用它的父類HashMapSpliterator中的構造方法初始化對象
       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;
    }
}

感謝各位的閱讀，以上就是“HashMap之keyset()方法的底層原理是什么”的內(nèi)容了，經(jīng)過本文的學習后，相信大家對HashMap之keyset()方法的底層原理是什么這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！