一、ArrayList 、LinkList和Vector查找和插入性能分析
ArrayList、Vector是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
当插入的数据量很小时，三者区别不太大；
当插入的数据量大且在靠前的部分插入或删除数据时，LinkList比较快速，ArrayList、Vector较慢；
当插入的数据量大且在靠后位置操作时，ArrayList、Vector较LinkList快速；
所以在不需要使用LinkedList实现栈、队列以及双端队列等数据结构时，推荐使用ArrayList较好(如果不需要线程安全，不推荐使用Vector);例子：
public class ArrayListTest {
public static void main(String[] args) {
List<Integer> arrayList = new ArrayList<>();
List<Integer> linkList = new LinkedList<>();
List<Integer> vector = new Vector<>();
//首先分别给两者插入10000条数据
for (int i = 0; i < 100000; i++) {
arrayList.add(i);
linkList.add(i);
vector.add(i);
}
//获得两者随机访问的时间;
System.out.println("arrayList time:" + getTime(arrayList));
System.out.println("linked time:" + getTime(linkList));
System.out.println("vector time:" + getTime(vector));
//获得两者插入数据的时间
System.out.println("arrayList insert time:" + insertTime(arrayList));
System.out.println("linked insert time:" + insertTime(linkList));
System.out.println("vector insert time:" + insertTime(vector));
}
public static long getTime(List<Integer> list) {
long time = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
int index = Collections.binarySearch(list, list.get(i));
if (index != i) {
System.out.println("ERROR!");
}
}
return System.currentTimeMillis() - time;
}
//插入数据
public static long insertTime(List<Integer> list) {
/*
* 插入的数据量和插入的位置是决定两者性能的主要方面，
* 我们可以通过修改这两个数据，来测试两者的性能
*/
long num = 10000; //表示要插入的数据量
int index = 1000; //表示从哪个位置插入
long time = System.currentTimeMillis();
for (int i = 1; i < num; i++) {
list.add(index, i);
}
return System.currentTimeMillis() - time;
}
}
二、ArrayList源码分析
参考
1. 继承类及接口
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
- 继承 AbstractList
- 实现
List<E>，
RandomAccess:(
1. RandomAccess是一个标记接口，接口内没有定义任何内容。
2. 此接口的主要用途是允许泛型算法改变其行为，以便在应用于随机或顺序访问列表。
3. 如果集合类是RandomAccess的实现，则尽量用
for(int i =0;i<size;i++)来遍历而不要用Iterator迭代器来遍历。
),
Cloneable(
1. 此类实现了 Cloneable 接口，以指示Object.clone() 方法可以合法地对该类实例进行按字段复制。没有实现该接口调用，则会导致抛出 CloneNotSupportedException 异常。
2. 注意：Cloneable接口没有任何方法
),
Serializable(
1. Java序列化是指把Java对象保存为二进制字节码的过程，Java反序列化是指把二进制码重新转换成Java对象的过程。
)
2. ArrayList的数据域
//底层使用Object数组，保存元素
private transient Object[] elementData;
//集合的大小
private int size;
3. transient 关键字
- transient是Java语言的关键字，用来表示一个域不是该对象序列化的一部分。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的。
- 例子：
public class TransientTest {
public static void main(String[] args) throws IOException {
//// TODO: 2017/11/1
Person person = new Person("张三", "123456");
System.out.println("序列化前：" + person);
//序列化保存
ObjectOutputStream o = null;
try {
o = new ObjectOutputStream(new FileOutputStream(
"person.out"));
o.writeObject(person);
o.close();
} catch (IOException e) {
e.printStackTrace();
}
//反序列读取
ObjectInputStream objectInputStream = new ObjectInputStream(new FileInputStream("person.out"));
try {
Object object = objectInputStream.readObject();
System.out.println("序列化后：" + object);
} catch (ClassNotFoundException e) {
e.printStackTrace();
}
}
}
/**
* 序列化前：Person{name='张三', password='123456'}
* 序列化后：Person{name='张三', password='null'}
*/
class Person implements Serializable {
String name;
transient String password;
public Person(String name, String password) {
this.name = name;
this.password = password;
}
@Override
public String toString() {
return "Person{" +
"name='" + name + '\'' +
", password='" + password + '\'' +
'}';
}
}
4. 自动扩容机制
- 源码
//1. 添加元素方法，才会检查容量的大小
public boolean add(E e) {
//检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果是使用无参构造方法实例化，则初始化底层数组容量为默认大小10
//
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//此字段由 iterator 和 listIterator 方法返回的迭代器和列表迭代器实现使用。
//如果意外更改了此字段中的值，则迭代器（或列表迭代器）将抛出 ConcurrentModificationException 来响应 next、remove、previous、set 或 add 操作。
//在迭代期间面临并发修改时，它提供了快速失败 行为，而不是非确定性行为。
modCount++;
// 防止数组越界，越界则进行扩容为本身容量的1.5倍
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//实现扩容的源码
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//计算新容量的大小为原来的1.5倍，oldCapacity >> 1等于(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);
}
//达到最大可分配值的限制
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
- 总结
- 在每次添加元素时，都会进行判断是否要扩容，所以，如果一开始就知道所需的容量，就在实例化时给定大小，或调用ensureCapacity方法初始化容量大小；这样就避免扩容时，对元素的操作带来的性能消耗
5.ArrayList的优缺点
优点
- get，set，时间复杂度为O(1)
- add（一般都是在末尾插入），时间复杂度为O(1)，最差情况下（往头部插入数据），时间复杂度O(n)
- 数据存储是顺序的
缺点
remove，时间复杂度为O(n)，最优情况下（移除末尾元素），时间复杂度为O(1)
ArrayList大小很大的时候，会存在空间浪费（可以通过trimToSize方法，清除空闲空间）
数组大小是由限制的，受jvm和机器的影响，当扩容超出上限时，ArrayList会抛出异常
线程安全
- 如果考虑到线程安全的话，可以使用CopyOnWriteArrayList或者外部同步ArrayList（List list = Collections.synchronizedList(new ArrayList(…));)
三、LinkList源码分析
参考
1. 继承类和实现接口
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
- 继承
AbstractSequentialList
- 实现
List<E>，
Cloneable,
Serializable，
Deque<E>(
1. 一个线性 collection，支持在两端插入和移除元素。
2. 虽然 Deque 实现没有严格要求禁止插入 null 元素，但建议最好不这样做。建议任何事实上允许 null 元素的 Deque 实现，用户最好不要利用插入 null 的功能。这是因为各种方法会将 null 用作特殊的返回值来指示双端队列为空。
)
2. 数据节点
- 数据节点图
节点图示.PNG
- 代码
//LinkList变量定义
transient int size = 0;//链表的长度
transient Node<E> first;//链表的头指针
transient Node<E> last;//链表的尾指针
private static class Node<E> {
//数据本身
E item;
//数据后继
Node<E> next;
//数据前驱
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
3. 添加操作
因为LinkedList即实现了List接口，又实现了Deque接口，所以LinkedList既可以添加将元素添加到尾部或头部，也可以将元素添加到指定索引位置
- 在尾部添加
代码
public boolean add(E e) {
linkLast(e);
return true;
}
void linkLast(E e) {
//指向链表的尾部
final Node<E> l = last;
//创建一个前驱为尾部节点的新节点
final Node<E> newNode = new Node<>(l, e, null);
//把尾部指针指向新节点
last = newNode;
//如果链表为空，则把新建的节点指向头指针中
if (l == null)
first = newNode;
//否则，就把尾指针的后继指向新节点
else
l.next = newNode;
size++;
modCount++;
}
尾部添加图解
LinkedList尾部添加节点图示.PNG
- 在指定位置添加元素
代码
public void add(int index, E element) {
checkPositionIndex(index);//检查index是否在[0,size]之间，不是抛出异常
if (index == size)
linkLast(element);//添加到尾部
else
linkBefore(element, node(index));//添加到指定的索引
}
//通过索引，返回指定节点
Node<E> node(int index) {
// assert isElementIndex(index);
//如果索引靠前，则从头开始遍历
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
//否则，从尾部开始遍历
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
//在节点前插入新节点
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
图解
LinkedList指定位置添加节点图示.PNG
