JDK容器学习之HashMap (三) : 迭代器实现

HashMap 迭代器实现方式

java的容器类,实现Collection接口的都会实现迭代器方式,Map则有点特殊,它不实现Collection接口,它的迭代使用方式则主要借助Collection来实现

1. Map的遍历方式

对于List,Set,我们可以直接用 foreach 来实现遍历,而Map则不能直接这么用,通常Map的遍历方式有三种

  1. Entry的遍历
for(Map.Entry entry: map.entrySet()) {
  // xxx
}
  1. Key的遍历
for(Object key : map.keySet()) {
  // xxx
}
  1. Value的遍历
for(Object value: map.values()) {
  // xxxx
}

上面遍历主要依赖的三个方法,前两个返回的都是Set,那么就有下面几个问题

  1. map.entrySet 返回的Entry集合元素个数和Map的size是否相同
  • 简单来讲就是假设有两个Entry的key的hash值相同
  • 那么这两个Entry都会放在这个Set集合中么?
  • 或者说等同HashMap的数组链表格式,Set集合中放的是链表头?
  1. map.keySet 对于key的hashcode相同的场景会出现什么情况
  2. map.values Map中value没有校验,因此value集合容量应可以小于map.size()

2. 实现方式

entrySet

方法的实现如下:

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

可以看到返回的是内部成员变量 entrySet,问题就集中在这个成员变量是如何维护的

按正常的理解是,在添加删除元素的时候,同步维护entrySet的值算是最简单的方法了,然而前面博文《JDK容器学习之HashMap (二) : 读写逻辑详解》中,并没有看到有维护这一段的逻辑

扫了一遍代码,愣是没有发现在什么地方维护有显示的向Set中添加or移除元素了

唯一的可能性就是下面这个初始化了,这一行代码到底做了什么呢?

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) {
     // xxx
  }
  public final boolean remove(Object o) {
    // xxx
  }
  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) {
      // xxx
  }
}


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

首先 EntrySet 是一个 Set 对象,而Set的遍历采用迭代器模式,迭代器模式主要依赖的 iterator() 方法的实现

返回继承 hashIteratorEntryIterator 对象,其中的核心的next()方法就是调用的 hashIterator.nextNode()

到这里,就可以大胆的得出结论,遍历 entrySet 其实就是在依次调用 hashIterator.nextNode() 方法,这个Set本身是不做元素的添加移除操作的,它就是直接封装了的HashMap内部的HashIterator,对外提供服务

HashIterator hash迭代器

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

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { 
          // 遍历数组直到找到第一个非空的Node节点
            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;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
          // 若出现hash碰撞,且当前节点的链尾非空,则next指向链表下一个节点
          // 没有hash碰撞,or链表尾为空,即Node节点内部的next指向空
          // 继续扫描table数组,找到下一个有效的Node节点,并赋值给next
            do {} 
            while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

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

遍历的逻辑如下:

  • 初始化:扫描table数组,找到第一个有效的Node对象并赋值给next对象
  • 依次遍历:
    • 将next对象赋值给临时变量e
      • 因为最终返回的就是当前的next对象
      • 为了保证遍历的可持续性,需要在返回之前,重新获取到下一个next对象
    • 重新设置next对象
      • 若e的next对象存在(即hash碰撞,且链表的下一个节点存在),则next指向下一个节点
      • 若e的next对象为空
      • 若e没有后缀(即这个不存在hash碰撞,链表结构只有这个链头)
      • 上面两种情况,则继续遍历table数组,找到下一个有效的Node对象

所以,针对数组+链表的结构图,扫描的流程应该是

问题一

map.entrySet 返回的Entry集合元素个数和Map的size是否相同

  • 因为entrySet集合实际上持有的依然是table数组中的数据对象,其迭代器就是扫描的table数组,所以size应该相同

借用上次的测试case进行实测, 下面的Demo重新hashCode确保会出现碰撞

public static class Demo {
  public int num;

  public Demo(int num) {
      this.num = num;
  }

  @Override
  public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      Demo demo = (Demo) o;

      return num == demo.num;
  }

  @Override
  public int hashCode() {
      return num % 3 + 16;
  }
}


@Test
public void testMapResize() {
  Map<Demo, Integer> map = new HashMap<>();
  for(int i = 1; i < 12; i++) {
      map.put(new Demo(i), i);
  }

  Set<Map.Entry<Demo, Integer>> set = map.entrySet();
  System.out.println(set.size());  // 11
  Assert.assertTrue(set.size() == map.size());
}

keySet, values

实际上三个实现思路差不多,都是定义一个内部Set对象,迭代器实现对table数组的扫描,因为原理大同小异,不再进行赘述, 看下面两个迭代器基本就知道了

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

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

同样回答下上面的问题

** map.keySet 对于key的hashcode相同的场景会出现什么情况**

  • 没什么关系,set中是根据 equals方法来去重的,与hashcode关系不太大

map.values Map中value没有校验,因此value集合容量应可以小于map.size()

  • 不对,通过上面的实现,可以知道size依然相同

2,小结&收获

1. 几种遍历方式对比

根据不同的场景选择遍历方式

  • 如果需要kv,则遍历EntrySet
  • 如果只需要key, 则遍历 KeySet
  • 如果只需要value,则遍历 ValueSet

2. 有意思的遍历思路

上面的遍历实现,非常的有意思,也有不小的借鉴意义,比如希望给一个对象的内部元素提供一些特殊的遍历方式,可以参考一下这种做法

实现思路:

  • 内部类实现迭代器
  • next方法实现成员变量的迭代逻辑

3, 相关博文

  • JDK容器学习之HashMap (一) : 底层存储结构分析
  • JDK容器学习之HashMap (二) : 读写逻辑详解

关注更多

关注 小灰灰blog

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java技术栈

Java 10 实战第 1 篇:局部变量类型推断

现在 Java 9 被遗弃了直接升级到了 Java 10,之前也发过 Java 10 新特性的文章,现在是开始实战 Java 10 的时候了。

1174
来自专栏java系列博客

java Arrays.aslist用法

1846
来自专栏博岩Java大讲堂

Java集合--HashMap解惑

3795
来自专栏禁心尽力

Java Collection知识总结

首先说说java中常用的集合容器:ArrayList,LinkedList,Vector,HashMap,Hashtable,HashSet,TreeSet。【...

19910
来自专栏编程直播室

读书笔记:《算法图解》第二章 选择排序选择排序:#

1884
来自专栏恰童鞋骚年

剑指Offer面试题:9.二进制中1的个数

  一个基本的思路:先判断整数二进制表示中最右边一位是不是1。接着把输入的整数右移一位,此时原来处于从右边数起的第二位被移到最右边了,再判断是不是1。这样每次移...

752
来自专栏Java学习123

10 个有关 String 的面试问题

1735
来自专栏Fish

归并排序

在课本上学到了归并排序,不过课本上写得有些模糊,所以查了一下,原本对某科已经失去了信心,不过发现某科C语言版的写得还挺好理解,于是就照着自己写了一个。代码可以自...

2477
来自专栏Bingo的深度学习杂货店

Q66 Plus One

Given a non-negative integer represented as a non-empty array of digits, plus on...

3356
来自专栏Java帮帮-微信公众号-技术文章全总结

第十一天 面向对象-接口多态【悟空教程】

1584

扫码关注云+社区

领取腾讯云代金券