容器

并发类容器

容器中的异常

Vector是一个线程安全的容器，但是下面的代码可能抛出ArrayIndexOutOfBoundsException

for(int i=0;i<vector.size();i++)
	doSomething(vector.get(i));

在使用迭代器Vector时可能出现CocurrentModificationException

List<String> list = Collections.synchronizedList(new ArrayList<String>);
for(String str: list)
	doSomething(str);

出现上面的问题主要因为这种基于先查看再访问的方式并不是原子的，在这两个步骤中间可能有别的线程修改了容器的大小(比如直接将容器清空)，解决的方案就是通过锁机制来保护该操作。

隐藏的迭代器

并发的问题最容易出现在对容器进行迭代的时候，一不小心就入坑了。显示的迭代还好，对于那些隐式的迭代可要小心啦。

private final Set<Integer> set = new HashSet<Integer>();
System.out.println(set);

上面的代码是打印出容器的内容，上面的代码中隐式的对set进行了迭代，通过调用容器中每个元素的toString()方法来获取字符串，然后将其拼接起来再输出。
隐式迭代还有containsAll, removeAll和retainAll等方法，还有就是将容器作为参数的构造函数也会对容器进行迭代

并发类容器

ConcurrentMap, ConcurrentLinkedQueue, CopyOnWriteArrayList,BlockingQueue等

ConcurrentHashMap的实现

为了提高并发度，采用锁分离技术来实现。内部有多个Segment，一个Segemnt其实就是一个类似HashTable的结构。ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作，第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。Segment的个数在Map初始化时就确定了，以后都不会发生改变。
get操作不需要加锁，但是put操作需要加锁

static final class Segment<K,V> extends ReentrantLock implements Serializable {
    transient volatile int count;
    transient int modCount;
    transient int threshold;
    transient volatile HashEntry<K,V>[] table;//注意这句话
    final float loadFactor;
}

http://blog.csdn.net/sherry_rui/article/details/51462549
http://blog.csdn.net/seapeak007/article/details/53409618
http://ifeve.com/concurrenthashmap-weakly-consistent/

在ConcurrentHashMap中对于那些先检查后访问的操作(若没有则添加，若相等则移除，若相等则替换)都变为了原子操作

//当且仅当K没有相应的映射值时才插入
V putIfAbsent(K key, V value)

//当且仅当K被映射到V时才移除
boolean remove(K key, V value)

//当且仅当K被映射到某个值时才替换为newValue
V replace(K key, V newValue)

可伸缩性的结果缓存

在一个业务流程中有一部分是耗时计算，为了减少这部分时间，可以将计算结果保存下来。在将来遇到相同的计算时，可以直接从缓存中取出结果,这样就将一个性能瓶颈转为一个可伸缩性瓶颈

public class Memory1 {
	private final Map<String, BigInteger> cache = new HashMap<>();
	
	public synchronized BigInteger compute(String arg) {
		BigInteger result = cache.get(arg);

		//缓存中没有则计算
		if (result == null) {
			result = compute1(arg);
			cache.put(arg, result);		
		}
		return result;
	}
	
	public static BigInteger compute1(String arg) {
		//TODO
	}
}

上面的代码是第一版，我们对compute做了加锁操作，但是有些问题。比如有两个线程都要计算，而缓存中都没有他俩的计算结果且这两个线程的计算结果也不一样。这时只能等第一个线程先计算完毕，第二个线程才能计算，这导致运算性能特别差。

public class Memory2 {
	private final Map<String, BigInteger> cache = new ConcurrentHashMap<>();
	
	public  BigInteger compute(String arg) {
		BigInteger result = cache.get(arg);

		//缓存中没有则计算
		if (result == null) {
			result = compute1(arg);
			cache.put(arg, result);		
		}
		return result;
	}
	
	public static BigInteger compute1(String arg) {
		//TODO
	}
}

该代码是第二版，虽然减少了锁的粒度(使用了ConcurrentHashMap)，相对于第一版提高了并发度。但是又出现了新的问题---当两个线程同时调用compute时可能会导致计算得到相同的值。改进的方法是：一个将要计算的线程先查看当前正在计算的线程是不是和自己算的一样，如果算的一样则等到其结束，然后去查询缓存中的值。

public class Memory3 {
	private final Map<String, Future<BigInteger>> cache = new ConcurrentHashMap<>();
	
	public  BigInteger compute(final String arg) {
		Future<BigInteger> result = cache.get(arg);

		//缓存中没有则计算
		if (result == null) {
			Callable<BigInteger> call = new Callable<BigInteger>() {
				public BigInteger = new Callable<BigInteger>() {
					public BigInteger call() {
						return compute1(arg);
					}
				}
			};
			FetureTask<BigInteger> f = new FetureTask<>(call);
			cache.put(arg, f);
			f.run();	
		}
		return f.get(); //将会一直阻塞，直到运算结束
	}
	
	public static BigInteger compute1(String arg) {
		//TODO
	}
}

该代码是第三版，其利用了FutureTask的特性，当一个线程要获取另一个线程的计算结果时将会阻塞在get方法上。若结果已经被算出来(保存在Future中)，那么将立即返回。如果其它线程正在计算该结果，那么新到的线程将一直等待这个结果被就算出来。上面的代码还是有点小瑕疵，因为其有一种可能就是同一个key被put了多次。

public class Memory3 {
	private final Map<String, Future<BigInteger>> cache = new ConcurrentHashMap<>();
	
	public  BigInteger compute(final String arg) {
		Future<BigInteger> result = cache.get(arg);

		//缓存中没有则计算
		if (result == null) {
			Callable<BigInteger> call = new Callable<BigInteger>() {
				public BigInteger = new Callable<BigInteger>() {
					public BigInteger call() {
						return compute1(arg);
					}
				}
			};
			FetureTask<BigInteger> f = new FetureTask<>(call);
			result = cache.putIfAbsent(arg, f);
			if (result == null) {
                                    result = f;
				result.run();
                            }
		}

		return result.get(); //将会一直阻塞，直到运算结束
	}
	
	public static BigInteger compute1(String arg) {
		//TODO
	}
}

上面的代码中，我们使用了putIfAbsent接口，它使得这种先检查后访问变成了原子性操作