coding……
但行好事 莫问前程

Java编程拾遗『容器概述』

在大学时,我们肯定都学过一门叫数据结构的课,里面详细的介绍了链表、栈、队列、散列、树、图等数据结构的概念及其实现。接下来的几篇文章将详细介绍一下Java API对常见数据结构的实现原理及应用,也就是Java API中的集合类(集合框架)。首先看一下Java集合框架的总体概况,如下:

总体而言,基本上可以分为两类,表示集合的Collection和表示K-V的Map。可以看到,所有的集合都间接实现了Collection接口,所有的Map都实现了Map接口。

1. 集合接口

1.1 Java集合设计思想

从上面集合框架的图中也可以发现一个规律,所有的具体集合类都会实现一个或多个接口,这其实就是Java API设计中,接口(interfaces)与实现(implementations)分离的思想。下面通过队列(queue)分离设计的例子,来解释一下这种实现思想的细节及优势。

我们都知道,队列是一种“先进先出”的数据结构,并且入队操作只能在队尾,出队操作只能在队头。所以队列接口应该提供方法,在队列尾部添加元素,在队列头部删除元素,并且可以查看队列中元素的个数,如下所示:

public interface Queue<E> {

    void add(E element);

    E remove();

    int size();
}

接口定义中,并没有说明队列是如何实现的。队列通常有两种实现方式:一种是使用循环数组,另一种是使用链表,如下所示:

 所以对于Queue接口可以有一下两种实现方式:

public class CircularArrayQueue<E> implements Queue<E> {

	public CircularArrayQueue(int capacity) {……}
	public void add(E element) {……}
	public E remove() {……}
	public int size() {……}

	private E[] elements;
	private int head;
	private int tail;
}
public class LinkedListQueue<E> implements Queue<E> {
	public LinkedListQueue() {……}
	public void add(E element) {……}
	public E remove() {……}
	public int size() {……}

	private Link head;
	private Link tail;
}

注意:这里讲的CircularArrayQueue和LinkedListQueue并不是Java API中真是存在的类,这里只是为了讲述一下Java集合的设计思想——接口和实现分离。实际上在Java API中,如果要使用一个循环数组队列,就可以使用ArrayDequeue,如果需要使一个链表队列,就可以使用LinkedList,这个类实现了Queue接口。

有如上两种队列的定义,在使用队列时,根据泛型类的继承规则,可以将实现类对象赋值给相同泛型类型的接口变量引用,如下:

Queue<Integer> queue = new CircularArrayQueue<>(100);
queue.add(1);

如果一旦改变了想法,就可以轻松的使用另一种不同的实现,只要对程序的一个地方做出修改,即修改调用构造器的地方就可以。如果觉得LinkedListQueue是个更好的选择,只需要将代码改为:

Queue<Integer> queue = new LinkedListQueue<>(100);
queue.add(1);

具体选用哪种实现,要根据具体需求而定。接口本身并不能说明哪种实现效率高,哪种实现效率低。循环数组队列一般情况下比链表队列效率高,但是循环数组是一个有界集合,容量有限。如果程序中要收集的对象没有上限,最好使用链表队列。

另外,仔细观察上面的集合框架图,也可以发现一个规律,一个具体的类一般会继承一个Abstract打头的抽象类,实现一个(多个)接口。这些Abstract打头的抽象类,其实也实现了相同的接口,并对接口中的一部分方法进行了实现。这些抽象类就是为类库实现者更方便的实现接口而设计的,比如如果我们要实现一个自定义队列,那么通过继承AbstractQueue类同时实现Queue接口的方式,要比直接实现Queue接口的方式要方便的多,因为一些通用方法已经在AbstractQueue中实现了。

1.2 Collection接口

所有的具体集合类都直接或间接实现了Collection接口,Collection接口定义了集合的一些通用方法,如下:

S.N. 方法 说明
1 boolean add(E e) 向集合中添加元素,如果调用改变了集合返回true
2 boolean addAll(Collection<? extends E> c) 将集合c中所有元素添加到集合中,如果调用改变了集合返回true
3 void clear() 清空集合
4 boolean contains(Object o) 判断集合中是否存在一个与o相等的元素,存在返回true
5 boolean containsAll(Collection<?> c) 判断集合是否包含集合c中的所有元素,包含返回true
6 boolean equals(Object o) equals方法
7 int hashCode() hashCode
8 boolean isEmpty() 判断集合是否为空,为空返回true
9 Iterator<E> iterator() 返回集合迭代器
10 default Stream<E> stream() Java 8新方法,返回集合流,用于支持集合函数式编程
11 default Stream<E> parallelStream() Java 8新方法,返回集合并行流
12 boolean remove(Object o) 删除集合中等于o的元素,如果有元素被删除,返回true
13 boolean removeAll(Collection<?> c) 从集合中删除另一个集合c中的所有元素,如果调用改变了集合返回true
14 default boolean removeIf(Predicate<? super E> filter) Java 8新方法,如果集合中的元素满足Predicate,则删除元素,如果调用改变了集合返回true
15 default void replaceAll(UnaryOperator<E> operator) Java 8新方法,根据UnaryOperator规则,将集合中每一个元素映射为另一个元素
16 boolean retainAll(Collection<?> c) 从集合中保留另一个集合c中的所有元素,如果调用改变了集合返回true
17 int size() 返回集合中元素的个数
18 default Spliterator<E> spliterator() Java 8新方法,返回集合的Spliterator迭代器
19 Object[] toArray() 集合转数组
20 <T> T[] toArray(T[] a) 集合转数组

上面讲过,Java集合框架中,一个接口往往会对应一个抽象类,实现一些接口中的通用方法。Collection接口也不例外,在Java API中存在一个叫AbstractCollection的抽象类,提供一些基于迭代器Iterator的contains、remove、removeAll等方法的实现,这样就能让实现者更容易的实现Collection接口。如下:

public abstract class AbstractCollection<E> implements Collection<E> {

	public abstract Iterator<E> iterator();

	//……
	public boolean contains(Object o) {
        Iterator<E> it = iterator();
        if (o==null) {
            while (it.hasNext())
                if (it.next()==null)
                    return true;
        } else {
            while (it.hasNext())
                if (o.equals(it.next()))
                    return true;
        }
        return false;
    }
    //……
}

1.3 迭代器Iterator

Java API中迭代器接口定义如下:

public interface Iterator<E> {

	boolean hasNext();

	E next();

	default void remove() {
        throw new UnsupportedOperationException("remove");
    }

    default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }
}

1.3.1 遍历元素

通过反复调用next方法,可以逐个访问集合中的每一个元素。但是到达集合的末尾,next方法将抛出一个noSuchElementException异常。因此在调用next之前要调用hasNext方法,判断是否存在下一个元素。如果要遍历一个集合中的所有元素,就可以请求一个迭代器,并在hasNext返回true时反复地调用next方法,如下:

Collection<String> c = …… ;
Iterator<String> iterator = c.iterator();
while(c.hasNext()) {
	
	String element = iterator.next();
	//处理element
}

Java 5之后,这种循环可以采用一种更优雅的方式进行遍历——for each循环。Java编译器会简单地将“for each”循环翻译为带有迭代器的循环。如下:

for (String element : c) {
	//处理element
}

1.3.2 删除元素

Iterator接口的remove方法用于删除上次调用next方法时返回的元素。通过如下方式,可以删除集合中第一个元素:

Iterator<String> iterator = c.iterator();
iterator.next();
iterator.remove();

一定要注意的是,remove方法的调用对next方法具有依赖性。如果调用remove方法之前没有调用next方法将是不合法的,会抛出一个IllegalStateException异常。比如要删除两个连续的相邻元素,不能直接这样调用:

iterator.remove();
iterator.remove(); //remove前未调用next方法,异常

1.3.3 forEachRemaining

forEachRemaining是Java 8中新引入的default方法,方法的参数Consumer用于逐个消费集合中的元素,如下:

List<String> list = Lists.newArrayList("this", "is", "list");
list.iterator().forEachRemaining(ele -> System.out.println("consume :" + ele));

2. Map

Java API中Map用于保存具有映射关系(K-V)的数据,Map的key不允许重复。HashMap、LinkedHashMap、TreeMap都实现了Map接口,下面来看一下Map接口的方法定义:

S.N. 方法 说明
1 void clear() 清除Map中所有的KV映射
2 default V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) Java 8新方法,如果key在Map中不存在,则根据Function规则计算key对应的value值,
并进行put操作(前提计算得到的value值也不为null)
3 default V computeIfPresent(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction)
Java 8新方法,如果key在Map中存在,则根据BiFunction规则通过key和对应的value
计算newValue,如果newValue为null,则删除key对应的键值对,否则替换key对应的value值
4 default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) Java 8新方法,相当于上述两个方法的综合,根据BiFunction,通过key和对应的value
计算newValue,如果newValue为null,会删除对应KV映射,否则会插入或替换原KV映射
5 boolean containsKey(Object key) 判断Map中是否存在key键
6 boolean containsValue(Object value) 判断Map中是否存在value值
7 Set<Map.Entry<K, V>> entrySet() 将Map所有的键值对转换为Set集合
8 boolean equals(Object o) equals方法
9 default void forEach(BiConsumer<? super K, ? super V> action) Java 8新方法,遍历Map,通过BiConsumer处理Map中每一个键值对的key、value
10 V get(Object key) 获取Map中key对应的value
11 default V getOrDefault(Object key, V defaultValue) Java 8新方法,获取Map中key对应的value,如果key不存在,则返回defaultValue
12 int hashCode() hashCode方法
13 boolean isEmpty() 判断Map是否为空
14 Set<K> keySet() 将Map中所有的key转化为Set集合
15 default V merge(K key, V value,
BiFunction<? super V, ? super V, ? extends V> remappingFunction)
如果key在Map中不存在或者对应的值为null,则给其一个对应的非null值value。否则根据
BiFunction规则通过oldValue和value计算一个newValue,替换或删除(newValue为null)原
键值对
16 V put(K key, V value); 为Map添加一个键值对
17 void putAll(Map<? extends K, ? extends V> m) 将另一个Map的所有键值对添加到该Map中
18 default V putIfAbsent(K key, V value) Java 8新方法,如果Map中key不存在,则添加一个key-value键值对
19 V remove(Object key) 从Map中移除key对应的键值对
20 default boolean remove(Object key, Object value) Java8新方法,删除key-value键值对
21 default V replace(K key, V value) Java8新方法,将Map中key对应的值替换为value
22 default boolean replace(K key, V oldValue, V newValue) Java8新方法,将Map中key-oldValue键值对的value值替换为newValue
23 default void replaceAll(BiFunction<? super K, ? super V, ? extends V> function) Java8新方法,将Map中所有的键值对的value,替换为根据BiFunction规则通过key-value
得到的新值
24 int size() 返回Map中EntrySet的数目
25 Collection<V> values() 返回Map中所有value组成的集合

 

赞(0) 打赏
Zhuoli's Blog » Java编程拾遗『容器概述』
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

zhuoli's blog

联系我关于我

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏