Java容器HashMap遍历方法和源代码解析

朴灿烈づ我的快乐病毒、 2022-06-15 01:23 147阅读 0赞

## **写在前面的话** ##

本文针对的是Java1.6进行的源码分析，与其他版本可能存在差异。关于HashMap的底层结构和基本方法的解析，请参阅[Java容器HashMap源代码解析][Java_HashMap]

## **HashMap遍历用法** ##

HashMap有四种遍历方法：1.遍历keySets，把每个key对应的值再取出来，这种方法最常用到；2.遍历values，直接获取map中的值；3.用迭代器直接进行遍历；4.遍历entrySet，此方法比起第一种方法来说，少了根据key去取value的操作，所以当数据量比较大时，效率会比一种方法高，推荐使用此方法。  
四种遍历方法的代码示例如下：

public static void main(String[] args) {
            Map<String, String> map = new HashMap<String, String>();
            map.put("k1", "v1");
            map.put("k2", "v2");
            map.put("k3", "v3");
    
            //第一种遍历方法，遍历keySet，用每个key再把value取出来，这种方法比较常用
            for(String key : map.keySet()) {
                System.out.println("key=" + key + ",value=" + map.get(key));
            }
    
            //第二种遍历方法，直接遍历values，这种方法的缺点是只能得到value值
            for(String value : map.values()) {
                System.out.println("value=" + value);
            }
    
            //第三种遍历方法，用迭代器
            Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
            while(iterator.hasNext()) {
                Map.Entry<String, String> entry = iterator.next();
                System.out.println("key=" + entry.getKey() + ",value=" + entry.getValue());
            }
    
            //第四种遍历方法，遍历entrySet,数据量大时推荐使用此种方法
            for(Map.Entry<String, String> entry : map.entrySet()) {
                System.out.println("key=" + entry.getKey() + ",value=" + entry.getValue());
            }
        }

## **HashMap遍历源代码解析** ##

在这里，我们以第一种遍历方式为例，来探讨一下HashMap遍历方法的实现。KeySet方法在HashMap中只有短短两行的代码，如下：

public Set<K> keySet() {
            //keySet是在AbstractMap中定义的一个set值
            Set<K> ks = keySet;
            //如果keySet有值就返回，如果为null就返回KeySet的一个对象
            return (ks != null ? ks : (keySet = new KeySet()));
        }

这两行代码很简洁，逻辑也很好懂，keySet是在AbstractMap中定义的一个set值。如果keySet不为null，就返回keySet；如果keySet的值为null，就生成KeySet类的一个对象，把这个对象赋值给keySet，并作为结果返回。  
刚开始看这段代码时，我也是很疑惑。我们都知道，HashMap的底层结构，实际上就是一个Entry类型的数组table。在没看源码前，我还以为keySet的实现是自己定义了一个数组，然后当每次往table中添加数据时，会显式的把key值同步添加到keySet的数组中。然而事实是，只用了这么短短的两行代码，就实现了这个功能。那究竟是怎么实现的呢？我们接着看KeySet这个类，答案就在这个类里。KeySet的源代码如下：

private final class KeySet extends AbstractSet<K> {
        
            //实现迭代器
            public Iterator<K> iterator() {
                return newKeyIterator();
            }
            //实现size()方法，直接返回HashMap的大小
            public int size() {
                return size;
            }
            //实现contains方法，直接调用HashMap的containsKey方法
            public boolean contains(Object o) {
                return containsKey(o);
            }
            //实现remove方法，直接调用HashMap的removeEntryForKey方法
            public boolean remove(Object o) {
                return HashMap.this.removeEntryForKey(o) != null;
            }
            //实现clear方法，直接调用HashMap的clear方法
            public void clear() {
                HashMap.this.clear();
            }
        }

KeySet类的代码也比较简单易懂，它继承了AbstractSet类，并实现了五个方法。后四个方法都是调用的HashMap中的方法，不再详述，我们主要看第一个方法，关于迭代器的实现。我们知道，增强型for循环，其实内部就是用迭代器来实现的，具体的可以参考这篇博文：[java中增强for循环的原理][java_for]。所以，第一种遍历方法，实际上用到的正是这个迭代器实现方法。下面我们在看newKeyIterator()这个方法源代码：

Iterator<K> newKeyIterator()   {
            return new KeyIterator();
        }

这个方法只是new了一个KeyIterator的对象，并把它返回。我们再往下继续找，看下KeyIterator的源代码：

private final class KeyIterator extends HashIterator<K> {
        
            public K next() {
                return nextEntry().getKey();
            }
        }

KeyIterator 继承了HashIterator，而且只有一个简单的next方法。我们都知道，迭代器接口定义了三个方法，即next()，hasNext()和remove()。next()方法是得到容器里的下一个数据，hasNext()是判断容器里是否还有数据，remove()是删除容器中的数据。KeyIterator 只实现了next()方法，说明其他的方法肯定是在HashIterator中实现的。我们先看HashIterator的实现代码：

private abstract class HashIterator<E> implements Iterator<E> {
        
            Entry<K,V> next;    //下一个Entry
            int expectedModCount;   //用于多线程中
            int index;      // 索引
            Entry<K,V> current; //  当前entry
    
            HashIterator() {
                expectedModCount = modCount;
                //构造函数，得到第一个Entry
                if (size > 0) {
                    //table就是HashMap的底层数组 
                    Entry[] t = table;
                    //找到table中的第一个Entry并赋值给next
                    while (index < t.length && (next = t[index++]) == null)
                        ;
                }
            }
    
            public final boolean hasNext() {
                //实现接口中的hasNext()方法，直接判断next是否等于null
                return next != null;
            }
    
            //寻找下一个Entry
            final Entry<K,V> nextEntry() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                //在构造函数中next已经指向第一个Entry，所以最开始e就是第一个Entry
                Entry<K,V> e = next;
                if (e == null)
                    throw new NoSuchElementException();
                //寻找到下一个Entry并赋值给next
                if ((next = e.next) == null) {
                    Entry[] t = table;
                    while (index < t.length && (next = t[index++]) == null)
                        ;
                }
                current = e;
                //把e返回，如果一直调用此方法，相当于从第一个Entry开始，逐个返回
                return e;
            }
    
            //实现接口中的remove()方法，调用HashMap中的removeEntryForKey方法
            public void remove() {
                if (current == null)
                    throw new IllegalStateException();
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
                Object k = current.key;
                current = null;
                HashMap.this.removeEntryForKey(k);
                expectedModCount = modCount;
            }
    
        }

HashIterator定义了四个字段，expectedModCount忽略不管，next存储的是下一个Entry，index储存的是next值在table中索引的下一个值，current是当前Entry。remove和next方法比较简单，就不再详述了，主要是看构造函数和nextEntry方法。构造函数的作用就是找到table中存储的第一个Entry，并赋值给next。因为HashMap往table中存储是不连续的，所以找到table中第一个不为null的值，即是我们要找的。nextEntry()的作用是寻找下一个Entry，寻找方法同构造函数，并且会把当前的Entry返回。  
理解了HashIterator之后，我们再回过头来看KeyIterator，它只实现了next方法，next返回的即是当前Entry的key。所以，当我们用增强型for循环，去遍历KeySet的时候，就会调用hasNext()方法和next方法，去遍历table中的所有key。分析到这里，终于弄明白HashMap是如何实现遍历的了。  
用values和entrySet遍历的方法与keySet遍历的原理是一样的，只是它们实现迭代器接口的next()方法有区别而已，代码如下：

private final class ValueIterator extends HashIterator<V> {
        
            public V next() {
                //返回的是当前entry的value值
                return nextEntry().value;
            }
        }

private final class EntryIterator extends HashIterator<Map.Entry<K,V>> {
        
            public Map.Entry<K,V> next() {
                //返回的是当前entry
                return nextEntry();
            }
        }

[Java_HashMap]: http://blog.csdn.net/kevin_zhai/article/details/72652516
[java_for]: http://blog.csdn.net/H_Gao/article/details/52901297