一、前言
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");
}
}
发表回复