HashMap 源码解析(二)-阿里云开发者社区

开发者社区> 云计算> 正文
登录阅读全文

HashMap 源码解析(二)

简介: hashMap 迭代机制源码解读

上篇文章介绍了hashMap 的基本数据结构和put() get() resize()流程 传送门

现在我们来介绍 hashmap 剩下的一些方法
hashMap 有些情况下会进行遍历操作,hashMap 支持提供了三种遍历方法
1 keySet()
官方注释是@return a set view of the keys contained in this map(返回map的key set)

    public Set<K> keySet() {
        Set<K> ks = keySet;
        if (ks == null) {
            ks = new KeySet();
            keySet = ks;
        }
        return ks;
    }

这个方法反回了一个KeySet类 看看这个KetSet是个什么啥

   final class KeySet extends AbstractSet<K> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        public final Iterator<K> iterator()     { return new KeyIterator(); }
        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 new KeySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        public final void forEach(Consumer<? super K> action) {
            Node<K,V>[] tab;
            if (action == null)
                throw new NullPointerException();
            if (size > 0 && (tab = table) != null) {
                int mc = modCount;
                for (int i = 0; i < tab.length; ++i) {
                    for (Node<K,V> e = tab[i]; e != null; e = e.next)
                        action.accept(e.key);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

KeySet是hashMap的内部类,没有没有写任何逻辑,如何去遍历这个KeySet的关键在于iterator() 不管是使用迭代器还是使用for加强循环,核心的东西都是这个迭代器
下面继续看KeyIterator.class 是个什么东西

  final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }

可以看到 这个迭代器继承于HashIterator ,仅重写了next() 方法,结合HashIterator代码一起分析

abstract class HashIterator {
       Node<K,V> next;        // next entry to return
       Node<K,V> current;     // current entry
       int expectedModCount;  // for fast-fail
       int index;
       }

首先在迭代器初始化时

       HashIterator() {
            expectedModCount = modCount; //将hashMap操作次数赋值给expectedModCount,
                                        //在其他线程操作该hashMap后 预期值和实际值不同直接抛出异常,类似于cas         
            Node<K,V>[] t = table; //将hashMap的数据集赋值给 t
            current = next = null; //设置迭代器的当前节点和下一个节点为空
            index = 0;             //hashMap table 游标设置为0
            if (t != null && size > 0) { // advance to first entry 判断是不是空map
                                         //获取table数组中第一个不为空的链表头节点
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

ok,现在迭代器初始化完成,迭代器的两大核心方法为hasNext() 判断是否存在下一条数据 和next() 获取下一条数据并将next指向下一条数据
1 hashNext(),很简单,判断next是不是为空就可以

public final boolean hasNext() {
           return next != null;
       }

2 next():抽象类HashIterator 没有定义该方法,是因为next() 有返回值,需要子类去自己定义返回值,HashIterator 将公用操作定义为nextNode方法
KeySet的迭代器KeyIterator 定义的方法为

public final K next() { return nextNode().key; }

HashIterator.nextNode()方法如下,方法很短,但是操作很多

       final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next; //获取next
            if (modCount != expectedModCount) //判断 hashMap是否被其他线程修改过
                throw new ConcurrentModificationException();
            if (e == null)//判断下一个节点是不是为空
                throw new NoSuchElementException();
             // 下面的操作比较复杂我们拆成多步操作
         /**  current = e;//  将current 
              next = current.next; //next赋值为current的下一个节点
              t=table;
              if(next == null&&t != null){//如果next为链表最后一个节点
                 do {} while (index < t.length && (next = t[index++]) == null);
                 // 数组游标++ 一直找到数组的下一个有数据的节点的头节点,假如是最后一个节点则跳出循环,next =null
              }**/
             if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

2 values()
values().iterator() 返回了一个ValueIterator()

    final class ValueIterator extends HashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

next() 方法也是调用HashIterator.nextNode()方法,只不过是去的value;
3 entrySet()
上代码

  final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

直接返回了整个node节点
hashMap遍历顺序
从nextNode()方法可以看出,hashMap在通过上述三种方法遍历时,都是从table数组 从小下标到大下标,如果发生hash冲突导致链表的,优先遍历链表,因此hashMap的遍历和插入顺序是不同的,和hashCode()有关 ,按照插入顺序遍历hashMap可以使用LinkedHashMap ,具体用法后面会继续写

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
云计算
使用钉钉扫一扫加入圈子
+ 订阅

时时分享云计算技术内容,助您降低 IT 成本,提升运维效率,使您更专注于核心业务创新。

其他文章