一、前言

  Java性能优化之影响性能的那些细节 - 续来了。打算把这个题目整个系列文章，前面缓缓积攒缓缓写。这是第一篇入口。这次内容次要来源于《Java程序性能优化实战》这本书，算是一份读书笔记，感兴趣的小伙伴能够浏览下这本书。

二、List接口

  先来看下这几个List的类图：

  • ArrayList

     
  • Vector

     
  • LinkedList

  ArrayList、Vector以及LinkedList3种List均来自AbstractList的实现，而AbstractList间接实现了List接口，并扩大自AbstractCollection。

1. ArrayList和Vector

  ArrayList和Vector根本差不多，所以就把这两放一块了。这两个实现类简直应用了雷同的算法，它们的 惟一区别 能够认为是对多线程的反对。ArrayList没有对任何一个办法做线程同步，因而不是线程平安的； Vector中的绝大部分办法都做了线程同步，是一种线程平安的实现形式；

  • ArrayList和Vector应用了数组。能够认为ArrayList或者Vector封装了对外部数组的操作，例如向数组中增加、删除、插入新的元素或者数组的扩大和重定义。(对于ArrayList和Vector的一些优化形式其实都是基于数组的来的，因而个别状况同样实用于底层应用数组的其余状况)
     
  • ArrayList的以后容量足够大【默认初始化长度为10】，add()操作的效率就十分高，ArrayList扩容【默认扩容本来的1.5倍】过程中会进行大量的数组复制操作，相对来说频繁的扩容会有性能影响；扩容的外围源码如下：
/** * Increases the capacity to ensure that it can hold at least the * number of elements specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    // 这里用位运算来实现的。相当于newCapacity = oldCapacity + (oldCapacity / 2)    int newCapacity = oldCapacity + (oldCapacity >> 1);    if (newCapacity - minCapacity < 0)        newCapacity = minCapacity;    if (newCapacity - MAX_ARRAY_SIZE > 0)        newCapacity = hugeCapacity(minCapacity);    // minCapacity is usually close to size, so this is a win:    elementData = Arrays.copyOf(elementData, newCapacity);}
从源码中咱们又能get一个细节：代码中的整数乘除应用位运算实现，能够大大提高计算效率。
  • 从尾部删除元素时效率很高,从头部删除元素时相当费时,起因是每次删除后都要进行数组的重组;
     
  • 插入操作都会进行一次数组复制【除尾端插入状况】，而这个操作在减少元素到List尾端的时候是不存在的。大量的数组重组操作会导致系统性能低下，并且插入的元素在List中的地位越靠前，数组重组的开销也越大；
     
  • 尽量间接拜访外部元素，而不要调用对应的接口。因为函数调用是须要耗费系统资源的，而间接拜访元素会更高效，比方间接应用List数组下标索引，而不必get接口。

2. LinkedList

  LinkedList应用了循环双向链表数据结构。与基于数组的List相比，这是两种截然不同的实现技术，这也决定了它们将实用于齐全不同的工作场景。LinkedList链表由一系列表项连贯而成。一个表项蕴含3局部，即元素内容、前驱表项和后驱表项。

  • 无论LinkedList是否为空，链表内都有一个header表项，它既示意链表的开始，也示意链表的结尾。循环链表 示意图如下：

     
  • LinkedList对堆内存和GC要求较高，起因是每次增加元素都要new Entry()，及每次都要封装数据，因为必须设置前指针和后指针，能力退出到链表中；
     
  • LinkedList从头、尾删除元素时效率相差无几级，然而从List两头删除元素时性能十分蹩脚,起因是每次都要遍历半个链表；
     
    （上面是前一篇文章中提到过的对于LinkedList的留神点）
  • 应用ListIterator（forEach，利用指针遍历）遍历LinkedList【链表个性】；
     
  • 防止任何承受或返回列表中元素索引的LinkedList办法【相似获取index的操作】，性能很差，遍历列表实现；

三、Map接口

  先来看下这几个Map的类图：

  • HashMap

     
  • LinkedHashMap

     
  • TreeMap

     

  这3个Map都是实现Map接口，继承AbstractMap类。HashMap和LinkedHashMap间接继承AbstractMap类，而LinkedHashMap继承了HashMap。

1. HashMap

  • HashMap的性能在肯定水平上取决于hashCode()的实现。一个好的hashCode()算法，能够尽可能减少抵触，从而进步HashMap的访问速度。另外，一个较大的负载因子意味着应用较少的内存空间，而空间越小，越可能引起Hash抵触。
     
  • HashMap初始化默认数组大小16，在创立的时候指定大小【默认应用达到75%进行主动扩容，每次扩容为原来的2倍，最大长度2^30】，参数必须是2的指数幂（不是的话强行转换）；扩容局部源码如下：
/**     * Initializes or doubles table size.  If null, allocates in     * accord with initial capacity target held in field threshold.     * Otherwise, because we are using power-of-two expansion, the     * elements from each bin must either stay at same index, or move     * with a power of two offset in the new table.     *     * @return the table     */    final Node<K,V>[] resize() {        Node<K,V>[] oldTab = table;        int oldCap = (oldTab == null) ? 0 : oldTab.length;        int oldThr = threshold;        int newCap, newThr = 0;        if (oldCap > 0) {            if (oldCap >= MAXIMUM_CAPACITY) {                threshold = Integer.MAX_VALUE;                return oldTab;            }            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                     oldCap >= DEFAULT_INITIAL_CAPACITY)                // 这里也是用的位运算，相当于乘2                newThr = oldThr << 1; // double threshold        }
HashMap扩容大体流程（jdk8）：
i. new一个新的数组
ii. 借助二进制的高下位指针进行数据迁徙（最高位是0则坐标不变，最高位是1则坐标为原地位+新数组长度，如果是树结构有额定的逻辑）【这里不过多的解释HashMap的扩容机制】；
iii. 链表长度大于8，且hash table长度大于等于64，则会将链表转红黑树(个别状况不应用红黑树，优先扩容) ；

2. LinkedHashMap

  • LinkedHashMap能够放弃元素输出时的程序；底层应用循环链表，在外部实现中，LinkedHashMap通过继承HashMap.Entry类，实现了LinkedHashMap.Entry，为HashMap.Entry减少了before和after属性，用于记录某一表项的前驱和后继。
     
  • 一些留神点参照LinkedList（链表）

3. TreeMap

  • TreeMap，实现了SortedMap接口，这意味着它能够对元素进行排序，然而TreeMap的性能却稍微低于HashMap；
     
  • TreeMap的外部实现是基于红黑树的。红黑树是一种均衡查找树，它的统计性能要优于均衡二叉树。它具备良好的最坏状况运行工夫，能够在O（logn）工夫内做查找、插入和删除操作。
     
  • 如果须要对Map中的数据进行排序，能够应用TreeMap，而不必本人再去实现很多代码，而且性能不肯定很高；

四、对于List的测试demo

package com.allen.list;import org.junit.Test;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Vector;/** * 1、ArrayList，Vector：尾部增加元素性能高，头部插入元素每次插入都会波及元素的复制和挪动，性能较低 * 2、LinkedList：每次增加元素都要new Entry()，对堆内存和GC要求较高【-Xmx512M -Xms512M 应用这个参数对测试后果有肯定影响】 */public class TestList {    private static final int CIRCLE1 = 50000;    protected List list;    protected void testAddTail(String funcname){        Object obj=new Object();        long starttime=System.currentTimeMillis();                for(int i=0;i<CIRCLE1;i++){            list.add(obj);        }        long endtime=System.currentTimeMillis();        System.out.println(funcname+": "+(endtime-starttime));    }    protected void testDelTail(String funcname){        Object obj=new Object();        for(int i=0;i<CIRCLE1;i++){            list.add(obj);        }                long starttime=System.currentTimeMillis();        while(list.size()>0){            list.remove(list.size()-1);        }        long endtime=System.currentTimeMillis();        System.out.println(funcname+": "+(endtime-starttime));    }    protected void testDelFirst(String funcname){        Object obj=new Object();        for(int i=0;i<CIRCLE1;i++){            list.add(obj);        }                long starttime=System.currentTimeMillis();        while(list.size()>0){            list.remove(0);        }        long endtime=System.currentTimeMillis();        System.out.println(funcname+": "+(endtime-starttime));    }    protected void testDelMiddle(String funcname){        Object obj=new Object();        for(int i=0;i<CIRCLE1;i++){            list.add(obj);        }                long starttime=System.currentTimeMillis();        while(list.size()>0){            list.remove(list.size()>>1);        }        long endtime=System.currentTimeMillis();        System.out.println(funcname+": "+(endtime-starttime));    }    protected void testAddFirst(String funcname){        Object obj=new Object();        long starttime=System.currentTimeMillis();                for(int i=0;i<CIRCLE1;i++){            list.add(0, obj);        }        long endtime=System.currentTimeMillis();        System.out.println(funcname+": "+(endtime-starttime));    }            // 测试ArrayList尾部增加    @Test    public void testAddTailArrayList() {        list=new ArrayList();        testAddTail("testAddTailArrayList");    }    //@Test    public void testAddTailVector() {        list=new Vector();        testAddTail("testAddTailVector");    }    // 测试LinkedList尾部增加    @Test    public void testAddTailLinkedList() {        list=new LinkedList();        testAddTail("testAddTailLinkedList");    }        // 测试ArrayList头部增加    @Test    public void testAddFirstArrayList() {        list=new ArrayList();        testAddFirst("testAddFirstArrayList");    }    //    @Test    public void testAddFirstVector() {        list=new Vector();        testAddFirst("testAddFirstVector");    }    // 测试LinkedList头部增加    @Test    public void testAddFirstLinkedList() {        list=new LinkedList();        testAddFirst("testAddFirstLinkedList");    }        // 测试ArrayList尾部删除    @Test    public void testDeleteTailArrayList() {        list=new ArrayList();                testDelTail("testDeleteTailArrayList");    }//    @Test    public void testDeleteTailVector() {        list=new Vector();        testDelTail("testDeleteTailVector");    }    // 测试LinkedList尾部删除    @Test    public void testDeleteTailLinkedList() {        list=new LinkedList();        testDelTail("testDeleteTailLinkedList");    }        // 测试ArrayList头部删除    @Test    public void testDeleteFirstArrayList() {        list=new ArrayList();        testDelFirst("testDeleteFirstArrayList");    }//    @Test    public void testDeleteFirstVector() {        list=new Vector();        testDelFirst("testDeleteFirstVector");    }    // 测试LinkedList头部删除    @Test    public void testDeleteFirstLinkedList() {        list=new LinkedList();        testDelFirst("testDeleteFirstLinkedList");    }    // 测试LinkedList两头删除    @Test    public void testDeleteMiddleLinkedList() {        list=new LinkedList();        testDelMiddle("testDeleteMiddleLinkedList");    }    // 测试ArrayList两头删除    @Test    public void testDeleteMiddleArrayList() {        list=new ArrayList();        testDelMiddle("testDeleteMiddleArrayList");    }}