HashMap之keyset()方法底層原理解讀

更新時(shí)間：2023年03月22日 10:20:15 作者：adi851270440

這篇文章主要介紹了HashMap之keyset()方法底層原理解讀，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

HashMap之keyset() 方法底層原理

獲取HashMap所有的鍵，通常調(diào)用方法keyset()即可返回所有的key集合。

那么keyset()的工作原理是什么？它真的會(huì)維護(hù)一個(gè)Set嗎，當(dāng)Map的鍵值對(duì)發(fā)生變化，就來(lái)更新這個(gè)Set?

如果真的是這樣，那么HashMap的性能將會(huì)大打折扣，并且存儲(chǔ)空間的消耗也會(huì)翻倍。

其實(shí)，HashMap采用了一種比較巧妙的方式實(shí)現(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();
? ? ? ? }
? ? }

當(dāng)我們調(diào)用keyset方法時(shí)，會(huì)先判斷keyset是否已經(jīng)初始化，如果沒(méi)有，則new LinkedKeySet 對(duì)象，然后更新成員變量keyset，下次再調(diào)用時(shí)，則直接返回已經(jīng)初始化的LinkedKeySet對(duì)象引用，不再初始化LinkedKeySet對(duì)象。

分析LinkedKeySet，發(fā)現(xiàn)該內(nèi)部類(lèi)只有無(wú)參的構(gòu)造方法，并且構(gòu)造方法僅僅new 了一個(gè)空對(duì)象，并沒(méi)有給Set集合初始化值，那么keyset值從哪兒來(lái)呢？

往下看，LinkedKeySet內(nèi)部類(lèi)有個(gè)方法iterator()，是集合類(lèi)接口Set聲明的iterator方法的一個(gè)具體實(shí)現(xiàn)，該方法會(huì)new一個(gè)迭代器。

當(dāng)我們做增強(qiáng)for循環(huán)時(shí)會(huì)調(diào)用該迭代器，該迭代器會(huì)遍歷HashMap的各個(gè)節(jié)點(diǎn)，拿到key。

? ? final class LinkedKeyIterator extends LinkedHashIterator
? ? ? ? implements Iterator<K> {
? ? ? ? public final K next() { return nextNode().getKey(); }
? ? }

還有一個(gè)問(wèn)題，當(dāng)我們debug的時(shí)候，我們會(huì)發(fā)現(xiàn)，keyset()方法返回的set集合并非一個(gè)空集合，里面是有數(shù)據(jù)的，這是為什么呢？

原因是IDEA在debug時(shí)會(huì)默認(rèn)調(diào)用toString()方法，所以我們debug看到的信息其實(shí)調(diào)用了父AbstractCollection的toString()方法。

包括我們通過(guò)System.out.println(set)打印數(shù)據(jù)的時(shí)候，都會(huì)調(diào)用這個(gè)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()方法詳細(xì)注釋

hashMap通過(guò)keyset遍歷時(shí)，先調(diào)用keySet()方法，該方法返回hashMap中存儲(chǔ)的key的集合ks, 然后再執(zhí)行內(nèi)部類(lèi) final class KeySet 中的iterator()，iterator()返回一個(gè)HashMap.KeyIterator()對(duì)象。

KeyIterator對(duì)象繼承HashIterator且實(shí)現(xiàn) Iterator<K>

HashIterator的構(gòu)造方法初始化時(shí)會(huì)把table中存儲(chǔ)的元素賦值給臨時(shí)node類(lèi)型變量t,并通過(guò)循環(huán)

do {} while (index < t.length && (next = t[index++]) == null);找到table中的第一個(gè)不為空的元素的前一個(gè)元素，賦值給next，。

KeyIterator對(duì)象實(shí)現(xiàn) Iterator<K>接口的next方法，這樣就能實(shí)現(xiàn)table中元素的遍歷 HashIterator 中的nextNode()方法可以找到table中的第一個(gè)不為空的元素的前一個(gè)元素，賦值給next。

keySet()注釋

?/*
? ? * hashMap通過(guò)keyset遍歷時(shí)，先調(diào)用keySet()方法，該方法返回hashMap中存儲(chǔ)的key的集合ks,
? ? 然后再執(zhí)行內(nèi)部類(lèi) final class KeySet extends AbstractSet<K>中的iterator()，iterator()
? ? 返回一個(gè)HashMap.KeyIterator()對(duì)象，KeyIterator對(duì)象繼承HashIterator且實(shí)現(xiàn) Iterator<K>
? ? ? HashIterator的構(gòu)造方法初始化時(shí)會(huì)把table中存儲(chǔ)的元素賦值給臨時(shí)node類(lèi)型變量t,并通過(guò)循環(huán)
? ? ? ? do {} while (index < t.length && (next = t[index++]) == null);找到table中的第一個(gè)
? ? ? ? 不為空的元素的前一個(gè)元素，賦值給next，
? ? KeyIterator對(duì)象實(shí)現(xiàn) Iterator<K>接口的next方法，這樣就能實(shí)現(xiàn)table中元素的遍歷
? ? * HashIterator 中的nextNode()方法可以找到table中的第一個(gè)不為空的元素的前一個(gè)元素，賦值給next，
? ? * */
?? ? ?public Set<K> keySet() {
? ? ? ? Set<K> ks = keySet; //keySet是hashMap的父類(lèi)AbstractMap的成員變量，創(chuàng)建Set類(lèi)型的ks對(duì)象，把keySet賦值給ks;
? ? ? ? if (ks == null) { //如果ks為空，創(chuàng)建一個(gè)KeySet對(duì)象，賦值給ks
? ? ? ? ? ? ks = new KeySet();
? ? ? ? ? ? keySet = ks; ?//把ks再賦值賦值給成員變量keySet
? ? ? ? }
? ? ? ? return ks; ? ? ? //返回ks
? ? }

KetSet內(nèi)部類(lèi)

/*
? ? * 定義一個(gè)不可變類(lèi)KeySet，繼承AbstractSet，重寫(xiě)它父類(lèi)的父類(lèi)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的長(zhǎng)度
? ? ? ? public final void clear() ? ? ? ? ? ? ? { HashMap.this.clear(); }//調(diào)用hashMap的clear方法，this表示調(diào)用clear()方法的hashMap對(duì)象
? ? ? ? public final Iterator<K> iterator() ? ? { return new HashMap.KeyIterator(); }//創(chuàng)建一個(gè)KeyIterator對(duì)象，該對(duì)象繼承HashIterator，implements Iterator<K>中的next方法，其它方法為啥不用實(shí)現(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);
? ? ? ? }//返回一個(gè)KeySpliterator對(duì)象，KeySpliterator 繼承 HashMapSpliterator<K,V>implements Spliterator<K>，調(diào)用父類(lèi)的構(gòu)造方法初始化對(duì)象
? ? ? ? //KeySpliterator的方法中調(diào)用它的父類(lèi)HashMapSpliterator中的構(gòu)造方法初始化對(duì)象
? ? ? ?public final void forEach(Consumer<? super K> action) {
? ? ? ? ? ? Node<K,V>[] tab; //定義Node類(lèi)型的數(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é)點(diǎn)
? ? ? ? ? ? ? ? ? ? ? ? action.accept(e.key);//調(diào)用Consumer中的accept(),傳入key
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if (modCount != mc) //如果modCount不等于mc，說(shuō)明有其它線(xiàn)程修改這個(gè)hashMap,拋出異常
? ? ? ? ? ? ? ? ? ? throw new ConcurrentModificationException();
? ? ? ? ? ? }
? ? ? ? }
? ? }

KeyIterator實(shí)現(xiàn)Iterator接口

Iterator接口里面有boolean hasNext() 、E next()、 void remove()、void forEachRemaining()方法，為啥只重寫(xiě)next方法？

HashIterator里面重寫(xiě)了boolean hasNext() 、E next()、 void remove()，但是void forEachRemaining()在HashIterator和KeyIterator中都沒(méi)有重寫(xiě)，沒(méi)想明白是為啥？

? final class KeyIterator extends HashMap.HashIterator
? ? ? ? implements Iterator<K>{
?
? ? @Override
? ? public K next() {
? ? ? ? return null;
? ? }
}