Redian新闻
>
公司新来一个同事:为什么 HashMap 不能一边遍历一边删除?一下子把我问懵了!

公司新来一个同事:为什么 HashMap 不能一边遍历一边删除?一下子把我问懵了!

公众号新闻

来源:https://juejin.cn/post/7114669787870920734


上一篇干货:新来的同事问我 where 1=1 是什么意思 ?

前段时间,同事在代码中KW扫描的时候出现这样一条:

上面出现这样的原因是在使用foreach对HashMap进行遍历时,同时进行put赋值操作会有问题,异常ConcurrentModificationException。

于是帮同简单的看了一下,印象中集合类在进行遍历时同时进行删除或者添加操作时需要谨慎,一般使用迭代器进行操作。

于是告诉同事,应该使用迭代器Iterator来对集合元素进行操作。同事问我为什么?这一下子把我问蒙了?对啊,只是记得这样用不可以,但是好像自己从来没有细究过为什么?

于是今天决定把这个HashMap遍历操作好好地研究一番,防止采坑!

foreach循环?

java foreach 语法是在jdk1.5时加入的新特性,主要是当作for语法的一个增强,那么它的底层到底是怎么实现的呢?下面我们来好好研究一下:

foreach 语法内部,对collection是用iterator迭代器来实现的,对数组是用下标遍历来实现。Java 5 及以上的编译器隐藏了基于iteration和数组下标遍历的内部实现。

(注意,这里说的是“Java编译器”或Java语言对其实现做了隐藏,而不是某段Java代码对其实现做了隐藏,也就是说,我们在任何一段JDK的Java代码中都找不到这里被隐藏的实现。这里的实现,隐藏在了Java 编译器中,查看一段foreach的Java代码编译成的字节码,从中揣测它到底是怎么实现的了)

我们写一个例子来研究一下:

public class HashMapIteratorDemo {

 String[] arr = {"aa""bb""cc"};

 public void test1() {
  for(String str : arr) {
  }
 }
}

将上面的例子转为字节码反编译一下(主函数部分):

也许我们不能很清楚这些指令到底有什么作用,但是我们可以对比一下下面段代码产生的字节码指令:

public class HashMapIteratorDemo2 {

 String[] arr = {"aa""bb""cc"};

 public void test1() {
  for(int i = 0; i < arr.length; i++) {
   String str = arr[i];
  }
 }
}

看看两个字节码文件,有木有发现指令几乎相同,如果还有疑问我们再看看对集合的foreach操作:

通过foreach遍历集合:

public class HashMapIteratorDemo3 {

 List<Integer> list = new ArrayList<>();

 public void test1() {
  list.add(1);
  list.add(2);
  list.add(3);

  for(Integer var : list) {
  }
 }
}

通过Iterator遍历集合:

public class HashMapIteratorDemo4 {

 List<Integer> list = new ArrayList<>();

 public void test1() {
  list.add(1);
  list.add(2);
  list.add(3);

  Iterator<Integer> it = list.iterator();
  while(it.hasNext()) {
   Integer var = it.next();
  }
 }
}

将两个方法的字节码对比如下:

我们发现两个方法字节码指令操作几乎一模一样;

这样我们可以得出以下结论:

对集合来说,由于集合都实现了Iterator迭代器,foreach语法最终被编译器转为了对Iterator.next()的调用;

对于数组来说,就是转化为对数组中的每一个元素的循环引用。

HashMap遍历集合并对集合元素进行remove、put、add

1、现象

根据以上分析,我们知道HashMap底层是实现了Iterator迭代器的 ,那么理论上我们也是可以使用迭代器进行遍历的,这倒是不假,例如下面:

public class HashMapIteratorDemo5 {

 public static void main(String[] args) {
  Map<Integer, String> map = new HashMap<>();
  map.put(1"aa");
  map.put(2"bb");
  map.put(3"cc");

  for(Map.Entry<Integer, String> entry : map.entrySet()){
      int k=entry.getKey();
      String v=entry.getValue();
      System.out.println(k+" = "+v);
  }
 }
}

输出:

ok,遍历没有问题,那么操作集合元素remove、put、add呢?

public class HashMapIteratorDemo5 {

 public static void main(String[] args) {
  Map<Integer, String> map = new HashMap<>();
  map.put(1"aa");
  map.put(2"bb");
  map.put(3"cc");

  for(Map.Entry<Integer, String> entry : map.entrySet()){
      int k=entry.getKey();
      if(k == 1) {
       map.put(1"AA");
      }
      String v=entry.getValue();
      System.out.println(k+" = "+v);
  }
 }
}

执行结果:

执行没有问题,put操作也成功了。

但是!但是!但是!问题来了!!!

我们知道HashMap是一个线程不安全的集合类,如果使用foreach遍历时,进行add,remove操作会java.util.ConcurrentModificationException异常。put操作可能会抛出该异常。(为什么说可能,这个我们后面解释)

为什么会抛出这个异常呢?

我们先去看一下java api文档对HasMap操作的解释吧。

翻译过来大致的意思就是该方法是返回此映射中包含的键的集合视图。集合由映射支持,如果在对集合进行迭代时修改了映射(通过迭代器自己的移除操作除外),则迭代的结果是未定义的。集合支持元素移除,通过Iterator.remove、set.remove、removeAll、retainal和clear操作从映射中移除相应的映射。简单说,就是通过map.entrySet()这种方式遍历集合时,不能对集合本身进行remove、add等操作,需要使用迭代器进行操作。

对于put操作,如果这个操作时替换操作如上例中将第一个元素进行修改,就没有抛出异常,但是如果是使用put添加元素的操作,则肯定会抛出异常了。我们把上面的例子修改一下:

public class HashMapIteratorDemo5 {

 public static void main(String[] args) {
  Map<Integer, String> map = new HashMap<>();
  map.put(1"aa");
  map.put(2"bb");
  map.put(3"cc");

  for(Map.Entry<Integer, String> entry : map.entrySet()){
      int k=entry.getKey();
      if(k == 1) {
       map.put(4"AA");
      }
      String v=entry.getValue();
      System.out.println(k+" = "+v);
  }

 }
}

执行出现异常:

这就是验证了上面说的put操作可能会抛出java.util.ConcurrentModificationException异常。

但是有疑问了,我们上面说过foreach循环就是通过迭代器进行的遍历啊?为什么到这里是不可以了呢?

这里其实很简单,原因是我们的遍历操作底层确实是通过迭代器进行的,但是我们的remove等操作是通过直接操作map进行的,如上例子:map.put(4, "AA");//这里实际还是直接对集合进行的操作,而不是通过迭代器进行操作。所以依然会存在ConcurrentModificationException异常问题。

2、细究底层原理

我们再去看看HashMap的源码,通过源代码,我们发现集合在使用Iterator进行遍历时都会用到这个方法:

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) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

这里modCount是表示map中的元素被修改了几次(在移除,新加元素时此值都会自增),而expectedModCount是表示期望的修改次数,在迭代器构造的时候这两个值是相等,如果在遍历过程中这两个值出现了不同步就会抛出ConcurrentModificationException异常。

现在我们来看看集合remove操作:

(1)HashMap本身的remove实现:

public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, nullfalsetrue)) == null ?
        null : e.value;
}

(2)HashMap.KeySet的remove实现

public final boolean remove(Object key) {
    return removeNode(hash(key), key, nullfalsetrue) != null;
}

(3)HashMap.EntrySet的remove实现

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, truetrue) != null;
    }
    return false;
}

(4)HashMap.HashIterator的remove方法实现

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, nullfalsefalse);
    expectedModCount = modCount; //----------------这里将expectedModCount 与modCount进行同步
}

以上四种方式都通过调用HashMap.removeNode方法来实现删除key的操作。在removeNode方法内只要移除了key, modCount就会执行一次自增操作,此时modCount就与expectedModCount不一致了;

final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable)
 
{
    Node<K,V>[] tab; Node<K,V> p; int n, index;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        ...
        if (node != null && (!matchValue || (v = node.value) == value ||
                             (value != null && value.equals(v)))) {
            if (node instanceof TreeNode)
                ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
            else if (node == p)
                tab[index] = node.next;
            else
                p.next = node.next;
            ++modCount;   //------------------------这里对modCount进行了自增,可能会导致后面与expectedModCount不一致
            --size;
            afterNodeRemoval(node);
            return node;
        }
        }
        return null;
   }

上面三种remove实现中,只有第三种iterator的remove方法在调用完removeNode方法后同步了expectedModCount值与modCount相同,所以在遍历下个元素调用nextNode方法时,iterator方式不会抛异常。

到这里是不是有一种恍然大明白的感觉呢!

所以,如果需要对集合遍历时进行元素操作需要借助Iterator迭代器进行,如下:

public class HashMapIteratorDemo5 {

 public static void main(String[] args) {
  Map<Integer, String> map = new HashMap<>();
  map.put(1"aa");
  map.put(2"bb");
  map.put(3"cc");
  //  for(Map.Entry<Integer, String> entry : map.entrySet()){  //      int k=entry.getKey();  //      //      if(k == 1) {//       map.put(1, "AA");//      }//      String v=entry.getValue();  //      System.out.println(k+" = "+v);  //  }

  Iterator<Map.Entry<Integer, String>> it = map.entrySet().iterator();
  while(it.hasNext()){
   Map.Entry<Integer, String> entry = it.next();
   int key=entry.getKey();
         if(key == 1){
             it.remove();
         }
  }
 }
}

来个“分享、点赞、在看”👇

微信扫码关注该文公众号作者

戳这里提交新闻线索和高质量文章给我们。
相关阅读
行人大呼痛快!执法人员开大卡车全部拉走货物!八大道无证摊贩被大面积查抄,街道一下子通畅了....全球Top1咨询公司新人内训手册曝光!645页PDF起底真实Case面…改了一行代码,数组遍历耗时从10.3秒降到了0.5秒!突发!知名公司新一轮大裁员!经济前景10年最低,加拿大央行或掉头紧缩?小说:兰欣与乌茶突发!Hinton入局机器人创业,公司新获9000万投资公司柯基被喂成“猪崽”,俩人抬不上车…同事:胖宝宝胖宝宝,一点也不沉同行不同命?一边是“蔚来销售月入10万”,另一边是“过半经销商亏损,超7成未达到销量目标”!新来一个同事:为什么 HashMap 不能一边遍历一边删除?一下子把我问懵了!大捡漏!国际重奢𝘼𝙦𝙪𝙖𝙨𝙘𝙪𝙩𝙪𝙢雅格狮丹出系列了!五防保暖夹克、POLO衫、西裤随便搭“为什么新来的员工工资比我高?”因为一道围栏,澳洲家庭被邻居告上法庭!一下子没了$16万为什么阿里巴巴修正了HashMap关于1024个元素扩容的次数?美国流感疫苗接种率竟然这么高?!为什么?为什么:$100 美元汇出 (华夏银行),只收到$86美元 (BoA)佐州夫妻买土地开Airbnb,被人盗图做假账号结果一下子火了!权力是最好的春药,为什么?9月上电影备案:《长安十二时辰》电影版、吴京公司新武侠电影《刀》通过备案马尔济斯尿了一个“?” ,主人惊了:一边尿尿一边写字?日本日记9: 富士宫市邂逅富士山时光里一叶小舟已经不是啥新鲜玩意的短剧,怎么一下子又成流量密码了?数据如何删除?《加州删除法案》介绍插画师玫瑰:你不能一辈子像一个小孩一样,一个劲地去延长你的童年|席外话04集中和分散的思考,如何看待遍历性?全球Top1咨询公司新题,居然在这本Casebook里找到了答案吹尽黄沙不见金(七十七):嫉妒牛的,一下子就被她拉回童年了~1折入!穿过国际重奢𝘼𝙦𝙪𝙖𝙨𝙘𝙪𝙩𝙪𝙢的男人,才会明白什么是品质!为什么 MAGA 要背叛乌克兰?纽时文译HMO正式获批,飞鹤率先推出国内首款HMO奶粉规培“两个同等对待”,西安在入编招聘中落实了!男子吃菌后开车幻觉撞到小孩,一句“我要关几天”问懵民警图文并茂,HashMap 这篇写得太好了!!一句“窝囊废”,男子杀害同事潜逃16年:为什么我劝你别惹老实人?红色日记 10.1-20婆婆打探儿媳的工资 为什么?大众与地平线合资公司新进展:调入上百人,CTO黄畅坐镇|36氪独家新来的同事问我 where 1=1 是什么意思 ?一边注销公司一边成立新公司,“核酸大王”张核子又有新动向→
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。