java集合框架

List,Set,Map的区别

List(对付顺序的好帮手)：List接口存储一组不唯一（可以有多个元素引用相同的对象）、有序的对象
Set(注重独一无二的性质)：不允许重复的集合，不会有多个元素引用相同的对象
Map(用Key搜索的专家)：使用键值对存储。Map会维护与key有关联的值。两个key可以引用相同的对象，
　　　　　　　　　　　　　但key不能重复。典型的key是String类型，但也可以是任意对象

ArrayList与LinkedList的区别

1.是否保证线程安全：ArrayList和LinkedList都是不同步的，也就是不保证线程安全；
2.底层数据结构：ArrayList底层使用的是Object数组，LinkedKList底层使用的是双向链表数据结构
　　　　　　　　（JDK1.6之前为循环链表，1.7取消了循环）；
3.插入和删除是否受元素位置的影响：a.ArrayList采用数组存储，所以插入和删除元素的时间复杂度受元素位置
　　　　　　　　　　　　　　　　　　的影响。比如：执行add(E e)方法的时候，ArrayList会默认在将指定的元
　　　　　　　　　　　　　　　　　　素追加到此列表的末尾，这种情况复杂度就是O(1) 指无穷小量。
　　　　　　　　　　　　　　　　　　但是如果要在指定位置i插入和删除元素的话
　　　　　　　　　　　　　　　　　　（add(int index,E element)），时间复杂度就是O(n-i)。因为上述操作时，
　　　　　　　　　　　　　　　　　　集合中第i和第i个元素之后的（n-i）个元素都要向后/前移一位的操作；
　　　　　　　　　　　　　　　　　　b.LinkedList采用链表存储，所以对于add(E e)方法的插入，删除元素时
　　　　　　　　　　　　　　　　　　间复杂度不收元素位置的影响，近似O(1)，如果是要在指定位置i插入和删除元素
　　　　　　　　　　　　　　　　　　的话（(add(int index, E element)）时间复杂度近似为o(n))因为需要先
　　　　　　　　　　　　　　　　　　移动到指定位置再插入；
4. 是否支持快速随机访问：LinkedList不支持高效的随机元素访问，而ArrayList支持。快速随机访问就是通
　　　　　　　　　　　　　　过元素的序号快速获取元素对象(对应于get(int index)方法)；
5. 内存空间占用：ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间，而LinkedList
　　　　　　　　　　的空间花费则体现在它的每一个元素都需要消耗比ArrayList更多的空间（因为要存放直接后继和
　　　　　　　　　　直接前驱以及数据）。

ensureCapacity()方法

public class EnsureCapacityTest {
	public static void main(String[] args) {
		ArrayList<Object> list = new ArrayList<Object>();
		final int N = 10000000;
		long startTime = System.currentTimeMillis();
		for (int i = 0; i < N; i++) {
			list.add(i);
		}
		long endTime = System.currentTimeMillis();
		System.out.println("使用ensureCapacity方法前："+(endTime - startTime));

		list = new ArrayList<Object>();
		long startTime1 = System.currentTimeMillis();
		list.ensureCapacity(N);
		for (int i = 0; i < N; i++) {
			list.add(i);
		}
		long endTime1 = System.currentTimeMillis();
		System.out.println("使用ensureCapacity方法后："+(endTime1 - startTime1));
	}
}

运行结果

使用ensureCapacity方法前：4637
使用ensureCapacity方法后：241

通过运行结果，我们可以很明显的看出向ArrayList添加大量元素之前最好先使用ensureCapacity()方法，以减少
增量重新分配的次数