H5W3
当前位置:H5W3 > java > 正文

【Java】Java List集合解析

List概述

List集合的元素以线性方式存储
1.可以允许重复的对象。
2.可以插入多个null元素。
3.是一个有序集合,保持了每个元素的插入顺序,输出的顺序就是插入的顺序。

List实现类

ArrayList

ArrayList底层是用数组实现的存储,Object[] elementData
查询效率高,增删效率低,线程不安全
ArrayList()提供了三种构造方法。
  ArrayList():构造一个初始容量为10的空列表。

    /**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

  ArrayList(int initialCapacity):构造具有指定初始容量的空列表。

    public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

  ArrayList(Collection c):构造一个包含指定集合的元素的列表,按照它们由集合的迭代器返回的顺序。

    public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

ArrayList关键源码解析

add()方法
    public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果minCapacity大于elementData的长度,则进行扩容处理
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//容量默认扩大1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//数组容量存在最大值
newCapacity = hugeCapacity(minCapacity);
//数组复制
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}    
  1. int newCapacity = oldCapacity + (oldCapacity >> 1);每次扩容是原数组的1.5倍
  2. elementData = Arrays.copyOf(elementData, newCapacity);创建一个长度是原数组容量1.5倍的新的数组,将原数组的数据复制到新数组中,elementData指向新的数组地址
  3. 扩容也是有限的,存在最大值Integer.MAX_VALUE,但是在某些虚拟机上数组容量达到MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8时会内存溢出

4.最重要的一个点:如果我们可以事先估计出数据量,那么最好给ArrayList一个初始值,这样可以减少其扩容次数,从而省掉很多次内存申请和数据搬移操作。(不指定初始值,至少会执行一次grow方法,用于初始化内部数组)。

remove()方法
    public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}

System.arraycopy(elementData, index+1, elementData, index,numMoved);复制一个index+1开始到最后的数组,然后把它放到index开始的位置

ArrayList为什么是线程不安全的

add()方法是非原子操作
1.多个线程进行add操作时可能会导致elementData数组越界
2.多线程环境下执行时,可能就会发生一个线程的值覆盖另一个线程添加的值

Vector

在ArrayList的所有方法加了synchronized关键字,线程安全。

LinkedList

ArrayList底层是用双向链表实现的存储,
查询效率低,增删效率高,线程不安全

Node节点:

    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;
}
}

LinkedList有一个空参构造函数和一个集合参数构造函数:


public LinkedList() {
}
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

LinkedList关键源码解析

get()方法:

    public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
Node<E> node(int index) {
// assert isElementIndex(index);
//查找位置 index 如果小于节点数量的一半(size>>1表示把size右移1位,相当于size/2)则从头节点开始查找,否则从尾节点查找
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;
}
}

LinkedList为什么是线程不安全的

add()方法是非原子操作
多个线程进行add操作时可能会节点覆盖

Stack

Stack 继承自Vector,底层也是用数组实现的存储,线程安全,遵守 LIFO(后进先出)的操作顺序

Stack关键源码解析

    //入栈,添加一个元素到数组末尾
public E push(E item) {
addElement(item);
return item;
}
//出栈,删除数组最后一个元素并返回
public synchronized E pop() {
E       obj;
int     len = size();
obj = peek();
removeElementAt(len - 1);
return obj;
}
//获取最后一个元素,不删除
public synchronized E peek() {
int     len = size();
if (len == 0)
throw new EmptyStackException();
return elementAt(len - 1);
}

参考:
一篇文章带您读懂List集合(源码分析)

本文地址:H5W3 » 【Java】Java List集合解析

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址