ArrayList、HashMap、ConcurrentHashMap并发下出现的问题

一、 ArrayList

ArrayList不是线程安全的，因为没有加锁。在并发环境下，会出现一些问
。题。
1.add()方法会出现数组越界问题。

———先说说add()方法的内部实现，①step1先检查数组容量，②step2容量足够直接添加，容量不够扩容为原来1.5倍后添加。在说说为什么会出现数组越界问题，假设有两个线程在操作同一个ArrayList，线程一执行step1(容量足够)后被挂起，线程二执行add()方法后，线程一被唤醒，这时线程一因为已经不再判断容量是否足够（已经判断过），执行step2就会出现数组越界。
2.add()方法出现数据丢失和插入null值得问题。
假设初始size为0，elementData为空。
代码2分解为两步：

elementData[size] = e；
size ++；

当线程A执行完elementData[size] = e；还未执行size++就停止了，此时，size=0; elementData[0]放的是A的value,

然后线程B正常完成一个add操作；此时size=1，elementData[0]里面放的是B的value，把A的value给覆盖了。

然后B继续执行size++； 此时，size=2了

3.remove()方法出现删不干净得情况

 ArrayList<String> list = new ArrayList<String>();  
            list.add("a");  
            list.add("bb");  
            list.add("bb");  
            list.add("ccc");  
            list.add("ccc");  
            list.add("ccc"); 
-----------------------------------------------------
public static void remove(ArrayList<String> list) {  
    for (int i = 0; i < list.size(); i++) {  
        String s = list.get(i);  
        if (s.equals("bb")) {  
            list.remove(s);  
        }  
    }  
}             
对于以上写法，执行后会发现有一个“bb”的字符串没有删掉。

先看remove源码：

public boolean remove(Object o) {  
        if (o == null) {  
            for (int index = 0; index < size; index++)  
                if (elementData[index] == null) {  
                    fastRemove(index);  
                    return true;  
                }  
        } else {  
            for (int index = 0; index < size; index++)  
                if (o.equals(elementData[index])) {  
                    fastRemove(index);  
                    return true;  
                }  
        }  
        return false;  
    }  

按一般执行路径会走到else路径下最终调用fastRemove(index)方法；

private void fastRemove(int index) {  
    modCount++;  
    int numMoved = size - index - 1;  
    if (numMoved > 0)  
        System.arraycopy(elementData, index+1, elementData, index,  
                         numMoved);  
    elementData[--size] = null; // Let gc do its work  
}  

可以看到会执行System.arraycopy方法，导致删除元素时涉及到数组元素的移动。针对错误写法一，在遍历第二个元素字符串bb时因为符合删除条件，所以将该元素从数组中删除，并且将后一个元素移动(也是字符串bb)至当前位置，导致下一次循环遍历时后一个字符串bb并没有遍历到，所以无法删除。针对这种情况可以倒序删除的方式来避免。
解决办法如下：

public static void remove(ArrayList<String> list){
    for(int i=list.size()-1;i>=0;i--){
        String s=list.get(i);
        if(s.equals("bb")){
            list.remove(s);
        }
    }
}

二、

HashMap

ps:jdk1.8版本中多线程put不会在出现死循环问题了，只有可能出现数据丢失的情况，因为1.8版本中，会将原来的链表结构保存在节点e中，然后依次遍历e,根据hash&n是否等于0,分成两条支链，保存在新数组中。
下面主要对1.7做出描述
1.put()方法在高并发下链表出现死循环，导致get()操作取不到数据。
先看源码

 //注意put方法是有返回值的
    public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            inflateTable(threshold);
        }
        //HashMap允许有一个key为null的键值对
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        //计算下标
        int i = indexFor(hash, table.length);
        //循环下标处的Entry链表
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            //hash值相等且key==或equals匹配，则替换value值并把旧值返回
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        //若循环Entry链表未匹配到，则加一个Entry
        addEntry(hash, key, value, i);
        return null;
    }

    //新增一个Entry
    void addEntry(int hash, K key, V value, int bucketIndex) {
        //若满足条件则需要扩容
        if ((size >= threshold) && (null != table[bucketIndex])) {
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }

        createEntry(hash, key, value, bucketIndex);
    }


    //扩容
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }

        //创建一个容量更大的新的数组
        Entry[] newTable = new Entry[newCapacity];
        //将旧数组中的Entry数据转移至新的数组
        transfer(newTable, initHashSeedAsNeeded(newCapacity));
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
    }


    //转移数据
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);
                //注意
                e.next = newTable[i];
                //注意
                newTable[i] = e;
                e = next;
            }
        }

Hashmap的Resize包含扩容和ReHash两个步骤，ReHash在并发的情况下可能会形成链表环。
当调用Get查找一个不存在的Key,而这个Key的Hash结果的位置恰好是带有环形链表的位置的时候，程序会进入死循环
上面的transfer方法，在多线程的情况下，会出现newTable[i].next=newTable[i]的情况，这也是文中提到的链表成环的原因

2.多线程put的时候可能导致元素丢失。
主要问题出在addEntry方法的new Entry (hash, key, value, e)，如果两个线程都同时取得了e,则他们下一个元素都是e，然后赋值给table元素的时候有一个成功有一个丢失。

ConcurrentHashMap