转载

JAVA 持有对象——容器初探（持续补充）

引言

如果一个程序只包含固定数量的且其生命周期都是已知对象，那么这是一个非常简单的程序——《think in java》

了解容器前，先提出一个问题，ArrayList和LinkedList谁的处理速度更快呢？

一持有对象的方式

在Java中，我们可以使用 数组 来保存一组对象。但是，数组是固定大小的，在一般情况下，我们写程序时并不知道将需要多少个对象，因此数组固定大小对于编程有些受限。

java类库中提供了一套相当完整的容器类来解决这个问题，其中基本类型有 List ， Queue ， Set ， Map ，这些对象类型被称为 集合类 。但是，Java类库中使用了 Collection 来指代集合类中的子集 {List，Queue，Set} ，所以集合类也被称为 容器 。容器提供了完善的方法来保存对象。

二类型安全的容器

java采用 泛型 保证我们不会向容器中插入不正确的类型，但是java的泛型只存在于程序源码中，在经过编译器编译就会将类型擦除。举一个例子：

java//经过编译前 List<String> list = new ArrayList<>(); list.add("ok"); System.out.println(list.get(0));  //经过编译后 List list = new ArrayList(); list.add("ok"); System.out.println((String)list.get(0));

这样做的好处是:在编写程序的时候，不会将其他非导出类型的对象添加到容器中。

三 List

数组存储多个对象的原因是它提前声明了能存储多少对象。那容器又是如何实现存储不定多对象的呢？

java//ArrayList部分源码 private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private transient Object[] elementData; private int size; public ArrayList(int initialCapacity) {  super();  if (initialCapacity < 0)   throw new IllegalArgumentException("Illegal Capacity: "+              initialCapacity);  this.elementData = new Object[initialCapacity]; } public ArrayList() {  super();  this.elementData = EMPTY_ELEMENTDATA; } public boolean add(E e) {  ensureCapacityInternal(size + 1);  // Increments modCount!!  elementData[size++] = e;  return true; } private void ensureCapacityInternal(int minCapacity) {  if (elementData == EMPTY_ELEMENTDATA) {   minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  }  ensureExplicitCapacity(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;  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); }

我们可以看到，在ArrayList类中有一个 elementData数组 。当使用无参构造函数时数组长度默认为空，当向ArrayList加入对象时，会调用一个方法来判断数组是否能放下这个对象。当数组为空时设置数组长度为10并申请相应大小空间， 当数组已满时，最少重新申请原数组大小1.5倍的空间 （除非达到int类型最大值-8）。而在LinkedList中却没有采用这种方式，而是采用链表方式。

java//LinkedList add方法 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++; }

在LinkedList中，他的add方法调用了linkLast方法，直接在链表后边加入一个新的节点。

四 Set

Set类型不保存重复的元素。判断对象元素是否相等采用的是equals方法，所以在存入自定义的对象时，如果重写equals方法依赖于可变属性，将会导致一些问题。

五 Map

Map类型是能够将对象映射到其他对象的一种容器，有区别于List的get方法。HashSet类中包含了一个HashMap对象，HashSet的实现依靠HashMap。

HashMap的实现采用了数组链表的方式，即数组的每一个位置都存放的是链表头。查找会先通过key的hash找到对应数组下标，再在该数组下标所对应的链表中找到是否有对应对象，查找方式为equals方法。

六 Queue

队列是一种典型的先进先出的容器，LinkedList实现了Queue接口。PriorityQueue实现了优先级队列。

七 List的选择

在文章开头提出了一个问题，数组实现的List快还是链表实现的List快。模拟一下试试：

javapublic static void add() {  long start = 0;  long end = 0;  List<Integer> alist = new ArrayList<>();  List<Integer> llist = new LinkedList<>();  System.out.println("ArrayList添加1000万数据所需毫秒数");  start = System.currentTimeMillis();  for (int i=0; i<10000000; i++)  {   alist.add(i);  }  end = System.currentTimeMillis();  System.out.println(end-start);  System.out.println("LinkedList添加1000万数据所需毫秒数");  start = System.currentTimeMillis();  for (int i=0; i<10000000; i++)  {   llist.add(i);  }  end = System.currentTimeMillis();  System.out.println(end-start+"/n");  System.out.println("ArrayList从1000万数据删除数据所需毫秒数");  start = System.currentTimeMillis();  alist.remove(0);  alist.remove(2000000);  alist.remove(4000000);  alist.remove(6000000);  alist.remove(8000000);  alist.remove(9999994);  end = System.currentTimeMillis();  System.out.println(end - start);  System.out.println("LinkedList从1000万数据删除数据所需毫秒数");  start = System.currentTimeMillis();  llist.remove(0);  llist.remove(2000000);  llist.remove(4000000);  llist.remove(6000000);  llist.remove(8000000);  llist.remove(9999994);  end = System.currentTimeMillis();  System.out.println(end - start+"/n");  System.out.println("ArrayList从1000万数据查找数据所需毫秒数");  start = System.currentTimeMillis();  alist.contains(0);  alist.contains(2000000);  alist.contains(4000000);  alist.contains(6000000);  alist.contains(8000000);  alist.contains(10000000);  end = System.currentTimeMillis();  System.out.println(end - start);  System.out.println("LinkedList从1000万数据查找数据所需毫秒数");  start = System.currentTimeMillis();  llist.contains(0);  llist.contains(2000000);  llist.contains(4000000);  llist.contains(6000000);  llist.contains(8000000);  llist.contains(10000000);  end = System.currentTimeMillis();  System.out.println(end - start+"/n"); }

JAVA 持有对象——容器初探（持续补充）可以看到，无论在何种情况下，数组实现的list都比链表快。当我在ArrayList构造方法中设置数组初始大小1000万时，ArrayLIst添加数据的速度慢了下来，降到5000毫秒左右，所以一般情况下不需要优化。