Java高级程序设计

集合与流

Collections

A collection — sometimes called a container — is simply an object that groups multiple elements into a single unit.

Collections are used to store, retrieve, manipulate, and communicate aggregate data.

https://docs.oracle.com/javase/tutorial/collections/index.html

Arrays vs. Collections

Arrays Collection
Fixed in size Growable in nature
With respect to memory, not recommended to use. With respect to memory, recommended to use.
With respect to performance, recommended to use. With respect to performance ,not recommended to use.
Hold only homogeneous data types elements (hold both object and primitive) Hold both homogeneous and and heterogeneous elements (only object types but primitive)

Collections Framework

A collections framework, for example C++ Standard Template Library (STL), is a unified architecture for representing and manipulating collections. All collections frameworks contain the following:

  • Interfaces: These are abstract data types that represent collections.
  • Implementations: These are the concrete implementations of the collection interfaces.
  • Algorithms: These are the methods that perform useful computations, such as searching and sorting.

Interfaces

The core collection interfaces encapsulate different types of collections. These interfaces allow collections to be manipulated independently of the details of their representation. Core collection interfaces form a hierarchy.

width:700px

Collection

public interface Collection<E> extends Iterable<E>

The root interface in the collection hierarchy. A collection represents a group of objects, known as its elements. Some collections allow duplicate elements and others do not. Some are ordered and others unordered.

This interface is typically used to pass collections around and manipulate them where maximum generality is desired.

https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html

Traversing Collections

There are three ways to traverse collections:

  1. using aggregate operations (talk later)
  2. with the for-each construct
  3. by using Iterators

for-each Construct

The for-each construct allows you to concisely traverse a collection or array using a for loop — see The for Statement. The following code uses the for-each construct to print out each element of a collection on a separate line.

for (Object o : collection)
    System.out.println(o);

Iterable

public interface Iterable<T>

Implementing this interface allows an object to be the target of the "for-each loop" statement

https://docs.oracle.com/javase/8/docs/api/java/lang/Iterable.html

Iterators

An Iterator is an object that enables you to traverse through a collection and to remove elements from the collection selectively, if desired. You get an Iterator for a collection by calling its iterator method. The following is the Iterator interface.

public interface Iterator<E> {
    boolean hasNext();
    E next();
    void remove(); //optional
}

https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.html

Collection Interface Bulk Operations

Bulk operations perform an operation on an entire Collection.

  • containsAll
  • addAll
  • removeAll
  • retainAll
  • clear

Collection Interface Array Operations

The toArray methods are provided as a bridge between collections and older APIs that expect arrays on input. The array operations allow the contents of a Collection to be translated into an array. The simple form with no arguments creates a new array of Object. The more complex form allows the caller to provide an array or to choose the runtime type of the output array.

Object[] a = c.toArray();

The List Interface

A List is an ordered Collection (sometimes called a sequence). Lists may contain duplicate elements. In addition to the operations inherited from Collection, the List interface includes operations of positional access, search, iteration and range-view.

The Java platform contains two general-purpose List implementations. ArrayList, which is usually the better-performing implementation, and LinkedList which offers better performance under certain circumstances.

ArrayList vs. LinkedList

width:800px

Performance diffrence?

The Set Interface

A Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction. The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited. Two Set instances are equal if they contain the same elements.

The Java platform contains three general-purpose Set implementations: HashSet, TreeSet and LinkedHashSet.

HashSet

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable

This class implements the Set interface, backed by a hash table (actually a HashMap instance). It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.

This class offers constant time performance for the basic operations (add, remove, contains and size).

https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html

The Map Interface

A Map is an object that maps keys to values. A map cannot contain duplicate keys: Each key can map to at most one value. It models the mathematical function abstraction. The Map interface includes methods for basic operations (such as put, get, remove, containsKey, containsValue, size, and empty), bulk operations (such as putAll and clear), and collection views (such as keySet, entrySet, and values).

The Java platform contains three general-purpose Map implementations: HashMap, TreeMap, and LinkedHashMap.

https://docs.oracle.com/javase/8/docs/api/java/util/Map.html

HashMap

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

Hash table based implementation of the Map interface. This implementation permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

https://docs.oracle.com/javase/8/docs/api/java/util/HashMap.html

HashMap Internal

Two parameters affect its performance: initial capacity and load factor. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed.

TreeMap

public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable

A Red-Black tree based NavigableMap implementation.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html

TreeMap Internal


width:500px

LinkedHashMap

Hash table and linked list implementation of the Map interface, with predictable iteration order.

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.

Back to The Set Interface

A Set is a Collection that cannot contain duplicate elements. It models the mathematical set abstraction. The Set interface contains only methods inherited from Collection and adds the restriction that duplicate elements are prohibited. Two Set instances are equal if they contain the same elements.

The Java platform contains three general-purpose Set implementations: HashSet, TreeSet and LinkedHashSet.

The Queue Interface

A collection designed for holding elements prior to processing. Besides basic Collection operations, queues provide additional insertion, extraction, and inspection operations.

https://docs.oracle.com/javase/8/docs/api/java/util/Queue.html

The Deque Interface

A linear collection that supports element insertion and removal at both ends. The name deque is short for "double ended queue" and is usually pronounced "deck". Most Deque implementations place no fixed limits on the number of elements they may contain, but this interface supports capacity-restricted deques as well as those with no fixed size limit.

https://docs.oracle.com/javase/8/docs/api/java/util/Deque.html

Summary of Interfaces

  • Collection interface
    • The Set interface does not allow duplicate elements
    • The List interface provides for an ordered collection
    • The Queue interface enables additional insertion, extraction, and inspection operations
    • The Deque interface enables operations at both the ends
  • Map's subinterface, SortedMap, maintains its key-value pairs in ascending order or in an order specified by a Comparator.

Back to Traversing Collections

There are three ways to traverse collections:

  1. using aggregate operations (talk now)
  2. with the for-each construct
  3. by using Iterators

Aggregate Operations

In JDK 8 and later, the preferred method of iterating over a collection is to obtain a stream and perform aggregate operations on it.

Aggregate operations are often used in conjunction with lambda expressions to make programming more expressive.

myShapesCollection.stream()
.filter(e -> e.getColor() == Color.RED)
.forEach(e -> System.out.println(e.getName()));

https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html#stream--

Stream

public interface Stream<T> extends BaseStream<T,Stream<T>>

A sequence of elements supporting sequential and parallel aggregate operations.

https://docs.oracle.com/javase/8/docs/api/java/util/stream/Stream.html

Parallel Stream

Likewise, you could easily request a parallel stream, which might make sense if the collection is large enough and your computer has enough cores:

myShapesCollection.parallelStream()
.filter(e -> e.getColor() == Color.RED)
.forEach(e -> System.out.println(e.getName()));

Java 8 Stream API

https://www.baeldung.com/java-8-streams

https://stackify.com/streams-guide-java-8/

Reactive Programming

In computing, reactive programming is a declarative programming paradigm concerned with data streams and the propagation of change. With this paradigm, it's possible to express static (e.g., arrays) or dynamic (e.g., event emitters) data streams with ease, and also communicate that an inferred dependency within the associated execution model exists, which facilitates the automatic propagation of the changed data flow.

https://en.wikipedia.org/wiki/Reactive_programming

http://www.reactive-streams.org

Java 9 Reactive Streams

public final class Flow extends Object

Interrelated interfaces and static methods for establishing flow-controlled components in which Publishers produce items consumed by one or more Subscribers, each managed by a Subscription.
These interfaces correspond to the reactive-streams specification. Communication relies on a simple form of flow control that can be used to avoid resource management problems that may otherwise occur in "push" based systems.

https://docs.oracle.com/javase/9/docs/api/java/util/concurrent/Flow.html

Java 9 Reactive Streams Tutorial

https://www.baeldung.com/java-9-reactive-streams