[Java concurrent][Collections]

同步容器类

同步容器类包括Vector和Hashtable，二者是早期JDK的一部分。以及一些在JDK1.2中添加的可以由Collections.synchronizedXxx等工厂方法创建的。
这些类实现线程安全的方式是，将它们的状态封装起来，并对每个公有方法都进行同步(synchronized)，使得每次只有一个线程能访问容器的状态。
同步容器类在一些情况下，可能需要额外的客户端加锁来保护复合操作。
eg:
```
public static Object getLast(Vector list) {
  synchronized(list) {
    int lastIndex = list.size() - 1;
    return list.get(lastIndex);
  }
}
```
比如在迭代的时候，需要加锁，那就会严重降低并发。这时候也可以考虑通过“克隆”容器的方法。通过考虑容器的大小、操作的开销等因素来抉择。

在迭代过程中，如果对容器进行修改就会抛出ConcurrentModificationException的异常（该异常即使是在单线程也可以抛出，即当对象直接从容器中删除而非使用Iterator.remove()时）。

The iterators returned by the iterator method of the collections
* returned by all of this class's "collection view methods" are
* fail-fast: if the Hashtable is structurally modified at any time
* after the iterator is created, in any way except through the iterator's own
* remove method, the iterator will throw a
* ConcurrentModificationException

Hashtable

An instance of Hashtable has two parameters that affect its performance: initial capacity and load factor.
The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. 因为在有冲突的时候需要顺序查找。
The load factor (default 0.75) is a measure of how full the hash table is allowed to get before its capacity is automatically increased.
variables are private;
public function are synchronized
用synchronized来锁住整张表来实现线程安全，即每次锁住整张表让线程独占。

synchronizedList

static function of Collections
Returns a synchronized (thread-safe) list backed by the specified list.
In order to guarantee serial access, it is critical that all access to the backing list is accomplished through the returned list.
实际上就是把原生collections封装在一个SynchronizedCollection内部，这个类有一个
final Object mutex; // Object on which to synchronized
其内部的方法都是类似
public boolean contains(Object o) { synchronized(mutex) {return c.contains(o); }}

并发容器

同步容器是通过将操作串行化来实现它们的线程安全性，因而严重降低了并发性。
Java5.0提供了多种容器来改进同步容器的性能。比如
- 增加了ConcurrentHashMap来替代同步且基于散列的Map
- CopyOnWriteArrayList用于在遍历操作为主要操作的情况下代替同步的List。
- 增加了对一些常见复合操作的支持，如“若没有则添加”、替换以及有条件删除等。

java.util.concurrent

refer javadoc.
java.util.concurrent: Utility classes commonly useful in concurrent programming.

Memory Consistency Properties

首先，你需要知道happens-before，可以参考link。
The methods of all classes in java.util.concurrent and its subpackages extend these guarantees to higher-level synchronized. In particular:
- Actions in a thread prior to placing an object into any concurrent collection happen-before actions subsequent to the access or removal of that element from the collection in another thread.
- Actions in a thread prior to the submission of a Runnable to an Executor happen-before its execution begins. Similarly for Callables submitted to an ExecutorService.
- Actions taken by the asynchronous computation represented by a Future happen-before actions subsequent to the retrieval of the result via Future.get() in another thread.
- Actions prior to "releasing" synchronizer methods such as Lock.unlock, Semaphore.release, and CountDownLatch.countDown happen-before actions subsequent to a successful "acquiring" method such as Lock.lock, Semaphore.acquire,Condition.await, and CountDownLatch.await on the same synchronizer object in another thread.
- For each pair of threads that successfully exchange objects via an Exchanger, actions prior to the exchange() in each thread happen-before those subsequent to the corresponding exchange() in another thread.
- Actions prior to calling CyclicBarrier.await and Phaser.awaitAdvance (as well as its variants) happen-before actions performed by the barrier action, and actions performed by the barrier action happen-before actions subsequent to a successful return from the corresponding await in other threads.

ConcurrentHashMap

Hashtable存在的问题是：在每个方法上都加锁而降低了并发。
ConcurrentHashMap采用的solution就是使用更细粒度的加锁机制来实现更大程度的共享，即分段锁(Lock Striping)。具体的原理是：
内部使用Segment来表示这些不同的部分，每个段其实就是一个小的hashtable，它们有自己的锁。只要修改操作发生在不同的段上，就可以并发进行。【The table is internally partitioned to try to permit the indicated number of concurrent updates without contention.】
有的方法需要跨段，比如size()和contains()，它们可能需要锁住整张表，这就需要按顺序锁定所有表，操作完毕后，又按顺序释放所有段的锁。
ConcurrentHashMap在线程安全地基础上提供了更好的并发写能力，但是降低了对读一致性的要求。(感觉像CAP)
实现上，大量利用了volatile，final，CAS(Compare and Swap)等lock-free技术来减少锁竞争对性能的影响。

Source Code

TBD...