`
javaG
  • 浏览: 555037 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

ConcurrentHashMap中的remove方法的bug

    博客分类:
  • java
阅读更多

最近研究了一下 ConcurrentHashMap中源码发现jdk中的remove方法实现有点问题.

同时参考了文章: http://www.iteye.com/topic/344876

以下是对此文章的一段评述的引用:

V get(Object key, int hash) {   
    if (count != 0) { // read-volatile   
        HashEntry<K,V> e = getFirst(hash);   
        while (e != null) {   
            if (e.hash == hash && key.equals(e.key)) {   
                V v = e.value;   
                if (v != null)   
                    return v;   
                return readValueUnderLock(e); // recheck   
            }   
            e = e.next;   
        }   
    }   
    return null;   
}  

 

marlonyao 写道
get操作不需要锁。第一步是访问count变量,这是一个volatile变量,由于所有的修改操作在进行结构修改时都会在最后一步写count变量,通过这种机制保证get操作能够得到几乎最新的结构更新。对于非结构更新,也就是结点值的改变,由于HashEntry的value变量是volatile的,也能保证读取到最新的值。接下来就是对hash链进行遍历找到要获取的结点,如果没有找到,直接访回null。对hash链进行遍历不需要加锁的原因在于链指针next是final的。但是头指针却不是final的,这是通过getFirst(hash)方法返回,也就是存在table数组中的值。这使得getFirst(hash)可能返回过时的头结点,例如,当执行get方法时,刚执行完getFirst(hash)之后,另一个线程执行了删除操作并更新头结点,这就导致get方法中返回的头结点不是最新的。这是可以允许,通过对count变量的协调机制,get能读取到几乎最新的数据,虽然可能不是最新的。要得到最新的数据,只有采用完全的同步。

 

 

 事实上这样也存在一定可能的脏读,同时参考文章:

http://www.ibm.com/developerworks/java/library/j-jtp08223

里面对remove的写法我觉得非常合理:

protected Object remove(Object key, Object value) {
    /*
      Find the entry, then 
        1. Set value field to null, to force get() to retry
        2. Rebuild the list without this entry.
           All entries following removed node can stay in list, but
           all preceding ones need to be cloned.  Traversals rely
           on this strategy to ensure that elements will not be
          repeated during iteration.
    */

    int hash = hash(key);
    Segment seg = segments[hash & SEGMENT_MASK];

    synchronized(seg) {
      Entry[] tab = table;
      int index = hash & (tab.length-1);
      Entry first = tab[index];
      Entry e = first;

      for (;;) {
        if (e == null)
          return null;
        if (e.hash == hash && eq(key, e.key)) 
          break;
        e = e.next;
      }

      Object oldValue = e.value;
      if (value != null && !value.equals(oldValue))
        return null;
     
      e.value = null;/这里很关键的一个设置但是可惜我们的jdk中没有此步骤,难道是sun故意的?
      Entry head = e.next;
      for (Entry p = first; p != e; p = p.next) 
        head = new Entry(p.hash, p.key, p.value, head);
      tab[index] = head;
      seg.count--;
      return oldValue;
    }
  }

return readValueUnderLock(e); // recheck   方法同是可以防止e.value=null的问题 

 

下面是我自己对jdk代码的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;
                        // All entries following removed node can stay
                        // in list, but all preceding ones need to be
                        // cloned.
                        ++modCount;
                        e.value=null;添加此行代码
                        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; // write-volatile
                    }
                }
                return oldValue;
            } finally {
                unlock();
            }
        }

 

 

参考文章:

http://www.iteye.com/topic/344876

http://www.ibm.com/developerworks/java/library/j-jtp08223

 

1
1
分享到:
评论

相关推荐

    JDK1.8中ConcurrentHashMap中computeIfAbsent死循环bug.docx

    这个bug主要出现在并发操作时,当`ConcurrentHashMap`需要进行扩容并且`computeIfAbsent`正在执行计算的过程中,可能会导致线程在内部循环中无限等待。我们首先来理解`computeIfAbsent`方法的基本概念,然后再深入...

    JDK1.8中ConcurrentHashMap中computeIfAbsent死循环bug问题

    但是,在JDK1.8中,ConcurrentHashMap的实现存在一个严重的bug,即 computeIfAbsent方法的死循环问题。 这个问题的原因是由于ConcurrentHashMap的实现细节。在ConcurrentHashMap中,键的哈希值是通过hashCode方法...

    高薪程序员面试题精讲系列49之说说ConcurrentHashMap#put方法的源码及数。。。.pdf,这是一份不错的文件

    在面试中,ConcurrentHashMap的底层原理、put方法的实现细节都是高频考点。本文将对ConcurrentHashMap#put方法的源码进行详细分析,从而帮助读者更好地理解ConcurrentHashMap的工作机理。 一、ConcurrentHashMap的...

    基于Java并发容器ConcurrentHashMap#put方法解析

    在ConcurrentHashMap中,put方法是最基本也是最重要的操作之一,它的正确实现对整个并发容器的性能和线程安全性产生了至关重要的影响。 ConcurrentHashMap的put方法是通过分段锁来实现线程安全的,每个segment对应...

    java7-8中的 HashMap和ConcurrentHashMap全解析

    `ConcurrentHashMap`提供了多种线程安全的操作,如`putIfAbsent()`, `remove()`, `replace()`等,这些方法在并发环境下可以确保操作的原子性。同时,`ConcurrentHashMap`还支持弱一致性迭代器,这意味着在迭代过程中...

    java源码剖析-ConcurrentHashMap

    `ConcurrentHashMap`是Java并发包(`java.util.concurrent`)中的一个重要组成部分,它提供了一个线程安全的哈希表实现。与传统的`Hashtable`相比,`ConcurrentHashMap`具有更高的并发性能,这主要得益于它的分段锁...

    ConcurrentHashMap源码剖析

    为了避免在扩容过程中锁住整个表,ConcurrentHashMap采用了特殊的扩容机制,确保即使在扩容过程中也能支持并发读写操作。 #### 四、应用场景 **1. 多线程环境下的数据共享** 当多个线程需要并发地访问和修改一个...

    java本地缓存ConcurrentHashMap

    java本地缓存ConcurrentHashMap

    Java并发编程笔记之ConcurrentHashMap原理探究.docx

    Java并发编程中的ConcurrentHashMap是HashMap的一个线程安全版本,设计目标是在高并发场景下提供高效的数据访问。相比HashTable,ConcurrentHashMap通过采用锁分离技术和更细粒度的锁定策略来提升性能。HashTable...

    ConcurrentHashMap源码解析

    在Java并发编程中,ConcurrentHashMap是一个重要的并发集合。它是由Doug Lea在JSR166y中引入,并在Java 5中提供的一种线程安全的HashMap实现。与传统的HashMap相比,ConcurrentHashMap在多线程环境下具有更好的性能...

    ConcurrentHashMap的实现原理

    ConcurrentHashMap 广泛应用于 Java 开发中,例如,在大型的 Web 应用程序中,ConcurrentHashMap 可以用来存储用户的 Session 信息,在分布式系统中,ConcurrentHashMap 可以用来存储分布式锁等。

    java7-8中的 HashMap和ConcurrentHashMap全解析.pdf

    在Java 7和8中,HashMap和ConcurrentHashMap是两种重要的数据结构,分别用于非线程安全和线程安全的键值对存储。本篇文章将深入解析这两种数据结构的内部实现,帮助读者理解它们的工作原理。 HashMap是Java中最常用...

    Java利用ConcurrentHashMap实现本地缓存demo

    Java利用ConcurrentHashMap实现本地缓存demo; 基本功能有缓存有效期、缓存最大数、缓存存入记录、清理线程、过期算法删除缓存、LRU算法删除、获取缓存值等功能。 复制到本地项目的时候,记得改包路径哦~

    Java中的ConcurrentHashMap:线程安全的哈希表实现与代码示例

    在Java的并发编程中,ConcurrentHashMap 是一个非常重要的组件,它提供了线程安全的HashMap实现。本文将深入探讨 ConcurrentHashMap 的内部实现原理,并通过代码示例展示其使用方法和优势。 通过本文,我们深入探讨...

    ConcurrentHashmap源码

    源码分析见我博文:http://blog.csdn.net/wabiaozia/article/details/50684556

    ConcurrentHashMap共18页.pdf.zip

    3. **操作方法**:`put`、`get`、`remove`等基本操作在`ConcurrentHashMap`中都进行了优化,能够在并发环境中高效运行,无需外部同步。 4. **版本差异**:从Java 5到Java 8,`ConcurrentHashMap`经历了重大改进,...

    Java中遍历ConcurrentHashMap的四种方式详解

    Java中遍历ConcurrentHashMap的四种方式详解 Java中遍历ConcurrentHashMap的四种方式详解是Java开发中一个非常重要的知识点。ConcurrentHashMap是Java中一种高效且线程安全的HashMap实现,它提供了高效的读写操作...

Global site tag (gtag.js) - Google Analytics