乐趣区

关于java:Java性能优化之影响性能的那些细节二

一、前言

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

二、List接口

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

  • ArrayList

     
  • Vector

     
  • LinkedList

ArrayListVector以及LinkedList 3 种 List 均来自 AbstractList 的实现,而 AbstractList 间接实现了 List 接口,并扩大自 AbstractCollection。

1. ArrayListVector

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

  • ArrayListVector 应用了数组。能够认为 ArrayList 或者 Vector 封装了对外部数组的操作,例如向数组中增加、删除、插入新的元素或者数组的扩大和重定义。(对于 ArrayListVector的一些优化形式其实都是基于数组的来的,因而个别状况同样实用于底层应用数组的其余状况)
     
  • 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 类。HashMapLinkedHashMap 间接继承 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 减少了 beforeafter属性,用于记录某一表项的前驱和后继。
     
  • 一些留神点参照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");
    }
}

退出移动版