理解和讨论HashMap的线程安全

    修改了一下题目=  =
    发这个帖子是想深入了解在多线程环境下操作HashMap引发的问题，探讨在某些特定的多线程环境下是不是能直接使用HashMap?在哪些特定的并发环境下能否正常使用呢?

    众所周知HashMap不是线程安全的，但到底HashMap在什么情况才不是线程安全的? 查看HashMap的源码，内部有一个modCount变量，在put、remove、等等进行结构性修改时改变这个值。在Hash Iterator中记录expectedModCount变量，在遍历或者删除时比较modCount与expectedModCount的值是否相等，不相等就抛出ConcurrentModificationException，类似一种乐观所的机制，代码如下：

 final Entry<K,V> nextEntry() {
            [color=red]if (modCount != expectedModCount)
                throw new ConcurrentModificationException();[/color]
            Entry<K,V> e = next;
            if (e == null)
                throw new NoSuchElementException();

            if ((next = e.next) == null) {
                Entry[] t = table;
                while (index < t.length && (next = t[index++]) == null)
                    ;
            }
	    current = e;
            return e;
        }

        public void remove() {
            if (current == null)
                throw new IllegalStateException();
            [color=red]if (modCount != expectedModCount)
                throw new ConcurrentModificationException();[/color]
            Object k = current.key;
            current = null;
            HashMap.this.removeEntryForKey(k);
            expectedModCount = modCount;
        }

那就是说，在多线程环境下是操作HashMap的内部类迭代器的时(Iterator的remove与遍历)，就有可能出现并发的问题。那假设我现在有一个HashMap，保证不对HashMap的迭代器操作，在多线程环境下单纯地调用HashMap的get、remove、put、containsKey等方法，是不是就不会出现并发的问题呢？

    static Random random = new Random();
    static HashMap<Integer, String> map = new HashMap<Integer, String>();

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {


        Thread t1 = new Thread() {
            @Override
            public void run() {
                for (int i = 0; i < 1000; i++) {
                    try {
                        TimeUnit.MILLISECONDS.sleep(1);
                    } catch (InterruptedException ex) {
                        System.err.println("t1 catch the InterruptedException...");
                    }
                    int key = random.nextInt(1000);
                    map.put(key, String.valueOf(key));
                }
            }
        };
        t1.start();

        Thread t2 = new Thread() {
            @Override
            public void run() {
                for (int i = 0; i < 1000; i++) {
                    try {
                        TimeUnit.MILLISECONDS.sleep(1);
                    } catch (InterruptedException ex) {
                        System.err.println("t2 catch the InterruptedException...");
                    }
                    int key = random.nextInt(1000);
                    map.get(key);
                }
            }
        };
        t2.start();

        Thread t3 = new Thread() {
            @Override
            public void run() {
                for (int i = 0; i < 1000; i++) {
                    try {
                        TimeUnit.MILLISECONDS.sleep(1);
                    } catch (InterruptedException ex) {
                        System.err.println("t3 catch the InterruptedException...");
                    }
                    Integer key = random.nextInt(1000);
                    map.containsKey(key);
                }
            }
        };
        t3.start();

        Thread t4 = new Thread() {
            @Override
            public void run() {
                for (int i = 0; i < 1000; i++) {
                    try {
                        TimeUnit.MILLISECONDS.sleep(1);
                    } catch (InterruptedException ex) {
                        System.err.println("t4 catch the InterruptedException...");
                    }
                    int key = random.nextInt(1000);
                    map.remove(key);
                }
            }
        };
        t4.start();
    }

经过测试之后，代码能正确运行，暂且不考虑数据的是否100%正确，最少没有抛出ConcurrentModificationException。原因是，上面代码中的4种操作都没有直接操作到HashMap内部的迭代器。
当然如果加上操作迭代器的代码，异常马上就出来了

    Thread t5 = new Thread() {
            @Override
            public void run() {
                for (int i = 0; i < 1000; i++) {
                    try {
                        TimeUnit.MILLISECONDS.sleep(1);
                    } catch (InterruptedException ex) {
                        System.err.println("t5 catch the InterruptedException...");
                    }
                    for (Integer key : map.keySet()) {
                    }
                }
            }
        };
        t5.start();

但在多线程环境下，HashMap的get、put、remove、containsKey这样的操作是否就正确并且保证一定没有问题！？(甚至保证对同一个key的get、put、remove、containsKey的操作是单线程的前提下，多线程是对于不同key)(否则就算多线程对相同的key操作最多也是会出现数据的不一致性，如对相同的key进行多次的put操作，后一个覆盖了前一个....)

带着查看一下JavaDoc关于HashMap同步的描述：
注意，此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须 保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：

JavaDoc的说法也是有点模糊，如果对HashMap多线程访问，从结构上修改了该映射就必须保持同步?但测试代码中的put、remove操作不也是结构性修改的动作吗？到了这里问题变得有点难以解释和理清思路了。。。

    跳出以上描述重新考虑这个问题，其中一种想法是：上面是建立在关心HashMap内部实现的基础上去讨论和测试的，但API文档已经说明HashMap并非线程安全的，不要在多线程环境下对HashMap进行结构性的动作，去冒将来不确定的时间发生任意不确定行为的风险。比如在某个版本会为了某种原因而去修改HashMap的内部实现，单纯调用HashMap的put、remove操作也会抛出ConcurrentModificationException(当然这个可能性比较低....)，那么以前写的旧代码就有可能出问题了。。。。

说到这里，希望各位高手、有经验的热心朋友可以指点一下，或一起探讨一下这个问题。。。谢谢


考虑了一下，多线程环境下put还是可能会有问题

void addEntry(int hash, K key, V value, int bucketIndex) {   
    Entry<K,V> e = table[bucketIndex];   
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);   
        if (size++ >= threshold)   
            resize(2 * table.length);   
    }  

发生在index相同的情况下，大家拿到的链头可能不是最新的，后一个会直接覆盖了前一个
而且当多条线程检测到容量超过负载因子时，会能发生多次resize。
结构性修改总是采用持有，替换的方式去操作，因此操作内部数组与单向链表的时候不会抛出NullPointerException

//======================add at 5.1=================================
小结一下：remove与put都是一样的，由于大家拿到的不是最新链头，只要大家在Entry数组的index相同时(经过hash后的index)，就有可能出现后一个覆盖前一个的操作，即前一个的操作无效。
可能产生的现象会是：
1)put进行的data有可能丢失了
2)一些通过remove(Object key)删除掉的元素(返回删除成功)又出来了。
3)多线程检测到HashMap容量超过负载因子时会进行多次的resize，由于要rehash，所以消耗的性能也是巨大的。

但如果put、与remove，是在同一条线程中处理，而get发生在多线程环境，是不会出现上述3种情况或抛出ConcurrentModificationException的。唯一可能出现的是返回不是最新的数据(可能拿到刚好被remove的，拿不到刚好put进去的)，但这种情况即使ConcurrentHashMap也会出现。但ConcurrentHashMap的get方法多了一步处理，看起来好像更精确.

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

        V readValueUnderLock(HashEntry<K,V> e) {
            lock();
            try {
                return e.value;
            } finally {
                unlock();
            }
        }

当调用ConcurrentHashMap的get方法时，找到key所对应的Entry而getValue为null时会调用readValueUnderLock(e)方法上分离锁取一次。这具体会发生什么情况下会发生呢且readValueUnderLock(e)能生效呢？网上有两种比较常见的说法：
1)另外一条线程在修改节点
2)HashEntry构造函数中对value的赋值以及对tab[index]的赋值可能被重新排序，或许源出自http://www.iteye.com/topic/344876
查看ConcurrentHashMap源码能看到put方法其实是创建一个新的节点并以之前的第一个节点为这个节点的next节点(即这个新创建的节点为单向链表的第一个节点)，然后

 tab[index] = new HashEntry<K,V>(key, hash, first, value);

执行赋值
remove方法则是重新把整条单向链表(除被删除Entry)全部拷贝一次执行赋值

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;

所有，既不是另外一条线程正在修改某节点，也不是重新排序。最后追踪到源码的注释：


原来还是Java内存模型的问题(Jmm)，执行

tab[index] = newFirst

或

tab[index] = new HashEntry<K,V>(key, hash, first, value);

时，Entry已经被认为初始化ok并返回给table(在堆中分派一块空间)，这是正好有其他线程调用到get方法，获取到这个刚“实例化好”的单向链表，但由于JMM初始化的无序性，当你get这个链表Entry中的value 时，他有可能还没完全初始化好！或按注释所说不知道发生过这样的初始化但这是合法的。。。。这和为什么Java的单例模式不能使用双重检查加锁的原因类似，都是由于Java内存模型(JMM)的无序性。这里有部分介绍http://rjx2008.iteye.com/admin/blogs/342474

数据一致性的问题扯远了，回到上述：但如果put、与remove，是在同一条线程中处理，而get发生在多线程环境，是不会出现上述3种情况或抛出ConcurrentModificationException的。
最少有两种的适用场合
1)类似委托的机制
2)类似命令模式的执行方式
这两种处理get,put时方式是很接近的，就是多线程接收到要删除、添加数据的指令
但最终会由一条线程去过滤这些指令，判断、分析、处理，最后单线程地对HashMap执行put、remove的操作。只要类似这种的处理方式，都应该可以使用。
这只是个人观点，请大家多提点意见、补充或纠正:-)

多线程环境下，hashmap并不保证线程安全，也就是说你说的get、put、remove、containsKey这样的操作都是非线程安全的，有可能得到不正确的值。ConcurrentModificationException是迭代器抛的，目的只是为了说明没有进行并发处理，最好别拿来在实际中用。

ConcorrentHashMap

并不是要询问一种代替HashMap线程安全的方法，而是想深入了解在多线程环境下操作HashMap引发的问题
探讨在某些特定的多线程环境下是不是能直接使用HashMap?在某些特定的并发环境下能否正常使用呢?
如对同一个key的get,remove,cotain,put是能保证单线程

考虑了一下，多线程环境下put还是可能会有问题

void addEntry(int hash, K key, V value, int bucketIndex) {
	Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<K,V>(hash, key, value, e);
        if (size++ >= threshold)
            resize(2 * table.length);
    }

发生在index相同的情况下，大家拿到的链头可能不是最新的，后一个会直接覆盖了前一个
而且当多条线程检测到容量超过负载因子时，会能发生多次resize。
结构性修改总是采用持有，替换的方式去操作，因此操作内部数组与单向链表的时候不会抛出NullPointerException

未抛出异常就是线程安全的么。。。。？ 真汗

= =LS误解了我的意思了，上面的回帖已经说明了，多线程put的时候可能会丢失数据。
同时也会数据的不一致性。这里只是想探讨在不抛出ConcurrentModificationException的情况下可能会引发的问题，并且是否能在一些特定的并发环境下可以使用。。

正如你所说，不抛出ConcurrentModificationException不代表线程安全，使用HashMap的时候更需要考虑各种可能发生的情况

有这个讨论价值么？ 性能比ConcurrentHashMap高？ 最终的结果就是产生误导效果

产生误导也看具体什么情况下产生什么的误导。或许在某些情况下或者是可接受的。
当然可以直接根据前辈的经验，多线程用ConcurrentHashMap，单线程或者只读的境况下用HashMap。
就算最终得出的结构式任何并发环境下都不能用，在具体分析、交流的过程中也是一种学习，能够更彻底理解容器的内部结构。
我觉得，程序员最忌就是泛泛而谈，不是一句不安全就不安全，在使用的同时也需要去分析和理解，当然这只是个人观点

有时间学点意义的东西，做点有意义的事情，什么时候ConcurrentHashMap性能有问题了？

楼主的所写的大家都没仔细看！楼主主要是想阐明HashMap在多线程环境下是如何发生数据不一致现象的。