原文：http://www.iteye.com/topic/1118660

整个ThreadPoolExecutor的任务处理有4步操作：

• 第一步，初始的poolSize < corePoolSize，提交的runnable任务，会直接做为new一个Thread的参数，立马执行
• 第二步，当提交的任务数超过了corePoolSize，就进入了第二步操作。会将当前的runable提交到一个block queue中
  
• 第三步，如果block queue是个有界队列，当队列满了之后就进入了第三步。如果poolSize < maximumPoolsize时，会尝试new 一个Thread的进行救急处理，立马执行对应的runnable任务
• 第四步，如果第三步救急方案也无法处理了，就会走到第四步执行reject操作。

Btrace容量规划

再提供一个btrace脚本，分析线上的thread pool容量规划是否合理，可以运行时输出poolSize等一些数据。

import static com.sun.btrace.BTraceUtils.addToAggregation;
import static com.sun.btrace.BTraceUtils.field;
import static com.sun.btrace.BTraceUtils.get;
import static com.sun.btrace.BTraceUtils.newAggregation;
import static com.sun.btrace.BTraceUtils.newAggregationKey;
import static com.sun.btrace.BTraceUtils.printAggregation;
import static com.sun.btrace.BTraceUtils.println;
import static com.sun.btrace.BTraceUtils.str;
import static com.sun.btrace.BTraceUtils.strcat;

import java.lang.reflect.Field;
import java.util.concurrent.atomic.AtomicInteger;

import com.sun.btrace.BTraceUtils;
import com.sun.btrace.aggregation.Aggregation;
import com.sun.btrace.aggregation.AggregationFunction;
import com.sun.btrace.aggregation.AggregationKey;
import com.sun.btrace.annotations.BTrace;
import com.sun.btrace.annotations.Kind;
import com.sun.btrace.annotations.Location;
import com.sun.btrace.annotations.OnEvent;
import com.sun.btrace.annotations.OnMethod;
import com.sun.btrace.annotations.OnTimer;
import com.sun.btrace.annotations.Self;

/**
 * 并行加载监控
 * 
 * @author jianghang 2011-4-7 下午10:59:53
 */
@BTrace
public class AsyncLoadTracer {

    private static AtomicInteger rejecctCount = BTraceUtils.newAtomicInteger(0);
    private static Aggregation   histogram    = newAggregation(AggregationFunction.QUANTIZE);
    private static Aggregation   average      = newAggregation(AggregationFunction.AVERAGE);
    private static Aggregation   max          = newAggregation(AggregationFunction.MAXIMUM);
    private static Aggregation   min          = newAggregation(AggregationFunction.MINIMUM);
    private static Aggregation   sum          = newAggregation(AggregationFunction.SUM);
    private static Aggregation   count        = newAggregation(AggregationFunction.COUNT);

    @OnMethod(clazz = "java.util.concurrent.ThreadPoolExecutor", method = "execute", location = @Location(value = Kind.ENTRY))
    public static void executeMonitor(@Self Object self) {
        Field poolSizeField = field("java.util.concurrent.ThreadPoolExecutor", "poolSize");
        Field largestPoolSizeField = field("java.util.concurrent.ThreadPoolExecutor", "largestPoolSize");
        Field workQueueField = field("java.util.concurrent.ThreadPoolExecutor", "workQueue");

        Field countField = field("java.util.concurrent.ArrayBlockingQueue", "count");
        int poolSize = (Integer) get(poolSizeField, self);
        int largestPoolSize = (Integer) get(largestPoolSizeField, self);
        int queueSize = (Integer) get(countField, get(workQueueField, self));

        println(strcat(strcat(strcat(strcat(strcat("poolSize : ", str(poolSize)), " largestPoolSize : "),
                                     str(largestPoolSize)), " queueSize : "), str(queueSize)));
    }

    @OnMethod(clazz = "java.util.concurrent.ThreadPoolExecutor", method = "reject", location = @Location(value = Kind.ENTRY))
    public static void rejectMonitor(@Self Object self) {
        String name = str(self);
        if (BTraceUtils.startsWith(name, "com.alibaba.pivot.common.asyncload.impl.pool.AsyncLoadThreadPool")) {
            BTraceUtils.incrementAndGet(rejecctCount);
        }
    }

    @OnTimer(1000)
    public static void rejectPrintln() {
        int reject = BTraceUtils.getAndSet(rejecctCount, 0);
        println(strcat("reject count in 1000 msec: ", str(reject)));
        AggregationKey key = newAggregationKey("rejectCount");
        addToAggregation(histogram, key, reject);
        addToAggregation(average, key, reject);
        addToAggregation(max, key, reject);
        addToAggregation(min, key, reject);
        addToAggregation(sum, key, reject);
        addToAggregation(count, key, reject);
    }

    @OnEvent
    public static void onEvent() {
        BTraceUtils.truncateAggregation(histogram, 10);
        println("---------------------------------------------");
        printAggregation("Count", count);
        printAggregation("Min", min);
        printAggregation("Max", max);
        printAggregation("Average", average);
        printAggregation("Sum", sum);
        printAggregation("Histogram", histogram);
        println("---------------------------------------------");
    }
}

运行结果：

poolSize : 1 , largestPoolSize = 10 , queueSize = 10
reject count in 1000 msec: 0

说明：

1. poolSize 代表为当前的线程数

2. largestPoolSize 代表为历史最大的线程数

3. queueSize 代表blockqueue的当前堆积的size

4. reject count 代表在1000ms内的被reject的数量

最后

  这是我对ThreadPoolExecutor使用过程中的一些经验总结，希望能对大家有所帮助，如有描述不对的地方欢迎拍砖。

1. 堆大小设置
   JVM 中最大堆大小有三方面限制：相关操作系统的数据模型（32-bt还是64-bit）限制；系统的可用虚拟内存限制；系统的可用物理内存限制。32位系统下，一般限制在1.5G~2G；64为操作系统对内存无限制。我在Windows Server 2003 系统，3.5G物理内存，JDK5.0下测试，最大可设置为1478m。
   典型设置：
   • java -Xmx3550m -Xms3550m -Xmn2g -Xss128k
     -Xmx3550m：设置JVM最大可用内存为3550M。
     -Xms3550m：设置JVM促使内存为3550m。此值可以设置与-Xmx相同，以避免每次垃圾回收完成后JVM重新分配内存。
     -Xmn2g：设置年轻代大小为2G。整个JVM内存大小=年轻代大小 + 年老代大小 + 持久代大小。持久代一般固定大小为64m，所以增大年轻代后，将会减小年老代大小。此值对系统性能影响较大，Sun官方推荐配置为整个堆的3/8。
     -Xss128k：设置每个线程的堆栈大小。JDK5.0以后每个线程堆栈大小为1M，以前每个线程堆栈大小为256K。更具应用的线程所需内存大小进行调整。在相同物理内存下，减小这个值能生成更多的线程。但是操作系统对一个进程内的线程数还是有限制的，不能无限生成，经验值在3000~5000左右。
     
   • java -Xmx3550m -Xms3550m -Xss128k -XX:NewRatio=4 -XX:SurvivorRatio=4 -XX:MaxPermSize=16m -XX:MaxTenuringThreshold=0
     -XX:NewRatio=4:设置年轻代（包括Eden和两个Survivor区）与年老代的比值（除去持久代）。设置为4，则年轻代与年老代所占比值为1：4，年轻代占整个堆栈的1/5
     -XX:SurvivorRatio=4：设置年轻代中Eden区与Survivor区的大小比值。设置为4，则两个Survivor区与一个Eden区的比值为2:4，一个Survivor区占整个年轻代的1/6
     -XX:MaxPermSize=16m:设置持久代大小为16m。
     -XX:MaxTenuringThreshold=0：设置垃圾最大年龄。如果设置为0的话，则年轻代对象不经过Survivor区，直接进入年老代。对于年老代比较多的应用，可以提高效率。如果将此值设置为一个较大值，则年轻代对象会在Survivor区进行多次复制，这样可以增加对象再年轻代的存活时间，增加在年轻代即被回收的概论。
2. 回收器选择
   JVM给了三种选择：串行收集器、并行收集器、并发收集器，但是串行收集器只适用于小数据量的情况，所以这里的选择主要针对并行收集器和并发收集器。默认情况下，JDK5.0以前都是使用串行收集器，如果想使用其他收集器需要在启动时加入相应参数。JDK5.0以后，JVM会根据当前系统配置进行判断。
   1. 吞吐量优先的并行收集器
      如上文所述，并行收集器主要以到达一定的吞吐量为目标，适用于科学技术和后台处理等。
      典型配置：
      • java -Xmx3800m -Xms3800m -Xmn2g -Xss128k -XX:+UseParallelGC -XX:ParallelGCThreads=20
        -XX:+UseParallelGC：选择垃圾收集器为并行收集器。此配置仅对年轻代有效。即上述配置下，年轻代使用并发收集，而年老代仍旧使用串行收集。
        -XX:ParallelGCThreads=20：配置并行收集器的线程数，即：同时多少个线程一起进行垃圾回收。此值最好配置与处理器数目相等。
        
      • java -Xmx3550m -Xms3550m -Xmn2g -Xss128k -XX:+UseParallelGC -XX:ParallelGCThreads=20 -XX:+UseParallelOldGC
        -XX:+UseParallelOldGC：配置年老代垃圾收集方式为并行收集。JDK6.0支持对年老代并行收集。
        
      • java -Xmx3550m -Xms3550m -Xmn2g -Xss128k -XX:+UseParallelGC  -XX:MaxGCPauseMillis=100
        -XX:MaxGCPauseMillis=100:设置每次年轻代垃圾回收的最长时间，如果无法满足此时间，JVM会自动调整年轻代大小，以满足此值。
        
      • java -Xmx3550m -Xms3550m -Xmn2g -Xss128k -XX:+UseParallelGC  -XX:MaxGCPauseMillis=100 -XX:+UseAdaptiveSizePolicy
        -XX:+UseAdaptiveSizePolicy：设置此选项后，并行收集器会自动选择年轻代区大小和相应的Survivor区比例，以达到目标系统规定的最低相应时间或者收集频率等，此值建议使用并行收集器时，一直打开。
   2. 响应时间优先的并发收集器
      如上文所述，并发收集器主要是保证系统的响应时间，减少垃圾收集时的停顿时间。适用于应用服务器、电信领域等。
      典型配置：
      • java -Xmx3550m -Xms3550m -Xmn2g -Xss128k -XX:ParallelGCThreads=20 -XX:+UseConcMarkSweepGC -XX:+UseParNewGC
        -XX:+UseConcMarkSweepGC：设置年老代为并发收集。测试中配置这个以后，-XX:NewRatio=4的配置失效了，原因不明。所以，此时年轻代大小最好用-Xmn设置。
        -XX:+UseParNewGC:设置年轻代为并行收集。可与CMS收集同时使用。JDK5.0以上，JVM会根据系统配置自行设置，所以无需再设置此值。
      • java -Xmx3550m -Xms3550m -Xmn2g -Xss128k -XX:+UseConcMarkSweepGC -XX:CMSFullGCsBeforeCompaction=5 -XX:+UseCMSCompactAtFullCollection
        -XX:CMSFullGCsBeforeCompaction：由于并发收集器不对内存空间进行压缩、整理，所以运行一段时间以后会产生“碎片”，使得运行效率降低。此值设置运行多少次GC以后对内存空间进行压缩、整理。
        -XX:+UseCMSCompactAtFullCollection：打开对年老代的压缩。可能会影响性能，但是可以消除碎片
3. 辅助信息
   JVM提供了大量命令行参数，打印信息，供调试使用。主要有以下一些：
   • -XX:+PrintGC
     输出形式：[GC 118250K->113543K(130112K), 0.0094143 secs]

                     [Full GC 121376K->10414K(130112K), 0.0650971 secs]

   • -XX:+PrintGCDetails
     输出形式：[GC [DefNew: 8614K->781K(9088K), 0.0123035 secs] 118250K->113543K(130112K), 0.0124633 secs]

                     [GC [DefNew: 8614K->8614K(9088K), 0.0000665 secs][Tenured: 112761K->10414K(121024K), 0.0433488 secs] 121376K->10414K(130112K), 0.0436268 secs]

   • -XX:+PrintGCTimeStamps -XX:+PrintGC：PrintGCTimeStamps可与上面两个混合使用
     输出形式：11.851: [GC 98328K->93620K(130112K), 0.0082960 secs]
     
   • -XX:+PrintGCApplicationConcurrentTime:打印每次垃圾回收前，程序未中断的执行时间。可与上面混合使用
     输出形式：Application time: 0.5291524 seconds
     
   • -XX:+PrintGCApplicationStoppedTime：打印垃圾回收期间程序暂停的时间。可与上面混合使用
     输出形式：Total time for which application threads were stopped: 0.0468229 seconds
     
   • -XX:PrintHeapAtGC:打印GC前后的详细堆栈信息
     输出形式：
     34.702: [GC {Heap before gc invocations=7:
      def new generation   total 55296K, used 52568K [0x1ebd0000, 0x227d0000, 0x227d0000)
     eden space 49152K,  99% used [0x1ebd0000, 0x21bce430, 0x21bd0000)
     from space 6144K,  55% used [0x221d0000, 0x22527e10, 0x227d0000)
       to   space 6144K,   0% used [0x21bd0000, 0x21bd0000, 0x221d0000)
      tenured generation   total 69632K, used 2696K [0x227d0000, 0x26bd0000, 0x26bd0000)
     the space 69632K,   3% used [0x227d0000, 0x22a720f8, 0x22a72200, 0x26bd0000)
      compacting perm gen  total 8192K, used 2898K [0x26bd0000, 0x273d0000, 0x2abd0000)
        the space 8192K,  35% used [0x26bd0000, 0x26ea4ba8, 0x26ea4c00, 0x273d0000)
         ro space 8192K,  66% used [0x2abd0000, 0x2b12bcc0, 0x2b12be00, 0x2b3d0000)
         rw space 12288K,  46% used [0x2b3d0000, 0x2b972060, 0x2b972200, 0x2bfd0000)
     34.735: [DefNew: 52568K->3433K(55296K), 0.0072126 secs] 55264K->6615K(124928K)Heap after gc invocations=8:
      def new generation   total 55296K, used 3433K [0x1ebd0000, 0x227d0000, 0x227d0000)
     eden space 49152K,   0% used [0x1ebd0000, 0x1ebd0000, 0x21bd0000)
       from space 6144K,  55% used [0x21bd0000, 0x21f2a5e8, 0x221d0000)
       to   space 6144K,   0% used [0x221d0000, 0x221d0000, 0x227d0000)
      tenured generation   total 69632K, used 3182K [0x227d0000, 0x26bd0000, 0x26bd0000)
     the space 69632K,   4% used [0x227d0000, 0x22aeb958, 0x22aeba00, 0x26bd0000)
      compacting perm gen  total 8192K, used 2898K [0x26bd0000, 0x273d0000, 0x2abd0000)
        the space 8192K,  35% used [0x26bd0000, 0x26ea4ba8, 0x26ea4c00, 0x273d0000)
         ro space 8192K,  66% used [0x2abd0000, 0x2b12bcc0, 0x2b12be00, 0x2b3d0000)
         rw space 12288K,  46% used [0x2b3d0000, 0x2b972060, 0x2b972200, 0x2bfd0000)
     }
     , 0.0757599 secs]
   • -Xloggc:filename:与上面几个配合使用，把相关日志信息记录到文件以便分析。
4. 常见配置汇总
   1. 堆设置
      • -Xms:初始堆大小
      • -Xmx:最大堆大小
      • -XX:NewSize=n:设置年轻代大小
      • -XX:NewRatio=n:设置年轻代和年老代的比值。如:为3，表示年轻代与年老代比值为1：3，年轻代占整个年轻代年老代和的1/4
      • -XX:SurvivorRatio=n:年轻代中Eden区与两个Survivor区的比值。注意Survivor区有两个。如：3，表示Eden：Survivor=3：2，一个Survivor区占整个年轻代的1/5
      • -XX:MaxPermSize=n:设置持久代大小
   2. 收集器设置
      • -XX:+UseSerialGC:设置串行收集器
      • -XX:+UseParallelGC:设置并行收集器
      • -XX:+UseParalledlOldGC:设置并行年老代收集器
      • -XX:+UseConcMarkSweepGC:设置并发收集器
   3. 垃圾回收统计信息
      • -XX:+PrintGC
      • -XX:+PrintGCDetails
      • -XX:+PrintGCTimeStamps
      • -Xloggc:filename
   4. 并行收集器设置
      • -XX:ParallelGCThreads=n:设置并行收集器收集时使用的CPU数。并行收集线程数。
      • -XX:MaxGCPauseMillis=n:设置并行收集最大暂停时间
      • -XX:GCTimeRatio=n:设置垃圾回收时间占程序运行时间的百分比。公式为1/(1+n)
   5. 并发收集器设置
      • -XX:+CMSIncrementalMode:设置为增量模式。适用于单CPU情况。
      • -XX:ParallelGCThreads=n:设置并发收集器年轻代收集方式为并行收集时，使用的CPU数。并行收集线程数。

四、调优总结

1. 年轻代大小选择
   • 响应时间优先的应用：尽可能设大，直到接近系统的最低响应时间限制（根据实际情况选择）。在此种情况下，年轻代收集发生的频率也是最小的。同时，减少到达年老代的对象。
   • 吞吐量优先的应用：尽可能的设置大，可能到达Gbit的程度。因为对响应时间没有要求，垃圾收集可以并行进行，一般适合8CPU以上的应用。
2. 年老代大小选择
   • 响应时间优先的应用：年老代使用并发收集器，所以其大小需要小心设置，一般要考虑并发会话率和会话持续时间等一些参数。如果堆设置小了，可以会造成内存碎片、高回收频率以及应用暂停而使用传统的标记清除方式；如果堆大了，则需要较长的收集时间。最优化的方案，一般需要参考以下数据获得：
     • 并发垃圾收集信息
     • 持久代并发收集次数
     • 传统GC信息
     • 花在年轻代和年老代回收上的时间比例
     减少年轻代和年老代花费的时间，一般会提高应用的效率
   • 吞吐量优先的应用：一般吞吐量优先的应用都有一个很大的年轻代和一个较小的年老代。原因是，这样可以尽可能回收掉大部分短期对象，减少中期的对象，而年老代尽存放长期存活对象。
3. 较小堆引起的碎片问题
   因为年老代的并发收集器使用标记、清除算法，所以不会对堆进行压缩。当收集器回收时，他会把相邻的空间进行合并，这样可以分配给较大的对象。但是，当堆空间较小时，运行一段时间以后，就会出现“碎片”，如果并发收集器找不到足够的空间，那么并发收集器将会停止，然后使用传统的标记、清除方式进行回收。如果出现“碎片”，可能需要进行如下配置：
   • -XX:+UseCMSCompactAtFullCollection：使用并发收集器时，开启对年老代的压缩。
   • -XX:CMSFullGCsBeforeCompaction=0：上面配置开启的情况下，这里设置多少次Full GC后，对年老代进行压缩

最近老是出现双击启动后，确定完workspace后，显示启动画面，没过一会就进入灰色无响应状态。启动画面始终停留在Loading workbench状态。反复重启，状态依旧。
在网上看到有人已经解决了，尝试使用后的确可以解决问题，所以留下分享。

搜索了一下，应该是非正常关机导致eclipse工作区的文件状态错误导致。在工作区目录中，有一个.metadata目录，里面是工作区及各插件的信息，删除此目录可以解决问题。

Jem保险起见，将.metadata改名移动到/tmp目录，再重启eclipse，果然可以正常启动eclipse了，但原来工作区的配置和项目信息也都消失，直接显示的是欢迎界面。

如何恢复原来的project配置呢？尝试对比了当前的.metadata和之前备份的那个目录，发现缺少了n多的配置文件。试着一点点恢复一些目录，但效果不理想。因为不知道哪些文件(目录)可以恢复，哪些恢复会带来问题。将备份的整个目录恢复试试？Eclipse又回到了无法启动的状态了。

咋办？这时想到启动停止时显示的状态:"Loading workbench"，看来和这个workbench插件有关。查看原来的.metadata/.plugins目录，在众多文件夹中

发现了两个：org.eclipse.ui.workbench和 org.eclipse.ui.workbench.texteditor。

不管三七二十一，删了这两个目录，重新启动eclipse。正常启动且原项目信息正确加载。

1.synchronized与static synchronized 的区别

        synchronized是对类的当前实例进行加锁，防止其他线程同时访问该类的该实例的所有synchronized块，注意这里是“类的当前实例”， 类的两个不同实例就没有这种约束了。那么static synchronized恰好就是要控制类的所有实例的访问了，static synchronized是限制线程同时访问jvm中该类的所有实例同时访问对应的代码快。实际上，在类中某方法或某代码块中有 synchronized，那么在生成一个该类实例后，改类也就有一个监视快，放置线程并发访问改实例synchronized保护快，而static synchronized则是所有该类的实例公用一个监视快了，也也就是两个的区别了,也就是synchronized相当于 this.synchronized，而static synchronized相当于Something.synchronized.
         一个日本作者-结成浩的《java多线程设计模式》有这样的一个列子：

pulbic class Something(){ 
    publicsynchronizedvoid isSyncA(){} 
    publicsynchronizedvoid isSyncB(){} 
    publicstaticsynchronizedvoid cSyncA(){} 
    publicstaticsynchronizedvoid cSyncB(){} 
} 
       那么，加入有Something类的两个实例a与b，那么下列组方法何以被1个以上线程同时访问呢

a. x.isSyncA()与x.isSyncB()  
b. x.isSyncA()与y.isSyncA() 
c. x.cSyncA()与y.cSyncB() 
d. x.isSyncA()与Something.cSyncA() 
      这里，很清楚的可以判断：

a，都是对同一个实例的synchronized域访问，因此不能被同时访问 b，是针对不同实例的，因此可以同时被访问 c，因为是static synchronized，所以不同实例之间仍然会被限制,相当于Something.isSyncA()与 Something.isSyncB()了，因此不能被同时访问。 那么，第d呢?，书上的 答案是可以被同时访问的，答案理由是synchronzied的是实例方法与synchronzied的类方法由于锁定（lock）不同的原因。 个人分析也就是synchronized 与static synchronized 相当于两帮派，各自管各自，相互之间就无约束了，可以被同时访问。目前还不是分清楚java内部设计synchronzied是怎么样实现的。
结论：A: synchronized static是某个类的范围，synchronized static cSync{}防止多个线程同时访问这个 类中的synchronized static 方法。它可以对类的所有对象实例起作用。
B: synchronized 是某实例的范围，synchronized isSync(){}防止多个线程同时访问这个实例中的synchronized 方法。

2.synchronized方法与synchronized代码快的区别 

        synchronized methods(){} 与synchronized（this）{}之间没有什么区别，只是synchronized methods(){} 便于阅读理解，而synchronized（this）{}可以更精确的控制冲突限制访问区域，有时候表现更高效率。

3.synchronized关键字是不能继承的

         这个在《搞懂java中的synchronized关键字》一文中看到的，我想这一点也是很值得注意的，继承时子类的覆盖方法必须显示定义成synchronized。（但是如果使用继承开发环境的话，会默认加上synchronized关键字）

在Java中,为了保证多线程读写数据时保证数据的一致性,可以采用两种方式:

同步

如用synchronized关键字,或者使用锁对象.

volatile

使用volatile关键字
用一句话概括volatile,它能够使变量在值发生改变时能尽快地让其他线程知道.

volatile详解

首先我们要先意识到有这样的现象,编译器为了加快程序运行的速度,对一些变量的写操作会先在寄存器或者是CPU缓存上进行,最后才写入内存.
而在这个过程,变量的新值对其他线程是不可见的.而volatile的作用就是使它修饰的变量的读写操作都必须在内存中进行!

volatile与synchronized

volatile本质是在告诉jvm当前变量在寄存器中的值是不确定的,需要从主存中读取,synchronized则是锁定当前变量,只有当前线程可以访问该变量,其他线程被阻塞住.
volatile仅能使用在变量级别,synchronized则可以使用在变量,方法.
volatile仅能实现变量的修改可见性,但不具备原子特性,而synchronized则可以保证变量的修改可见性和原子性.
volatile不会造成线程的阻塞,而synchronized可能会造成线程的阻塞.
volatile标记的变量不会被编译器优化,而synchronized标记的变量可以被编译器优化.

一般大家都知道ArrayList和LinkedList的大致区别：
     1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
     2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
     3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。

ArrayList和LinkedList是两个集合类，用于存储一系列的对象引用(references)。例如我们可以用ArrayList来存储一系列的String或者Integer。那么ArrayList和LinkedList在性能上有什么差别呢？什么时候应该用ArrayList什么时候又该用LinkedList呢？

一．时间复杂度
首先一点关键的是，ArrayList的内部实现是基于基础的对象数组的，因此，它使用get方法访问列表中的任意一个元素时(random access)，它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的一端开始检查，直到另外一端。对LinkedList而言，访问列表中的某个指定元素没有更快的方法了。
假设我们有一个很大的列表，它里面的元素已经排好序了，这个列表可能是ArrayList类型的也可能是LinkedList类型的，现在我们对这个列表来进行二分查找(binary search)，比较列表是ArrayList和LinkedList时的查询速度，看下面的程序：

Java代码  

1. package com.mangocity.test;    
2. import java.util.LinkedList;    
3. import java.util.List;    
4. import java.util.Random;    
5. import java.util.ArrayList;    
6. import java.util.Arrays;    
7. import java.util.Collections;    
8. public class TestList ...{    
9.      public static final int N=50000;    
10.   
11.      public static List values;    
12.   
13.      static...{    
14.          Integer vals[]=new Integer[N];    
15.   
16.          Random r=new Random();    
17.   
18.          for(int i=0,currval=0;i<N;i++)...{    
19.              vals=new Integer(currval);    
20.              currval+=r.nextInt(100)+1;    
21.          }    
22.   
23.          values=Arrays.asList(vals);    
24.      }    
25.   
26.      static long timeList(List lst)...{    
27.          long start=System.currentTimeMillis();    
28.          for(int i=0;i<N;i++)...{    
29.              int index=Collections.binarySearch(lst, values.get(i));    
30.              if(index!=i)    
31.                  System.out.println("***错误***");    
32.          }    
33.          return System.currentTimeMillis()-start;    
34.      }    
35.      public static void main(String args[])...{    
36.          System.out.println("ArrayList消耗时间："+timeList(new ArrayList(values)));    
37.          System.out.println("LinkedList消耗时间："+timeList(new LinkedList(values)));    
38.      }    
39. }   

package com.mangocity.test; 
import java.util.LinkedList; 
import java.util.List; 
import java.util.Random; 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Collections; 
public class TestList ...{ 
     public static final int N=50000; 

     public static List values; 

     static...{ 
         Integer vals[]=new Integer[N]; 

         Random r=new Random(); 

         for(int i=0,currval=0;i<N;i++)...{ 
             vals=new Integer(currval); 
             currval+=r.nextInt(100)+1; 
         } 

         values=Arrays.asList(vals); 
     } 

     static long timeList(List lst)...{ 
         long start=System.currentTimeMillis(); 
         for(int i=0;i<N;i++)...{ 
             int index=Collections.binarySearch(lst, values.get(i)); 
             if(index!=i) 
                 System.out.println("***错误***"); 
         } 
         return System.currentTimeMillis()-start; 
     } 
     public static void main(String args[])...{ 
         System.out.println("ArrayList消耗时间："+timeList(new ArrayList(values))); 
         System.out.println("LinkedList消耗时间："+timeList(new LinkedList(values))); 
     } 
} 

 
我得到的输出是：ArrayList消耗时间：15
                 LinkedList消耗时间：2596
这个结果不是固定的，但是基本上ArrayList的时间要明显小于LinkedList的时间。因此在这种情况下不宜用LinkedList。二分查找法使用的随机访问(random access)策略，而LinkedList是不支持快速的随机访问的。对一个LinkedList做随机访问所消耗的时间与这个list的大小是成比例的。而相应的，在ArrayList中进行随机访问所消耗的时间是固定的。
这是否表明ArrayList总是比LinkedList性能要好呢？这并不一定，在某些情况下LinkedList的表现要优于ArrayList，有些算法在LinkedList中实现时效率更高。比方说，利用Collections.reverse方法对列表进行反转时，其性能就要好些。
看这样一个例子，加入我们有一个列表，要对其进行大量的插入和删除操作，在这种情况下LinkedList就是一个较好的选择。请看如下一个极端的例子，我们重复的在一个列表的开端插入一个元素：

Java代码  

1. package com.mangocity.test;    
2.   
3. import java.util.*;    
4. public class ListDemo {    
5.      static final int N=50000;    
6.      static long timeList(List list){    
7.      long start=System.currentTimeMillis();    
8.      Object o = new Object();    
9.      for(int i=0;i<N;i++)    
10.          list.add(0, o);    
11.      return System.currentTimeMillis()-start;    
12.      }    
13.      public static void main(String[] args) {    
14.          System.out.println("ArrayList耗时："+timeList(new ArrayList()));    
15.          System.out.println("LinkedList耗时："+timeList(new LinkedList()));    
16.      }    
17. }   

package com.mangocity.test; 

import java.util.*; 
public class ListDemo { 
     static final int N=50000; 
     static long timeList(List list){ 
     long start=System.currentTimeMillis(); 
     Object o = new Object(); 
     for(int i=0;i<N;i++) 
         list.add(0, o); 
     return System.currentTimeMillis()-start; 
     } 
     public static void main(String[] args) { 
         System.out.println("ArrayList耗时："+timeList(new ArrayList())); 
         System.out.println("LinkedList耗时："+timeList(new LinkedList())); 
     } 
} 

 这时我的输出结果是：ArrayList耗时：2463

                           LinkedList耗时：15
这和前面一个例子的结果截然相反，当一个元素被加到ArrayList的最开端时，所有已经存在的元素都会后移，这就意味着数据移动和复制上的开销。相反的，将一个元素加到LinkedList的最开端只是简单的未这个元素分配一个记录，然后调整两个连接。在LinkedList的开端增加一个元素的开销是固定的，而在ArrayList的开端增加一个元素的开销是与ArrayList的大小成比例的。

二．空间复杂度
在LinkedList中有一个私有的内部类，定义如下：

Java代码  

1. private static class Entry {    
2.          Object element;    
3.          Entry next;    
4.          Entry previous;    
5.      }   

private static class Entry { 
         Object element; 
         Entry next; 
         Entry previous; 
     } 

 
每个Entry对象reference列表中的一个元素，同时还有在LinkedList中它的上一个元素和下一个元素。一个有1000个元素的LinkedList对象将有1000个链接在一起的Entry对象，每个对象都对应于列表中的一个元素。这样的话，在一个LinkedList结构中将有一个很大的空间开销，因为它要存储这1000个Entity对象的相关信息。
ArrayList使用一个内置的数组来存储元素，这个数组的起始容量是10.当数组需要增长时，新的容量按如下公式获得：新容量=(旧容量*3)/2+1，也就是说每一次容量大概会增长50%。这就意味着，如果你有一个包含大量元素的ArrayList对象，那么最终将有很大的空间会被浪费掉，这个浪费是由ArrayList的工作方式本身造成的。如果没有足够的空间来存放新的元素，数组将不得不被重新进行分配以便能够增加新的元素。对数组进行重新分配，将会导致性能急剧下降。如果我们知道一个ArrayList将会有多少个元素，我们可以通过构造方法来指定容量。我们还可以通过trimToSize方法在ArrayList分配完毕之后去掉浪费掉的空间。

三．总结
ArrayList和LinkedList在性能上各有优缺点，都有各自所适用的地方，总的说来可以描述如下：
1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是统一的，分配一个内部Entry对象。

2．在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。

3．LinkedList不支持高效的随机元素访问。

4．ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间

可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。