持有对象-容器类基础

容器类的作用是存储对象(持有对象),它们提供不同的方式保存程序中的对象,常用的容器有ArrayList,LinkedList,HashMap等…

Java容器的继承结构

容器类基本关系

橙色框是最常用的几个容器类。

容器的基本概念

Java容器类类库的用途是保存对象
容器类被划分为两大类:Collection和Map

Collection

Collection是独立元素的序列,这些元素的存储都必须遵守一定的规则;比如List按照顺序插入,Set不能有重复元素等。

Map

键值对存储。与Collecton不同,Map将对象之间建立了一种关联,也被称为关联数组或者字典。

基本容器

ArrayList

List实现Collection,添加了大量的方法,List有两种类型:ArrayList和LinkedList,它们的底层数据结构分别是可变数组和链表。这意味着在使用List的过程中不需要担心长度的限制,它们是动态变化的。

ArrayList长于随机访问元素,而插入删除的效率较低。

LinkedList

LinkedList相对于ArrayList,它长于插入删除元素,而随机访问效率较低。

除了具备ArrayList的操作之外,LinkedList还包含了可以将其当作栈,队列/双端队列使用的方法。

例如:peek方法常用做获取栈顶元素,在LinkedList中peek方法和getFirst()、element()完全一样,它们都是获取链表首个元素。它们的区别只存在于表为空时:peek方法返回null,而其他两个方法则会抛出NoSuchElementException异常。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   public static void main(String[] args) {
LinkedList<Integer> list=new LinkedList<>();
list.add(1);
list.add(4);
list.add(23);
System.out.println(list.toString());
System.out.print(list.getFirst()+"-");
System.out.print(list.element()+"-");
System.out.println(list.peek());
/**输出
* [1, 4, 23]
1-1-1
*/
}

poll方法与removeFirst()和remove()也是一样的,都是移除收个元素,它们的区别和peek()、getFirst()一样。

虽然LinkedList提供了这些方法,但是并不常用,栈/队列有单独的实现。

Stack

LinkedList具有能够直接实现栈的所有功能的方法,因此可以直接将LinkedList作为栈使用。不过,有时一个真正的栈更能把事情讲清楚。
——摘自《Java编程思想》

Stack基本操作就是push()入栈,pop()出栈,peek()获取栈顶,empty()判断是否为空等。

1
2
3
4
5
6
7
8
9
public static void main(String[] args) {
Stack<Integer> stack=new Stack<>();
stack.push(12);
stack.push(4);
System.out.print(stack.pop()+"-");
System.out.print(stack.toString()+"-");
System.out.print(stack.peek()+"-");
System.out.println(stack.empty());
}//输出:4-[12]-12-false

Set

Set不允许元素重复,Set最常用来判断某个对象是否在集合中,于是Set最重要的操作是查找,HashSet专门对快速查找进行了优化。

Set实际上和Collection是同一个东西,它没有任何扩展的方法,只是行为不同。

HashSet是Set的一个实现,底层使用散列函数来实现快速查找,考虑到效率,HashSet的输出顺序与加入的顺序可能完全不同。

1
2
3
4
5
6
7
8
public static void main(String[] args) {
Set<Integer> set=new HashSet<>();
set.add(5);
set.add(4);
set.add(7);
set.add(7);
System.out.println(set); //输出:[4, 5, 7]
}

实际上Set的三个实现HashSet、TreeSet、LinkedHashSet的底层实现都不完全相同,比如
TreeSet使用的是红黑树,TreeSet的输出是排好序的输出,因此如果需要对结果排序,可以使用TreeSet。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void main(String[] args) {
Set<Integer> hashSet=new HashSet<>();
hashSet.add(51);
hashSet.add(4);
hashSet.add(17);
hashSet.add(4);
System.out.println(hashSet); //输出:[17, 51, 4]
Set<Integer> treeSet=new TreeSet<>();
treeSet.add(51);
treeSet.add(4);
treeSet.add(17);
System.out.println(treeSet); //输出:[4, 17, 51]
}

Map

将对象映射到其他对象的能力是一种解决编程的杀手锏。
——摘自《Java编程思想》

Map就是这个杀手锏,键值对的存储结构能够根据键查到对应的值。在《Java编程思想》中,引入了一个验证Random随机性的例子,很好的展示了Map的基本使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static void main(String[] args) {
Random rand=new Random(47);
Map<Integer,Integer> m=new HashMap<>();
for(int i=0;i<1000;i++) {
int r=rand.nextInt(20);
Integer freq=m.get(r);
m.put(r, freq==null?1:freq+1);
}
System.out.println(m);
//输出
//{0=42, 1=44, 2=53, 3=43, 4=44, 5=53, 6=42,
//7=53, 8=46, 9=56, 10=58, 11=55, 12=48, 13=55,
//14=52, 15=50, 16=53, 17=50, 18=51, 19=52}
}

上面的例子中,体现出了Map的一些特点:

  • 如果键不在Map中,get()方法将返回null;否则,将得到相关联的对象
  • Map中的键是唯一的,而值无关紧要

Map可以扩展到多维,你可以用其他的容器(包括Map本身)作为key-value(键值对)

1
2
3
4
5
6
7
8
9
10
11
	public static void main(String[] args) {
Map<String, List<String>> map=new HashMap<>();
List<String> javaList=new ArrayList<>();
javaList.add("Java");
javaList.add("kotlin");
List<String> cList=new ArrayList<>();
cList.add("C++");
cList.add("C#");
map.put("Java", javaList);
map.put("C",cList);
}

Map最常见的实现是HashMap,进一步了解它,请参考我的另一篇博客:深入理解HashMap;

Queue

队列与栈相反,是一种先进先出(FIFO)的数据结构,即从容器的一端添加,另一端取出。

队列常被当作一种可靠的将对象从程序的某个区域传输到另一个区域的途径。队列在并发编程中特别重要。
——摘自《Java编程思想》

LinkedList对Queue的支持已经很不错了,完美完全可以将LinkedList当作Queue使用,需要将LinkedList向上转型为Queue.

1
2
3
4
5
6
7
8
9
10
   public static void main(String[] args) {
Queue<Integer> queue=new LinkedList<>();
queue.offer(34);
queue.offer(23);
queue.offer(26);
System.out.println(queue); //输出:[34, 23, 26]
System.out.println(queue.peek()); //输出:34
System.out.println(queue.poll()); //输出:34
System.out.println(queue); //输出:[23,26]
}

offer()方法用于向队尾添加一个元素,peek()输出队首元素,它们与栈是相通的。
队尾对应链表尾,队头对应链表头。

优先队列

优先队列是队列的一种实现,优先队列保证每次取出的元素是优先级最高的,而不是先进入的。实现优先级高低的方式是对元素进行排序。默认优先队列的优先级保持为对象在队列中的自然顺序。

如果是使用Integer,String等内置的类型,问题会得到简化,因为它们都已经内置了排序规则。Integer数值小的拥有更大的优先级,String则是首字母的ASCII码小的拥有更大的优先级。

1
2
3
4
5
6
7
8
9
10
11
12
public static void main(String[] args) {
PriorityQueue<Integer> queue=new PriorityQueue<>();
queue.offer(51);
queue.offer(6);
queue.offer(91);
System.out.println(queue); //output:[6, 51, 91]
PriorityQueue<String> queue2=new PriorityQueue<>();
queue2.offer("");
queue2.offer("hello");
queue2.offer("fine");
System.out.println(queue2); //output:[, hello, fine]
}

自定义优先级需要在自定义的对象中实现Comparable接口并重写compareTo方法。

使用迭代器遍历容器

当需要遍历容器时,你可以使用简单的for循环或者foreach循环。使用for循环遍历容器的缺点在于:遍历与容器本身的类型互相关联,导致容器不一样,代码也需要改变。

迭代器(Iterator)可以解决这个问题,迭代器是一个对象(同时也是一种设计模式),它的作用是遍历并选择序列中的对象,创建迭代器的代价也很小。

可以通过Collection的 iterator() 方法返回一个迭代器(Iterator只能迭代Collection及其子类),通过 hasNext()和next()方法 判断是否由下一个元素以及获取下一个元素。

可以使用remove()方法将迭代器新近返回的元素删除,这一点比for循环要强:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static void main(String[] args) {
List<String> list=new ArrayList<>();
list.add("abide");
list.add("texture");
Iterator<String> it=list.iterator();
while(it.hasNext()) {
System.out.print(it.next()+" "); //依次输出: abide texture
}
it=list.iterator();
for(int i=0;i<2;i++) {
it.next();
it.remove();
}
System.out.println(list); //输出空表: []
}

如果你使用Arrays.asList()创建一个List;比如
List list= Arrays.asList(“abide”,”texture”);

那么是无法使用迭代器的remove()方法的,实际上,asList返回的是一个ArrayList,但是它并不是java.util.ArrayList,它没有实现删除和增加的方法,但是可以进行修改操作。

迭代器的必要性在于:

能够将遍历序列的操作与序列底层的结构分离。正由于此,我们有时会说:迭代器统一了对容器的访问方式。
——摘自《Java编程思想》

Foreach与迭代器

你可能直到foreach语法可以应用于所有的Collection,也可以用于数组,你可以把foreach理解为一种语法糖。之所以能够使用foreach的原因在于:Collection实现了Iterable接口,Iterable接口也包含iterator()方法返回一个迭代器。
换句话说,你自己随便写一个类实现Iterable接口,就可以使用foreach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ForeachTest {	
public class MyCollection implements Iterable<String> {
List<String> list=new ArrayList<>();
@Override
public Iterator<String> iterator() {
return list.iterator();
}
public void add(String s) {
list.add(s);
}
}
public static void main(String[] args) {
MyCollection coll=new ForeachTest().new MyCollection();
coll.add("hello");
coll.add("world!");
for(String s:coll) {
System.out.print(s+" ");
}//输出:hello world!
}
}

请注意:虽然foreach可以用于数组,但数组并不是Iterable类型的。

Iterator默认只能向后遍历,那么如果我喜欢搞事或者实际需要向前遍历,应该怎么做?
正确的做法是自己再新建一个Iterator,这需要添加一个返回Iterable对象的方法(这样可以继续使用foreach)

具体做法如下(仔细研究reverseIterator()方法,其中嵌套类两层匿名内部类):

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
public class DoubleDirList extends ArrayList<String> {
public Iterable<String> reverseIterator(){
return new Iterable<String>() {
@Override
public Iterator<String> iterator() {
return new Iterator<String>() {
int cur=size()-1;
@Override
public boolean hasNext() {
return cur>-1;
}
@Override
public String next() {
return get(cur--);
}
};
}

};
}

public static void main(String[] args) {
DoubleDirList list=new DoubleDirList();
list.add("hello");
list.add("world");
for(String s:list) {
System.out.print(s+" "); //output:hello world
}
System.out.println();
for(String s:list.reverseIterator()) {
System.out.print(s+" "); //output:world hello
}
}
}

容器的打印

无论是哪种容器,它们的打印相比较数组而言都变得更加简单,不需要任何多余的toString()等方法,并且容器的输出是格式化的,帮助观察容器中的内容。
List会使用[,,,]的形式,Map会使用{=,=,=}的形式。

1
2
3
4
5
6
7
8
public static void main(String[] args) {
List<String> list=Arrays.asList("abc","def","gh");
System.out.println(list); //output:[abc, def, gh]
Map<String, String> map=new HashMap<>();
map.put("v", "success");
map.put("adj", "successful");
System.out.println(map); //output:{v=success, adj=successful}
}

总结

  1. Collection保存单一的对象,Map保存相互关联的对象。
  2. 容器只能存储对象,基本类型无法使用容器。
  3. List是排好序的容器,自动扩充容量。
  4. Queue和栈的行为由LinkedList实现。
  5. Map存储键值对,HashMap的设计专门用于快速访问,TreeMap的键是排序的,所以TreeMap没有HashMap快。
  6. Set不能存储重复元素,HashSet提供了最快的查找速度。
  7. 尽管在示例中使用了Stack,但是如今请不要使用过时的Vector,HashTable和Stack。
smartpig wechat
扫一扫关注微信公众号
0%