容器基础

泛型和类型安全的容器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import java.lang.reflect.Array;
import java.util.ArrayList;
class Apple{}
public class Main {
public static void main(String[] args) {
ArrayList list = new ArrayList();
list.add(new StringBuffer("a"));
list.add(new Array[2]);
list.add(new Apple());
for(int i=0;i<list.size();i++){
System.out.println(list.get(i));
System.out.println(list.get(i) instanceof java.lang.StringBuffer);
}
}
}

编译和运行时都不会报错。

输出结果:

1
2
3
4
5
6
a
true
[Ljava.lang.reflect.Array;@610455d6
false
Apple@511d50c0
false

System.out.println()调用String.valueOf()方法,后者最终调用object的toString()方法。注意这个容器get拿到的是原本的类型,List知道每个元素的类型,在get时已经自动完成了转型。

使用范型可以在编译期防止将错误类型的对象放置道容器中

1
2
3
4
5
6
7
8
9
10
11
12
import java.lang.reflect.Array;
import java.util.ArrayList;
class Apple{}
public class Main {
public static void main(String[] args) {
ArrayList<Apple> apples = new ArrayList();
apples.add(new Apple());
apples.add(new Array[2]); //此行编译时报错,类型不能加到list里
}
}

基本概念

向上转型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
class Apple{}
public class Main {
public static void main(String[] args) {
List<Apple> apples1 = new ArrayList<Apple>();
List<Apple> apples2 = new LinkedList<Apple>();
LinkedList<Apple> apples3 = new LinkedList<Apple>();
apples2.addFirst(new Apple());//报错没有这个方法
apples3.addFirst(new Apple());
}
}

向上转型的好处是改变实现时,只需在创建处修改。坏处是向上转型后有些类的额外特有的方法就不能用了。

因此,根据是否需要使用具体方法可以选择是否向上转型。

添加元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Main {
public static void main(String[] args) {
Collection<Integer> collection = new ArrayList<Integer>(Arrays.asList(1,2));
collection.addAll(Arrays.asList(3,4));
Collections.addAll(collection,1,2,3,4);
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = Arrays.asList(1,2);
list1.add(3);
System.out.println(list1.getClass());
System.out.println(Arrays.asList(1,2).getClass());
list2.add(3);
}
}

输出结果:

1
2
3
4
5
6
class java.util.ArrayList
class java.util.Arrays$ArrayList
Exception in thread "main" java.lang.UnsupportedOperationException
at java.util.AbstractList.add(AbstractList.java:148)
at java.util.AbstractList.add(AbstractList.java:108)
at Main.main(Main.java:14)

Arrays.asList()方法接受一个数组或一个用逗号隔开的元素列表,并将其转换为一个List对象,注意这个对象不能使用add()或delete()方法,这个对象的类型是Arrays内部类ArrayList,这个内部类继承了AbstractList这个抽象类,AbstractList类提供了一个不可变的List的实现。

Collection的构造器可以接受另一个Collection,用它来初始化自身。
Collection.addAll()只能接受另一个Collection对象作为参数。
Collections.addAll()方法接受一个Collection对象,以及一个数组或逗号分隔的列表,将元素加到第一个参数指定的Collection对象里。

打印容器

容器提供了toString()方法,所以可以直接生成可读性很强的打印结果。


List

List接口在Collection接口的基础上添加了大量的方法,使得可以在List的中间插入和移除元素。

有两种类型的List:

  • 可变数组的实现——基本的ArrayList, 它善长于随机访问元素,但是在List的中间插入和移除元素时较慢。

  • 双向链表的实现——LinkedList, 它能代价较低地在List中间进行插入和删除操作,提供了优化的顺序访问。LinkedList在随机访问方面相对较慢,但是它的特性集较ArrayListg更大。

两种实现都是not synchronized,所以多个进程访问时,需要内部实现同步。或者在创建时阻止非同步的访问。

1
2
List list = Collections.synchronizedList(new ArrayList(...));
List list = Collections.synchronizedList(new LinkedList(...));

contains()、indexOf()、removeAll()、retainAll()、remove()等方法都用到了equals()方法,继承的是根类Object的equals方法,即比较的是对象的地址。

LinkedList的方法的实现跟双向链表的操作类似。LinkedList还添加了可以使其用作栈、队列或双端队列的方法。值得注意的是clear()方法,没有简单的将first = null; last = null; size = 0;而是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void clear() {
// Clearing all of the links between nodes is "unnecessary", but:
// - helps a generational GC if the discarded nodes inhabit
// more than one generation
// - is sure to free memory even if there is a reachable Iterator
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
modCount++;
}

原因注释写的很清楚了。

ArrayList里的几个方法:

  • add()
1
2
3
4
5
6
7
8
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++;
}
  • remove()
1
2
3
4
5
6
7
8
9
10
11
12
13
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;
}
  • addAll()、removeAll()、retainAll()实现与上面类似,用的

System.arraycopy()方法。

  • 还需要注意toArray()方法
1
2
3
4
5
6
7
8
9
10
11
12
13
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}

无参数版本返回一个Object数组,如果向这个重载版本传递一个目标类型的数组,那么它将产生指定类型的数据,注意:参数数组太小的话,会返回一个具有合适大小的数组,太大多余的位置置为null。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Main {
public static void main(String[] args) {
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new LinkedList<Integer>();
list1.add(1);
list1.addAll(0,Arrays.asList(2,3));
list2.add(3);
System.out.println(Arrays.toString(list1.toArray()));
System.out.println(Arrays.toString(list1.toArray(new Integer[2])));
System.out.println(Arrays.toString(list2.toArray(new Integer[2])));
}
}

输出结果:

1
2
3
[2, 3, 1]
[2, 3, 1]
[3, null]

迭代器

迭代器也是一种设计模式,迭代器模式(Iterator),提供一种方法顺序访问一个聚合对象中的各种元素,而又不暴露该对象的内部表示。

如果只是前向遍历List,不改变List对象本身,使用foreach语法更简洁。

Iterator

Iterator可以移除由next()产生的最后一个元素,就是说在remove()之前必须先调用一下next()。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>(Arrays.asList(1,2,3));
System.out.println(list);
Iterator<Integer> it = list.iterator();
for(int i = 0; i < 2; i++) {
it.next();
it.remove();
}
System.out.println(list);
}
}

输出结果:

1
2
[1, 2, 3]
[3]

ListIterator

ListIterator是一个更加强大的Iterator的子类型,它只能用于各种List类的访问。Iterator只能向前遍历,但ListIterator可以双向移动,且可以拿到前后元素的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.*;
public class Main {
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>(Arrays.asList(1,2,3));
System.out.println(list);
ListIterator<Integer> it = list.listIterator();
while (it.hasNext()){
System.out.println(it.previousIndex() + "," + it.nextIndex() + ":" + it.next() + "," + it.nextIndex());
}
System.out.println(list);
while (it.hasPrevious()) {
it.previous();
it.set(1);
}
System.out.println(list);
it = list.listIterator(1);
while (it.hasNext()) {
it.next();
it.remove();
}
System.out.println(list);
}
}

输出结果:

1
2
3
4
5
6
7
[1, 2, 3]
-1,0:1,1
0,1:2,2
1,2:3,3
[1, 2, 3]
[1, 1, 1]
[1]

listIterator(n)创建一个开始索引为n的迭代器。


Stack

栈通常指“后进先出”的容器。LinkedList具有能够直接实现栈的所有功能的方法,因此一般直接把LinkedList作为栈使用。

Java Stack类继承了Vector类,后者实现了List接口。


Set

Set接口实现了Collection接口,接口里的方法完全一样,没有额外的功能,只是行为不同,Set不允许有重复的元素。

HashSet类使用的是散列函数。TreeSet将元素存储于红黑树中,且元素按照比较器的顺序排列。LinkedHashSet使用了散列和链表,元素顺序保持插入的顺序。


Map

HashMap、TreeMap、LinkedHashMap的区别与几种Set一致。


Queue

队列是一个典型的“先进先出”的容器。LinkedList提供了方法来支持队列的行为,并且它实现了队列的接口,因此LinkedList可以用作Queue的一种实现。

通过向上转型成Queue接口类型,窄化了对LinkedList方法的访问权限,使得只有恰当的方法才可以使用。

1
2
3
4
5
6
7
8
9
10
11
12
import java.util.*;
public class Main {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(1);
System.out.println(queue.poll());
System.out.println(queue.peek());
}
}

输出结果:

1
2
1
null

注意的是peek()在队列为空时返回null,而LinkedList里的remove()等方法会抛出NoSuchElementException。

PriorityQueue

优先级队列——声明下一个弹出的元素是优先级最高的元素,优先级可以自行指定,用起来很方便。使用小顶堆来维护优先级。

有几个方法的源码值得看一下:深入理解Java PriorityQueue - CarpenterLee - 博客园

1
2
3
4
5
6
7
8
9
10
11
import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(4,Collections.<Integer>reverseOrder());
queue.addAll(Arrays.asList(1,2,3,4));
System.out.println(queue.toString());
}
}

输出结果:

1
[4, 3, 2, 1]

Collection 和Iterator

Collection是描述所有序列容器共性的根接口。另外AbstractCollection类提供了一个Collection的默认实现。

使用接口描述的一个理由是它可以使我们能够创建更通用的代码,Java用迭代器表示容器之间的共性。

Collection接口和Iterator迭代器都可以实现方法和底层容器的解耦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.util.*;
public class Main {
public static void main(String[] args) {
}
public class Pets extends AbstractCollection{
@Override
public Iterator iterator() {
return null;
}
@Override
public int size() {
return 0;
}
}
public class Cars implements Collection{
@Override
public Object[] toArray() {
return new Object[0];
}
@Override
public T[] toArray(Object[] a) {
return new T[0];
}
@Override
public void clear() {
}
@Override
public boolean removeAll(Collection c) {
return false;
}
...
}
}

Collection的好处在于它实现了Iterable接口,所以可以用foreach语法使得代码更加清晰。但是当你实现一个不是Collection类型的外部类时,继承AbstractionCollection类更轻松,虽然还是得强制实现iterator()和size()方法。但相比实现Collection接口要简单多了,实现该接口要实现接口里的所有的方法。如果你的外部类已经继承了另一个类,当然要是接口里的方法你不需要,可以实现一些其他接口,如果需要,那只能实现Collection接口的方法了。


Foreach和迭代器

实现了Iterable接口的类,都可以使用foreach语句。虽然数组可以用foreach语法,但
数组不是Itrable类型。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import java.util.*;
public class Main {
public static void main(String[] args) {
String[] s = {"a","b"};
//test(s);//编译报错String[]不是Iterable<T>类型
test(Arrays.asList(s));//显式转换后没有报错
}
static <T> void test(Iterable<T> it){
for (T t: it)
System.out.print(t + " ");
}
}

输出结果:

1
a b

适配器方法惯用法

两种适配器模式(Adapter Pattern) - CSDN博客

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.*;
public class Main {
public static void main(String[] args) {
String[] s = {"a","b","c"};
System.out.println(Arrays.toString(s));
List<String> list1 = new ArrayList<String>(Arrays.asList(s));
Collections.shuffle(list1);
System.out.println(Arrays.toString(s));
List<String> list2 = Arrays.asList(s);
Collections.shuffle(list2);
System.out.println(Arrays.toString(s));
}
}

输出结果:

1
2
3
[a, b, c]
[a, b, c]
[b, c, a]

Arrays.asList()传递给ArrayList的构造器后,shuffle不会打乱原数组。

0 Comments