开发者

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

开发者 https://www.devze.com 2023-03-23 10:25 出处:网络 作者: adi851270440
目录HashMap之keyset() 方法底层原理HashMap (jdk1.8) keySet()方法详细注释keySet()注释KetSet内部类KeyIterator实现Iterator接口总结HashMap之keyset() 方法底层原理
目录
  • HashMap之keyset() 方法底层原理
  • HashMap (jdk1.8) keySet()方法详细注释
    • keySet()注释
    • KetSet内部类
    • KeyIterator实现Iterator接口
  • 总结

    HashMap之keyset() 方法底层原理

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

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

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

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

    源码如下:

      publ编程客栈ic 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>js 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();
        }
      }

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

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

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

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

      final class LinkedKeyIterator extends LinkedHashIterator
        implements Iterator<K> {
        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<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()、entr开发者_开发培训ySet()方法也是如此。

    HashMap (jdk1.8) keySet()方法详细注释

    hashMap通过keyset遍历时,先调用keySet()方法,该方法返回hashMap中存储的key的集合ks, 然后再执行内部类 final class KeySet 中的iterator(),iterator()返回一个HashMap.KeyIterator()对象。

    KeyIterator对象继承HashIterator且实现 Iterator<K>

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

    do {} while (index < t.length && (next = t[index++]) == null);找到table中的第一个不为空的元素的前一个元素,赋值给next,。

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

    keySet()注释

    /*
      * hashMap通过keyset遍历时,先调用keySet()方法,该方法返回hashMap中存储的key的集合ks,
      然后再执行内部类 final class KeySet extends AbstractSet<K>中的iterator(),iterator()
      返回一个HashMap.KeyIterator()对象,KeyIterator对象继承HashIterator且实现 Iterator<K>
       HashIterator的构造方法初始化时会把table中存储的元素赋值给临时node类型变量t,并通过循环
        do {} while (index < t.length && (next = t[index++])编程客栈 == null);找到table中的第一个
        不为空的元素的前一个元素,赋值给next,
      KeyIterator对象实现 Iterator<K>接口的next方法,这样就能实现table中元素的遍历
      * HashIterator 中的nextNode()方法可以找到table中的第一个不为空的元素的前一个元素,赋值给next,
      * */
      public Set<K> keySet() {
        Set<K> 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,继承AbstractSe编程客栈t,重写它父类的父类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(); }//调用hashMap的clear方法,this表示调用clear()方法的hashMap对象
        public final Iterator<K> iterator()   { return new HashMap.KeyIterator(); }//创建一个KeyIterator对象,该对象继承HashIterator,implements Iterator<K>中的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<K> spliterator() {
          return new HashMap.KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }//返回一个KeySpliterator对象,KeySpliterator 继承 HashMapSpliterator<K,V>implements Spliterator<K>,调用父类的构造方法初始化对象
        //KeySpliterator的方法中调用它的父类HashMapSpliterator中的构造方法初始化对象
       public final void forEach(Consumer<? super K> action) {
          Node<K,V>[] 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<K, V> 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<K>{
    
      @Override
      public K next() {
        return null;
      }
    }

    总结

    以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

    0

    精彩评论

    暂无评论...
    验证码 换一张
    取 消

    关注公众号