Java性能优化那些影响性能的细节（二）

1.前言Java性能优化那些影响性能的细节——续。打算把整个系列的文章都写成这个标题，以后慢慢积累再写。这是第一个条目。这次的内容主要来自《Java程序性能优化实战》这本书，算是读书笔记吧。有兴趣的朋友可以看看这本书。2.List接口?先看这几个List的类图：ArrayListVectorLinkedListArrayList、Vector和LinkedList都是来自AbstractList的实现，而AbstractList直接实现了List接口，扩展自AbstractCollection。1.ArrayList和VectorArrayList和Vector基本类似，所以把这两个放在一起。这两个实现类使用了几乎相同的算法，它们唯一的区别可以认为是对多线程的支持。ArrayList不对任何方法进行线程同步，因此不是线程安全的；Vector中的大部分方法都有线程同步，是线程安全的实现；ArrayList和Vector使用数组。可以认为ArrayList或Vector封装了对内部数组的操作，例如向数组中添加、删除、插入新元素，或者扩展和重新定义数组。（ArrayList和Vector的一些优化方法其实是基于数组的，所以一般情况也适用于其他底层使用数组的情况）ArrayList当前容量够大【默认初始化长度为10】，add()操作的效率非常高。ArrayList在扩容过程中【默认扩容为原来的1.5倍】，会进行大量的数组复制操作。相对来说，频繁扩容会对性能产生影响；扩展的核心源代码如下：/***增加容量以确保它至少可以容纳最小容量参数指定的*个元素。**@paramminCapacity所需的最小容量*/privatevoidgrow(intminCapacity){//溢出意识代码intoldCapacity=elementData.length;//这是使用位操作实现的。相当于newCapacity=oldCapacity+(oldCapacity/2)intnewCapacity=oldCapacity+(oldCapacity>>1);如果(newCapacity-minCapacity<0)newCapacity=minCapacity;如果(newCapacity-MAX_ARRAY_SIZE>0)newCapacity=hugeCapacity(minCapacity);//minCapacity通常接近于size，所以这是一个胜利：elementData=Arrays.copyOf(elementData,newCapacity);}从源代码中，我们可以得到另一个细节：代码中的整数乘法和除法是使用bit实现的操作，可以大大提高计算效率。从尾部删除元素效率很高，但从头部删除元素很耗时。原因是每次删除后都要重新组织数组；插入操作会执行一个数组复制[除了在末尾插入]，而这个操作在向List末尾添加元素时是不存在的。大量的数组重组操作会导致系统性能低下，插入元素在List中的位置越高，数组重组的代价越大；尽量直接访问内部元素，而不是调用相应的接口。因为函数调用需要消耗系统资源，直接访问元素效率更高，比如直接使用List数组的下标索引，而不是get接口。2.LinkedListLinkedList采用循环双向链表数据结构。与基于数组的List相比，这是两种完全不同的实现技术，也决定了它们将适用于完全不同的工作场景。LinkedList链表是由一系列条目连接而成。一个表项包括3部分，即元素内容、前驱表项和从动表项。不管LinkedList是否为空，链表中都有一个headerentry，它不仅表示链表的开始，也表示链表的结束。循环链表示意图如下：LinkedList对堆内存和GC要求很高，因为每次添加元素都要newEntry()，每次都要封装数据，因为前指针和后指针必须先设置指针，然后才能将其添加到链表中；LinkedList从头尾删除元素的效率差不多，但是从List中间删除元素时性能很差，因为每次都要遍历链表的一半；（以下是上篇文章提到的LinkedList注意点）使用ListIterator（forEach，使用指针遍历）遍历LinkedList【链表的特点】；避免任何接受或返回列表中元素索引的LinkedList方法[类似获取索引的操作]，性能很差，实现的是遍历列表；3.Map接口首先看这几个Map的类图：HashMapLinkedHashMapTreeMap这三个Map都实现了Map接口，继承了AbstractMap类。HashMap和LinkedHashMap直接继承了AbstractMap类，而LinkedHashMap则继承了HashMap。1、HashMapHashMap的性能在一定程度上取决于hashCode()的实现。一个好的hashCode()算法可以尽可能减少冲突，从而提高HashMap的访问速度。另外，负载因子越大，意味着使用的内存空间越少，空间越小，越容易造成Hash冲突。HashMap初始化默认数组大小为16，创建时指定大小【默认使用达到75%自动扩容，每次扩容为原来大小的两倍，最大长度为2^30】，参数必须为2的指数（如果不是，强制转换）；扩展部分的源代码如下：/***初始化或加倍表大小。如果为空，则根据字段阈值中的初始容量目标在*中进行分配。*否则，因为我们使用的是二次幂扩展，所以每个bin中的*元素必须保持相同的索引，或者在新表中以二次方偏移量移动*。**@return表格*/finalNode[]resize(){Node[]oldTab=table;intoldCap=(oldTab==null)?0:旧标签长度；intoldThr=阈值；intnewCap,newThr=0;if(oldCap>0){if(oldCap>=MAXIMUM_CAPACITY){threshold=Integer.MAX_VALUE;返回旧标签；}elseif((newCap=oldCap<<1)=DEFAULT_INITIAL_CAPACITY)//这里也用到了按位运算，相当于乘以2newThr=oldThr<<1;//双阈值}HashMap扩充通用流程（jdk8）：i.新建一个新数组ii。使用二进制高低指针进行数据迁移（最高位为0，坐标不变，最高位为1，坐标为原位置+新数组长度，如果是树结构，则有是附加逻辑）【这里不过多解释HashMap的扩展机制】；三.链表的长度如果大于8，而哈希表的长度大于等于64，则链表会转为红黑树（一般情况下，红黑树是未使用，优先扩容）；2、LinkedHashMapLinkedHashMap可以保持元素输入的顺序；底层使用循环链表，在内部实现中，LinkedHashMap通过继承HashMap.Entry类实现LinkedHashMap.Entry，并为HashMap.Entry添加before和after属性，用于记录一张表的前驱和后继物品。一些注意点可以参考LinkedList（链表）3.TreeMapTreeMap，它实现了SortedMap接口，也就是说可以对元素进行排序，但是TreeMap的性能略低于HashMap；TreeMap的内部实现是基于红黑树的。红黑树是一种平衡搜索树，其统计性能优于平衡二叉树。它具有良好的最坏情况运行时间，可以在O(logn)时间内进行查找、插入和删除。如果需要对Map中的数据进行排序，可以使用TreeMap，不用自己实现一大堆代码，性能不一定高；4.测试demopackagecom.allen.list;importorg.junit.TestonList;importjava.util.ArrayList;importjava.util.LinkedList;importjava.util.List;importjava.util.Vector;/***1、ArrayList、Vector：末尾添加元素性能高，且每次在头部插入元素Insertion会涉及到元素的拷贝和移动，性能低下*2.LinkedList:每次添加元素都需要newEntry()，对堆内存和GC要求高[-Xmx512M-Xms512M使用该参数对测试结果有一定影响】*/publicclassTestList{privatestaticfinalintCIRCLE1=50000;受保护的列表列表；protectedvoidtestAddTail(Stringfuncname){Objectobj=newObject();长启动时间=System.currentTimeMillis();;i0){list.remove(list.size()-1);}longendtime=System.currentTimeMillis();System.out.println(funcname+":"+(endtime-starttime));}protectedvoidtestDelFirst(Stringfuncname){Objectobj=newObject();for(inti=0;i0){list.remove(0);}longendtime=System.currentTimeMillis();System.out.println(funcname+":"+(endtime-starttime));}protectedvoidtestDelMiddle(Stringfuncname){Objectobj=newObject();for(inti=0;i0){list.remove(list.size()>>1);}长结束时间=System.currentTimeMillis();System.out.println(funcname+":"+(endtime-starttime));}protectedvoidtestAddFirst(Stringfuncname){Objectobj=newObject();长启动时间=System.currentTimeMillis();for(inti=0;i