首先list和set集合都实现了同一个集合的顶级接口Collection，那么collection与collections有什么区别呢？Collection是一个集合接口，提供了对集合对象进行操作的通用接口方法。而collections则是集合类的一个工具类，提供了一系列的静态方法，包括对集合的排序、搜索及线程安全等操作。 我们常见的list有LinkedList和ArrayList ,下面我们从底层数据结构与实现来分析一下各自的优缺点。 1、ArrayList底层是一个基于索引object数组，查询时间复杂度为O(1),因为插入和删除时需要移动下标所以导致开销增大效率低下，在JDK1.7及之前，初始化一个ArrayList的默认容量大小为10,JDK1.8初始容量为空，等第一次添加数据时自动扩容，此时容量为10，再次扩容容量以1.5倍增大，这是面试过程中常被问到的一个问题，下边我们看一下源码： JDK1.7 ArrayList底层object数组
private transient Object[] elementData; //存储ArrayList元素的数组缓冲区。
// 创建一个空构造ArrayList对象
ArrayList arr = new ArrayList();
/**
* 底层创建了长度是10的Object[]
*/
无参构造函数
public ArrayList() {
this(10);
}
this所调用函数
public ArrayList(int initialCapacity/*此时形参为10*/) {
super();
if (initialCapacity < 0)//不成立，抛出非法参数异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];//创建一个Object数组长度为10
}
JDK1.8创建对象ArrayList arr = new ArrayList();//调用无参构造
调用无参构造函数
public ArrayList() {
//private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//transient Object[] elementData;
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
//将空Object[]数组对象赋值给elementData
}
第一次添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // modCount增加
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//当elementData == 空对象数组
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY:默认容量 private static final int DEFAULT_CAPACITY = 10;
//minCapacity：最小需要容量
//取这两个中最大的一个作为最小需要容量
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
扩容方法
/**
* 增加容量，以确保它至少可以容纳由最小容量参数指定的元素数量。
*/
private void grow(int minCapacity) {
/**
1.oldCapacity：当前集合容量
2.newCapacity：当前集合容量的1.5倍
3.当newCapacity < 最小需要的容量值 将最小需要的容量值赋值给newCapacity
4.当newCapacity > 最大数组长度 调用hugeCapacity方法；
如果最小需要容量值 > 最大数组长度：返回 Integer.MAX_VALUE
反之：返回最大容量值、将返回的值赋值给newCapacity
5.调用Arrays.copyOf方法，赋值给一个指定的新长度的数组
*/
1.int oldCapacity = elementData.length;
2.int newCapacity = oldCapacity + (oldCapacity >> 1);
3.if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
4.if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
5.elementData = Arrays.copyOf(elementData, newCapacity);
}
2、LinkedList底层是一个双向链表，它比ArrayList更占用内存空间，因为每一个节点存储了两个引用单元，一个指向前一个元素，一个指向后一个元素，查询时间复杂度为O(n),但插入和删除较快其时间复杂度为O(1)。
|
