乐趣区

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

jiezi

一、前言

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

二、List接口

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

  • ArrayList

     
  • Vector

     
  • LinkedList

  ArrayList、Vector以及LinkedList 3 种 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");
    }
}
退出移动版