常用的集合

Collection
├List
│├LinkedList
│├ArrayList
│└Vector
│　└Stack
└Set
Map
├Hashtable
├HashMap
└WeakHashMap

Collection接口

Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素。所有Collection都支持iterator方法。即：

Iterator it = collection.iterator();

while(it.hasNext()){

    Object obj = it.next();

}

List接口

List是有序的Collection，允许有相同元素。常用类有LinkedList、ArrayList、Vector和Stack。

LinkedList类

允许null元素，内部由链表实现，随机访问O（n）。提供额外的get、remove、insert方法。没有同步方法，如果需要多线程使用，则可构造同步List： List list = Collection.synchronizedList(new LinkedList());

ArrayList类

内部由数组实现，随机访问O（1），插入时间长。

Vector类

同步的。

Stack类

继承自Vector，实现一个后进先出的堆栈。额外提供了push、pop，peek获取栈顶元素，empty判空，search检索某元素在栈中的位置。

Set接口

不包含重复元素。

Map接口

key-value映射。

Hashtable类

继承Map接口，不能有null元素。是同步的。

HashMap类

是非同步的，且允许null value和null key。

WeakHashMap类

对key实行弱引用，如果一个key不再被外部引用，则会被GC回收。

并发集合

• 并发List：

Vector和CopyOnWriteArrayList是两个线程安全的List。Vector读写操作都用了同步，适合写多读少的场合。CopyOnWriteArrayList使用Copy-On-write原则，即写入时，先copy出一份副本，而后对该副本进行操作，写操作完成后将引用指向该副本。因此读操作时不会加锁。适用于写少读多的场景。

• 并发Set：

CopyOnWriteArraySet基于CopyOnWriteArrayList来实现的，只是不允许存在重复对象。

• 并发Map：

ConcurrentHashMap是专用于高并发的Map实现，内部实现了锁分离，get操作无锁。锁分离即内部使用segment分段锁，将HashMap分段加锁，这样多线程访问不同区块时可获取不同的锁。

• 并发的Queue：

（1）ConcurrentLinkedQueue，高性能队列，适用于高并发场景，通过无锁方式实现。BlockingQueue阻塞队列，典型应用场景是生产者-消费者模式，如果生产快于消费，生产队列装满时会阻塞，等待消费。

• 并发的Dueue：

Queue是一种双端队列，它允许在队列的头部和尾部进行出队和入队的操作。Dueue实现类有非线程安全的LinkedList、ArrayDueue和线程安全的LinkedBlockingDueue。LinkedBlockingDueue读写只有一个锁，同一时间只能有一个线程对其进行操作。

• 并发锁重入锁ReentrantLock：

是一种互斥锁的实现，即一次最多只能一个线程拿到锁。

• 读写锁ReadWriteLock：

有读取和写入两种锁，读取锁允许多个读取线程同时持有，而写入锁只能有一个线程持有。

• 条件Condition：

调用Condition对象的相关方法，可以方便的挂起和唤醒线程。

Condition，Condition 将 Object 监视器方法（wait、notify 和 notifyAll）分解成截然不同的对象，以便通过将这些对象与任意 Lock 实现组合使用，为每个对象提供多个等待 set （wait-set）。其中，Lock 替代了 synchronized 方法和语句的使用，Condition 替代了 Object 监视器方法的使用。下面将之前写过的一个线程通信的例子替换成用Condition实现(Java线程(三))，代码如下：

public class ThreadTest2 {  
    public static void main(String[] args) {  
        final Business business = new Business();  
        new Thread(new Runnable() {  
            @Override  
            public void run() {  
                threadExecute(business, "sub");  
            }  
        }).start();  
        threadExecute(business, "main");  
    }     
    public static void threadExecute(Business business, String threadType) {  
        for(int i = 0; i < 100; i++) {  
            try {  
                if("main".equals(threadType)) {  
                    business.main(i);  
                } else {  
                    business.sub(i);  
                }  
            } catch (InterruptedException e) {  
                e.printStackTrace();  
            }  
        }  
    }  
}  
class Business {  
    private boolean bool = true;  
    private Lock lock = new ReentrantLock();  
    private Condition condition = lock.newCondition();   
    public /*synchronized*/ void main(int loop) throws InterruptedException {  
        lock.lock();  
        try {  
            while(bool) {                 
                condition.await();//this.wait();  
            }  
            for(int i = 0; i < 100; i++) {  
                System.out.println("main thread seq of " + i + ", loop of " + loop);  
            }  
            bool = true;  
            condition.signal();//this.notify();  
        } finally {  
            lock.unlock();  
        }  
    }     
    public /*synchronized*/ void sub(int loop) throws InterruptedException {  
        lock.lock();  
        try {  
            while(!bool) {  
                condition.await();//this.wait();  
            }  
            for(int i = 0; i < 10; i++) {  
                System.out.println("sub thread seq of " + i + ", loop of " + loop);  
            }  
            bool = false;  
            condition.signal();//this.notify();  
        } finally {  
            lock.unlock();  
        }  
    }  
}  

在Condition中，用await()替换wait()，用signal()替换notify()，用signalAll()替换notifyAll()，传统线程的通信方式，Condition都可以实现，这里注意，Condition是被绑定到Lock上的，要创建一个Lock的Condition必须用newCondition()方法。

 

        这样看来，Condition和传统的线程通信没什么区别，Condition的强大之处在于它可以为多个线程间建立不同的Condition，下面引入API中的一段代码，加以说明。

class BoundedBuffer {  
   final Lock lock = new ReentrantLock();//锁对象  
   final Condition notFull  = lock.newCondition();//写线程条件   
   final Condition notEmpty = lock.newCondition();//读线程条件   
  
   final Object[] items = new Object[100];//缓存队列  
   int putptr/*写索引*/, takeptr/*读索引*/, count/*队列中存在的数据个数*/;  
  
   public void put(Object x) throws InterruptedException {  
     lock.lock();  
     try {  
       while (count == items.length)//如果队列满了   
         notFull.await();//阻塞写线程  
       items[putptr] = x;//赋值   
       if (++putptr == items.length) putptr = 0;//如果写索引写到队列的最后一个位置了，那么置为0  
       ++count;//个数++  
       notEmpty.signal();//唤醒读线程  
     } finally {  
       lock.unlock();  
     }  
   }  
  
   public Object take() throws InterruptedException {  
     lock.lock();  
     try {  
       while (count == 0)//如果队列为空  
         notEmpty.await();//阻塞读线程  
       Object x = items[takeptr];//取值   
       if (++takeptr == items.length) takeptr = 0;//如果读索引读到队列的最后一个位置了，那么置为0  
       --count;//个数--  
       notFull.signal();//唤醒写线程  
       return x;  
     } finally {  
       lock.unlock();  
     }  
   }   
 }  

这是一个处于多线程工作环境下的缓存区，缓存区提供了两个方法，put和take，put是存数据，take是取数据，内部有个缓存队列，具体变量和方法说明见代码，这个缓存区类实现的功能：有多个线程往里面存数据和从里面取数据，其缓存队列(先进先出后进后出)能缓存的最大数值是100，多个线程间是互斥的，当缓存队列中存储的值达到100时，将写线程阻塞，并唤醒读线程，当缓存队列中存储的值为0时，将读线程阻塞，并唤醒写线程，这也是ArrayBlockingQueue的内部实现。下面分析一下代码的执行过程：

 

        1. 一个写线程执行，调用put方法；

        2. 判断count是否为100，显然没有100；

        3. 继续执行，存入值；

        4. 判断当前写入的索引位置++后，是否和100相等，相等将写入索引值变为0，并将count+1；

        5. 仅唤醒读线程阻塞队列中的一个；

        6. 一个读线程执行，调用take方法；

        7. ……

        8. 仅唤醒写线程阻塞队列中的一个。

        这就是多个Condition的强大之处，假设缓存队列中已经存满，那么阻塞的肯定是写线程，唤醒的肯定是读线程，相反，阻塞的肯定是读线程，唤醒的肯定是写线程，那么假设只有一个Condition会有什么效果呢，缓存队列中已经存满，这个Lock不知道唤醒的是读线程还是写线程了，如果唤醒的是读线程，皆大欢喜，如果唤醒的是写线程，那么线程刚被唤醒，又被阻塞了，这时又去唤醒，这样就浪费了很多时间。

 

转自：http://blog.csdn.net/ghsau/article/details/7481142