HashMap1.8 源码解析(4)--遍历元素

完整代码:代码

前言

这篇文章主要分析HashMap1.8中是如何遍历元素的,先会介绍普通遍历Iterator然后再介绍Spliterator.

`Iterator`接口

public interface Iterator<E> {
    //是否有下一个元素
    boolean hasNext();
    //取出元素
    E next();
    //删除元素 至于删除什么样的元素需要根据子类的实现而定
    default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    // 1.8加入的新方法 其实就是遍历
    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

抽象类`HashIterator`

HashIterator虽然没有继承Iterator接口,但是它实现了除了next方法外的所有抽象方法,相当于是一个辅助类.

另外注意一下nextNode方法,它其实是整个函数的核心函数,它完成了如何遍历整个table的功能,方法是一个槽一个槽的遍历,指的是不为null的槽.

abstract class HashIterator {
        Node<K,V> next;        // 下一个要返回的entry
        Node<K,V> current;     // 当前的 entry
        int expectedModCount;  // 期望的修改次数
        int index;             // 当前的槽index

        HashIterator() {        //构造函数
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { // 初始化next,寻找第一个不为null的槽
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        public final boolean hasNext() {  //判断是否还有下一个元素
            return next != null;
        }

        final Node<K,V> nextNode() {      //找到下一个节点
            Node<K,V>[] t;
            Node<K,V> e = next;           // 把下一个元素赋值给e,在后面e会赋值给current
            if (modCount != expectedModCount)   //如果修改次数没有变化
                throw new ConcurrentModificationException();
            if (e == null)                
                throw new NoSuchElementException();
            /**
             * 1. if条件里面的意思是检查当前槽是否遍历完,没有遍历完就把链表下一个元素给next
             *     请注意不论当前槽是链表(节点类型Node)还是红黑树结构(TreeNode)
             *     都保存了链表结构(Node或者TreeNode) 节点类型都是Node或者Node的子类TreeNode
             *     所以可以返回Node
             * 2. do{}while里面是去找下一个槽并且存在next中
             */
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }
        
        /**
         * 删除操作,
         * 1. 请注意删除的是current元素,而不是next元素
         * 2. 调用removeNode删除成功会使得modCount增加1,
         *    此时会与expectedModCount不相等,但是又把修改后的modCount赋值给expectedModCount
         */
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

接下来看看三个实现Iterator的类:KeyIterator,ValueIterator,EntryIterator

// 继承HashIterator的方法并且实现next()从而实现了Iterator的所有方法
    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }
    // 继承HashIterator的方法并且实现next()从而实现了Iterator的所有方法
    final class ValueIterator extends HashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }
    // 继承HashIterator的方法并且实现next()从而实现了Iterator的所有方法
    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

明白了这些之后,就要进入下面的正题了entrySet()

`entrySet()`方法

    transient Set<Map.Entry<K, V>> entrySet;    
    @Override
    public Set<Map.Entry<K, V>> entrySet() {
        Set<Map.Entry<K,V>> es;
        return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
    }
    
    
    final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
        public final int size()                 { return size; }
        public final void clear()               { HashMap.this.clear(); }
        //生成迭代器
        public final Iterator<Map.Entry<K,V>> iterator() {
                System.out.println("creating Iterator in EntrySet...");
            return new EntryIterator();
        }
        //判断是否存在对象o
        public final boolean contains(Object o) {
            if (!(o instanceof Map.Entry))
                return false;
            Map.Entry<?,?> e = (Map.Entry<?,?>) o;
            Object key = e.getKey();
            Node<K,V> candidate = getNode(hash(key), key);
            return candidate != null && candidate.equals(e);
        }
        //删除对象o
        public final boolean remove(Object o) {
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>) o;
                Object key = e.getKey();
                Object value = e.getValue();
                return removeNode(hash(key), key, value, true, true) != null;
            }
            return false;
        }
        //分离式迭代器 
        public final Spliterator<Map.Entry<K,V>> spliterator() {
            return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }
        //遍历
        public final void forEach(Consumer<? super Map.Entry<K,V>> 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);
                }
                if (modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }
    }

看到这里,直接看个小例子

小例子

import java.util.Iterator;
import java.util.Map;

public class TestHashMapIteration {

    public static void main(String[] args) {
        HashMap<String, Integer> map = new HashMap<>();
        String str = "ABCDEFG";
        for (int i = 0; i < str.length(); i++) {
            map.put(str.charAt(i) + "", i);
        }
        System.out.println("modCount->" + map.modCount);
        // foreach是调用iterator()方法返回迭代器 用迭代器来遍历
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.print("[" + entry.getKey() + "->" + entry.getValue() + "] ");
        }
        System.out.println("\nmodCount->" + map.modCount);
        System.out.println("-----------------------------------");
        Iterator iter = map.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry<String, Integer> entry = (Map.Entry<String, Integer>)iter.next();
            System.out.print("[" + entry.getKey() + "->" + entry.getValue() + "] ");
            //map.remove(entry.getKey()); // 会产生java.util.ConcurrentModificationException
            //map.put("X", -1);  //会产生java.util.ConcurrentModificationException
            //map.put("A", 2);  //不会有影响,因为是更新节点,不会modCount++
            iter.remove(); //没有影响  
        }
        System.out.println("\nmodCount->" + map.modCount);
        System.out.println("size:" + map.size);
    }
}

结果:可以看到foreach其实是调用迭代器实现的,还有一点是在迭代器中使用HashMap的成员方法remove(Object key)会使得modCount与迭代器中的expectedCount不相同,会抛出java.util.ConcurrentModificationException异常.但是使用迭代器自身的remove就不会有影响,至于为什么?在上面的代码中有提到.

modCount->7
creating Iterator in EntrySet...
[A->0] [B->1] [C->2] [D->3] [E->4] [F->5] [G->6] 
modCount->7
-----------------------------------
creating Iterator in EntrySet...
[A->0] [B->1] [C->2] [D->3] [E->4] [F->5] [G->6] 
modCount->14
size:0

相同原理的KeySet就不多解释了,keySet变量是AbstractMap中继承的,

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

    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();
            }
        }
    }

有一点大家可以思考下,即使类HashMap中没有实现keySet()方法,只需要实现entrySet()方法后,下面的代码也可以运行成功.原因大家可以自己思考一下？

for (String k : map.keySet()) {
    System.out.print("[" + k + "->" + map.get(k) + "] ");
}

答案在AbstractMap中,看一下源码就知道了.

`Spliterator`

对Spliterator不了解的人可以参考用例子解析Spliterator,

 static class HashMapSpliterator<K,V> {
            //存数据的map
        final HashMap<K,V> map;
        // 当前节点
        Node<K,V> current;          // current node
        // 当前槽
        int index;                  // current index, modified on advance/split
        //最后一个槽 有效槽[index, fence-1]
        int fence;                  // one past last index
        //预计节点的数量 估计值  不是正确的值没有去统计
        int est;                    // size estimate
        int expectedModCount;       // for comodification checks

        HashMapSpliterator(HashMap<K,V> m, int origin,
                           int fence, int est,
                           int expectedModCount) {
            this.map = m;
            this.index = origin;
            this.fence = fence;
            this.est = est;
            this.expectedModCount = expectedModCount;
        }
        
        //初始化
        final int getFence() { // initialize fence and size on first use
            int hi;
            if ((hi = fence) < 0) {
                HashMap<K,V> m = map;
                est = m.size;
                expectedModCount = m.modCount;
                Node<K,V>[] tab = m.table;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            return hi;
        }
        
        public final long estimateSize() {
            getFence(); // force init
            return (long) est;
        }
    }

static final class EntrySpliterator<K,V>
        extends HashMapSpliterator<K,V>
        implements Spliterator<Map.Entry<K,V>> {
            
            //构造函数
        EntrySpliterator(HashMap<K,V> m, int origin, int fence, int est,
                         int expectedModCount) {
            super(m, origin, fence, est, expectedModCount);
        }
        
        //拆分 二分拆分并且est只是单纯的除以2
        public EntrySpliterator<K,V> trySplit() {
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid || current != null) ? null :
                new EntrySpliterator<>(map, lo, index = mid, est >>>= 1,
                                          expectedModCount);
        }
        
        //遍历
        public void forEachRemaining(Consumer<? super Map.Entry<K,V>> action) {
            int i, hi, mc;
            if (action == null)
                throw new NullPointerException();
            HashMap<K,V> m = map;
            Node<K,V>[] tab = m.table;
            if ((hi = fence) < 0) {
                mc = expectedModCount = m.modCount;
                hi = fence = (tab == null) ? 0 : tab.length;
            }
            else
                mc = expectedModCount;
            if (tab != null && tab.length >= hi &&
                (i = index) >= 0 && (i < (index = hi) || current != null)) {
                Node<K,V> p = current;
                current = null;
                do {
                    if (p == null)
                        p = tab[i++];
                    else {
                        action.accept(p);
                        p = p.next;
                    }
                } while (p != null || i < hi);
                //在遍历期间modCount不能发生变化 在增加一个节点和删除一个节点的时候都会造成modCount发生变化
                if (m.modCount != mc)
                    throw new ConcurrentModificationException();
            }
        }

        public boolean tryAdvance(Consumer<? super Map.Entry<K,V>> action) {
            int hi;
            if (action == null)
                throw new NullPointerException();
            Node<K,V>[] tab = map.table;
            if (tab != null && tab.length >= (hi = getFence()) && index >= 0) {
                while (current != null || index < hi) {
                    if (current == null)
                        current = tab[index++];
                    else {
                        Node<K,V> e = current;
                        current = current.next;
                        action.accept(e);
                        if (map.modCount != expectedModCount)
                            throw new ConcurrentModificationException();
                        return true;
                    }
                }
            }
            return false;
        }

        public int characteristics() {
            return (fence < 0 || est == map.size ? Spliterator.SIZED : 0) |
                Spliterator.DISTINCT;
        }
        
        //我自己加的函数 方便测试
        public String toString() {
                return "[index=" + super.index + ", fence=" + getFence() + ", est=" + est + "]";
        }
    }

调用在EntrySet类中

//分离式迭代器 
        public final Spliterator<Map.Entry<K,V>> spliterator() {
            return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
        }

测试:

public class TestHashMapIteration {

    public static void main(String[] args) {
        test_spliterator();
    }
    
    public static void test_spliterator() {
        HashMap<String, Integer> map = new HashMap<>();
        String str = "ABCDEFG";
        for (int i = 0; i < str.length(); i++) {
            map.put(str.charAt(i) + "", i);
        }
        System.out.println("capacity:" + map.table.length);
        Spliterator<Map.Entry<String,Integer>> ster_1 = map.entrySet().spliterator();
        System.out.println("ster_1:" + ster_1);
        Spliterator<Map.Entry<String,Integer>> ster_2 = ster_1.trySplit();
        System.out.println("----------split------------");
        System.out.println("ster_1:" + ster_1);
        System.out.println("ster_2:" + ster_2);
        Spliterator<Map.Entry<String,Integer>> ster_3 = ster_1.trySplit();
        Spliterator<Map.Entry<String,Integer>> ster_4 = ster_2.trySplit();
        System.out.println("----------split------------");
        System.out.println("ster_1:" + ster_1);
        System.out.println("ster_2:" + ster_2);
        System.out.println("ster_3:" + ster_3);
        System.out.println("ster_4:" + ster_4);
        
        System.out.println("------ster1-------");
        printSpliterator(map, ster_1);
        System.out.println("------ster2-------");
        printSpliterator(map, ster_2);
        System.out.println("------ster3-------");
        printSpliterator(map, ster_3);
        System.out.println("------ster4-------");
        printSpliterator(map, ster_4);
    }
    
    private static void printSpliterator(HashMap<String, Integer> map, Spliterator<Map.Entry<String,Integer>> ster) {
        ster.forEachRemaining(new Consumer<Map.Entry<String,Integer>>(){

            @Override
            public void accept(Entry<String, Integer> t) {
                System.out.println(t.getKey() + "->" + t.getValue());
                //map.remove("A");   //java.util.ConcurrentModificationException
                //map.put("A", -1);    //更新节点 不影响
            }
            
        });
    }
}

结果:

capacity:16
ster_1:[index=0, fence=16, est=7]
----------split------------
ster_1:[index=8, fence=16, est=3]
ster_2:[index=0, fence=8, est=3]
----------split------------
ster_1:[index=12, fence=16, est=1]
ster_2:[index=4, fence=8, est=1]
ster_3:[index=8, fence=12, est=1]
ster_4:[index=0, fence=4, est=1]
------ster1-------

------ster2-------
[D->3] [E->4] [F->5] [G->6] 
------ster3-------

------ster4-------
[A->0] [B->1] [C->2]

KeySpliterator和ValueSpliterator与EntrySpliterator类似

1.HashMap1.8 源码解析(1)--插入元素
2.HashMap1.8 源码解析(2)--删除元素
3.HashMap1.8 源码解析(3)--TreeNode(红黑树)包括每一个方法
4.HashMap1.8 源码解析(4)--遍历元素

最后编辑于：2018.06.27 04:07:53

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 206,839评论 6赞 482
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 88,543评论 2赞 382
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 153,116评论 0赞 344
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 55,371评论 1赞 279
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 64,384评论 5赞 374
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 49,111评论 1赞 285
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 38,416评论 3赞 400
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 37,053评论 0赞 259
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 43,558评论 1赞 300
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 36,007评论 2赞 325
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 38,117评论 1赞 334
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 33,756评论 4赞 324
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 39,324评论 3赞 307
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 30,315评论 0赞 19
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 31,539评论 1赞 262
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 45,578评论 2赞 355
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 42,877评论 2赞 345

HashMap1.8 源码解析(4)--遍历元素

前言

Iterator接口

抽象类HashIterator

entrySet()方法

小例子

Spliterator

推荐阅读更多精彩内容

`Iterator`接口

抽象类`HashIterator`

`entrySet()`方法

`Spliterator`