Java集合框架早也是个老话题了,今天主要是总结一下关于Java中的集合框架List的核心知识点。肯定有人会问,这篇写的是List那接下来就还有三篇?是的,java集合框架一共会有四篇。希望通过这个系列能让你全面的get到Java集合框架的核心知识点。
目的
更希望通过这个系列的文章有所收获,不仅可以用于工作中,也可以用于面试中。
Java 集合是一个存储相同类型数据的容器,类似数组,集合可以不指定长度,但是数组必须指定长度。集合类主要从 Collection 和 Map 两个根接口派生出来,比如常用的 ArrayList、LinkedList、HashMap、HashSet、ConcurrentHashMap 等等。包目录:java.util
学过Java的都知道Java有四大集合框架,JDK版本1.8
下面展示常用的集合框架(下面图中的两种线:虚线为实现,实线为继承)
ArrayList 是基于动态数组实现,容量能自动增长的集合。随机访问效率高,随机插入、随机删除效率低。线程不安全,多线程环境下可以使用 Collections.synchronizedList(list) 函数返回一个线程安全的 ArrayList 类,也可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类。
动态数组,是指当数组容量不足以存放新的元素时,会创建新的数组,然后把原数组中的内容复制到新数组。
主要属性:
//存储实际数据,使用transient修饰,序列化的时不会被保存
transient Object[] elementData;
//元素的数量,即容量。
private int size;
数据结构:动态数组
特征:
使用场景:
常用方法介绍
add(element) 流程:添加元素
private static final int DEFAULT_CAPACITY = 10;
//添加的数据e放在list的后面
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;
}
grow() 流程:扩容
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
add(index,element) 流程:向指定下标添加元素
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
set(index,element) 流程:设置新值,返回旧值
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
get(index) 流程:通过下标获取list中的数据
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
remove(index) 流程:按照下标移除lsit中的数据
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;
}
remove(object) 流程:
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0){
//数组拷贝
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
}
//方便GC
elementData[--size] = null;
}
总结:
LinkedList 是可以在任何位置进行插入和移除操作的有序集合,它是基于双向链表实现的,线程不安全。LinkedList 功能比较强大,可以实现栈、队列或双向队列。
主要属性:
//链表长度
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;
}
数据结构:双向链表
特征:
使用场景:
add() 流程:
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++;
}
get(index) 流程:
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int 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;
}
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
return index >= 0 && index < size;
}
remove() 流程:
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
private void checkElementIndex(int index) {
if (!isElementIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
Vector 是矢量队列,也是基于动态数组实现,容量可以自动扩容。跟 ArrayList 实现原理一样,但是 Vector 是线程安全,使用 Synchronized 实现线程安全,性能非常差,已被淘汰,使用 CopyOnWriteArrayList 替代 Vector。
主要属性:
//存储实际数据
protected Object[] elementData;
//动态数组的实际大小
protected int elementCount;
//动态数组的扩容系数
protected int capacityIncrement;
数据结构:动态数组
特征:
使用场景:多线程环境
为什么是线程安全的,看看下面的几个常用方法就知道了。
public synchronized void addElement(E obj) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
public boolean remove(Object o) {
return removeElement(o);
}
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
这几个常用方法中,方法都是使用同步锁synchronized修饰,所以它是线程安全的。
Stack 是栈,先进后出原则,Stack 继承 Vector,也是通过数组实现,线程安全。因为效率比较低,不推荐使用,可以使用 LinkedList(线程不安全)或者 ConcurrentLinkedDeque(线程安全)来实现先进先出的效果。
数据结构:动态数组
构造函数:只有一个默认 Stack()
特征:先进后出
实现原理:
public class Stack<E> extends Vector<E> {
//....
}
CopyOnWriteArrayList 是线程安全的 ArrayList,写操作(add、set、remove 等等)时,把原数组拷贝一份出来,然后在新数组进行写操作,操作完后,再将原数组引用指向到新数组。CopyOnWriteArrayList 可以替代 Collections.synchronizedList(List list)。这个是在JUC包目录下的。内部使用了AQS实现的锁。
java.util.concurrent
数据结构:动态数组
特征:
缺点:
实现原理:
CopyOnWriteArrayList 写操作加了锁,不然多线程进行写操作时会复制多个副本;读操作没有加锁,所以可以实现并发读,但是可能读到旧的数据,比如正在执行读操作时,同时有多个写操作在进行,遇到这种场景时,就会都到旧数据。
public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8673264195747942595L;
/** The lock protecting all mutators */
final transient ReentrantLock lock = new ReentrantLock();
//添加数据
public boolean add(E e) {
//使用到了锁机制
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
//释放锁
lock.unlock();
}
}
//移除数据
public E remove(int index) {
//锁机制
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
E oldValue = get(elements, index);
int numMoved = len - index - 1;
if (numMoved == 0)
setArray(Arrays.copyOf(elements, len - 1));
else {
Object[] newElements = new Object[len - 1];
System.arraycopy(elements, 0, newElements, 0, index);
System.arraycopy(elements, index + 1, newElements, index,
numMoved);
setArray(newElements);
}
return oldValue;
} finally {
//释放锁
lock.unlock();
}
}
好的,以上便是今天分享的内容。希望你有所收获。