首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >get的过程中另一个线程删除一个entry

get的过程中另一个线程删除一个entry

原创
作者头像
用户7365393
修改2021-10-08 15:19:53
4740
修改2021-10-08 15:19:53
举报
get的过程中另一个线程删除一个entry

  假设我们的链表元素是:e1-> e2 -> e3 -> e4 我们要删除 e3这个entry   因为HashEntry中next的不可变,所以我们无法直接把e2的next指向e4,而是将要删除的节点之前的节点复制一份,形成新的链表。它的实现大致如下图所示:

  注意:最后才将数组中对应桶位置的链表替换为新链表(也就是在最后一步替换之前,tab[i]指向的始终是删除之前的链表,详细看下面的remove方法)。   如果我们get的也恰巧是e3,可能我们顺着链表刚找到e1,这时另一个线程就执行了删除e3的操作,而我们线程还会继续沿着旧的链表找到e3返回,这时候可能看到被删除的数据,但是在高并发环境下,这种影响是很小的。

remove方法
    V remove(Object key, int hash, Object value) { 
           lock();         // 加锁
           try{ 
               int c = count - 1; 
               HashEntry<K,V>[] tab = table; 
               int index = hash & (tab.length - 1); 
               HashEntry<K,V> first = tab[index]; 
               HashEntry<K,V> e = first; 
               while(e != null&& (e.hash != hash || !key.equals(e.key))) 
                   e = e.next; 
 
               V oldValue = null; 
               if(e != null) { 
                   V v = e.value; 
                   if(value == null|| value.equals(v)) { // 找到要删除的节点
                       oldValue = v; 
                       ++modCount; 
                       // 所有处于待删除节点之后的节点原样保留在链表中
                       // 所有处于待删除节点之前的节点被克隆(其实是把所有值取出来放到一个新的HashEntry对象中)到新链表中
                       HashEntry<K,V> newFirst = e.next;// 待删节点的后继结点
                       for(HashEntry<K,V> p = first; p != e; p = p.next) 
                           newFirst = new HashEntry<K,V>(p.key, p.hash,  newFirst, p.value); 

                       // 新的头结点是原链表中,删除节点之前的那个节点
                       tab[index] = newFirst; 
                       count = c;      // 写 count 变量
                   } 
               } 
               return oldValue; 
           } finally{ 
               unlock();               // 解锁
           } 
       }

  和 get 操作一样,首先根据散列码找到具体的链表;然后遍历这个链表找到要删除的节点;最后把待删除节点之后的所有节点原样保留在新链表中,把待删除节点之前的每个节点克隆(其实是把所有值取出来放到一个新的HashEntry对象中)到新链表中;最后才将数组中对应桶位置的链表替换为新链表(也就是在替换之前,get的始终是删除之前的链表)。   下面通过图例来说明 remove 操作。假设写线程执行 remove 操作,要删除链表的 C 节点,另一个读线程同时正在遍历这个链表。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。

如有侵权,请联系 cloudcommunity@tencent.com 删除。

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • get的过程中另一个线程删除一个entry
  • remove方法
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档