常用集合剖析

Posted by 阿呆 on 2019-02-01

前言

在实现方法时,选择不同的数据结构会导致其实现风格以及性能存在很大的差异

Java集合框架

Java最初的版本只为常用的数据结构提供了很少的一组类:Vector、Stack、Hashtable、BitSet与 Enumeration接口,其中Enumeration接口提供了一种用于访问任意容器中各个元素的抽象机制。

随着Java SE1.2的问世,设计人员感到推出一组功能完善的数据结构的时机了。

将集合的接口{interface}与实现{implementation}分离

来看一个例子,队列是如何将接口与实现分离的

1
2
3
4
5
public interface Queue<E>{
void add(E e);
E remove();
int size();
}

何为分离:这个接口并没有说明队列是如何实现的,队列通常有两种实现方式:

一种是用循环数组

一种是使用链表

如何优雅地使用集合:

接口与实现分离有个很大地好处,就是集合地使用将会更灵活:

1
2
Queue<Customer> expressLane = new CirclarArrayQueue(100);
expressLane.add(new Customer("Harry"));

当在程序中使用队列时,一旦构建了集合就不需要知道究竟使用了哪种实现。因此,只有在构建集合对象的时候,使用具体的类才有意义,可以使用接口类型存放集合的引用

利用这种方式,一旦改变了想法,可以轻松地使用另外一种不同地实现,只需要在程序的一个地方做出修改,即调用构造器的地方。

既然功能一样,为什么要选择另一种实现呢?

这可能是由于效率或者一些具体的限制等方面的原因。或者说,比如一个保存文件提取文件的类,你可以在内部实现保存地址的差异化。又比如说循环数组实现的队列,对元素的个数是有要求的,当元素较多,最好采用链表方式来实现。

Collection接口

在Java类库中,集合的基本接口是 Collection 接口,这个接口有两个基本方法:

1
2
3
4
5
public interface Collection<E>{
boolean add(E element);
Iterator<E> iterator();
... // 还有几个方法,将在稍后介绍
}

几个需要注意的地方:

1.add方法的返回值:代表添加元素是否确实改变了集合,是就返回true,没有则返回false,例如试图向set中添加一个元素e,但是set中已经存在,那么则返回fasle

2.iterator方法用于返回一个实现了 Iterator 接口的对象,可以使用这个迭代器对象依次访问集合中的元素,下一节讨论迭代器。

迭代器

Iterator接口包含四个方法:

1
2
3
4
5
6
public interface Iterator<E>{
E next();
boolean hasNext();
void remove();
default void forEachRemaining(Consumer<? super E>action);
}

通过反复调用next()方法可以遍历集合中的每个元素,但是,如果到达了集合的末尾,next()方法将抛出一个NoSuchElementException。

因此,需要在调用next()之前,调用hasNext()方法。如果要查看集合中的所有元素,就请求一个迭代器,并在hasNext返回true时反复地调用 next() 方法,例如:

1
2
3
4
5
6
Collection<String> c = ...;
Iterator<String> iter = c.iterator();
while(iter.hasNext()){
String element = iter.next();
// do sth with element
}

for…each循环

用 for…each 循环可以更简练地表达上述操作

1
2
3
4
for(String element:c){
// do sth with element
}
// 编译器简单地将 for..each 循环翻译为带有迭代器的循环

元素被访问的顺序取决于集合类型:

如果对ArrayList进行迭代,迭代器将从索引0开始,每迭代一次,索引值加一

然而访问 HashSet 中的元素,则顺序随机

Java迭代器的特点

Java迭代器的查找操作与位置变更是紧密相连的,查找一个元素的唯一方法是调用 next,而在执行查找操作的同时,迭代器的位置随之向前移动

因此,应该将Java迭代器认为是位于两个元素之间,当调用next时,迭代器就越过下一个元素,并返回刚刚越过的那个元素的引用

Iterator的remove方法将会删除上次调用next方法时返回的元素,例如下面是删除字符串集合中第一个元素的方法:

1
2
3
Iterator<String> it = c.iterator();
it.next();
it.remove();

泛型实用方法

由于Collection 与 Iterator 都是泛型接口,可以编写操作任何集合类型的实用方法。例如:

1
2
3
4
5
6
7
public static <E> boolean contains(Collection<E> c,Object obj){
for(E element:c){
if(element.equals(obj))
return true;
}
return false;
}

Collections接口声明了很多有用的方法,所有的实现类都必须实现这些方法(按照常用程度):

1
2
3
4
5
6
7
8
9
10
11
12
int size();
boolean isEmpty();
boolean contains(Object obj);
boolean containsAll(Collection<?> c);
boolean equals(Object other);
boolean addAll(Collection<? extends E> from);
boolean remove(Object obj);
boolean removeAll(Collection<?> c);
void clear();
boolean retainAll(Collection<?> c);
Object[] toArray();
<T> T[] toArray(T[] arrayToFill)