HashMap之keyset()方法底层原理解读

这篇文章主要介绍了HashMap之keyset()方法底层原理解读，具有很好的参考价值，希望对大家有所帮助。如有错误或未考虑完全的地方，望不吝赐教

HashMap之keyset() 方法底层原理

获取HashMap所有的键，通常调用方法keyset()即可返回所有的key集合。

那么keyset()的工作原理是什么？它真的会维护一个Set吗，当Map的键值对发生变化，就来更新这个Set?

如果真的是这样，那么HashMap的性能将会大打折扣，并且存储空间的消耗也会翻倍。

其实，HashMap采用了一种比较巧妙的方式实现keyset。

源码如下：

    public Set keySet() {         Set ks = keySet;         if (ks == null) {             ks = new LinkedKeySet();             keySet = ks;         }         return ks;     }       final class LinkedKeySet extends AbstractSet {         public final int size()                 { return size; }         public final void clear()               { LinkedHashMap.this.clear(); }         public final Iterator 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 spliterator()  {             return Spliterators.spliterator(this, Spliterator.SIZED |                                             Spliterator.ORDERED |                                             Spliterator.DISTINCT);         }         public final void forEach(Consumer action) {             if (action == null)                 throw new NullPointerException();             int mc = modCount;             for (LinkedHashMap.Entry e = head; e != null; e = e.after)                 action.accept(e.key);             if (modCount != mc)                 throw new ConcurrentModificationException();         }     }

当我们调用keyset方法时，会先判断keyset是否已经初始化，如果没有，则new LinkedKeySet 对象，然后更新成员变量keyset，下次再调用时，则直接返回已经初始化的LinkedKeySet对象引用，不再初始化LinkedKeySet对象。

分析LinkedKeySet，发现该内部类只有无参的构造方法，并且构造方法仅仅new 了一个空对象，并没有给Set集合初始化值，那么keyset值从哪儿来呢？

往下看，LinkedKeySet内部类有个方法iterator()，是集合类接口Set声明的iterator方法的一个具体实现，该方法会new一个迭代器。

当我们做增强for循环时会调用该迭代器，该迭代器会遍历HashMap的各个节点，拿到key。

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

还有一个问题，当我们debug的时候，我们会发现，keyset()方法返回的set集合并非一个空集合，里面是有数据的，这是为什么呢？

原因是IDEA在debug时会默认调用toString()方法，所以我们debug看到的信息其实调用了父AbstractCollection的toString()方法。

包括我们通过System.out.println(set)打印数据的时候，都会调用这个toString方法。

    public String toString() {         Iterator 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遍历时，先调用keySet()方法，该方法返回hashMap中存储的key的集合ks, 然后再执行内部类 final class KeySet 中的iterator()，iterator()返回一个HashMap.KeyIterator()对象。

KeyIterator对象继承HashIterator且实现 Iterator

HashIterator的构造方法初始化时会把table中存储的元素赋值给临时node类型变量t,并通过循环

do {} while (index

KeyIterator对象实现 Iterator接口的next方法，这样就能实现table中元素的遍历 HashIterator 中的nextNode()方法可以找到table中的第一个不为空的元素的前一个元素，赋值给next。

keySet()注释

 /*     * hashMap通过keyset遍历时，先调用keySet()方法，该方法返回hashMap中存储的key的集合ks,     然后再执行内部类 final class KeySet extends AbstractSet中的iterator()，iterator()     返回一个HashMap.KeyIterator()对象，KeyIterator对象继承HashIterator且实现 Iterator       HashIterator的构造方法初始化时会把table中存储的元素赋值给临时node类型变量t,并通过循环         do {} while (index 接口的next方法，这样就能实现table中元素的遍历     * HashIterator 中的nextNode()方法可以找到table中的第一个不为空的元素的前一个元素，赋值给next，     * */       public Set keySet() {         Set ks = keySet; //keySet是hashMap的父类AbstractMap的成员变量，创建Set类型的ks对象，把keySet赋值给ks;         if (ks == null) { //如果ks为空，创建一个KeySet对象，赋值给ks             ks = new KeySet();             keySet = ks;  //把ks再赋值赋值给成员变量keySet         }         return ks;       //返回ks     }

KetSet内部类

/*     * 定义一个不可变类KeySet，继承AbstractSet，重写它父类的父类AbstractCollection中的size()、     * clear()\ iterator()\contains(Object o)\remove(Object key)\     * spliterator()\forEach(Consumer action) 方法      * */     final class KeySet extends AbstractSet {         public final int size()                 { return size; } //返回hashMap的成员变量size的长度         public final void clear()               { HashMap.this.clear(); }//调用hashMap的clear方法，this表示调用clear()方法的hashMap对象         public final Iterator iterator()     { return new HashMap.KeyIterator(); }//创建一个KeyIterator对象，该对象继承HashIterator，implements Iterator中的next方法，其它方法为啥不用实现？         public final boolean contains(Object o) { return containsKey(o); }//调用hashMap的 containsKey(o)方法         public final boolean remove(Object key) {             return removeNode(hash(key), key, null, false, true) != null; //调用hashMap的 removeNode()方法         }         public final Spliterator spliterator() {             return new HashMap.KeySpliterator<>(HashMap.this, 0, -1, 0, 0);         }//返回一个KeySpliterator对象，KeySpliterator 继承 HashMapSpliteratorimplements Spliterator，调用父类的构造方法初始化对象         //KeySpliterator的方法中调用它的父类HashMapSpliterator中的构造方法初始化对象        public final void forEach(Consumer action) {             Node[] tab; //定义Node类型的数组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修改次数                 for (Node e : tab) { //遍历tab                     for (; e != null; e = e.next) //循环条件e不为空，有next节点                         action.accept(e.key);//调用Consumer中的accept(),传入key                 }                 if (modCount != mc) //如果modCount不等于mc，说明有其它线程修改这个hashMap,抛出异常                     throw new ConcurrentModificationException();             }         }     }

KeyIterator实现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{       @Override     public K next() {         return null;     } }