对象的容器，定义了对多个对象进行 *** 作的常用方法，可以实现数组的功能。存在于java.util.*
集合和数组的区别- 数组的长度固定，集合的长度不固定
- 数组可以存储基本类型和引用类型，而集合只能存储引用类型
单列集合(Collection)
双列集合(Map)
- collection实现子类可以存放多个元素，每个元素可以是Object
- Collection的实现类，有些可以存放重复元素，有些不可以
- Collection的实现类，有些是有序的(List)，有些是无序的(Set)
- Collection接口没有直接的实现子类，是通过他的子接口 List 和 Set 来实现的
补充Iterator接口，用于迭代遍历集合元素
- List集合类中元素有序(即添加和取出顺序一致)、且可以重复
- List集合中的每个元素都有其对应的顺序索引，即支持索引
- 常有的实现类有：ArrayList、linkedList、Vector
- ArrayList可以加入null值，没有数量限制
- ArrayList是由数组来实现数据存储的
- ArrayList是线程不安全的，如果再多线程的情况下，可以考虑使用Vector。
- ArrayList中维护了一个Object类型的数组elementData transient Object[] elementData;(transient 表示当前属性不会被序列化)
- 当创建了ArrayList对象时，如果使用的是无参构造器，则初始的elementData容量为0，第一次添加，则扩容elementData为10，如需要再次扩容，则扩容elementData为1.5倍
- 如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容为elementData的1.5倍
首先重点对下面要用到的一些变量做解释：
elementData：存放当前ArrayList集合的数组，其大小就是当前ArrayList集合中元素的数量
size：表示当前ArrayList集合中元素的数量
DEFAULT_CAPACITY：默认的初始容量，值为10
minCapacity：当前ArrayList所需要的最小容量，当大于集合中元素数量时，说明所需大于已有，就要进行扩容
newCapacity：扩容之后的新数组的大小
modCount：对当前ArrayList进行修改的次数
MAX_ARRAY_SIZE ：数组可容纳的最大的数量
当调用无参构造器时，首先会初始化容量为0的空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
......
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
当调用有参构造器时，会指定数组大小
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);
}
}
当调用add方法的时候，会进入下面一系列的 *** 作
public boolean add(E e) {
// 首先判断在当前长度基础上再加上一个新元素后，集合容量是否还够
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 判断是否是第一次调用add方法，即判断当前数组是否为空，如果为空则初始化容量为10，否则直接返回当前所需最小容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是第一次调用add方法，即此时数组为空数组，则初始化此时容量为10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
// 修改次数加一
modCount++;
// overflow-conscious code
// 判断此时所需最小容量和当前集合长度的关系
// 如果所需最小容量大于了当前集合的长度值，则说明此时的数组已经无法容纳更多元素加入，所以要进行扩容
// 如果所需最小容量小于当前集合的长度之，说明此时数组可以存放更多的元素，则不需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩容为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果是第一次调用add方法，此时数组大小为0，常规扩容无效
// 或者扩容后还是不能满足元素的存放需求
// 此时则需要直接将所需最小容量复制给新容量
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);
}
(二) Vector底层结构和源码分析
Vector与ArrayList对比
Vector构造方法
public Vector() {
this(10);
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public Vector(Collection c) {
elementData = c.toArray();
elementCount = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
Vector的add方法(扩容)
public synchronized void addElement(E obj) {
modCount++;
// 首先判断数组的长度是否足够加入新元素
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = obj;
}
private void ensureCapacityHelper(int minCapacity) {
// overflow-conscious code
// 如果所需最小容量比当前数组的长度值大，说明不够存储新元素，所以扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 如果构造方法中capacityIncrement值大于0，则扩容为原容量+capacityIncrement
// 如果构造方法中capacityIncrement为默认0值，则扩容为原来的两倍
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
// 第一次扩容，数组大小为0，避免扩容失败，所以直接将所需最小容量赋值给新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
(三) linkedList底层结构和源码分析(重点)
linkedList特点
- linkedList底层实现了双向链表和双端队列特点
- 可以添加任意元素(元素可重复)，包括null
- 线程不安全，没有实现同步
- linkedList底层维护了一个双向链表
- linkedList中维护了两个属性first和last分别指向 首节点和尾节点
- 每个节点都是一个Node对象，里面维护了prev、next、item三个属性，其中通过prev指向前一个节点，通过next指向后一个节点，最终实现双向链表
private static class Node{ E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } }
- 因为此时增加、删除元素不需要进行扩容和元素复制，所以效率较高
调用无参构造器， first 和 last 都为null
public linkedList() {
}
1. add()方法
public boolean add(E e) {
// 调用尾插法
linkLast(e);
return true;
}
// 尾插法
void linkLast(E e) {
// 得到尾结点
final Node l = last;
// 创建要加入的新节点，并设置前驱节点为last(因为是尾插，插到last之后)
final Node newNode = new Node<>(l, e, null);
// 将尾节点指向新节点
last = newNode;
// 如果之前不存在尾节点，即第一次插入，则直接让头结点指向新结点(只有一个节点，头尾都指向它)
// 否则，让上一个尾节点的后继节点指向当前新的尾节点(即加入的新节点)
if (l == null)
first = newNode;
else
l.next = newNode;
// 链表长度加一
size++;
modCount++;
}
2. removeLast()方法
public E removeLast() {
// 直接得到最后一个元素值，传入unlinkLast方法进行删除 *** 作
final Node l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
private E unlinkLast(Nodel) { // assert l == last && l != null; // 得到最后一个元素值，最后作为返回值 final E element = l.item; // 先创建节点指向要删除的尾结点的前驱节点 final Node prev = l.prev; // 将尾结点的值和前驱节点置为空 l.item = null; l.prev = null; // help GC // 尾结点指向其前驱节点，即此时尾结点为上一个节点 last = prev; // 如果prev为空，说明此时链表为空，则首节点也置为空(头尾都指向null) // 否则，说明链表不为空，就让现在新的尾节点的后继节点指向null,之前的尾结点没有任何指向 if (prev == null) first = null; else prev.next = null; // 长度减一 size--; modCount++; return element; }
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）