Collection

├List

│├LinkedList

│├ArrayList

│└Vector

│　└Stack

└Set

Map

├Hashtable

├HashMap

└WeakHashMap

Collection接口

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

1 Iterator it = collection.iterator();2 3 while(it.hasNext()){4 5     Object obj = it.next();6 7 }

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线程(三))，代码如下：

1 public class ThreadTest2 {   2     public static void main(String[] args) {   3         final Business business = new Business();   4         new Thread(new Runnable() {   5             @Override   6             public void run() {   7                 threadExecute(business, "sub");   8             }   9         }).start();  10         threadExecute(business, "main");  11     }     12     public static void threadExecute(Business business, String threadType) {  13         for(int i = 0; i < 100; i++) {  14             try {  15                 if("main".equals(threadType)) {  16                     business.main(i);  17                 } else {  18                     business.sub(i);  19                 }  20             } catch (InterruptedException e) {  21                 e.printStackTrace();  22             }  23         }  24     }  25 }  26 class Business {  27     private boolean bool = true;  28     private Lock lock = new ReentrantLock();  29     private Condition condition = lock.newCondition();   30     public /*synchronized*/ void main(int loop) throws InterruptedException {  31         lock.lock();  32         try {  33             while(bool) {                 34                 condition.await();//this.wait();  35             }  36             for(int i = 0; i < 100; i++) {  37                 System.out.println("main thread seq of " + i + ", loop of " + loop);  38             }  39             bool = true;  40             condition.signal();//this.notify();  41         } finally {  42             lock.unlock();  43         }  44     }     45     public /*synchronized*/ void sub(int loop) throws InterruptedException {  46         lock.lock();  47         try {  48             while(!bool) {  49                 condition.await();//this.wait();  50             }  51             for(int i = 0; i < 10; i++) {  52                 System.out.println("sub thread seq of " + i + ", loop of " + loop);  53             }  54             bool = false;  55             condition.signal();//this.notify();  56         } finally {  57             lock.unlock();  58         }  59     }  60 }

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

 

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

1 class BoundedBuffer {   2    final Lock lock = new ReentrantLock();//锁对象   3    final Condition notFull  = lock.newCondition();//写线程条件    4    final Condition notEmpty = lock.newCondition();//读线程条件    5    6    final Object[] items = new Object[100];//缓存队列   7    int putptr/*写索引*/, takeptr/*读索引*/, count/*队列中存在的数据个数*/;   8    9    public void put(Object x) throws InterruptedException {  10      lock.lock();  11      try {  12        while (count == items.length)//如果队列满了   13          notFull.await();//阻塞写线程  14        items[putptr] = x;//赋值   15        if (++putptr == items.length) putptr = 0;//如果写索引写到队列的最后一个位置了，那么置为0  16        ++count;//个数++  17        notEmpty.signal();//唤醒读线程  18      } finally {  19        lock.unlock();  20      }  21    }  22   23    public Object take() throws InterruptedException {  24      lock.lock();  25      try {  26        while (count == 0)//如果队列为空  27          notEmpty.await();//阻塞读线程  28        Object x = items[takeptr];//取值   29        if (++takeptr == items.length) takeptr = 0;//如果读索引读到队列的最后一个位置了，那么置为0  30        --count;//个数--  31        notFull.signal();//唤醒写线程  32        return x;  33      } finally {  34        lock.unlock();  35      }  36    }   37  }

这是一个处于多线程工作环境下的缓存区，缓存区提供了两个方法，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不知道唤醒的是读线程还是写线程了，如果唤醒的是读线程，皆大欢喜，如果唤醒的是写线程，那么线程刚被唤醒，又被阻塞了，这时又去唤醒，这样就浪费了很多时间。

 

转自：