HashMap的entrySet与keySet区别?源码分析

前言

这个问题在我分析HashMap源码时,困扰了我一段时间,在网上搜了很多文章,反复揣摩n次之后,终于直到为什么了.
如果你也困惑,不清楚entrySet和keySet数据的来源,为什么entrySet比keySet快,就请往下看.

entrySet

源码分析

public Set<Map.Entry<K,V>> entrySet() {
    Set<Map.Entry<K,V>> es;
    return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}

transient Set<Map.Entry<K,V>> entrySet;

进入HashMap的这个方法,我们可以看到,首先去找成员变量entrySet如果为空就创建一个EntrySet对象,不为空直接进行返回
这个方法返回的是Set集合,里面放的是Map.Entry<K,V>类型,

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

因为内部类Nodestatic class Node<K,V> implements Map.Entry<K,V>实现了Map.Entry<K,V>接口,
所以所Set集合中放的都是Node节点,Node里面封装了我们需要的数据,
我们知道了Set集合中放入的是什么了,我们再进入EntrySet对象一探究竟,
我们entrySet()方法返回的entrySet变量是通过new EntrySet()得来的.

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() {
        return new EntryIterator();
    }
    public final boolean contains(Object o) {...}
    public final boolean remove(Object o) {...}
    public final Spliterator<Map.Entry<K,V>> spliterator() {...}
    public final void forEach(Consumer<? super Map.Entry<K,V>> action) {...}
}

这里我对一些方法体进行了省略,我们可以看到EntrySet对象是继承AbstractSet<Map.Entry<K,V>>对象的,
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {
根据继承的特点,父类AbstractSet<E>实现了Set<E>接口,我们可知子类EntrySet也相当于实现了Set接口,
这里的Set集合的size()方法,返回的就是HashMap成员变量size,作用是记录数据量,里面有多少个Node节点.

遍历数据(for,while)

HashMap<String,String> hashMap=new HashMap<>();
hashMap.put("a", "aa");
hashMap.put("b", "bb");
hashMap.put("c", "cc");
hashMap.put("d", "dd");

Set<Map.Entry<String, String>> entries = hashMap.entrySet();
for (Map.Entry<String,String> e:entries)
{
    System.out.println(e);
}

根据迭代器的原理,我们想遍历Set集合,需要先通过方法iterator()获取迭代器,通过迭代器才能循环获取里面的数据,
而这里的iterator()方法返回的是一个EntryIterator对象,我们再继续往下走,一探究竟 ->

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

可以看出,它确实实现了迭代器Iterator接口,而且接口封装了Map.Entry<K,V>数据,也就是说迭代器所迭代的就是Node节点数据.
EntryIterator对象继承了HashIterator对象,
根据继承性,创建EntryIterator无参对象会先调用HashIterator无参构造函数,

abstract class HashIterator {
    Node<K,V> next;        // 下一个 Node节点
    Node<K,V> current;     // 当前 Node节点
    int expectedModCount;  // 用于判断fast-fail快速失败
    int index;             // 当前位置

    HashIterator() {
        /*
        获取结构变化记录数,
        用于判断结构是否变化
        只有(添加,删除)记录数才会变化.
        */
        expectedModCount = modCount;
        /* 获取全部数据 */
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        
        /*
        用next记录下一个有数据的下标位置,
        并把index+1用作下一次循环使用.
        */
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

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

    final Node<K,V> nextNode() {...}

    public final void remove() {...}
}

我们忽略了它的一些方法,执行完了HashIterator无参构造函数,我们知道这些是进行迭代器的数据初始化,
把next指针指向了下一个不为空的Node节点的下标,并把index+1指向下一个下标(用于下一次循环),把结构记录数记录下来(用于判断并发修改异常).
这时执行完iterator()方法返回一个EntryIterator对象,也就是我们所需的迭代器,

Set<Map.Entry<String, String>> entries = hashMap.entrySet();

for (Map.Entry<String,String> e : entries)
{
       System.out.println(e);
}

我们初始化了迭代器(迭代器 = new EntryIterator()),开始进行第一次循环,在第一次进入循环体{}中之前,
先判断迭代器是否可以循环,也就是调用迭代器的hasNext()方法,返回true,才能进行第一次迭代,
我们上面分析了迭代器对象就是new EntryIterator()对象,在EntryIterator中没有hasNext()方法,
根据继承性,就往父类HashIterator中找,找到hasNext()方法,

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

如果next指向的下一个节点不为空,就继续往下执行,调用迭代器的next()方法,获取第一次迭代的Node数据,
(这里会不会有人不知道为什么迭代的是Node数据? 因为上面我们说了EntryIterator实现了Iterator<Map.Entry<K,V>>,而迭代器Iterator接口中封装了Map.Entry<K,V>,也就是封装了Node节点,所以迭代的就是Node数据.)
此时执行了EntryIterator类中的public final Map.Entry<K,V> next() { return nextNode(); }方法,
而nextNode()方法是在父类HashIterator中的,

final Node<K,V> nextNode() {
    Node<K,V>[] t;
    Node<K,V> e = next;
    //1. 如果循环时,添加,删除了数据,抛并发修改异常
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    //2. 没有这个元素,抛异常
    if (e == null)
        throw new NoSuchElementException();
    /*
    3. 这个很重要,这里`(next = (current = e).next)`两个next是不一样的.
    e和current:表示当前循环的节点,也就是返回的节点
    第一个next:表示当前循环节点e的next指针指向的下一个节点,index才是指向的下一个数组下标的位置.
    情况1:next节点为空,table不为null,也就是if为true,此时,可以进入执行do()while{},
          进行数组往下循环,next指向下一个数组下标不为空的节点,index+1
    情况2:next节点不为空,也就是表示不是链表的最后一个节点,
          需要next指向链表的下一个节点,直接返回e
    */
    if ((next = (current = e).next) == null && (t = table) != null) {
        do {} while (index < t.length && (next = t[index++]) == null);
    }
    //4. 返回循环的Node数据
    return e;
}

主要是理解步骤3,它是对当前循环的位置是否有链表,或红黑树存在,而做出的处理.
这个返回的数据e节点,会指向for (Map.Entry<String,String> e:entries)中的循环变量e,这时候才可以进入for的循环体{}中.
执行完循环体{},会再次判断hasNext()方法,返回true,再执行next()方法并把返回的Node节点给循环变量e …

综上所知(下面两种循环的效果相同):

HashMap<String,String> hashMap=new HashMap<>();
hashMap.put("a", "aa");
hashMap.put("b", "bb");
hashMap.put("c", "cc");
hashMap.put("d", "dd");
// 方法1
Set<Map.Entry<String, String>> entries = hashMap.entrySet();
for (Map.Entry<String,String> e:entries)
{
    System.out.println(e);
}

// 方法2
Iterator<Map.Entry<String, String>> iterator = hashMap.entrySet().iterator();
Map.Entry<String, String> e2;
while (iterator.hasNext())
{
    e2=iterator.next();
    System.out.println(e2);
}

foreach循环

但是如果使用的是foreach循环,
我们可知entrySet是HashMap的全局变量,它的指针指向的是一个new EntrySet()对象(迭代器),
使用entrySet.foreach()就是调用EntrySet类中的forEach(...)方法.

HashMap<String,String> hashMap=new HashMap<>();
hashMap.put("a", "aa");
hashMap.put("b", "bb");
hashMap.put("c", "cc");
hashMap.put("d", "dd");
// 全写
hashMap.entrySet().forEach(new Consumer<Map.Entry<String, String>>()
{
    @Override
    public void accept(Map.Entry<String, String> e)
    {
        System.out.println(e);
    }
});
// 简写,Java8 函数式编程写法
hashMap.entrySet().foreach(e ->{
    System.out.println(e);
});

public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
    Node<K,V>[] tab;
    /*
    1. 传入对象为null抛异常
    */
    if (action == null)
        throw new NullPointerException();
    /*
    2. HashMap中有数据
    */
    if (size > 0 && (tab = table) != null) {
        int mc = modCount;
        /*
        (1) 循环获取table数组中的Node节点数据3
        i位置的第一个节点会先赋值给e,如果当前节点e不为空就进入`accept`方法,
        这个`accept`方法就是我们foreach的循环体{}中的内容,执行完循环体,
        把e指向下一个节点,这个是用来判断当前位置是否为链表,红黑树,
        否则,把i+1执行下一个数组下标节点 ...
        */
        for (int i = 0; i < tab.length; ++i) {
            for (Node<K,V> e = tab[i]; e != null; e = e.next)
                action.accept(e);
        }
        //(2) (添加,删除了数据)结构变化,抛并发修改异常
        if (modCount != mc)
            throw new ConcurrentModificationException();
    }
}

由上我们可以看出,foreach和for循环的道理都是差不多的,可以说几乎相同,只不过方式不太一样,
for是调用了迭代器进行循环,其内部还是操作的HashMap的成员变量,
foreach则就是一个方法,直接进行成员变量的操作,更为简洁.

总结

由上我们可以知道entrySet()方法返回的是Set集合,这个Set集合指向的EntrySet对象,
而EntrySet对象可以作为迭代器进行使用,从而实现遍历的效果,
其内部并没保存任何数据,操作的还是HashMap的成员变量(table数组 size大小 等数据),
遍历的Node节点里面封装了我们需要的数据(key,value),HashMap是排序是无序的,所以迭代器遍历起来也是无序的.

keySet

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

//AbstractMap<K,V>中的成员变量,同entrySet变量一样是Set集合
transient Set<K>        keySet;

// KeySet类继承了AbstractSet<K>,也继承了成员变量
final class KeySet extends AbstractSet<K>{
...
public final Iterator<K> iterator()     { return new KeyIterator(); }
...
}

final class KeyIterator extends HashIterator
    implements Iterator<K> {
    // 返回的是它的key,而不是封装的Node节点了.
    public final K next() { return nextNode().key; }
}

我粘贴出部分不同的地方,同理也可分析出ketSet()获取,和迭代也是和entrySet()是同样的,
不同的地方就在于它迭代的是Node节点的key值,而不是Node节点.

所以,如果你需要用到key和value,就用entrySet()进行获取.
这样避免了获取到key,再使用HashMap的get(Object key)方法去获取其对应的value所带来的损耗.

HashMap<String, String> hashMap = new HashMap<>();
hashMap.put("a", "aa");
hashMap.put("b", "bb");
hashMap.put("c", "cc");
hashMap.put("d", "dd");
//方法1:推荐使用
for (Map.Entry<String, String> e : hashMap.entrySet())
{
    System.out.println(e.getKey());// key
    System.out.println(e.getValue());// value
}
//方法2:不推荐
for (String k:hashMap.keySet())
{
    System.out.println(k);// key
    System.out.println(hashMap.get(k));// value
}

values

原理同上.

public Collection<V> values() {
    Collection<V> vs = values;
    if (vs == null) {
        vs = new Values();
        values = vs;
    }
    return vs;
}

//AbstractMap<K,V>中的成员变量,但它是Collection集合.
transient Collection<V> values;

总结

1. 由上面分析,我们知道了实际上entrySet() keySet() values(),
   这三个方法遍历的其实是用来维护HashMap的内部数组table中的数据.
2. 因为其插入是(散列)随机的,所以,遍历起来也是无序的.
3. 其中entrySet() keySet()是Set视图,所以里面保存的都是不重复的数据,
   而values()则不同,它是Collection视图,里面保存的数据是可重复的.