对于 Netty ByteBuf 的零拷贝(Zero Copy) 的理解

根据 Wiki 对 Zero-copy 的定义:

“Zero-copy” describes computer operations in which the CPU does not perform the task of copying data from one memory area to another. This is frequently used to save CPU cycles and memory bandwidth when transmitting a file over a network.

即所谓的 Zero-copy, 就是在操作数据时, 不需要将数据 buffer 从一个内存区域拷贝到另一个内存区域. 因为少了一次内存的拷贝, 因此 CPU 的效率就得到的提升.

在 OS 层面上的 Zero-copy 通常指避免在 用户态(User-space)内核态(Kernel-space) 之间来回拷贝数据. 例如 Linux 提供的 mmap 系统调用, 它可以将一段用户空间内存映射到内核空间, 当映射成功后, 用户对这段内存区域的修改可以直接反映到内核空间; 同样地, 内核空间对这段区域的修改也直接反映用户空间. 正因为有这样的映射关系, 我们就不需要在 用户态(User-space)内核态(Kernel-space) 之间拷贝数据, 提高了数据传输的效率.

而需要注意的是, Netty 中的 Zero-copy 与上面我们所提到到 OS 层面上的 Zero-copy 不太一样, Netty的 Zero-coyp 完全是在用户态(Java 层面)的, 它的 Zero-copy 的更多的是偏向于 优化数据操作 这样的概念.

Netty 的 Zero-copy 体现在如下几个个方面:

  • Netty 提供了 CompositeByteBuf 类, 它可以将多个 ByteBuf 合并为一个逻辑上的 ByteBuf, 避免了各个 ByteBuf 之间的拷贝.
  • 通过 wrap 操作, 我们可以将 byte[] 数组、ByteBuf、ByteBuffer等包装成一个 Netty ByteBuf 对象, 进而避免了拷贝操作.
  • ByteBuf 支持 slice 操作, 因此可以将 ByteBuf 分解为多个共享同一个存储区域的 ByteBuf, 避免了内存的拷贝.
  • 通过 FileRegion 包装的FileChannel.tranferTo 实现文件传输, 可以直接将文件缓冲区的数据发送到目标 Channel, 避免了传统通过循环 write 方式导致的内存拷贝问题.

下面我们就来简单了解一下这几种常见的零拷贝操作.

通过 CompositeByteBuf 实现零拷贝

假设我们有一份协议数据, 它由头部和消息体组成, 而头部和消息体是分别存放在两个 ByteBuf 中的, 即:

ByteBuf header = ...
ByteBuf body = ...

我们在代码处理中, 通常希望将 header 和 body 合并为一个 ByteBuf, 方便处理, 那么通常的做法是:

ByteBuf allBuf = Unpooled.buffer(header.readableBytes() + body.readableBytes());
allBuf.writeBytes(header);
allBuf.writeBytes(body);

可以看到, 我们将 header 和 body 都拷贝到了新的 allBuf 中了, 这无形中增加了两次额外的数据拷贝操作了.

那么有没有更加高效优雅的方式实现相同的目的呢? 我们来看一下 CompositeByteBuf 是如何实现这样的需求的吧.

ByteBuf header = ...
ByteBuf body = ...

CompositeByteBuf compositeByteBuf = Unpooled.compositeBuffer();
compositeByteBuf.addComponents(true, header, body);

上面代码中, 我们定义了一个 CompositeByteBuf 对象, 然后调用

public CompositeByteBuf addComponents(boolean increaseWriterIndex, ByteBuf... buffers) {
...
}

方法将 headerbody 合并为一个逻辑上的 ByteBuf, 即:

不过需要注意的是, 虽然看起来 CompositeByteBuf 是由两个 ByteBuf 组合而成的, 不过在 CompositeByteBuf 内部, 这两个 ByteBuf 都是单独存在的, CompositeByteBuf 只是逻辑上是一个整体.

上面 CompositeByteBuf 代码还以一个地方值得注意的是, 我们调用 addComponents(boolean increaseWriterIndex, ByteBuf... buffers) 来添加两个 ByteBuf, 其中第一个参数是 true, 表示当添加新的 ByteBuf 时, 自动递增 CompositeByteBuf 的 writeIndex.
如果我们调用的是

compositeByteBuf.addComponents(header, body);

那么其实 compositeByteBufwriteIndex 仍然是0, 因此此时我们就不可能从 compositeByteBuf 中读取到数据, 这一点希望大家要特别注意.

除了上面直接使用 CompositeByteBuf 类外, 我们还可以使用 Unpooled.wrappedBuffer 方法, 它底层封装了 CompositeByteBuf 操作, 因此使用起来更加方便:

ByteBuf header = ...
ByteBuf body = ...

ByteBuf allByteBuf = Unpooled.wrappedBuffer(header, body);

通过 wrap 操作实现零拷贝

例如我们有一个 byte 数组, 我们希望将它转换为一个 ByteBuf 对象, 以便于后续的操作, 那么传统的做法是将此 byte 数组拷贝到 ByteBuf 中, 即:

byte[] bytes = ...
ByteBuf byteBuf = Unpooled.buffer();
byteBuf.writeBytes(bytes);

显然这样的方式也是有一个额外的拷贝操作的, 我们可以使用 Unpooled 的相关方法, 包装这个 byte 数组, 生成一个新的 ByteBuf 实例, 而不需要进行拷贝操作. 上面的代码可以改为:

byte[] bytes = ...
ByteBuf byteBuf = Unpooled.wrappedBuffer(bytes);

可以看到, 我们通过 Unpooled.wrappedBuffer 方法来将 bytes 包装成为一个 UnpooledHeapByteBuf 对象, 而在包装的过程中, 是不会有拷贝操作的. 即最后我们生成的生成的 ByteBuf 对象是和 bytes 数组共用了同一个存储空间, 对 bytes 的修改也会反映到 ByteBuf 对象中.

Unpooled 工具类还提供了很多重载的 wrappedBuffer 方法:

public static ByteBuf wrappedBuffer(byte[] array)
public static ByteBuf wrappedBuffer(byte[] array, int offset, int length)

public static ByteBuf wrappedBuffer(ByteBuffer buffer)
public static ByteBuf wrappedBuffer(ByteBuf buffer)

public static ByteBuf wrappedBuffer(byte[]... arrays)
public static ByteBuf wrappedBuffer(ByteBuf... buffers)
public static ByteBuf wrappedBuffer(ByteBuffer... buffers)

public static ByteBuf wrappedBuffer(int maxNumComponents, byte[]... arrays)
public static ByteBuf wrappedBuffer(int maxNumComponents, ByteBuf... buffers)
public static ByteBuf wrappedBuffer(int maxNumComponents, ByteBuffer... buffers)

这些方法可以将一个或多个 buffer 包装为一个 ByteBuf 对象, 从而避免了拷贝操作.

通过 slice 操作实现零拷贝

slice 操作和 wrap 操作刚好相反, Unpooled.wrappedBuffer 可以将多个 ByteBuf 合并为一个, 而 slice 操作可以将一个 ByteBuf 切片 为多个共享一个存储区域的 ByteBuf 对象.
ByteBuf 提供了两个 slice 操作方法:

public ByteBuf slice();
public ByteBuf slice(int index, int length);

不带参数的 slice 方法等同于 buf.slice(buf.readerIndex(), buf.readableBytes()) 调用, 即返回 buf 中可读部分的切片. 而 slice(int index, int length) 方法相对就比较灵活了, 我们可以设置不同的参数来获取到 buf 的不同区域的切片.

下面的例子展示了 ByteBuf.slice 方法的简单用法:

ByteBuf byteBuf = ...
ByteBuf header = byteBuf.slice(0, 5);
ByteBuf body = byteBuf.slice(5, 10);

slice 方法产生 header 和 body 的过程是没有拷贝操作的, header 和 body 对象在内部其实是共享了 byteBuf 存储空间的不同部分而已. 即:

通过 FileRegion 实现零拷贝

Netty 中使用 FileRegion 实现文件传输的零拷贝, 不过在底层 FileRegion 是依赖于 Java NIO FileChannel.transfer 的零拷贝功能.

首先我们从最基础的 Java IO 开始吧. 假设我们希望实现一个文件拷贝的功能, 那么使用传统的方式, 我们有如下实现:

public static void copyFile(String srcFile, String destFile) throws Exception {
    byte[] temp = new byte[1024];
    FileInputStream in = new FileInputStream(srcFile);
    FileOutputStream out = new FileOutputStream(destFile);
    int length;
    while ((length = in.read(temp)) != -1) {
        out.write(temp, 0, length);
    }

    in.close();
    out.close();
}

上面是一个典型的读写二进制文件的代码实现了. 不用我说, 大家肯定都知道, 上面的代码中不断中源文件中读取定长数据到 temp 数组中, 然后再将 temp 中的内容写入目的文件, 这样的拷贝操作对于小文件倒是没有太大的影响, 但是如果我们需要拷贝大文件时, 频繁的内存拷贝操作就消耗大量的系统资源了.
下面我们来看一下使用 Java NIO 的 FileChannel 是如何实现零拷贝的:

public static void copyFileWithFileChannel(String srcFileName, String destFileName) throws Exception {
    RandomAccessFile srcFile = new RandomAccessFile(srcFileName, "r");
    FileChannel srcFileChannel = srcFile.getChannel();

    RandomAccessFile destFile = new RandomAccessFile(destFileName, "rw");
    FileChannel destFileChannel = destFile.getChannel();

    long position = 0;
    long count = srcFileChannel.size();

    srcFileChannel.transferTo(position, count, destFileChannel);
}

可以看到, 使用了 FileChannel 后, 我们就可以直接将源文件的内容直接拷贝(transferTo) 到目的文件中, 而不需要额外借助一个临时 buffer, 避免了不必要的内存操作.

有了上面的一些理论知识, 我们来看一下在 Netty 中是怎么使用 FileRegion 来实现零拷贝传输一个文件的:

@Override
public void channelRead0(ChannelHandlerContext ctx, String msg) throws Exception {
    RandomAccessFile raf = null;
    long length = -1;
    try {
        // 1. 通过 RandomAccessFile 打开一个文件.
        raf = new RandomAccessFile(msg, "r");
        length = raf.length();
    } catch (Exception e) {
        ctx.writeAndFlush("ERR: " + e.getClass().getSimpleName() + ": " + e.getMessage() + '\n');
        return;
    } finally {
        if (length < 0 && raf != null) {
            raf.close();
        }
    }

    ctx.write("OK: " + raf.length() + '\n');
    if (ctx.pipeline().get(SslHandler.class) == null) {
        // SSL not enabled - can use zero-copy file transfer.
        // 2. 调用 raf.getChannel() 获取一个 FileChannel.
        // 3. 将 FileChannel 封装成一个 DefaultFileRegion
        ctx.write(new DefaultFileRegion(raf.getChannel(), 0, length));
    } else {
        // SSL enabled - cannot use zero-copy file transfer.
        ctx.write(new ChunkedFile(raf));
    }
    ctx.writeAndFlush("\n");
}

上面的代码是 Netty 的一个例子, 其源码在 netty/example/src/main/java/io/netty/example/file/FileServerHandler.java
可以看到, 第一步是通过 RandomAccessFile 打开一个文件, 然后 Netty 使用了 DefaultFileRegion 来封装一个 FileChannel 即:

new DefaultFileRegion(raf.getChannel(), 0, length)

当有了 FileRegion 后, 我们就可以直接通过它将文件的内容直接写入 Channel 中, 而不需要像传统的做法: 拷贝文件内容到临时 buffer, 然后再将 buffer 写入 Channel. 通过这样的零拷贝操作, 无疑对传输大文件很有帮助.

使用 Spring Webflux 进行异步非阻塞编程

Spring webflux,是在将要发布的Spring 5和Spring boot 2中提供的,结合非阻塞IO,Reactive 风格编程的异步非阻塞开发框架。

之前有一篇文章介绍了Vert.x,初次之外Java中还有Ratpack等以异步非阻塞编程为目标的项目。然而就目前来看,Spring Webflux将会是API设计最良好,最方便使用的一个。

Spring Webflux 介绍

Spring Webflux 是一个基于事件驱动的非阻塞实现,底层可以使用:

  1. Netty。
  2. 支持Servlet3.1 Non-Blocking Servlet标准的Web容器。具体的有Tomcat,Undertow,Jetty等。

默认使用的是Netty。毕竟Servlet整个生态都是针对阻塞IO的实现的,Async Servlet和Non-Blocking Servlet就是在Servlet标准中打的奇怪的格格不入的补丁。在性能上,Netty也有着不小的优势。

Spring Webflux 使用的Reactive System实现是Reactor,但是也支持使用RxJava,还有Java8 CompletableFuture。Reactor和RxJava2.0的实现接口基本一致,然而Reactor是基于Java8实现的,可以利用Java8中的许多既有实现(比如CompletableFuture,Stream等)。Reactor中最常使用的是Publisher的两个实现,Mono和Flux,Mono表示0或1,对应于RxJava中的MayBe,Completable,和Single;Flux表示1+数量,对应于RxJava中的Observable。

Spring Webflux 还提供了一个Netty实现的非阻塞WebClient,用来做Http 请求。

Spring Webflux 实例

我们这里完成一个和之前Vert.x一样功能的简单程序,使用HTTP请求网易新闻头条内容,然后抽取其中的文章标题,并以Json格式返回给客户端。项目使用Spring Boot开发。

@RestController
public class TopLinesHandler {

    @Resource
    private ObjectMapper mapper;

    @GetMapping("/top_lines")
    public Mono<Object> handleGetUserById() {
        return getTopLines().map(this::extractTitles);
    }

    private Mono<String> getTopLines() {
        WebClient webClient = WebClient.create("http://c.m.163.com");
        return webClient.get().uri("/nc/article/headline/T1348647853363/0-20.html")
                .accept(MediaType.APPLICATION_JSON)
                .exchange()
                .flatMap(resp -> resp.bodyToMono(String.class));
    }

    private List<String> extractTitles(String jsonStr) {
        JsonNode jsonNode;
        try {
            jsonNode = mapper.readTree(jsonStr);
        } catch (IOException e) {
            throw new UncheckedIOException(e);
        }
        JsonNode articles = jsonNode.get("T1348647853363");
        List<String> list = new ArrayList<>(articles.size());
        for (int i = 0; i < articles.size(); i++) {
            JsonNode article = articles.get(i);
            String title = article.get("title").textValue();
            list.add(title);
        }
        return list;
    }
}

可以看到,在webflux中,也可以使用SpringMVC中定义的注解,这大大简化了路由,response处理等工作。

然后我们需要启动一个Spring Webflux应用程序:

@SpringBootApplication
public class WebfluxApplication {

    public static void main(String[] args) {
        new SpringApplicationBuilder()
                .bannerMode(Banner.Mode.OFF)
                .sources(WebfluxApplication.class)
                .run(args);
    }
}

还是熟悉的配方,还是熟悉的味道。

当然,对于JDBC这种只有同步阻塞实现的,还是需要wrap到额外的线程池,以避免阻塞EventLoop,目前Spring Webflux还没有对这些做封装,需要的话只能自己动手了。

现在已经可以使用start.spring.io/方便的创建自己的Spring Webflux项目,注意SpringBoot要选2.0版本,Dependencies里加上Webflux。

Java多线程编程:Callable、Future和FutureTask浅析(多线程编程之四)

Java多线程:Callable、Future和FutureTask浅析(多线程编程之四)

通过前面几篇的学习,我们知道创建线程的方式有两种,一种是实现Runnable接口,另一种是继承Thread,但是这两种方式都有个缺点,那就是在任务执行完成之后无法获取返回结果,那如果我们想要获取返回结果该如何实现呢?还记上一篇Executor框架结构中提到的Callable接口和Future接口吗?,是的,从JAVA SE 5.0开始引入了Callable和Future,通过它们构建的线程,在任务执行完成后就可以获取执行结果,今天我们就来聊聊线程创建的第三种方式,那就是实现Callable接口。

1.Callable<V>接口
我们先回顾一下java.lang.Runnable接口,就声明了run(),其返回值为void,当然就无法获取结果了。
  1. public interface Runnable {
  2.     public abstract void run();
  3. }

而Callable的接口定义如下

  1. public interface Callable<V> {
  2.       V   call()   throws Exception;
  3. }

该接口声明了一个名称为call()的方法,同时这个方法可以有返回值V,也可以抛出异常。嗯,对该接口我们先了解这么多就行,下面我们来说明如何使用,前篇文章我们说过,无论是Runnable接口的实现类还是Callable接口的实现类,都可以被ThreadPoolExecutor或ScheduledThreadPoolExecutor执行,ThreadPoolExecutor或ScheduledThreadPoolExecutor都实现了ExcutorService接口,而因此Callable需要和Executor框架中的ExcutorService结合使用,我们先看看ExecutorService提供的方法:

  1. <T> Future<T> submit(Callable<T> task);
  2. <T> Future<T> submit(Runnable task, T result);
  3. Future<?> submit(Runnable task);
第一个方法:submit提交一个实现Callable接口的任务,并且返回封装了异步计算结果的Future。
第二个方法:submit提交一个实现Runnable接口的任务,并且指定了在调用Future的get方法时返回的result对象。
第三个方法:submit提交一个实现Runnable接口的任务,并且返回封装了异步计算结果的Future。
因此我们只要创建好我们的线程对象(实现Callable接口或者Runnable接口),然后通过上面3个方法提交给线程池去执行即可。还有点要注意的是,除了我们自己实现Callable对象外,我们还可以使用工厂类Executors来把一个Runnable对象包装成Callable对象。Executors工厂类提供的方法如下:
  1. public static Callable<Object> callable(Runnable task)
  2. public static <T> Callable<T> callable(Runnable task, T result)
2.Future<V>接口
Future<V>接口是用来获取异步计算结果的,说白了就是对具体的Runnable或者Callable对象任务执行的结果进行获取(get()),取消(cancel()),判断是否完成等操作。我们看看Future接口的源码:
  1. public interface Future<V> {
  2.     boolean cancel(boolean mayInterruptIfRunning);
  3.     boolean isCancelled();
  4.     boolean isDone();
  5.     V get() throws InterruptedException, ExecutionException;
  6.     V get(long timeout, TimeUnit unit) throws InterruptedException, ExecutionException, TimeoutException;
  7. }
方法解析:
V get() :获取异步执行的结果,如果没有结果可用,此方法会阻塞直到异步计算完成。
V get(Long timeout , TimeUnit unit) :获取异步执行结果,如果没有结果可用,此方法会阻塞,但是会有时间限制,如果阻塞时间超过设定的timeout时间,该方法将抛出异常。
boolean isDone() :如果任务执行结束,无论是正常结束或是中途取消还是发生异常,都返回true。
boolean isCanceller() :如果任务完成前被取消,则返回true。
boolean cancel(boolean mayInterruptRunning) :如果任务还没开始,执行cancel(…)方法将返回false;如果任务已经启动,执行cancel(true)方法将以中断执行此任务线程的方式来试图停止任务,如果停止成功,返回true;当任务已经启动,执行cancel(false)方法将不会对正在执行的任务线程产生影响(让线程正常执行到完成),此时返回false;当任务已经完成,执行cancel(…)方法将返回false。mayInterruptRunning参数表示是否中断执行中的线程。
通过方法分析我们也知道实际上Future提供了3种功能:(1)能够中断执行中的任务(2)判断任务是否执行完成(3)获取任务执行完成后额结果。
但是我们必须明白Future只是一个接口,我们无法直接创建对象,因此就需要其实现类FutureTask登场啦。
3.FutureTask类
我们先来看看FutureTask的实现
  1. public class FutureTask<V> implements RunnableFuture<V> {

FutureTask类实现了RunnableFuture接口,我们看一下RunnableFuture接口的实现:

  1. public interface RunnableFuture<V> extends Runnable, Future<V> {
  2.     void run();
  3. }
分析:FutureTask除了实现了Future接口外还实现了Runnable接口,因此FutureTask也可以直接提交给Executor执行。 当然也可以调用线程直接执行(FutureTask.run())。接下来我们根据FutureTask.run()的执行时机来分析其所处的3种状态:
(1)未启动,FutureTask.run()方法还没有被执行之前,FutureTask处于未启动状态,当创建一个FutureTask,而且没有执行FutureTask.run()方法前,这个FutureTask也处于未启动状态。
(2)已启动,FutureTask.run()被执行的过程中,FutureTask处于已启动状态。
(3)已完成,FutureTask.run()方法执行完正常结束,或者被取消或者抛出异常而结束,FutureTask都处于完成状态。


下面我们再来看看FutureTask的方法执行示意图(方法和Future接口基本是一样的,这里就不过多描述了)

分析:
(1)当FutureTask处于未启动或已启动状态时,如果此时我们执行FutureTask.get()方法将导致调用线程阻塞;当FutureTask处于已完成状态时,执行FutureTask.get()方法将导致调用线程立即返回结果或者抛出异常。
(2)当FutureTask处于未启动状态时,执行FutureTask.cancel()方法将导致此任务永远不会执行。
当FutureTask处于已启动状态时,执行cancel(true)方法将以中断执行此任务线程的方式来试图停止任务,如果任务取消成功,cancel(…)返回true;但如果执行cancel(false)方法将不会对正在执行的任务线程产生影响(让线程正常执行到完成),此时cancel(…)返回false。
当任务已经完成,执行cancel(…)方法将返回false。
最后我们给出FutureTask的两种构造函数:
  1. public FutureTask(Callable<V> callable) {
  2. }
  3. public FutureTask(Runnable runnable, V result) {
  4. }
3.Callable<V>/Future<V>/FutureTask的使用
通过上面的介绍,我们对Callable,Future,FutureTask都有了比较清晰的了解了,那么它们到底有什么用呢?我们前面说过通过这样的方式去创建线程的话,最大的好处就是能够返回结果,加入有这样的场景,我们现在需要计算一个数据,而这个数据的计算比较耗时,而我们后面的程序也要用到这个数据结果,那么这个时Callable岂不是最好的选择?我们可以开设一个线程去执行计算,而主线程继续做其他事,而后面需要使用到这个数据时,我们再使用Future获取不就可以了吗?下面我们就来编写一个这样的实例
3.1 使用Callable+Future获取执行结果
Callable实现类如下:
  1. package com.zejian.Executor;
  2. import java.util.concurrent.Callable;
  3. public class CallableDemo implements Callable<Integer> {
  4.     private int sum;
  5.     @Override
  6.     public Integer call() throws Exception {
  7.         System.out.println(“Callable子线程开始计算啦!”);
  8.         Thread.sleep(2000);
  9.         for(int i=0 ;i<5000;i++){
  10.             sum=sum+i;
  11.         }
  12.         System.out.println(“Callable子线程计算结束!”);
  13.         return sum;
  14.     }
  15. }

Callable执行测试类如下:

  1. package com.zejian.Executor;
  2. import java.util.concurrent.ExecutorService;
  3. import java.util.concurrent.Executors;
  4. import java.util.concurrent.Future;
  5. public class CallableTest {
  6.     public static void main(String[] args) {
  7.         //创建线程池
  8.         ExecutorService es = Executors.newSingleThreadExecutor();
  9.         //创建Callable对象任务
  10.         CallableDemo calTask=new CallableDemo();
  11.         //提交任务并获取执行结果
  12.         Future<Integer> future =es.submit(calTask);
  13.         //关闭线程池
  14.         es.shutdown();
  15.         try {
  16.             Thread.sleep(2000);
  17.         System.out.println(“主线程在执行其他任务”);
  18.         if(future.get()!=null){
  19.             //输出获取到的结果
  20.             System.out.println(“future.get()–>”+future.get());
  21.         }else{
  22.             //输出获取到的结果
  23.             System.out.println(“future.get()未获取到结果”);
  24.         }
  25.         } catch (Exception e) {
  26.             e.printStackTrace();
  27.         }
  28.         System.out.println(“主线程在执行完成”);
  29.     }
  30. }
执行结果:

Callable子线程开始计算啦!
主线程在执行其他任务
Callable子线程计算结束!
future.get()–>12497500
主线程在执行完成
3.2 使用Callable+FutureTask获取执行结果
  1. package com.zejian.Executor;
  2. import java.util.concurrent.ExecutorService;
  3. import java.util.concurrent.Executors;
  4. import java.util.concurrent.Future;
  5. import java.util.concurrent.FutureTask;
  6. public class CallableTest {
  7.     public static void main(String[] args) {
  8. //      //创建线程池
  9. //      ExecutorService es = Executors.newSingleThreadExecutor();
  10. //      //创建Callable对象任务
  11. //      CallableDemo calTask=new CallableDemo();
  12. //      //提交任务并获取执行结果
  13. //      Future<Integer> future =es.submit(calTask);
  14. //      //关闭线程池
  15. //      es.shutdown();
  16.         //创建线程池
  17.         ExecutorService es = Executors.newSingleThreadExecutor();
  18.         //创建Callable对象任务
  19.         CallableDemo calTask=new CallableDemo();
  20.         //创建FutureTask
  21.         FutureTask<Integer> futureTask=new FutureTask<>(calTask);
  22.         //执行任务
  23.         es.submit(futureTask);
  24.         //关闭线程池
  25.         es.shutdown();
  26.         try {
  27.             Thread.sleep(2000);
  28.         System.out.println(“主线程在执行其他任务”);
  29.         if(futureTask.get()!=null){
  30.             //输出获取到的结果
  31.             System.out.println(“futureTask.get()–>”+futureTask.get());
  32.         }else{
  33.             //输出获取到的结果
  34.             System.out.println(“futureTask.get()未获取到结果”);
  35.         }
  36.         } catch (Exception e) {
  37.             e.printStackTrace();
  38.         }
  39.         System.out.println(“主线程在执行完成”);
  40.     }
  41. }
执行结果:
Callable子线程开始计算啦!
主线程在执行其他任务
Callable子线程计算结束!
futureTask.get()–>12497500
主线程在执行完成
主要参考资料:
java并发编程的艺术

java/android线程池-Executor框架之ThreadPoolExcutor/ScheduledThreadPoolExecutor浅析(多线程编程之三)

无论是在java还是在android中其实使用到的线程池都基本是一样的,因此本篇我们将来认识一下线程池Executor框架(相关知识点结合了并发编程艺术书以及Android开发艺术探索而总结),下面是本篇的主要知识点:

1.Executor框架浅析
首先我们得明白一个 问题,为什么需要线程池?在java中,使用线程来执行异步任务时,线程的创建和销毁需要一定的开销,如果我们为每一个任务创建一个新的线程来执行的话,那么这些线程的创建与销毁将消耗大量的计算资源。同时为每一个任务创建一个新线程来执行,这样的方式可能会使处于高负荷状态的应用最终崩溃。所以线程池的出现为解决这个问题带来曙光。我们将在线程池中创建若干条线程,当有任务需要执行时就从该线程池中获取一条线程来执行任务,如果一时间任务过多,超出线程池的线程数量,那么后面的线程任务就进入一个等待队列进行等待,直到线程池有线程处于空闲时才从等待队列获取要执行的任务进行处理,以此循环…..这样就大大减少了线程创建和销毁的开销,也会缓解我们的应用处于超负荷时的情况。
1.1Executor框架的两级调度模型
在java线程启动时会创建一个本地操作系统线程,当该java线程终止时,这个操作系统线程也会被回收。而每一个java线程都会被一对一映射为本地操作系统的线程,操作系统会调度所有的线程并将它们分别给可用的CPU。而所谓的映射方式是这样实现的,在上层,java多线程程序通过把应用分为若干个任务,然后使用用户级的调度器(Executor框架)将这些任务映射为固定数量的线程;在底层,操作系统内核将这些线程映射到硬件处理器上。这样种两级调度模型如下图所示:

从图中我们可以看出,应用程序通过Executor框架控制上层的调度,而下层的调度由操作系统内核控制,下层的调度不受应用程序的控制。
1.2 Executor框架的结构
Executor框架的结构主要包括3个部分
1.任务:包括被执行任务需要实现的接口:Runnable接口或Callable接口
2.任务的执行:包括任务执行机制的核心接口Executor,以及继承自Executor的EexcutorService接口。Exrcutor有两个关键类实现了ExecutorService接口(ThreadPoolExecutor和ScheduledThreadPoolExecutor)。
3.异步计算的结果:包括接口Future和实现Future接口的FutureTask类(这个我们放在下一篇文章说明)
下面我们通过一个UML图来认识一下这些类间的关系:

Extecutor是一个接口,它是Executor框架的基础,它将任务的提交与任务的执行分离开来。
ThreadPoolExecutor是线程池的核心实现类,用来执行被提交的任务。
ScheduledThreadPoolExecutor是一个实现类,可以在给定的延迟后运行命令,或者定期执行命令。ScheduledThreadPoolExecutor比Timer更灵活,功能更强大。
Future接口和实现Future接口的FutureTask类,代表异步计算的结果。
Runnable接口和Callable接口的实现类,都可以被ThreadPoolExecutor或者ScheduledThreadPoolExecutor执行。区别就是Runnable无法返回执行结果,而Callable可以返回执行结果。
下面我们通过一张图来理解它们间的执行关系:

分析说明:
主线程首先创建实现Runnable或Callable接口的任务对象,工具类Executors可以把一个Runnable对象封装为一个Callable对象,使用如下两种方式:
Executors.callable(Runnable task)或者Executors.callable(Runnable task,Object resule)。
然后可以把Runnable对象直接提交给ExecutorService执行,方法为ExecutorService.execute(Runnable command);或者也可以把Runnable对象或者Callable对象提交给ExecutorService执行,方法为ExecutorService.submit(Runnable task)或ExecutorService.submit(Callable<T> task)。这里需要注意的是如果执行ExecutorService.submit(…),ExecutorService将返回一个实现Future接口的对象(其实就是FutureTask)。当然由于FutureTask实现了Runnable接口,我们也可以直接创建FutureTask,然后提交给ExecutorService执行。到此Executor框架的主要体系结构我们都介绍完了,我们对此有了大概了解后,下面我们就重点聊聊两个主要的线程池实现类。
2.ThreadPoolExecutor浅析
ThreadPoolExecutor是线程的真正实现,通常使用工厂类Executors来创建,但它的构造方法提供了一系列参数来配置线程池,下面我们就先介绍ThreadPoolExecutor的构造方法中各个参数的含义。
  1. public ThreadPoolExecutor(int corePoolSize,
  2.                               int maximumPoolSize,
  3.                               long keepAliveTime,
  4.                               TimeUnit unit,
  5.                               BlockingQueue<Runnable> workQueue,
  6.                               ThreadFactory threadFactory) {
  7.         this(corePoolSize, maximumPoolSize, keepAliveTime, unit, workQueue,
  8.              threadFactory, defaultHandler);
  9.     }
corePoolSize:线程池的核心线程数,默认情况下,核心线程数会一直在线程池中存活,即使它们处理闲置状态。如果将ThreadPoolExecutor的allowCoreThreadTimeOut属性设置为true,那么闲置的核心线程在等待新任务到来时会执行超时策略,这个时间间隔由keepAliveTime所指定,当等待时间超过keepAliveTime所指定的时长后,核心线程就会被终止。
maximumPoolSize:线程池所能容纳的最大线程数量,当活动线程数到达这个数值后,后续的新任务将会被阻塞。
keepAliveTime:非核心线程闲置时的超时时长,超过这个时长,非核心线程就会被回收。当ThreadPoolExecutor的allowCoreThreadTimeOut属性设置为true时,keepAliveTime同样会作用于核心线程。
unit:用于指定keepAliveTime参数的时间单位,这是一个枚举,常用的有TimeUnit.MILLISECONDS(毫秒),TimeUnit.SECONDS(秒)以及TimeUnit.MINUTES(分钟)等。
workQueue:线程池中的任务队列,通过线程池的execute方法提交Runnable对象会存储在这个队列中。
threadFactory:线程工厂,为线程池提供创建新线程的功能。ThreadFactory是一个接口,它只有一个方法:Thread newThread(Runnable r)。
除了上面的参数外还有个不常用的参数,RejectExecutionHandler,这个参数表示当ThreadPoolExecutor已经关闭或者ThreadPoolExecutor已经饱和时(达到了最大线程池大小而且工作队列已经满),execute方法将会调用Handler的rejectExecution方法来通知调用者,默认情况 下是抛出一个RejectExecutionException异常。了解完相关构造函数的参数,我们再来看看ThreadPoolExecutor执行任务时的大致规则:
(1)如果线程池的数量还未达到核心线程的数量,那么会直接启动一个核心线程来执行任务
(2)如果线程池中的线程数量已经达到或者超出核心线程的数量,那么任务会被插入到任务队列中排队等待执行。
(3)如果在步骤(2)中无法将任务插入到任务队列中,这往往是由于任务队列已满,这个时候如果线程数量未达到线程池规定的最大值,那么会立刻启动一个非核心线程来执行任务。
(4)如果在步骤(3)中线程数量已经达到线程池规定的最大值,那么就会拒绝执行此任务,ThreadPoolExecutor会调用RejectExecutionHandler的rejectExecution方法来通知调用者。
到此ThreadPoolExecutor的详细配置了解完了,ThreadPoolExecutor的执行规则也了解完了,那么接下来我们就来介绍3种常见的线程池,它们都直接或者间接地通过配置ThreadPoolExecutor来实现自己的功能特性,这个3种线程池分别是FixedThreadPool,CachedThreadPool,ScheduledThreadPool以及SingleThreadExecutor。
2.1FixedThreadPool
 FixedThreadPool模式会使用一个优先固定数目的线程来处理若干数目的任务。规定数目的线程处理所有任务,一旦有线程处理完了任务就会被用来处理新的任务(如果有的话)。FixedThreadPool模式下最多的线程数目是一定的。创建FixedThreadPool对象代码如下:
  1. ExecutorService fixedThreadPool=Executors.newFixedThreadPool(5);

我们来看看FixedThreadPool创建方法源码:

  1. public static ExecutorService newFixedThreadPool(int nThreads) {
  2.         return new ThreadPoolExecutor(nThreads, nThreads,
  3.                                       0L, TimeUnit.MILLISECONDS,
  4.                                       new LinkedBlockingQueue<Runnable>());
  5.     }

FixedThreadPool的corePoolSize和maximumPoolSize参数都被设置为nThreads。当线程池中的线程数量大于corePoolSize时,keepAliveTime为非核心空闲线程等待新任务的最长时间,超过这个时间后非核心线程将被终止,这里keepAliveTime设置为0L,就说明非核心线程会立即被终止。事实上这里也没有非核心线程创建,因为核心线程数和最大线程数都一样的。下面我们来看看FixedThreadPool的execute()方法的运行流程:

分析:
(1)如果当前运行线程数少corePoolSize,则创建一个新的线程来执行任务。
(2)如果当前线程池的运行线程数等于corePoolSize,那么后面提交的任务将加入LinkedBlockingQueue。
(3)线程在执行完图中的1后,会在循环中反复从LinkedBlockingQueue获取任务来执行。
这里还有点要说明的是FixedThreadPool使用的是无界队列LinkedBlockingQueue作为线程池的工作队列(队列容量为Integer.MAX_VALUE)。使用该队列作为工作队列会对线程池产生如下影响
(1)当前线程池中的线程数量达到corePoolSize后,新的任务将在无界队列中等待。
(2)由于我们使用的是无界队列,所以参数maximumPoolSize和keepAliveTime无效。
(3)由于使用无界队列,运行中的FixedThreadPool不会拒绝任务(当然此时是未执行shutdown和shutdownNow方法),所以不会去调用RejectExecutionHandler的rejectExecution方法抛出异常。
下面我们给出案例,该案例来自java编程思想一书:
  1. public class LiftOff implements Runnable{
  2.     protected int countDown = 10//Default   
  3.     private static int taskCount = 0;
  4.     private final int id = taskCount++;
  5.     public LiftOff() {}
  6.     public LiftOff(int countDown) {
  7.         this.countDown = countDown;
  8.     }
  9.     public String status() {
  10.         return “#” + id + “(“ +
  11.             (countDown > 0 ? countDown : “LiftOff!”) + “) “;
  12.     }
  13.     @Override
  14.     public void run() {
  15.         while(countDown– > 0) {
  16.             System.out.print(status());
  17.             Thread.yield();
  18.         }
  19.     }
  20. }

声明一个Runnable对象,使用FixedThreadPool执行任务如下:

  1. public class FixedThreadPool {
  2.     public static void main(String[] args) {
  3.         //三个线程来执行五个任务   
  4.         ExecutorService exec = Executors.newFixedThreadPool(3);
  5.         for(int i = 0; i < 5; i++) {
  6.             exec.execute(new LiftOff());
  7.         }
  8.         exec.shutdown();
  9.     }
  10. }
2.2 CachedThreadPool
CachedThreadPool首先会按照需要创建足够多的线程来执行任务(Task)。随着程序执行的过程,有的线程执行完了任务,可以被重新循环使用时,才不再创建新的线程来执行任务。创建方式:
  1. ExecutorService cachedThreadPool=Executors.newCachedThreadPool();
  1. public static ExecutorService newCachedThreadPool() {
  2.         return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
  3.                                       60L, TimeUnit.SECONDS,
  4.                                       new SynchronousQueue<Runnable>());
  5.     }

从该静态方法,我们可以看到CachedThreadPool的corePoolSize被设置为0,而maximumPoolSize被设置Integer.MAX_VALUE,即maximumPoolSize是无界的,而keepAliveTime被设置为60L,单位为妙。也就是空闲线程等待时间最长为60秒,超过该时间将会被终止。而且在这里CachedThreadPool使用的是没有容量的SynchronousQueue作为线程池的工作队列,但其maximumPoolSize是无界的,也就是意味着如果主线程提交任务的速度高于maximumPoolSize中线程处理任务的速度时CachedThreadPool将会不断的创建新的线程,在极端情况下,CachedThreadPool会因为创建过多线程而耗尽CPU和内存资源。CachedThreadPool的execute()方法的运行流程:

分析:
(1)首先执行SynchronousQueue.offer(Runnable task),添加一个任务。如果当前CachedThreadPool中有空闲线程正在执行SynchronousQueue.poll(keepAliveTime,TimeUnit.NANOSECONDS),其中NANOSECONDS是毫微秒即十亿分之一秒(就是微秒/1000),那么主线程执行offer操作与空闲线程执行poll操作配对成功,主线程把任务交给空闲线程执行,execute()方法执行完成,否则进入第(2)步。
(2)当CachedThreadPool初始线程数为空时,或者当前没有空闲线程,将没有线程去执行SynchronousQueue.poll(keepAliveTime,TimeUnit.NANOSECONDS)。这样的情况下,步骤(1)将会失败,此时CachedThreadPool会创建一个新的线程来执行任务,execute()方法执行完成。
(3)在步骤(2)中创建的新线程将任务执行完成后,会执行SynchronousQueue.poll(keepAliveTime,TimeUnit.NANOSECONDS),这个poll操作会让空闲线程最多在SynchronousQueue中等待60秒,如果60秒内主线程提交了一个新任务,那么这个空闲线程将会执行主线程提交的新任务,否则,这个空闲线程将被终止。由于空闲60秒的空闲线程会被终止,因此长时间保持空闲的 CachedThreadPool是不会使用任何资源的。
根据前面的分析我们知道SynchronousQueue是一个没有容量的阻塞队列(其实个人认为是相对应时间而已的没有容量,因为时间到空闲线程就会被移除)。每个插入操作必须等到一个线程与之对应。CachedThreadPool使用SynchronousQueue,把主线程的任务传递给空闲线程执行。流程如下:


CachedThreadPool使用的案例代码如下:

  1. public class CachedThreadPool {
  2.     public static void main(String[] args) {
  3.         ExecutorService exec = Executors.newCachedThreadPool();
  4.         for(int i = 0; i < 10; i++) {
  5.             exec.execute(new LiftOff());
  6.         }
  7.         exec.shutdown();
  8.     }
  9. }
2.3 SingleThreadExecutor

SingleThreadExecutor模式只会创建一个线程。它和FixedThreadPool比较类似,不过线程数是一个。如果多个任务被提交给SingleThreadExecutor的话,那么这些任务会被保存在一个队列中,并且会按照任务提交的顺序,一个先执行完成再执行另外一个线程。SingleThreadExecutor模式可以保证只有一个任务会被执行。这种特点可以被用来处理共享资源的问题而不需要考虑同步的问题。

创建方式:
  1. ExecutorService singleThreadExecutor=Executors.newSingleThreadExecutor();
  1. public static ExecutorService newSingleThreadExecutor() {
  2.         return new FinalizableDelegatedExecutorService
  3.             (new ThreadPoolExecutor(11,
  4.                                     0L, TimeUnit.MILLISECONDS,
  5.                                     new LinkedBlockingQueue<Runnable>()));
  6.     }

从静态方法可以看出SingleThreadExecutor的corePoolSize和maximumPoolSize被设置为1,其他参数则与FixedThreadPool相同。SingleThreadExecutor使用的工作队列也是无界队列LinkedBlockingQueue。由于SingleThreadExecutor采用无界队列的对线程池的影响与FixedThreadPool一样,这里就不过多描述了。同样的我们先来看看其运行流程:

分析:
(1)如果当前线程数少于corePoolSize即线程池中没有线程运行,则创建一个新的线程来执行任务。
(2)在线程池的线程数量等于corePoolSize时,将任务加入到LinkedBlockingQueue。
(3)线程执行完成(1)中的任务后,会在一个无限循环中反复从LinkedBlockingQueue获取任务来执行。
SingleThreadExecutor使用的案例代码如下:
  1. public class SingleThreadExecutor {
  2.     public static void main(String[] args) {
  3.         ExecutorService exec = Executors.newSingleThreadExecutor();
  4.         for (int i = 0; i < 2; i++) {
  5.             exec.execute(new LiftOff());
  6.         }
  7.     }
  8. }
2.4 各自的适用场景
FixedThreadPool:适用于为了满足资源管理需求,而需要限制当前线程的数量的应用场景,它适用于负载比较重的服务器。
SingleThreadExecutor:适用于需要保证执行顺序地执行各个任务;并且在任意时间点,不会有多个线程是活动的场景。
CachedThreadPool:大小无界的线程池,适用于执行很多的短期异步任务的小程序,或者负载较轻的服务器。
3.ScheduledThreadPoolExecutor浅析
3.1 ScheduledThreadPoolExecutor执行机制分析
ScheduledThreadPoolExecutor继承自ThreadPoolExecutor。它主要用来在给定的延迟之后执行任务,或者定期执行任务。ScheduledThreadPoolExecutor的功能与Timer类似,但比Timer更强大,更灵活,Timer对应的是单个后台线程,而ScheduledThreadPoolExecutor可以在构造函数中指定多个对应的后台线程数。接下来我们先来了解一下ScheduledThreadPoolExecutor的运行机制:

分析:DelayQueue是一个无界队列,所以ThreadPoolExecutor的maximumPoolSize在ScheduledThreadPoolExecutor中无意义。ScheduledThreadPoolExecutor的执行主要分为以下两个部分
(1)当调用ScheduledThreadPoolExecutor的scheduleAtFixedRate()方法或者scheduleWithFixedDelay()方法时,会向ScheduledThreadPoolExecutor的DelayQueue添加一个实现了RunnableScheduledFuture接口的ScheduleFutureTask。
(2)线程池中的线程从DelayQueue中获取ScheduleFutureTask,然后执行任务。
3.2 如何创建ScheduledThreadPoolExecutor?
ScheduledThreadPoolExecutor通常使用工厂类Executors来创建,Executors可以创建两种类型的ScheduledThreadPoolExecutor,如下:
(1)ScheduledThreadPoolExecutor:可以执行并行任务也就是多条线程同时执行。
(2)SingleThreadScheduledExecutor:可以执行单条线程。
创建ScheduledThreadPoolExecutor的方法构造如下:
  1. public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize)
  2. public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize, ThreadFactory threadFactory)

创建SingleThreadScheduledExecutor的方法构造如下:

  1. public static ScheduledExecutorService newSingleThreadScheduledExecutor()
  2. public static ScheduledExecutorService newSingleThreadScheduledExecutor(ThreadFactory threadFactory)

创建实例对象代码如下:

  1. ScheduledExecutorService scheduledThreadPoolExecutor=Executors.newScheduledThreadPool(5);
  1. ScheduledExecutorService singleThreadScheduledExecutor=Executors.newSingleThreadScheduledExecutor();
3.3 ScheduledThreadPoolExecutor和SingleThreadScheduledExecutor的适用场景
ScheduledThreadPoolExecutor:适用于多个后台线程执行周期性任务,同时为了满足资源管理的需求而需要限制后台线程数量的应用场景。
SingleThreadScheduledExecutor:适用于需要单个后台线程执行周期任务,同时需要保证任务顺序执行的应用场景。
3.4 ScheduledThreadPoolExecutor使用案例
我们创建一个Runnable的对象,然后使用ScheduledThreadPoolExecutor的Scheduled()来执行延迟任务,输出执行时间即可:
我们先来介绍一下该类延迟执行的方法:
  1. public ScheduledFuture<?> schedule(Runnable command,long delay, TimeUnit unit);
参数解析:
command:就是一个实现Runnable接口的类
delay:延迟多久后执行。
unit:用于指定keepAliveTime参数的时间单位,这是一个枚举,常用的有TimeUnit.MILLISECONDS(毫秒),TimeUnit.SECONDS(秒)以及TimeUnit.MINUTES(分钟)等。
这里要注意这个方法会返回ScheduledFuture实例,可以用于获取线程状态信息和延迟时间。
  1. package com.zejian.Executor;
  2. import java.text.ParsePosition;
  3. import java.text.SimpleDateFormat;
  4. import java.util.Date;
  5. /**
  6.  * @author zejian
  7.  * @time 2016年3月14日 下午9:10:41
  8.  * @decrition 创建一个工作线程继承Runnable
  9.  */
  10. public class WorkerThread implements Runnable{
  11.     @Override
  12.     public void run() {
  13.          System.out.println(Thread.currentThread().getName()+” Start. Time = “+getNowDate());
  14.          threadSleep();
  15.          System.out.println(Thread.currentThread().getName()+” End. Time = “+getNowDate());
  16.     }
  17.     /**
  18.      * 睡3秒
  19.      */
  20.     public void threadSleep(){
  21.         try {
  22.             Thread.sleep(3000);
  23.         } catch (InterruptedException e) {
  24.             // TODO Auto-generated catch block
  25.             e.printStackTrace();
  26.         }
  27.     }
  28.      /**
  29.       * 获取现在时间
  30.       * 
  31.       * @return 返回时间类型 yyyy-MM-dd HH:mm:ss
  32.       */
  33.     public static String getNowDate() {
  34.           Date currentTime = new Date();
  35.           SimpleDateFormat formatter;
  36.             formatter = new SimpleDateFormat (“yyyy-MM-dd HH:mm:ss”);
  37.             String ctime = formatter.format(currentTime);
  38.           return ctime;
  39.          }
  40. }

执行类如下:

  1. package com.zejian.Executor;
  2. import java.text.ParsePosition;
  3. import java.text.SimpleDateFormat;
  4. import java.util.Date;
  5. import java.util.concurrent.Executors;
  6. import java.util.concurrent.ScheduledExecutorService;
  7. import java.util.concurrent.TimeUnit;
  8. public class ScheduledThreadPoolTest {
  9.     public static void main(String[] args) {
  10.         ScheduledExecutorService scheduledThreadPool = Executors.newScheduledThreadPool(5);
  11.          try {
  12.         //schedule to run after sometime
  13.         System.out.println(“Current Time = “+getNowDate());
  14.         for(int i=0; i<3; i++){
  15.             Thread.sleep(1000);
  16.             WorkerThread worker = new WorkerThread();
  17.             //延迟10秒后执行
  18.             scheduledThreadPool.schedule(worker, 10, TimeUnit.SECONDS);
  19.         }
  20.             Thread.sleep(3000);
  21.         } catch (InterruptedException e) {
  22.             e.printStackTrace();
  23.         }
  24.         scheduledThreadPool.shutdown();
  25.         while(!scheduledThreadPool.isTerminated()){
  26.             //wait for all tasks to finish
  27.         }
  28.         System.out.println(“Finished all threads”);
  29.     }
  30.      /**
  31.       * 获取现在时间
  32.       * 
  33.       * @return 返回时间类型 yyyy-MM-dd HH:mm:ss
  34.       */
  35.      public static String getNowDate() {
  36.       Date currentTime = new Date();
  37.       SimpleDateFormat formatter;
  38.         formatter = new SimpleDateFormat (“yyyy-MM-dd HH:mm:ss”);
  39.         String ctime = formatter.format(currentTime);
  40.       return ctime;
  41.      }
  42. }

运行输入执行结果:


线程任务确实在10秒延迟后才开始执行。这就是schedule()方法的使用。下面我们再介绍2个可用于周期性执行任务的方法。

public ScheduledFuture<?> scheduleAtFixedRate(Runnable command,long initialDelay,long period,TimeUnit unit)

scheduleAtFixedRate方法的作用是预定在初始的延迟结束后,周期性地执行给定的任务,周期长度为period,其中initialDelay为初始延迟。

(按照固定的时间来执行,即:到点执行)

  1. public ScheduledFuture<?> scheduleWithFixedDelay(Runnable command,long initialDelay,long delay,TimeUnit unit);
scheduleWithFixedDelay方法的作用是预定在初始的延迟结束后周期性地执行给定任务,在一次调用完成和下一次调用开始之间有长度为delay的延迟,其中initialDelay为初始延迟(简单说是是等上一个任务结束后,在等固定的时间,然后执行。即:执行完上一个任务后再执行)。
下面给出实现案例代码参考:
  1. package com.zejian.Executor;
  2. import java.util.Date;
  3. import java.util.concurrent.ScheduledThreadPoolExecutor;
  4. import java.util.concurrent.TimeUnit;
  5. public class ScheduledTask {
  6.     public ScheduledThreadPoolExecutor se = new ScheduledThreadPoolExecutor(5);
  7.     public static void main(String[] args) {
  8.         new ScheduledTask();
  9.     }
  10.     public void fixedPeriodSchedule() {
  11.         // 设定可以循环执行的runnable,初始延迟为0,这里设置的任务的间隔为5秒
  12.         for(int i=0;i<5;i++){
  13.             se.scheduleAtFixedRate(new FixedSchedule(), 05, TimeUnit.SECONDS);
  14.         }
  15.     }
  16.     public ScheduledTask() {
  17.         fixedPeriodSchedule();
  18.     }
  19.     class FixedSchedule implements Runnable {
  20.         public void run() {
  21.             System.out.println(“当前线程:”+Thread.currentThread().getName()+”  当前时间:”+new Date(System.currentTimeMillis()));
  22.         }
  23.     }
  24. }
运行结果(后来补贴的结果,所以时间是2017)
  1. 当前线程:pool-1-thread-5  当前时间:Tue Aug 08 09:43:18 CST 2017
  2. 当前线程:pool-1-thread-4  当前时间:Tue Aug 08 09:43:18 CST 2017
  3. 当前线程:pool-1-thread-3  当前时间:Tue Aug 08 09:43:18 CST 2017
  4. 当前线程:pool-1-thread-1  当前时间:Tue Aug 08 09:43:18 CST 2017
  5. 当前线程:pool-1-thread-2  当前时间:Tue Aug 08 09:43:18 CST 2017
  6. 当前线程:pool-1-thread-1  当前时间:Tue Aug 08 09:43:23 CST 2017
  7. 当前线程:pool-1-thread-4  当前时间:Tue Aug 08 09:43:23 CST 2017
  8. 当前线程:pool-1-thread-3  当前时间:Tue Aug 08 09:43:23 CST 2017
  9. 当前线程:pool-1-thread-5  当前时间:Tue Aug 08 09:43:23 CST 2017
  10. 当前线程:pool-1-thread-2  当前时间:Tue Aug 08 09:43:23 CST 2017
  11. 当前线程:pool-1-thread-1  当前时间:Tue Aug 08 09:43:28 CST 2017
  12. 当前线程:pool-1-thread-4  当前时间:Tue Aug 08 09:43:28 CST 2017
  13. 当前线程:pool-1-thread-5  当前时间:Tue Aug 08 09:43:28 CST 2017
  14. 当前线程:pool-1-thread-3  当前时间:Tue Aug 08 09:43:28 CST 2017
  15. 当前线程:pool-1-thread-1  当前时间:Tue Aug 08 09:43:28 CST 2017
至于scheduleWithFixedDelay方法,大家就把代码稍微修改一下执行试试就行,这里就不重复了。而SingleThreadScheduledExecutor的使用的方法基本是类似,只不过是单线程罢了,这里也不再描述了。好了,今天就到这吧。

主要参考书籍:

java核心技术卷1

android开发艺术探索

java并发编程的艺术

java多线程同步以及线程间通信详解&消费者生产者模式&死锁&Thread.join()(多线程编程之二)

本篇我们将讨论以下知识点:

1.线程同步问题的产生

什么是线程同步问题,我们先来看一段卖票系统的代码,然后再分析这个问题:
  1. public class Ticket implements Runnable
  2. {
  3.     //当前拥有的票数
  4.     private  int num = 100;
  5.     public void run()
  6.     {
  7.         while(true)
  8.         {
  9.                 if(num>0)
  10.                 {
  11.                     try{Thread.sleep(10);}catch (InterruptedException e){}
  12.                     //输出卖票信息
  13.                     System.out.println(Thread.currentThread().getName()+“…..sale….”+num–);
  14.                 }
  15.         }
  16.     }
  17. }

上面是卖票线程类,下来再来看看执行类:

  1. public class TicketDemo {
  2.     public static void main(String[] args)
  3.     {
  4.         Ticket t = new Ticket();//创建一个线程任务对象。
  5.         //创建4个线程同时卖票
  6.         Thread t1 = new Thread(t);
  7.         Thread t2 = new Thread(t);
  8.         Thread t3 = new Thread(t);
  9.         Thread t4 = new Thread(t);
  10.         //启动线程
  11.         t1.start();
  12.         t2.start();
  13.         t3.start();
  14.         t4.start();
  15.     }
  16. }

运行程序结果如下(仅截取部分数据):

从运行结果,我们就可以看出我们4个售票窗口同时卖出了1号票,这显然是不合逻辑的,其实这个问题就是我们前面所说的线程同步问题。不同的线程都对同一个数据进了操作这就容易导致数据错乱的问题,也就是线程不同步。那么这个问题该怎么解决呢?在给出解决思路之前我们先来分析一下这个问题是怎么产生的?我们声明一个线程类Ticket,在这个类中我们又声明了一个成员变量num也就是票的数量,然后我们通过run方法不断的去获取票数并输出,最后我们在外部类TicketDemo中创建了四个线程同时操作这个数据,运行后就出现我们刚才所说的线程同步问题,从这里我们可以看出产生线程同步(线程安全)问题的条件有两个:1.多个线程在操作共享的数据(num),2.操作共享数据的线程代码有多条(4条线程);既然原因知道了,那该怎么解决?
解决思路:将多条操作共享数据的线程代码封装起来,当有线程在执行这些代码的时候,其他线程时不可以参与运算的。必须要当前线程把这些代码都执行完毕后,其他线程才可以参与运算。 好了,思路知道了,我们就用java代码的方式来解决这个问题。
2.解决线程同步的两种典型方案
在java中有两种机制可以防止线程安全的发生,Java语言提供了一个synchronized关键字来解决这问题,同时在Java SE5.0引入了Lock锁对象的相关类,接下来我们分别介绍这两种方法
2.1通过锁(Lock)对象的方式解决线程安全问题
在给出解决代码前我们先来介绍一个知识点:Lock,锁对象。在java中锁是用来控制多个线程访问共享资源的方式,一般来说,一个锁能够防止多个线程同时访问共享资源(但有的锁可以允许多个线程并发访问共享资源,比如读写锁,后面我们会分析)。在Lock接口出现之前,java程序是靠synchronized关键字(后面分析)实现锁功能的,而JAVA SE5.0之后并发包中新增了Lock接口用来实现锁的功能,它提供了与synchronized关键字类似的同步功能,只是在使用时需要显式地获取和释放锁,缺点就是缺少像synchronized那样隐式获取释放锁的便捷性,但是却拥有了锁获取与释放的可操作性,可中断的获取锁以及超时获取锁等多种synchronized关键字所不具备的同步特性。接下来我们就来介绍Lock接口的主要API方便我们学习
方法 相关描述内容
void lock() 获取锁,调用该方法当前线程会获取锁,当获取锁后。从该方法返回
void lockInterruptibly()
throws InterruptedException
可中断获取锁和lock()方法不同的是该方法会响应中断,即在获取锁
中可以中断当前线程。例如某个线程在等待一个锁的控制权的这段时
间需要中断。
boolean tryLock() 尝试非阻塞获取锁,调用该方法后立即返回,如果能够获取锁则返回
true,否则返回false。
boolean tryLock(long time,TimeUnit unit)
throws  InterruptedException
超时获取锁,当前线程在以下3种情况返回:
1.当前线程在超时时间内获取了锁
2.当前线程在超时时间被中断
3.当前线程超时时间结束,返回false
void unlock() 释放锁
Condition newCondition() 条件对象,获取等待通知组件。该组件和当前的锁绑定,当前线程只有
获取了锁,才能调用该组件的await()方法,而调用后,当前线程将缩放
锁。
这里先介绍一下API,后面我们将结合Lock接口的实现子类ReentrantLock使用某些方法。
ReentrantLock(重入锁):
重入锁,顾名思义就是支持重新进入的锁,它表示该锁能够支持一个线程对资源的重复加锁,也就是说在调用lock()方法时,已经获取到锁的线程,能够再次调用lock()方法获取锁而不被阻塞,同时还支持获取锁的公平性和非公平性。这里的公平是在绝对时间上,先对锁进行获取的请求一定先被满足,那么这个锁是公平锁,反之,是不公平的。那么该如何使用呢?看范例代码:
1.同步执行的代码跟synchronized类似功能:
  1. ReentrantLock lock = new ReentrantLock(); //参数默认false,不公平锁  
  2. ReentrantLock lock = new ReentrantLock(true); //公平锁  
  3. lock.lock(); //如果被其它资源锁定,会在此等待锁释放,达到暂停的效果  
  4. try {
  5.     //操作  
  6. finally {
  7.     lock.unlock();  //释放锁
  8. }

2.防止重复执行代码:

  1. ReentrantLock lock = new ReentrantLock();
  2. if (lock.tryLock()) {  //如果已经被lock,则立即返回false不会等待,达到忽略操作的效果   
  3.     try {
  4.         //操作  
  5.     } finally {
  6.         lock.unlock();
  7.    }
  8. }

3.尝试等待执行的代码:

  1. ReentrantLock lock = new ReentrantLock(true); //公平锁  
  2. try {
  3.     if (lock.tryLock(5, TimeUnit.SECONDS)) {
  4.         //如果已经被lock,尝试等待5s,看是否可以获得锁,如果5s后仍然无法获得锁则返回false继续执行  
  5.        try {
  6.             //操作  
  7.         } finally {
  8.             lock.unlock();
  9.         }
  10.     }
  11. catch (InterruptedException e) {
  12.     e.printStackTrace(); //当前线程被中断时(interrupt),会抛InterruptedException                   
  13. }

这里有点需要特别注意的,把解锁操作放在finally代码块内这个十分重要。如果在临界区的代码抛出异常,锁必须被释放。否则,其他线程将永远阻塞。好了,ReentrantLock我们就简单介绍到这里,接下来我们通过ReentrantLock来解决前面卖票线程的线程同步(安全)问题,代码如下:

  1. import java.util.concurrent.locks.Lock;
  2. import java.util.concurrent.locks.ReentrantLock;
  3. public class Ticket implements Runnable {
  4.     //创建锁对象
  5.     private Lock ticketLock = new ReentrantLock();
  6.     //当前拥有的票数
  7.     private int num = 100;
  8.     public void run() {
  9.         while (true) {
  10.             try {
  11.                 ticketLock.lock();//获取锁
  12.                 if (num > 0) {
  13.                     Thread.sleep(10);//输出卖票信息System.out.println(Thread.currentThread().getName()+”…..sale….”+num–); }
  14.                 } else {
  15.                     break;
  16.                 }
  17.             } catch (InterruptedException e) {
  18.                 Thread.currentThread().interrupt();//出现异常就中断
  19.             } finally {
  20.                 ticketLock.unlock();//释放锁
  21.             }
  22.         }
  23.     }
  24. }
TicketDemo类无需变化,运行结果正常(太多不贴了),线程安全问题就此解决。
2.2通过synchronied关键字的方式解决线程安全问题
在Java中内置了语言级的同步原语-synchronized,这个可以大大简化了Java中多线程同步的使用。从JAVA SE1.0开始,java中的每一个对象都有一个内部锁,如果一个方法使用synchronized关键字进行声明,那么这个对象将保护整个方法,也就是说调用该方法线程必须获得内部的对象锁。
  1. public synchronized void method{
  2.   //method body
  3. }

等价于

  1. private Lock ticketLock = new ReentrantLock();
  2. public void method{
  3.  ticketLock.lock();
  4.  try{
  5.   //…….
  6.  }finally{
  7.    ticketLock.unlock();
  8.  }
  9. }

从这里可以看出使用synchronized关键字来编写代码要简洁得多了。当然,要理解这一代码,我们必须知道每个对象有一个内部锁,并且该锁有一个内部条件。由锁来管理那些试图进入synchronized方法的线程,由条件来管那些调用wait的线程(wait()/notifyAll/notify())。同时我们必须明白一旦有一个线程通过synchronied方法获取到内部锁,该类的所有synchronied方法或者代码块都无法被其他线程访问直到当前线程释放了内部锁。刚才上面说的是同步方法,synchronized还有一种同步代码块的实现方式:

  1. Object obj = new Object();
  2. synchronized(obj){
  3.   //需要同步的代码
  4. }

其中obj是对象锁,可以是任意对象。那么我们就通过其中的一个方法来解决售票系统的线程同步问题:

  1. class Ticket implements Runnable
  2. {
  3.     private  int num = 100;
  4.     Object obj = new Object();
  5.     public void run()
  6.     {
  7.         while(true)
  8.         {
  9.             synchronized(obj)
  10.             {
  11.                 if(num>0)
  12.                 {
  13.                     try{Thread.sleep(10);}catch (InterruptedException e){}
  14.                     System.out.println(Thread.currentThread().getName()+“…..sale….”+num–);
  15.                 }
  16.             }
  17.         }
  18.     }
  19. }
嗯,同步代码块解决,运行结果也正常。到此同步问题也就解决了,当然代码同步也是要牺牲效率为前提的:
同步的好处:解决了线程的安全问题。
同步的弊端:相对降低了效率,因为同步外的线程的都会判断同步锁。
同步的前提:同步中必须有多个线程并使用同一个锁。
3.线程间的通信机制
线程开始运行,拥有自己的栈空间,但是如果每个运行中的线程,如果仅仅是孤立地运行,那么没有一点儿价值,或者是价值很小,如果多线程能够相互配合完成工作的话,这将带来巨大的价值,这也就是线程间的通信啦。在java中多线程间的通信使用的是等待/通知机制来实现的。
3.1synchronied关键字等待/通知机制:是指一个线程A调用了对象O的wait()方法进入等待状态,而另一个线程B调用了对象O的notify()或者notifyAll()方法,线程A收到通知后从对象O的wait()方法返回,进而执行后续操作。上述的两个线程通过对象O来完成交互,而对象上的wait()和notify()/notifyAll()的关系就如同开关信号一样,用来完成等待方和通知方之间的交互工作。
等待/通知机制主要是用到的函数方法是notify()/notifyAll(),wait()/wait(long),wait(long,int),这些方法在上一篇文章都有说明过,这里就不重复了。当然这是针对synchronied关键字修饰的函数或代码块,因为要使用notify()/notifyAll(),wait()/wait(long),wait(long,int)这些方法的前提是对调用对象加锁,也就是说只能在同步函数或者同步代码块中使用。
3.2条件对象的等待/通知机制:所谓的条件对象也就是配合前面我们分析的Lock锁对象,通过锁对象的条件对象来实现等待/通知机制。那么条件对象是怎么创建的呢?
  1. //创建条件对象
  2. Condition conditionObj=ticketLock.newCondition();
就这样我们创建了一个条件对象。注意这里返回的对象是与该锁(ticketLock)相关的条件对象。下面是条件对象的API:
方法 函数方法对应的描述
void await() 将该线程放到条件等待池中(对应wait()方法)
void signalAll() 解除该条件等待池中所有线程的阻塞状态(对应notifyAll()方法)
void signal() 从该条件的等待池中随机地选择一个线程,解除其阻塞状态(对应notify()方法)
上述方法的过程分析:一个线程A调用了条件对象的await()方法进入等待状态,而另一个线程B调用了条件对象的signal()或者signalAll()方法,线程A收到通知后从条件对象的await()方法返回,进而执行后续操作。上述的两个线程通过条件对象来完成交互,而对象上的await()和signal()/signalAll()的关系就如同开关信号一样,用来完成等待方和通知方之间的交互工作。当然这样的操作都是必须基于对象锁的,当前线程只有获取了锁,才能调用该条件对象的await()方法,而调用后,当前线程将缩放锁。
这里有点要特别注意的是,上述两种等待/通知机制中,无论是调用了signal()/signalAll()方法还是调用了notify()/notifyAll()方法并不会立即激活一个等待线程。它们仅仅都只是解除等待线程的阻塞状态,以便这些线程可以在当前线程解锁或者退出同步方法后,通过争夺CPU执行权实现对对象的访问。到此,线程通信机制的概念分析完,我们下面通过生产者消费者模式来实现等待/通知机制。
4.生产者消费者模式
4.1单生产者单消费者模式
顾名思义,就是一个线程消费,一个线程生产。我们先来看看等待/通知机制下的生产者消费者模式:我们假设这样一个场景,我们是卖北京烤鸭店铺,我们现在只有一条生产线也只有一条消费线,也就是说只能生产线程生产完了,再通知消费线程才能去卖,如果消费线程没烤鸭了,就必须通知生产线程去生产,此时消费线程进入等待状态。在这样的场景下,我们不仅要保证共享数据(烤鸭数量)的线程安全,而且还要保证烤鸭数量在消费之前必须有烤鸭。下面我们通过java代码来实现:
北京烤鸭生产资源类KaoYaResource:
  1. public class KaoYaResource {
  2.     private String name;
  3.     private int count = 1;//烤鸭的初始数量
  4.     private boolean flag = false;//判断是否有需要线程等待的标志
  5.     /**
  6.      * 生产烤鸭
  7.      */
  8.     public synchronized void product(String name){
  9.         if(flag){
  10.             //此时有烤鸭,等待
  11.             try {
  12.                 this.wait();
  13.             } catch (InterruptedException e) {
  14.                 e.printStackTrace()
  15. ;
  16.             }
  17.         }
  18.         this.name=name+count;//设置烤鸭的名称
  19.         count++;
  20.         System.out.println(Thread.currentThread().getName()+“…生产者…”+this.name);
  21.         flag=true;//有烤鸭后改变标志
  22.         notifyAll();//通知消费线程可以消费了
  23.     }
  24.     /**
  25.      * 消费烤鸭
  26.      */
  27.     public synchronized void consume(){
  28.         if(flag){//如果没有烤鸭就等待
  29.             try{this.wait();}catch(InterruptedException e){}
  30.         }
  31.         System.out.println(Thread.currentThread().getName()+“…消费者……..”+this.name);//消费烤鸭1
  32.         flag = false;
  33.         notifyAll();//通知生产者生产烤鸭
  34.     }
  35. }
在这个类中我们有两个synchronized的同步方法,一个是生产烤鸭的,一个是消费烤鸭的,之所以需要同步是因为我们操作了共享数据count,同时为了保证生产烤鸭后才能消费也就是生产一只烤鸭后才能消费一只烤鸭,我们使用了等待/通知机制,wait()和notify()。当第一次运行生产现场时调用生产的方法,此时有一只烤鸭,即flag=false,无需等待,因此我们设置可消费的烤鸭名称然后改变flag=true,同时通知消费线程可以消费烤鸭了,即使此时生产线程再次抢到执行权,因为flag=true,所以生产线程会进入等待阻塞状态,消费线程被唤醒后就进入消费方法,消费完成后,又改变标志flag=false,通知生产线程可以生产烤鸭了………以此循环。
生产消费执行类Single_Producer_Consumer.java:
  1. public class Single_Producer_Consumer {
  2.     public static void main(String[] args)
  3.     {
  4.         KaoYaResource r = new KaoYaResource();
  5.         Producer pro = new Producer(r);
  6.         Consumer con = new Consumer(r);
  7.         //生产者线程
  8.         Thread t0 = new Thread(pro);
  9.         //消费者线程
  10.         Thread t2 = new Thread(con);
  11.         //启动线程
  12.         t0.start();
  13.         t2.start();
  14.     }
  15. }
  16. class Producer implements Runnable
  17. {
  18.     private KaoYaResource r;
  19.     Producer(KaoYaResource r)
  20.     {
  21.         this.r = r;
  22.     }
  23.     public void run()
  24.     {
  25.         while(true)
  26.         {
  27.             r.product(“北京烤鸭”);
  28.         }
  29.     }
  30. }
  31. class Consumer implements Runnable
  32. {
  33.     private KaoYaResource r;
  34.     Consumer(KaoYaResource r)
  35.     {
  36.         this.r = r;
  37.     }
  38.     public void run()
  39.     {
  40.         while(true)
  41.         {
  42.             r.consume();
  43.         }
  44.     }
  45. }

在这个类中我们创建两个线程,一个是消费者线程,一个是生产者线程,我们分别开启这两个线程用于不断的生产消费,运行结果如下:

很显然的情况就是生产一只烤鸭然后就消费一只烤鸭。运行情况完全正常,嗯,这就是单生产者单消费者模式。上面使用的是synchronized关键字的方式实现的,那么接下来我们使用对象锁的方式实现:KaoYaResourceByLock.java
  1. public class KaoyaResourceByLock {
  2.     private String name;
  3.     private int count = 1;//烤鸭的初始数量
  4.     private boolean flag = false;//判断是否有需要线程等待的标志
  5.     //创建一个锁对象
  6.     private Lock resourceLock=new ReentrantLock();
  7.     //创建条件对象
  8.     private Condition condition= resourceLock.newCondition();
  9.     /**
  10.      * 生产烤鸭
  11.      */
  12.     public  void product(String name){
  13.         resourceLock.lock();//先获取锁
  14.         try{
  15.             if(flag){
  16.                 try {
  17.                     condition.await();
  18.                 } catch (InterruptedException e) {
  19.                     e.printStackTrace();
  20.                 }
  21.             }
  22.             this.name=name+count;//设置烤鸭的名称
  23.             count++;
  24.             System.out.println(Thread.currentThread().getName()+“…生产者…”+this.name);
  25.             flag=true;//有烤鸭后改变标志
  26.             condition.signalAll();//通知消费线程可以消费了
  27.         }finally{
  28.             resourceLock.unlock();
  29.         }
  30.     }
  31.     /**
  32.      * 消费烤鸭
  33.      */
  34.     public  void consume(){
  35.         resourceLock.lock();
  36.         try{
  37.         if(!flag){//如果没有烤鸭就等待
  38.             try{condition.await();}catch(InterruptedException e){}
  39.         }
  40.         System.out.println(Thread.currentThread().getName()+“…消费者……..”+this.name);//消费烤鸭1
  41.         flag = false;
  42.         condition.signalAll();//通知生产者生产烤鸭
  43.         }finally{
  44.             resourceLock.unlock();
  45.         }
  46.     }
  47. }
代码变化不大,我们通过对象锁的方式去实现,首先要创建一个对象锁,我们这里使用的重入锁ReestrantLock类,然后通过手动设置lock()和unlock()的方式去获取锁以及释放锁。为了实现等待/通知机制,我们还必须通过锁对象去创建一个条件对象Condition,然后通过锁对象的await()和signalAll()方法去实现等待以及通知操作。Single_Producer_Consumer.java代码替换一下资源类即可,运行结果就不贴了,有兴趣自行操作即可。
4.2多生产者多消费者模式
分析完了单生产者单消费者模式,我们再来聊聊多生产者多消费者模式,也就是多条生产线程配合多条消费线程。既然这样的话我们先把上面的代码Single_Producer_Consumer.java类修改成新类,大部分代码不变,仅新增2条线程去跑,一条t1的生产  共享资源类KaoYaResource不作更改,代码如下:
  1. public class Mutil_Producer_Consumer {
  2.     public static void main(String[] args)
  3.     {
  4.         KaoYaResource r = new KaoYaResource();
  5.         Mutil_Producer pro = new Mutil_Producer(r);
  6.         Mutil_Consumer con = new Mutil_Consumer(r);
  7.         //生产者线程
  8.         Thread t0 = new Thread(pro);
  9.         Thread t1 = new Thread(pro);
  10.         //消费者线程
  11.         Thread t2 = new Thread(con);
  12.         Thread t3 = new Thread(con);
  13.         //启动线程
  14.         t0.start();
  15.         t1.start();
  16.         t2.start();
  17.         t3.start();
  18.     }
  19. class Mutil_Producer implements Runnable
  20. {
  21.     private KaoYaResource r;
  22.     Mutil_Producer(KaoYaResource r)
  23.     {
  24.         this.r = r;
  25.     }
  26.     public void run()
  27.     {
  28.         while(true)
  29.         {
  30.             r.product(“北京烤鸭”);
  31.         }
  32.     }
  33. }
  34. class Mutil_Consumer implements Runnable
  35. {
  36.     private KaoYaResource r;
  37.     Mutil_Consumer(KaoYaResource r)
  38.     {
  39.         this.r = r;
  40.     }
  41.     public void run()
  42.     {
  43.         while(true)
  44.         {
  45.             r.consume();
  46.         }
  47.     }
  48. }

就多了两条线程,我们运行代码看看,结果如下:


不对呀,我们才生产一只烤鸭,怎么就被消费了3次啊,有的烤鸭生产了也没有被消费啊?难道共享数据源没有进行线程同步?我们再看看之前的KaoYaResource.java
  1. public class KaoYaResource {
  2.     private String name;
  3.     private int count = 1;//烤鸭的初始数量
  4.     private boolean flag = false;//判断是否有需要线程等待的标志
  5.     /**
  6.      * 生产烤鸭
  7.      */
  8.     public synchronized void product(String name){
  9.         if(flag){
  10.             //此时有烤鸭,等待
  11.             try {
  12.                 this.wait();
  13.             } catch (InterruptedException e) {
  14.                 e.printStackTrace();
  15.             }
  16.         }
  17.         this.name=name+count;//设置烤鸭的名称
  18.         count++;
  19.         System.out.println(Thread.currentThread().getName()+“…生产者…”+this.name);
  20.         flag=true;//有烤鸭后改变标志
  21.         notifyAll();//通知消费线程可以消费了
  22.     }
  23.     /**
  24.      * 消费烤鸭
  25.      */
  26.     public synchronized void consume(){
  27.         if(!flag){//如果没有烤鸭就等待
  28.             try{this.wait();}catch(InterruptedException e){}
  29.         }
  30.         System.out.println(Thread.currentThread().getName()+“…消费者……..”+this.name);//消费烤鸭1
  31.         flag = false;
  32.         notifyAll();//通知生产者生产烤鸭
  33.     }
  34. }
共享数据count的获取方法都进行synchronized关键字同步了呀!那怎么还会出现数据混乱的现象啊?
分析:确实,我们对共享数据也采用了同步措施,而且也应用了等待/通知机制,但是这样的措施只在单生产者单消费者的情况下才能正确应用,但从运行结果来看,我们之前的单生产者单消费者安全处理措施就不太适合多生产者多消费者的情况了。那么问题出在哪里?可以明确的告诉大家,肯定是在资源共享类,下面我们就来分析问题是如何出现,又该如何解决?直接上图


解决后的资源代码如下只将if改为了while:

  1. public class KaoYaResource {
  2.     private String name;
  3.     private int count = 1;//烤鸭的初始数量
  4.     private boolean flag = false;//判断是否有需要线程等待的标志
  5.     /**
  6.      * 生产烤鸭
  7.      */
  8.     public synchronized void product(String name){
  9.         while(flag){
  10.             //此时有烤鸭,等待
  11.             try {
  12.                 this.wait();
  13.             } catch (InterruptedException e) {
  14.                 e.printStackTrace();
  15.             }
  16.         }
  17.         this.name=name+count;//设置烤鸭的名称
  18.         count++;
  19.         System.out.println(Thread.currentThread().getName()+“…生产者…”+this.name);
  20.         flag=true;//有烤鸭后改变标志
  21.         notifyAll();//通知消费线程可以消费了
  22.     }
  23.     /**
  24.      * 消费烤鸭
  25.      */
  26.     public synchronized void consume(){
  27.         while(!flag){//如果没有烤鸭就等待
  28.             try{this.wait();}catch(InterruptedException e){}
  29.         }
  30.         System.out.println(Thread.currentThread().getName()+“…消费者……..”+this.name);//消费烤鸭1
  31.         flag = false;
  32.         notifyAll();//通知生产者生产烤鸭
  33.     }
  34. }

运行代码,结果如下:


到此,多消费者多生产者模式也完成,不过上面用的是synchronied关键字实现的,而锁对象的解决方法也一样将之前单消费者单生产者的资源类中的if判断改为while判断即可代码就不贴了哈。不过下面我们将介绍一种更有效的锁对象解决方法,我们准备使用两组条件对象(Condition也称为监视器)来实现等待/通知机制,也就是说通过已有的锁获取两组监视器,一组监视生产者,一组监视消费者。有了前面的分析这里我们直接上代码:
  1. public class ResourceBy2Condition {
  2.     private String name;
  3.     private int count = 1;
  4.     private boolean flag = false;
  5.     //创建一个锁对象。
  6.     Lock lock = new ReentrantLock();
  7.     //通过已有的锁获取两组监视器,一组监视生产者,一组监视消费者。
  8.     Condition producer_con = lock.newCondition();
  9.     Condition consumer_con = lock.newCondition();
  10.     /**
  11.      * 生产
  12.      * @param name
  13.      */
  14.     public  void product(String name)
  15.     {
  16.         lock.lock();
  17.         try
  18.         {
  19.             while(flag){
  20.                 try{producer_con.await();}catch(InterruptedException e){}
  21.             }
  22.             this.name = name + count;
  23.             count++;
  24.             System.out.println(Thread.currentThread().getName()+“…生产者5.0…”+this.name);
  25.             flag = true;
  26. //          notifyAll();
  27. //          con.signalAll();
  28.             consumer_con.signal();//直接唤醒消费线程
  29.         }
  30.         finally
  31.         {
  32.             lock.unlock();
  33.         }
  34.     }
  35.     /**
  36.      * 消费
  37.      */
  38.     public  void consume()
  39.     {
  40.         lock.lock();
  41.         try
  42.         {
  43.             while(!flag){
  44.                 try{consumer_con.await();}catch(InterruptedException e){}
  45.             }
  46.             System.out.println(Thread.currentThread().getName()+“…消费者.5.0…….”+this.name);//消费烤鸭1
  47.             flag = false;
  48. //          notifyAll();
  49. //          con.signalAll();
  50.             producer_con.signal();//直接唤醒生产线程
  51.         }
  52.         finally
  53.         {
  54.             lock.unlock();
  55.         }
  56.     }
  57. }
从代码中可以看到,我们创建了producer_con 和consumer_con两个条件对象,分别用于监听生产者线程和消费者线程,在product()方法中,我们获取到锁后,
如果此时flag为true的话,也就是此时还有烤鸭未被消费,因此生产线程需要等待,所以我们调用生产线程的监控器producer_con的
await()的方法进入阻塞等待池;但如果此时的flag为false的话,就说明烤鸭已经消费完,需要生产线程去生产烤鸭,那么生产线程将进行烤
鸭生产并通过消费线程的监控器consumer_con的signal()方法去通知消费线程对烤鸭进行消费。consume()方法也是同样的道理,这里就不
过多分析了。我们可以发现这种方法比我们之前的synchronized同步方法或者是单监视器的锁对象都来得高效和方便些,之前都是使用
notifyAll()和signalAll()方法去唤醒池中的线程,然后让池中的线程又进入 竞争队列去抢占CPU资源,这样不仅唤醒了无关的线程而且又让全
部线程进入了竞争队列中,而我们最后使用两种监听器分别监听生产者线程和消费者线程,这样的方式恰好解决前面两种方式的问题所在,
我们每次唤醒都只是生产者线程或者是消费者线程而不会让两者同时唤醒,这样不就能更高效得去执行程序了吗?好了,到此多生产者多消
费者模式也分析完毕。
5.线程死锁
现在我们再来讨论一下线程死锁问题,从上面的分析,我们知道锁是个非常有用的工具,运用的场景非常多,因为它使用起来非常简单,而
且易于理解。但同时它也会带来一些不必要的麻烦,那就是可能会引起死锁,一旦产生死锁,就会造成系统功能不可用。我们先通过一个例
子来分析,这个例子会引起死锁,使得线程t1和线程t2互相等待对方释放锁。
  1. public class DeadLockDemo {
  2.     private static String A=“A”;
  3.     private static String B=“B”;
  4.     public static void main(String[] args) {
  5.         DeadLockDemo deadLock=new DeadLockDemo();
  6.         while(true){
  7.             deadLock.deadLock();
  8.         }
  9.     }
  10.     private void deadLock(){
  11.         Thread t1=new Thread(new Runnable(){
  12.             @SuppressWarnings(“static-access”)
  13.             @Override
  14.             public void run() {
  15.                 synchronized (A) {
  16.                     try {
  17.                         Thread.currentThread().sleep(2000);
  18.                     } catch (InterruptedException e) {
  19.                         e.printStackTrace();
  20.                     }
  21.                 }
  22.                 synchronized(B){
  23.                     System.out.println(“1”);
  24.                 }
  25.             }
  26.         });
  27.         Thread t2 =new Thread(new Runnable() {
  28.             @Override
  29.             public void run() {
  30.                 synchronized (B) {
  31.                     synchronized (A) {
  32.                         System.out.println(“2”);
  33.                     }
  34.                 }
  35.             }
  36.         });
  37.         //启动线程
  38.         t1.start();
  39.         t2.start();
  40.     }
  41. }
同步嵌套是产生死锁的常见情景,从上面的代码中我们可以看出,当t1线程拿到锁A后,睡眠2秒,此时线程t2刚好拿到了B锁,接着要获取A锁,但是此时A锁正好被t1线程持有,因此只能等待t1线程释放锁A,但遗憾的是在t1线程内又要求获取到B锁,而B锁此时又被t2线程持有,到此结果就是t1线程拿到了锁A同时在等待t2线程释放锁B,而t2线程获取到了锁B也同时在等待t1线程释放锁A,彼此等待也就造成了线程死锁问题。虽然我们现实中一般不会向上面那么写出那样的代码,但是有些更为复杂的场景中,我们可能会遇到这样的问题,比如t1拿了锁之后,因为一些异常情况没有释放锁(死循环),也可能t1拿到一个数据库锁,释放锁的时候抛出了异常,没有释放等等,所以我们应该在写代码的时候多考虑死锁的情况,这样才能有效预防死锁程序的出现。下面我们介绍一下避免死锁的几个常见方法:
1.避免一个线程同时获取多个锁。
2.避免在一个资源内占用多个 资源,尽量保证每个锁只占用一个资源。
3.尝试使用定时锁,使用tryLock(timeout)来代替使用内部锁机制。
4.对于数据库锁,加锁和解锁必须在一个数据库连接里,否则会出现解锁失败的情况。
5.避免同步嵌套的发生
6.Thread.join()
如果一个线程A执行了thread.join()语句,其含义是:当前线程A等待thread线程终止之后才能从thread.join()返回。线程Thread除了提供join()方法之外,还提供了join(long millis)和join(long millis,int nanos)两个具备超时特性的方法。这两个超时的方法表示,如果线程在给定的超时时间里没有终止,那么将会从该超时方法中返回。下面给出一个例子,创建10个线程,编号0~9,每个线程调用钱一个线程的join()方法,也就是线程0结束了,线程1才能从join()方法中返回,而0需要等待main线程结束。
  1. package com.zejian.test;
  2. /**
  3.  * @author zejian
  4.  * @time 2016年3月13日 下午4:10:03
  5.  * @decrition join案例
  6.  */
  7. public class JoinDemo {
  8.     public static void main(String[] args) {
  9.         Thread previous = Thread.currentThread();
  10.         for(int i=0;i<10;i++){
  11.             //每个线程拥有前一个线程的引用。需要等待前一个线程终止,才能从等待中返回
  12.             Thread thread=new Thread(new Domino(previous),String.valueOf(i));
  13.             thread.start();
  14.             previous=thread;
  15.         }
  16.         System.out.println(Thread.currentThread().getName()+” 线程结束”);
  17.     }
  18. }
  19. class Domino implements Runnable{
  20.     private Thread thread;
  21.     public Domino(Thread thread){
  22.         this.thread=thread;
  23.     }
  24.     @Override
  25.     public void run() {
  26.         try {
  27.             thread.join();
  28.         } catch (InterruptedException e) {
  29.             e.printStackTrace();
  30.         }
  31.         System.out.println(Thread.currentThread().getName()+” 线程结束”);
  32.     }
  33. }

好了,到此本篇结束。

java多线程-概念&创建启动&中断&守护线程&优先级&线程状态(多线程编程之一)

今天开始就来总结一下java多线程的基础知识点,下面是本篇的主要内容(大部分知识点参考java核心技术卷1):

1.什么是线程以及多线程与进程的区别
2.多线程的创建与启动
3.中断线程和守护线程以及线程优先级
4.线程的状态转化关系
1.什么是线程以及多线程与进程的区别
在现代操作在运行一个程序时,会为其创建一个进程。例如启动一个QQ程序,操作系统就会为其创建一个进程。而操作系统中调度的最小单位元是线程,也叫轻量级进程,在一个进程里可以创建多个线程,这些线程都拥有各自的计数器,堆栈和局部变量等属性,并且能够访问共享的内存变量。处理器在这些线程上高速切换,让使用者感觉到这些线程在同时执行。因此我们可以这样理解:
进程:正在运行的程序,是系统进行资源分配和调用的独立单位。每一个进程都有它自己的内存空间和系统资源。
线程:是进程中的单个顺序控制流,是一条执行路径一个进程如果只有一条执行路径,则称为单线程程序。一个进程如果有多条执行路径,则称为多线程程序。
2.多线程的创建与启动
创建多线程有两种方法,一种是继承Thread类重写run方法,另一种是实现Runnable接口重写run方法。下面我们分别给出代码示例,继承Thread类重写run方法:
  1. public class ThreadByEx extends Thread{
  2.     /**
  3.      * 重写run方法
  4.      */
  5.     @Override
  6.     public void run() {
  7.         System.out.println(“I’m a thread that extends Thread!”);
  8.     }
  9. }

实现Runnable接口重写run方法:

  1. public class ThreadByRunnable implements Runnable{
  2.     /**
  3.      * 实现run方法
  4.      */
  5.     @Override
  6.     public void run() {
  7.         System.out.println(“I’m a thread that implements Runnable !”);
  8.     }
  9. }

怎么启动线程?

  1. public class MainTest {
  2.     public static void main(String[] args) {
  3.         //继承Thread启动的方法
  4.         ThreadByEx t1=new ThreadByEx();
  5.         t1.start();//启动线程
  6.         //实现Runnable启动线程的方法
  7.         ThreadByRunnable r = new ThreadByRunnable();
  8.         Thread t2 =new Thread(r);
  9.         t2.start();//启动线程
  10.     }
  11. }

运行结果:

  1. I’m a thread that extends Thread!
  2. I’m a thread that implements Runnable !
代码相当简单,不过多解释。这里有点需要注意的是调用start()方法后并不是是立即的执行多线程的代码,而是使该线程变为可运行态,什么时候运行多线程代码是由操作系统决定的。
3.中断线程和守护线程以及线程优先级
什么是中断线程?
我们先来看看中断线程是什么?(该解释来自java核心技术一书,我对其进行稍微简化),当线程的run()方法执行方法体中的最后一条语句后,并经由执行return语句返回时,或者出现在方法中没有捕获的异常时线程将终止。在java早期版本中有一个stop方法,其他线程可以调用它终止线程,但是这个方法现在已经被弃用了,因为这个方法会造成一些线程不安全的问题。我们可以把中断理解为一个标识位的属性,它表示一个运行中的线程是否被其他线程进行了中断操作,而中断就好比其他线程对该线程打可个招呼,其他线程通过调用该线程的interrupt方法对其进行中断操作,当一个线程调用interrupt方法时,线程的中断状态(标识位)将被置位(改变),这是每个线程都具有的boolean标志,每个线程都应该不时的检查这个标志,来判断线程是否被中断。而要判断线程是否被中断,我们可以使用如下代码
  1. Thread.currentThread().isInterrupted()
  1. while(!Thread.currentThread().isInterrupted()){
  2.     do something
  3. }

但是如果此时线程处于阻塞状态(sleep或者wait),就无法检查中断状态,此时会抛出InterruptedException异常。如果每次迭代之后都调用sleep方法(或者其他可中断的方法),isInterrupted检测就没必要也没用处了,如果在中断状态被置位时调用sleep方法,它不会休眠反而会清除这一休眠状态并抛出InterruptedException。所以如果在循环中调用sleep,不要去检测中断状态,只需捕获InterruptedException。代码范例如下:

  1. public void run(){
  2.         while(more work to do ){
  3.             try {
  4.                 Thread.sleep(5000);
  5.             } catch (InterruptedException e) {
  6.                 //thread was interrupted during sleep
  7.                 e.printStackTrace();
  8.             }finally{
  9.                 //clean up , if required
  10.             }
  11.         }
同时还有点要注意的就是我们在捉中断异常时尽量按如下形式处理,不要留空白什么都不处理!
不妥的处理方式:
  1. void myTask(){
  2.     …
  3.    try{
  4.        sleep(50)
  5.       }catch(InterruptedException e){
  6.    …
  7.    }
  8. }
  1. void myTask()throw InterruptedException{
  2.     sleep(50)
  3. }

或者

  1. void myTask(){
  2.     …
  3.     try{
  4.     sleep(50)
  5.     }catch(InterruptedException e){
  6.      Thread.currentThread().interrupt();
  7.     }
  8. }
最后关于中断线程,我们这里给出中断线程的一些主要方法:
void interrupt():向线程发送中断请求,线程的中断状态将会被设置为true,如果当前线程被一个sleep调用阻塞,那么将会抛出interrupedException异常。
static boolean interrupted():测试当前线程(当前正在执行命令的这个线程)是否被中断。注意这是个静态方法,调用这个方法会产生一个副作用那就是它会将当前线程的中断状态重置为false。
boolean isInterrupted():判断线程是否被中断,这个方法的调用不会产生副作用即不改变线程的当前中断状态。
static Thread currentThread() : 返回代表当前执行线程的Thread对象。
什么是守护线程?
首先我们可以通过t.setDaemon(true)的方法将线程转化为守护线程。而守护线程的唯一作用就是为其他线程提供服务。计时线程就是一个典型的例子,它定时地发送“计时器滴答”信号告诉其他线程去执行某项任务。当只剩下守护线程时,虚拟机就退出了,因为如果只剩下守护线程,程序就没有必要执行了。另外JVM的垃圾回收、内存管理等线程都是守护线程。还有就是在做数据库应用时候,使用的数据库连接池,连接池本身也包含着很多后台线程,监控连接个数、超时时间、状态等等。最后还有一点需要特别注意的是在java虚拟机退出时Daemon线程中的finally代码块并不一定会执行哦,代码示例:
  1. public class Demon {
  2.     public static void main(String[] args) {
  3.         Thread deamon = new Thread(new DaemonRunner(),“DaemonRunner”);
  4.         //设置为守护线程
  5.         deamon.setDaemon(true);
  6.         deamon.start();//启动线程
  7.     }
  8.     static class DaemonRunner implements Runnable{
  9.         @Override
  10.         public void run() {
  11.             try {
  12.                 Thread.sleep(500);
  13.             } catch (InterruptedException e) {
  14.                 e.printStackTrace();
  15.             }finally{
  16.                 System.out.println(“这里的代码在java虚拟机退出时并不一定会执行哦!”);
  17.             }
  18.         }
  19.     }
  20. }
因此在构建Daemon线程时,不能依靠finally代码块中的内容来确保执行关闭或清理资源的逻辑。
什么是线程优先级
在现代操作系统中基本采用时分的形式调度运行的线程,操作系统会分出一个个时间片,线程会分配到若干时间片,当线程的时间片用完了就会发生线程调度,并等待着下一次分配。线程分配到的时间片多少也决定了线程使用处理器资源的多少,而线程优先级就是决定线程需要多或者少分配一些处理器资源的线程属性。在java线程中,通过一个整型的成员变量Priority来控制线程优先级,每一个线程有一个优先级,默认情况下,一个线程继承它父类的优先级。可以用setPriority方法提高或降低任何一个线程优先级。可以将优先级设置在MIN_PRIORITY(在Thread类定义为1)与MAX_PRIORITY(在Thread类定义为10)之间的任何值。线程的默认优先级为NORM_PRIORITY(在Thread类定义为5)。尽量不要依赖优先级,如果确实要用,应该避免初学者常犯的一个错误。如果有几个高优先级的线程没有进入非活动状态,低优先级线程可能永远也不能执行。每当调度器决定运行一个新线程时,首先会在具有高优先级的线程中进行选择,尽管这样会使低优先级的线程可能永远不会被执行到。因此我们在设置优先级时,针对频繁阻塞(休眠或者I/O操作)的线程需要设置较高的优先级,而偏重计算(需要较多CPU时间或者运算)的线程则设置较低的优先级,这样才能确保处理器不会被长久独占。当然还有要注意就是在不同的JVM以及操作系统上线程的规划存在差异,有些操作系统甚至会忽略对线程优先级的设定,如mac os系统或者Ubuntu系统……..
4.线程的状态转化关系
(1). 新建状态(New):新创建了一个线程对象。
(2). 就绪状态(Runnable):线程对象创建后,其他线程调用了该对象的start()方法。该状态的线程位于可运行线程池中,变得可运行,等待获取CPU的使用权。
(3). 运行状态(Running):就绪状态的线程获取了CPU,执行程序代码。
(4). 阻塞状态(Blocked):阻塞状态是线程因为某种原因放弃CPU使用权,暂时停止运行。直到线程进入就绪状态,才有机会转到运行状态。阻塞的情况分三种:

– 等待阻塞(WAITING):运行的线程执行wait()方法,JVM会把该线程放入等待池中。

– 同步阻塞(Blocked):运行的线程在获取对象的同步锁时,若该同步锁被别的线程占用,则JVM会把该线程放入锁池中。

– 超时阻塞(TIME_WAITING):运行的线程执行sleep(long)或join(long)方法,或者发出了I/O请求时,JVM会把该线程置为阻塞状态。

(5). 死亡状态(Dead):线程执行完了或者因异常退出了run()方法,该线程结束生命周期。

图中的方法解析如下:

Thread.sleep():在指定时间内让当前正在执行的线程暂停执行,但不会释放”锁标志”。不推荐使用。
Thread.sleep(long):使当前线程进入阻塞状态,在指定时间内不会执行。
Object.wait()和Object.wait(long):在其他线程调用对象的notify或notifyAll方法前,导致当前线程等待。线程会释放掉它所占有的”锁标志”,从而使别的线程有机会抢占该锁。 当前线程必须拥有当前对象锁。如果当前线程不是此锁的拥有者,会抛出IllegalMonitorStateException异常。 唤醒当前对象锁的等待线程使用notify或notifyAll方法,也必须拥有相同的对象锁,否则也会抛出IllegalMonitorStateException异常,waite()和notify()必须在synchronized函数或synchronized中进行调用。如果在non-synchronized函数或non-synchronized中进行调用,虽然能编译通过,但在运行时会发生IllegalMonitorStateException的异常。
Object.notifyAll():则从对象等待池中唤醒所有等待等待线程
Object.notify():则从对象等待池中唤醒其中一个线程。
Thread.yield()方法 暂停当前正在执行的线程对象,yield()只是使当前线程重新回到可执行状态,所以执行yield()的线程有可能在进入到可执行状态后马上又被执行,yield()只能使同优先级或更高优先级的线程有执行的机会。
Thread.Join():把指定的线程加入到当前线程,可以将两个交替执行的线程合并为顺序执行的线程。比如在线程B中调用了线程A的Join()方法,直到线程A执行完毕后,才会继续执行线程B。
好了。本篇线程基础知识介绍到此结束。

关于Java Lambda的教程,简单明了

许多热门的编程语言如今都有一个叫做lambda或者闭包的语言特性,包括比较经典的函数式编程语言Lisp,Scheme,也有稍微年轻的语言比如JavaScript,Python,Ruby,Groovy,Scale,C#,甚至C++也有Lambda表达式。一些语言是运行在java虚拟机上,作为虚拟机最具代表的语言java当然也不想落后。

究竟什么是Lambda表达式?

Lambda表达式的概念来自于Lambda演算,下面是一个java lambda的简单例子,

(int x)->{ return x+1;}

简单来看lambda像一个没有名字的方法,它具有一个方法应该有的部分:参数列表int x,方法body return x+1,和方法相比lambda好像缺少了一个返回值类型、异常抛出和名字。返回值类型和异常是通过编译器在方法体中推导出来,在上面这个例子中返回值类型是int,没有抛出异常。真正缺少的就是一个名字,从这个角度来看,lambda表达式是一种匿名方法。

Lambda表达式和匿名内部类

从上面的分析可以看出lambda和java内部类的特性有点相似,匿名内部类不只是一个方法,而是一个包含一个或多个方法的类,他们的作用都是一样的,都是作为方法的参数传递,我从JDK源码中提取出来listFiles(FileFilter) 方法:

关于Java Lambda的教程,简单明了

public interface FileFilter { boolean accept(File pathname); }

fileFilter接收一个File对象返回一个boolean值,listFiles方法把Filter应用到所有的File对象接收 那些accept返回true的文件。对于listFiles方法来讲我们必须传递一个函数式接口给他,这是FileFileter的一个实现,一般我们通过匿名类来完成:

关于Java Lambda的教程,简单明了

我们现在可以用lambda来实现:

关于Java Lambda的教程,简单明了

这两种情况我们都是传递了一个函数式接口给方法就像传递对象一样,我们使用代码就像使用数据一样,使用匿名类我们实际上传递了一个对象给方法,使用lambda不再需要创建对象,我们只需要把lambda代码传递给方法。

除了传递lambda之外我们还可以传递一个方法引用,比如:

File[] files = myDir.listFiles( File::isFile );

Lambda表达式的表示

在之前的例子,我们使用lambda表达式定义了一个函数,我们可以把它作为参数传递给一个方法,方法把它当成一个对象来使用,lambda表达式有函数和对象的一些属性,看你从什么角度来看:

  • 从概念来讲,lambda表达式是一个匿名函数,它有签名和方法体但是没有名字
  • 当lambda表达式作为参数传递给方法时,接收方法把它当对象使用,在listFiles方法内部,lambda表达式是一个对象的引用,在这里lambda表达式是一种常规的对象,比如有地址和类型。

从实际的角度来分析,lambda对象是由编译期和运行时系统来创建的,这就允许编译期进行优化而使用者不需要关心具体细节,编译器从lambda表达式的上下文环境来获取lambda对象的语义类型,但是编译期并不创建那个对象而是直到运行时由虚拟机动态创建,这里说的动态创建是指调用

invokedynamic字节码指令来创建。使用动态创建可以推迟对象的创建到对象第一次被使用时,如果你只是定义了lambda表达式而从未使用,它的类型和对象都不会创建。

函数式接口

整个魔幻之处就在于类型的推导,这个类型称为目标类型,运行时系统动态创建的类型是目标类型的子类型。之前的那个例子我们看到目标类型是FileFilter,在例子中我们定义了一个lambda表达式把它传递给listFiles方法,然后listFiles方法把它作为FileFilter子类的一个对象来使用。这里看起来好像有点神奇,我们并没有声明lambda表达式实现了FileFilter接口,listFiles方法也没有表明它很愉快的接收了lambda表达式,它只是需要一个FileFilter的子类的对象,这是如何工作的?

这里面的魔术在于编译期执行了类型推导,编译器根据lambda表达式的上下文来决定需要什么类型的对象,然后编译器观察lambda表达式是否兼容需要的类型。如果Java是一种函数式编程语言的话lambda表达式最自然的类型就是某种函数式类型,用来描述函数的一种特殊类型。函数式类型仅仅描述了函数的签名比如(int,int)->boolean.但是Java不是函数式编程语言因此没有函数式类型,语言的设计者可以选择添加一种新的类型,由于他们不想给Java的类型系统引入太多的改变,因此他们尝试寻找一种办法来集成lambda表达式到语言中而不需要添加函数式类型。

结果他们使用函数式接口来代替,函数式接口是只有一个方法的接口,这样的接口在JDK里有很多,比如经典的Runnable接口,它只有一个方法void run(),还有很多其他的,比如Readable,Callable,Iterable,closeable,Flushnable,Formattable,Comparable,Comparator,或者我们前面提到的FileFilter接口。函数是接口和lambda表达式奕扬都只有一个方法,语言的设计者决定让编译器把lambda表达式转换成匹配的函数式接口。这种转换通常是自动的。比如我们前面提到的(File f) -> { return f.isFile(); },编译器知道listFiles方法的签名,因此我们需要的类型就是FileFilter,FileFilter是这样的:
public interface FileFilter { boolean accept(File pathname); }
FileFilter仅仅需要一个方法因此它是函数式接口类型,我们定义的lambda表达式有一个相匹配的签名,接收一个File对象,返回一个boolean值,不抛出检查的异常,因此编译器把lambda表达式转换成函数式接口FileFilter类型。

假如我们有下面两个函数式接口:
关于Java Lambda的教程,简单明了

我们的lambda表达式兼容两种函数式接口类型:
关于Java Lambda的教程,简单明了

当我们试图给两个变量相互赋值时编译器会报错,虽然两个变量都是同一个lambda表达式,原因很简单两个变量是不同的类型。也有可能出现编译器无法判断匹配的函数式接口类型,比如这个例子:
Object ref = (File f) -> { return f.isFile(); };
这个赋值语句的上下文没有提供足够的信息来转换,因此编译器会报错,解决这个问题最简单的方法就是添加一个类型转换:
Object ref = (FileFilter) (File f) -> { return f.isFile(); };

Lambda表达式和匿名内部类的区别

Lambda表达式出现在我们通常需要匿名内部类的地方,在很多场合他们是可以互换的。但是他们还是有几个区别:

1.语法

匿名类一般这样编写:
关于Java Lambda的教程,简单明了

而Lambda表达式有多种形式:
关于Java Lambda的教程,简单明了

2.运行时成本

匿名类相对Lambda表达式来讲多了一些成本,使用匿名类或造成新类型的创建、新类型对象的创建。运行时匿名内需要:类加载 > 内存分配、对象初始化 > 调用非静态方法。

Lambda表达式需要函数式接口的转换和最终的调用,类型推导发生在编译期,不需要运行时消耗,之前提到过,lambda对象的创建是通过字节码指令invokedynamic来完成的,减少了类型和实例的创建消耗。

3.变量绑定

匿名类可以访问外部域的final变量,如下所示关于Java Lambda的教程,简单明了

对于lambda表达式,cnt变量不需要显式声明为final的,一旦变量在lambda中使用编译期会自动把它当成是final的变量,换句话说在lambda中使用的外部域变量是隐式final的,

关于Java Lambda的教程,简单明了

从java8开始匿名内部类也不需要再显式声明final类,编译器会自动把它当成是final。

4.作用域

匿名内部类是一个类,也就是说它自己引入了一个作用域,你可以在里面定义变量,而lambda表达式没有自己的作用域。
关于Java Lambda的教程,简单明了

lambda表达式:
关于Java Lambda的教程,简单明了

不同的作用域规则对于this和super关键字有不同的效果,在匿名类中this表示匿名类对象本身的引用,super表示匿名类的父类。在lambda表达式this和super关键字意思和外部域中this和super的意思一样,this一般是包含它的那个对象,super表示包含它的类的父类。

java8的新特性以及用法简介,再不学习,代码都看不懂了

1. 介绍

本文简单介绍下java8里面有哪些新的特性,以及相关的用法。

JAVA8是意义深远的一个新版本。随着大数据的兴起,函数式编程在处理大数据上的优势开始体现。JAVA8也紧跟时代,引入了函数式语言的特性,值得关注。下面看看其有哪些新的内容。

2 接口的默认方法

Java 8允许我们给接口添加一个非抽象的方法实现,只需要使用 default关键字即可,这个特征又叫做扩展方法。JAVA可以实现多个接口,从而来对原本的类进行方法扩展。JAVA只能继承1个类,所以以前的接口没法提供这种灵活的扩展方法。现在要简单的扩展方法,也不需要使用Spring的代码织入了,直接用扩展方法即可。不过横切逻辑织入还是用Spring好。

下面看个例子:

interface Formula {  
    double calculate(int a);  
    
    //default修饰的扩展方法 
    default double sqrt(int a) {  
        return Math.sqrt(a);  
    } 
}

Formula接口在拥有calculate方法之外同时还定义了sqrt方法,实现了Formula接口的子类只需要实现一个calculate方法,默认方法sqrt将在子类上可以直接使用。

Formula formula = new Formula() {  
    @Override  
    public double calculate(int a) { 
        return sqrt(a * 100);  
    } 
}; 
formula.calculate(100); // 100.0 
formula.sqrt(16); // 4.0

新的Java 8 的这个特新在编译器实现的角度上来说更加接近Scala的trait。 在C#中也有名为扩展方法的概念,允许给已存在的类型扩展方法,和Java 8的这个在语义上有差别。

2 lambda表达式

首先看看在老版本的Java中是如何排列字符串的:

List<String> names = Arrays.asList("peter", "anna", "mike", "xenia"); 
Collections.sort(names, new Comparator<String>() {  
    @Override  
    public int compare(String a, String b) {  
         return b.compareTo(a);  
    } 
});

只需要给静态方法 Collections.sort 传入一个List对象以及一个比较器来按指定顺序排列。通常做法都是创建一个匿名的比较器对象然后将其传递给sort方法。在Java 8 中你就没必要使用这种传统的匿名对象的方式了,Java 8提供了更简洁的语法,lambda表达式:

Collections.sort(names, 
     (String a, String b) -> {  return b.compareTo(a); });

看到了吧,代码变得更段且更具有可读性,但是实际上还可以写得更短:

Collections.sort(names, (String a, String b) -> b.compareTo(a));

对于函数体只有一行代码的,你可以去掉大括号{}以及return关键字,但是你还可以写得更短点,Java编译器可以自动推导出参数类型,所以你可以不用再写一次类型。

Collections.sort(names, (a, b) -> b.compareTo(a));

2.1 函数式接口

每个lambda表达式对应一个函数式接口。函数式接口”是指仅仅只包含一个抽象方法的接口,每一个该类型的lambda表达式都会被匹配到这个抽象方法。因为 默认方法 不算抽象方法,所以你也可以给你的函数式接口添加默认方法。

我们可以将lambda表达式当作任意只包含一个抽象方法的接口类型,确保你的接口一定达到这个要求,你只需要给你的接口添加 @FunctionalInterface 注解,编译器如果发现你标注了这个注解的接口有多于一个抽象方法的时候会报错的。

//需要注解修饰表明是函数式接口
@FunctionalInterface
interface Converter<F, T> {  
    //必须仅包含一个抽象方法,用于lambda表达式给出具体实现。这里可以包    含扩展方法 
    T convert(F from); 
} 
// Integer.valueOf(from)是函数式接口里面抽象方法的实现。Converter<String, Integer> converter = 
      (from) -> Integer.valueOf(from); 
Integer converted = converter.convert("123"); System.out.println(converted); // 123

需要注意如果@FunctionalInterface如果没有指定,上面的代码也是对的。

译者注 将lambda表达式映射到一个单方法的接口上,这种做法在Java 8之前就有别的语言实现,比如Rhino JavaScript解释器,如果一个函数参数接收一个单方法的接口而你传递的是一个function,Rhino 解释器会自动做一个单接口的实例到function的适配器

2.2 方法与构造函数引用

Java 8 允许你使用 :: 关键字来传递方法或者构造函数引用

Converter<String, Integer> converter = Integer::valueOf; 
Integer converted = converter.convert("123"); System.out.println(converted); // 123

获取构造函数的引用的话使用 ::new,后面接new关键字即可。

2.3 访问局部变量

在lambda表达式中访问外层作用域和老版本的匿名对象中的方式很相似。你可以直接访问标记了final的外层局部变量,或者实例的字段以及静态变量。

//不用final修饰也可以访问,但是要确保其不备修改,所以还是建议用final修饰final
int num = 1; 
Converter<Integer, String> stringConverter = 
     (from) -> String.valueOf(from + num); 
stringConverter.convert(2); // 3

2.4 访问对象字段与静态变量

和本地变量不同的是,lambda内部对于实例的字段以及静态变量是即可读又可写。该行为和匿名对象是一致的:

class Lambda4 {  
    static int outerStaticNum;  
    int outerNum;  
    void testScopes() {  
        Converter<Integer, String> stringConverter1 = 
           (from) -> { outerNum = 23;  
                return String.valueOf(from);  
           };  
        Converter<Integer, String> stringConverter2 = 
           (from) -> {  
                outerStaticNum = 72; 
                return String.valueOf(from); 
           };  
     } 
}

3. 内建函数式接口

JDK 1.8 API包含了很多内建的函数式接口,在老Java中常用到的比如Comparator或者Runnable接口,这些接口都增加了@FunctionalInterface注解以便能用在lambda上。

Java 8 API同样还提供了很多全新的函数式接口来让工作更加方便,有一些接口是来自Google Guava库里的,即便你对这些很熟悉了,还是有必要看看这些是如何扩展到lambda上使用的。

这些已经默认提供的内建函数式接口主要是:

  • Predicate — 传入一个参数,返回一个bool结果, 方法为boolean test(T t)
  • Consumer — 传入一个参数,无返回值,纯消费。 方法为void accept(T t)
  • Function<t,r> — 传入一个参数,返回一个结果,方法为R apply(T t)</t,r>
  • Supplier — 无参数传入,返回一个结果,方法为T get()

3.1 Predicate接口

Predicate 接口只有一个参数,返回boolean类型。该接口包含多种默认方法来将Predicate组合成其他复杂的逻辑(比如:与,或,非):

//用于做一些判断Predicate<String>

predicate = (s) -> s.length() > 0; 
predicate.test("foo"); // true
predicate.negate().test("foo"); // false 
Predicate<Boolean> nonNull = Objects::nonNull; 
Predicate<Boolean> isNull = Objects::isNull; 
Predicate<String> isEmpty = String::isEmpty; 
Predicate<String> isNotEmpty = isEmpty.negate();

3.2 Function 接口

Function 接口有一个参数并且返回一个结果,并附带了一些可以和其他函数组合的默认方法(compose, andThen):

Function<String, Integer> toInteger = Integer::valueOf; Function<String, String> backToString = toInteger.andThen(String::valueOf); 
backToString.apply("123"); // "123"

3.3 Supplier 接口

Supplier 接口返回一个任意范型的值,和Function接口不同的是该接口没有任何参数

Supplier<Person> personSupplier = Person::new; 
personSupplier.get(); // new Person

3.4 Consumer 接口

Consumer 接口表示执行在单个参数上的操作。

Consumer<Person> greeter = (p) -> System.out.println("Hello, " + p.firstName); 
greeter.accept(new Person("Luke", "Skywalker"));

3.5 Comparator 接口

Comparator 是老Java中的经典接口, Java 8在此之上添加了多种默认方法:

Comparator<Person> comparator = (p1, p2) -> p1.firstName.compareTo(p2.firstName); 
Person p1 = new Person("John", "Doe"); 
Person p2 = new Person("Alice", "Wonderland"); 
comparator.compare(p1, p2); // > 0 
comparator.reversed().compare(p1, p2); // < 0

3.6 Optional 接口

Optional 不是函数是接口,这是个用来防止NullPointerException异常的辅助类型,这是下一届中将要用到的重要概念,现在先简单的看看这个接口能干什么:

Optional 被定义为一个简单的容器,其值可能是null或者不是null。在Java 8之前一般某个函数应该返回非空对象但是偶尔却可能返回了null,而在Java 8中,不推荐你返回null而是返回Optional。

Optional<String> optional = Optional.of("bam"); 
optional.isPresent(); // true 
optional.get(); // "bam" optional.orElse("fallback"); // "bam" 
optional.ifPresent((s) -> System.out.println(s.charAt(0))); // "b"

3.7 Stream 接口

java.util.Stream 表示能应用在一组元素上一次执行的操作序列。Stream 操作分为中间操作或者最终操作两种,最终操作返回一特定类型的计算结果,而中间操作返回Stream本身,这样你就可以将多个操作依次串起来。Stream 的创建需要指定一个数据源,比如 java.util.Collection的子类,List或者Set, Map不支持。Stream的操作可以串行执行或者并行执行。

首先看看Stream是怎么用,首先创建实例代码的用到的数据List:

List<String> stringCollection = new ArrayList<>(); 
stringCollection.add("ddd2"); 
stringCollection.add("aaa2"); 
stringCollection.add("bbb1"); 
stringCollection.add("aaa1"); 
stringCollection.add("bbb3"); 
stringCollection.add("ccc"); 
stringCollection.add("bbb2"); 
stringCollection.add("ddd1");

Java 8扩展了集合类,可以通过 Collection.stream() 或者 Collection.parallelStream() 来创建一个Stream。下面几节将详细解释常用的Stream操作:

3.7.1 Filter过滤

过滤通过一个predicate接口来过滤并只保留符合条件的元素,该操作属于中间操作,所以我们可以在过滤后的结果来应用其他Stream操作(比如forEach)。forEach需要一个函数来对过滤后的元素依次执行。forEach是一个最终操作,所以我们不能在forEach之后来执行其他Stream操作。

stringCollection
   .stream()  
   .filter((s) -> s.startsWith("a"))
   .forEach(System.out::println); // "aaa2", "aaa1"

3.7.2 Sort 排序

排序是一个中间操作,返回的是排序好后的Stream。如果你不指定一个自定义的Comparator则会使用默认排序。

stringCollection
   .stream()
   .sorted()
   .filter((s) -> s.startsWith("a"))  
   .forEach(System.out::println); // "aaa1", "aaa2"

需要注意的是,排序只创建了一个排列好后的Stream,而不会影响原有的数据源,排序之后原数据stringCollection是不会被修改的:

System.out.println(stringCollection); // ddd2, aaa2, bbb1, aaa1, bbb3, ccc, bbb2, ddd1

3.7.3 Map 映射

中间操作map会将元素根据指定的Function接口来依次将元素转成另外的对象,下面的示例展示了将字符串转换为大写字符串。你也可以通过map来讲对象转换成其他类型,map返回的Stream类型是根据你map传递进去的函数的返回值决定的。

stringCollection
   .stream()  
   .map(String::toUpperCase)  
   .sorted((a, b) -> b.compareTo(a))  
   .forEach(System.out::println); // "DDD2", "DDD1", "CCC", "BBB3", "BBB2", "AAA2", "AAA1"

3.7.4 Match 匹配

Stream提供了多种匹配操作,允许检测指定的Predicate是否匹配整个Stream。所有的匹配操作都是最终操作,并返回一个boolean类型的值。

boolean anyStartsWithA = stringCollection  
    .stream() 
    .anyMatch((s) -> s.startsWith("a"));             System.out.println(anyStartsWithA); // true boolean 
allStartsWithA = stringCollection  
    .stream()  
    .allMatch((s) -> s.startsWith("a")); System.out.println(allStartsWithA); // false boolean
noneStartsWithZ =  stringCollection  
    .stream()  
    .noneMatch((s) -> s.startsWith("z")); System.out.println(noneStartsWithZ); // true

3.7.5 Count 计数

计数是一个最终操作,返回Stream中元素的个数,返回值类型是long。

long startsWithB = stringCollection  
    .stream()  
    .filter((s) -> s.startsWith("b"))  
    .count(); 
System.out.println(startsWithB); // 3

3.7.6 Reduce 规约

这是一个最终操作,允许通过指定的函数来讲stream中的多个元素规约为一个元素,规越后的结果是通过Optional接口表示的:

Optional<String> reduced = stringCollection
    .stream()  
    .sorted()  
    .reduce((s1, s2) -> s1 + "#" + s2); reduced.ifPresent(System.out::println); //"aaa1#aaa2#bbb1#bbb2#bbb3#ccc#ddd1#ddd2"

3.7.7 并行Streams

前面提到过Stream有串行和并行两种,串行Stream上的操作是在一个线程中依次完成,而并行Stream则是在多个线程上同时执行。

下面的例子展示了是如何通过并行Stream来提升性能:

首先我们创建一个没有重复元素的大表:

int max = 1000000; 
List<String> values = new ArrayList<>(max); 
for (int i = 0; i < max; i++) {  
   UUID uuid = UUID.randomUUID();  
   values.add(uuid.toString()); 
}

然后我们计算一下排序这个Stream要耗时多久,

串行排序:

long t0 = System.nanoTime(); 
long count = values.stream().sorted().count(); 
System.out.println(count); 
long t1 = System.nanoTime(); 
long millis = TimeUnit.NANOSECONDS.toMillis(t1 - t0); 
System.out.println(String.format("sequential sort took: %d ms",  millis));

// 串行耗时: 899 ms

并行排序:

long t0 = System.nanoTime(); 
long count = values.parallelStream().sorted().count(); System.out.println(count); 
long t1 = System.nanoTime(); 
long millis = TimeUnit.NANOSECONDS.toMillis(t1 - t0); 
System.out.println(String.format("parallel sort took: %d ms", millis));

// 并行排序耗时: 472 ms

上面两个代码几乎是一样的,但是并行版的快了50%之多,唯一需要做的改动就是将stream()改为parallelStream()。

4. Map

前面提到过,Map类型不支持stream,不过Map提供了一些新的有用的方法来处理一些日常任务。

Map<Integer, String> map = new HashMap<>(); 
for (int i = 0; i < 10; i++) {  
   map.putIfAbsent(i, "val" + i); 
}
map.forEach((id, val) -> System.out.println(val));

以上代码很容易理解, putIfAbsent 不需要我们做额外的存在性检查,而forEach则接收一个Consumer接口来对map里的每一个键值对进行操作。

下面的例子展示了map上的其他有用的函数:

map.computeIfPresent(3,(num, val) -> val + num); 
map.get(3); // val33 
map.computeIfPresent(9, (num, val) -> null); 
map.containsKey(9); // false 
map.computeIfAbsent(23, num -> "val" + num); 
map.containsKey(23); // true 
map.computeIfAbsent(3, num -> "bam"); 
map.get(3); // val33

接下来展示如何在Map里删除一个键值全都匹配的项:

map.remove(3, "val3"); 
map.get(3); // val33 
map.remove(3, "val33"); 
map.get(3); // null

另外一个有用的方法:

map.getOrDefault(42, "not found"); // not found

对Map的元素做合并也变得很容易了:

map.merge(9,"val9", (value, newValue) -> value.concat(newValue)); map.get(9); // val9 
map.merge(9, "concat", (value, newValue) -> value.concat(newValue)); 
map.get(9); // val9concat

Merge做的事情是如果键名不存在则插入,否则则对原键对应的值做合并操作并重新插入到map中。

5. Date API

Java 8 在包java.time下包含了一组全新的时间日期API。新的日期API和开源的Joda-Time库差不多,但又不完全一样,下面的例子展示了这组新API里最重要的一些部分:

5.1 Clock 时钟

Clock类提供了访问当前日期和时间的方法,Clock是时区敏感的,可以用来取代 System.currentTimeMillis() 来获取当前的微秒数。某一个特定的时间点也可以使用Instant类来表示,Instant类也可以用来创建老的java.util.Date对象。

Clock clock = Clock.systemDefaultZone(); 
long millis = clock.millis(); 
Instant instant = clock.instant(); 
Date legacyDate = Date.from(instant); // legacy java.util.Date

5.2 Timezones 时区

在新API中时区使用ZoneId来表示。时区可以很方便的使用静态方法of来获取到。 时区定义了到UTS时间的时间差,在Instant时间点对象到本地日期对象之间转换的时候是极其重要的。

System.out.println(ZoneId.getAvailableZoneIds());
 // prints all available timezone ids ZoneId zone1 = 
ZoneId.of("Europe/Berlin"); 
ZoneId zone2 = ZoneId.of("Brazil/East"); 
System.out.println(zone1.getRules()); 
System.out.println(zone2.getRules()); // 
ZoneRules[currentStandardOffset=+01:00] // 
ZoneRules[currentStandardOffset=-03:00]

5.3 LocalTime 本地时间

LocalTime 定义了一个没有时区信息的时间,例如 晚上10点,或者 17:30:15。下面的例子使用前面代码创建的时区创建了两个本地时间。之后比较时间并以小时和分钟为单位计算两个时间的时间差:

LocalTime now1 = LocalTime.now(zone1); 
LocalTime now2 = LocalTime.now(zone2); 
System.out.println(now1.isBefore(now2)); // false 
long hoursBetween = ChronoUnit.HOURS.between(now1, now2); 
long minutesBetween = ChronoUnit.MINUTES.between(now1, now2); 
System.out.println(hoursBetween); // -3 
System.out.println(minutesBetween); // -239

LocalTime 提供了多种工厂方法来简化对象的创建,包括解析时间字符串。

LocalTime late = LocalTime.of(23, 59, 59); 
System.out.println(late); // 23:59:59 
DateTimeFormatter germanFormatter =  
    DateTimeFormatter
    .ofLocalizedTime(FormatStyle.SHORT)  
    .withLocale(Locale.GERMAN); 
LocalTime leetTime = LocalTime.parse("13:37", germanFormatter); 
System.out.println(leetTime); // 13:37

5.4 LocalDate 本地日期

LocalDate 表示了一个确切的日期,比如 2014-03-11。该对象值是不可变的,用起来和LocalTime基本一致。下面的例子展示了如何给Date对象加减天/月/年。另外要注意的是这些对象是不可变的,操作返回的总是一个新实例。

LocalDate today = LocalDate.now(); 
LocalDate tomorrow = today.plus(1, ChronoUnit.DAYS); 
LocalDate yesterday = tomorrow.minusDays(2); 
LocalDate independenceDay = LocalDate.of(2014, Month.JULY, 4); DayOfWeek dayOfWeek = independenceDay.getDayOfWeek();

System.out.println(dayOfWeek); // FRIDAY

从字符串解析一个LocalDate类型和解析LocalTime一样简单:

DateTimeFormatter germanFormatter = DateTimeFormatter  
   .ofLocalizedDate(FormatStyle.MEDIUM)  
   .withLocale(Locale.GERMAN); 
LocalDate xmas = LocalDate.parse("24.12.2014", germanFormatter); 
System.out.println(xmas); // 2014-12-24

5.5 LocalDateTime 本地日期时间

LocalDateTime 同时表示了时间和日期,相当于前两节内容合并到一个对象上了。LocalDateTime和LocalTime还有LocalDate一样,都是不可变的。LocalDateTime提供了一些能访问具体字段的方法。

LocalDateTime sylvester = LocalDateTime.of(2014, Month.DECEMBER, 31, 23, 59, 59); 
DayOfWeek dayOfWeek = sylvester.getDayOfWeek(); 
System.out.println(dayOfWeek); // WEDNESDAY Month month = 
sylvester.getMonth(); 
System.out.println(month); // DECEMBER long 
minuteOfDay = sylvester.getLong(ChronoField.MINUTE_OF_DAY); 
System.out.println(minuteOfDay); // 1439

只要附加上时区信息,就可以将其转换为一个时间点Instant对象,Instant时间点对象可以很容易的转换为老式的java.util.Date。

Instant instant = sylvester  
   .atZone(ZoneId.systemDefault())  
   .toInstant(); 
Date legacyDate = Date.from(instant); 
System.out.println(legacyDate); // Wed Dec 31 23:59:59 CET 2014

格式化LocalDateTime和格式化时间和日期一样的,除了使用预定义好的格式外,我们也可以自己定义格式:

DateTimeFormatter formatter = DateTimeFormatter  
   .ofPattern("MMM dd, yyyy - HH:mm"); 
LocalDateTime parsed = LocalDateTime.parse("Nov 03, 2014 - 07:13", 
formatter); 
String string = formatter.format(parsed); 
System.out.println(string); // Nov 03, 2014 - 07:13

和java.text.NumberFormat不一样的是新版的DateTimeFormatter是不可变的,所以它是线程安全的。

6. Annotation 注解

6.1 多重注解

在Java 8中支持多重注解了,先看个例子来理解一下是什么意思。

首先定义一个包装类Hints注解用来放置一组具体的Hint注解:

@interface Hints {  Hint[] value(); } 
@Repeatable(Hints.class) 
@interface Hint {  String value(); }

Java 8允许我们把同一个类型的注解使用多次,只需要给该注解标注一下@Repeatable即可。

例子:

  1. 使用包装类当容器来存多个注解(老方法) java @Hints({@Hint("hint1"), @Hint("hint2")}) class Person {}
  1. 使用多重注解(新方法) java @Hint("hint1") @Hint("hint2") class Person {} 第二个例子里java编译器会隐性的帮你定义好@Hints注解,了解这一点有助于你用反射来获取这些信息:
    java
    Hint hint = Person.class.getAnnotation(Hint.class);
    System.out.println(hint); // null
    Hints hints1 =
    Person.class.getAnnotation(Hints.class);
    System.out.println(hints1.value().length); // 2
    Hint[] hints2 =
    Person.class.getAnnotationsByType(Hint.class);
    System.out.println(hints2.length); // 2即便我们没有在Person类上定义@Hints注解,我们还是可以通过 getAnnotation(Hints.class) 来获取 @Hints注解,更加方便的方法是使用 getAnnotationsByType 可以直接获取到所有的@Hint注解。

6.2 新的target

另外Java 8的注解还增加到两种新的target上了:

@Target({ElementType.TYPE_PARAMETER, ElementType.TYPE_USE}) @interface MyAnnotation {}

7. more

JDK 1.8里还有很多很有用的东西,比如Arrays.parallelSort, StampedLock和CompletableFuture等等。

https://www.kancloud.cn/wizardforcel/modern-java-zh/141721

 

常见数据结构与算法整理总结(下)

这篇文章是常见数据结构与算法整理总结的下篇,上一篇主要是对常见的数据结构进行集中总结,这篇主要是总结一些常见的算法相关内容,文章中如有错误,欢迎指出。

一、概述
二、查找算法
三、排序算法
四、其它算法
五、常见算法题
六、总结

一、概述

以前看到这样一句话,语言只是工具,算法才是程序设计的灵魂。的确,算法在计算机科学中的地位真的很重要,在很多大公司的笔试面试中,算法掌握程度的考察都占据了很大一部分。不管是为了面试还是自身编程能力的提升,花时间去研究常见的算法还是很有必要的。下面是自己对于算法这部分的学习总结。

算法简介

算法是指解题方案的准确而完整的描述,是一系列解决问题的清晰指令,算法代表着用系统的方法描述解决问题的策略机制。对于同一个问题的解决,可能会存在着不同的算法,为了衡量一个算法的优劣,提出了空间复杂度与时间复杂度这两个概念。

时间复杂度

一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间度量记为 ** T(n) = O(f(n)) **,它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。这里需要重点理解这个增长率。

举个例子,看下面3个代码:

1、{++x;}

2、for(i = 1; i <= n; i++) { ++x; }

3、for(j = 1; j <= n; j++) 
        for(j = 1; j <= n; j++) 
             { ++x; }

上述含有 ++x 操作的语句的频度分别为1 、n 、n^2,

假设问题的规模扩大了n倍,3个代码的增长率分别是1 、n 、n^2

它们的时间复杂度分别为O(1)、O(n )、O(n^2)

空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度,记做S(n)=O(f(n))。一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。

二、查找算法

查找和排序是最基础也是最重要的两类算法,熟练地掌握这两类算法,并能对这些算法的性能进行分析很重要,这两类算法中主要包括二分查找、快速排序、归并排序等等。

顺序查找

顺序查找又称线性查找。它的过程为:从查找表的最后一个元素开始逐个与给定关键字比较,若某个记录的关键字和给定值比较相等,则查找成功,否则,若直至第一个记录,其关键字和给定值比较都不等,则表明表中没有所查记录查找不成功,它的缺点是效率低下。

二分查找

  • 简介

二分查找又称折半查找,对于有序表来说,它的优点是比较次数少,查找速度快,平均性能好。

二分查找的基本思想是将n个元素分成大致相等的两部分,取a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x。

二分查找的时间复杂度为O(logn)

  • 实现
//给定有序查找表array 二分查找给定的值data
//查找成功返回下标 查找失败返回-1

static int funBinSearch(int[] array, int data) {

    int low = 0;
    int high = array.length - 1;

    while (low <= high) {

        int mid = (low + high) / 2;

        if (data == array[mid]) {
            return mid;
        } else if (data < array[mid]) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return -1;
}

三、排序算法

排序是计算机程序设计中的一种重要操作,它的功能是将一个数据元素(或记录)的任意序列,重新排列成一个按关键字有序的序列。下面主要对一些常见的排序算法做介绍,并分析它们的时空复杂度。

常见排序算法

常见排序算法性能比较:

图片来自网络

上面这张表中有稳定性这一项,排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前和排序后他们的相对位置不发生变化。

下面从冒泡排序开始逐一介绍。

冒泡排序

  • 简介

冒泡排序的基本思想是:设排序序列的记录个数为n,进行n-1次遍历,每次遍历从开始位置依次往后比较前后相邻元素,这样较大的元素往后移,n-1次遍历结束后,序列有序。

例如,对序列(3,2,1,5)进行排序的过程是:共进行3次遍历,第1次遍历时先比较3和2,交换,继续比较3和1,交换,再比较3和5,不交换,这样第1次遍历结束,最大值5在最后的位置,得到序列(2,1,3,5)。第2次遍历时先比较2和1,交换,继续比较2和3,不交换,第2次遍历结束时次大值3在倒数第2的位置,得到序列(1,2,3,5),第3次遍历时,先比较1和2,不交换,得到最终有序序列(1,2,3,5)。

需要注意的是,如果在某次遍历中没有发生交换,那么就不必进行下次遍历,因为序列已经有序。

  • 实现
// 冒泡排序 注意 flag 的作用
static void funBubbleSort(int[] array) {

    boolean flag = true;

    for (int i = 0; i < array.length - 1 && flag; i++) {

        flag = false;

        for (int j = 0; j < array.length - 1 - i; j++) {

            if (array[j] > array[j + 1]) {

                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;

                flag = true;
            }
        }
    }

    for (int i = 0; i < array.length; i++) {
        System.out.println(array[i]);
    }
}
  • 分析

最佳情况下冒泡排序只需一次遍历就能确定数组已经排好序,不需要进行下一次遍历,所以最佳情况下,时间复杂度为** O(n) **。

最坏情况下冒泡排序需要n-1次遍历,第一次遍历需要比较n-1次,第二次遍历需要n-2次,…,最后一次需要比较1次,最差情况下时间复杂度为** O(n^2) **。

简单选择排序

  • 简介

简单选择排序的思想是:设排序序列的记录个数为n,进行n-1次选择,每次在n-i+1(i = 1,2,…,n-1)个记录中选择关键字最小的记录作为有效序列中的第i个记录。

例如,排序序列(3,2,1,5)的过程是,进行3次选择,第1次选择在4个记录中选择最小的值为1,放在第1个位置,得到序列(1,3,2,5),第2次选择从位置1开始的3个元素中选择最小的值2放在第2个位置,得到有序序列(1,2,3,5),第3次选择因为最小的值3已经在第3个位置不需要操作,最后得到有序序列(1,2,3,5)。

  • 实现
static void funSelectionSort(int[] array) {

    for (int i = 0; i < array.length - 1; i++) {

        int mink = i;

            // 每次从未排序数组中找到最小值的坐标
        for (int j = i + 1; j < array.length; j++) {

            if (array[j] < array[mink]) {
                mink = j;
            }
        }

        // 将最小值放在最前面
        if (mink != i) {
            int temp = array[mink];
            array[mink] = array[i];
            array[i] = temp;
        }
    }

    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
}
  • 分析

简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况** 无关。当i=1时,需进行n-1次比较;当i=2时,需进行n-2次比较;依次类推,共需要进行的比较次数是(n-1)+(n-2)+…+2+1=n(n-1)/2,即进行比较操作的时间复杂度为 O(n^2) ,进行移动操作的时间复杂度为 O(n) 。总的时间复杂度为 O(n^2) **。

最好情况下,即待排序记录初始状态就已经是正序排列了,则不需要移动记录。最坏情况下,即待排序记录初始状态是按第一条记录最大,之后的记录从小到大顺序排列,则需要移动记录的次数最多为3(n-1)。

简单选择排序是不稳定排序。

直接插入排序

  • 简介

直接插入的思想是:是将一个记录插入到已排好序的有序表中,从而得到一个新的、记录数增1的有序表。

例如,排序序列(3,2,1,5)的过程是,初始时有序序列为(3),然后从位置1开始,先访问到2,将2插入到3前面,得到有序序列(2,3),之后访问1,找到合适的插入位置后得到有序序列(1,2,3),最后访问5,得到最终有序序列(1,2,3,5).

  • 实现
static void funDInsertSort(int[] array) {

    int j;

    for (int i = 1; i < array.length; i++) {

        int temp = array[i];

        j = i - 1;

        while (j > -1 && temp < array[j]) {

            array[j + 1] = array[j];

            j--;
        }

        array[j + 1] = temp;

    }

    for (int i = 0; i < array.length; i++) {
        System.out.print(array[i] + " ");
    }
}
  • 分析

最好情况下,当待排序序列中记录已经有序时,则需要n-1次比较,不需要移动,时间复杂度为** O(n) 。最差情况下,当待排序序列中所有记录正好逆序时,则比较次数和移动次数都达到最大值,时间复杂度为 O(n^2) 。平均情况下,时间复杂度为 O(n^2) **。

希尔排序

希尔排序又称“缩小增量排序”,它是基于直接插入排序的以下两点性质而提出的一种改进:(1) 直接插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。(2) 直接插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。点击查看更多关于希尔排序的内容

归并排序

  • 简介

归并排序是分治法的一个典型应用,它的主要思想是:将待排序序列分为两部分,对每部分递归地应用归并排序,在两部分都排好序后进行合并。

例如,排序序列(3,2,8,6,7,9,1,5)的过程是,先将序列分为两部分,(3,2,8,6)和(7,9,1,5),然后对两部分分别应用归并排序,第1部分(3,2,8,6),第2部分(7,9,1,5),对两个部分分别进行归并排序,第1部分继续分为(3,2)和(8,6),(3,2)继续分为(3)和(2),(8,6)继续分为(8)和(6),之后进行合并得到(2,3),(6,8),再合并得到(2,3,6,8),第2部分进行归并排序得到(1,5,7,9),最后合并两部分得到(1,2,3,5,6,7,8,9)。

  • 实现
    //归并排序
    static void funMergeSort(int[] array) {

        if (array.length > 1) {

            int length1 = array.length / 2;
            int[] array1 = new int[length1];
            System.arraycopy(array, 0, array1, 0, length1);
            funMergeSort(array1);

            int length2 = array.length - length1;
            int[] array2 = new int[length2];
            System.arraycopy(array, length1, array2, 0, length2);
            funMergeSort(array2);

            int[] datas = merge(array1, array2);
            System.arraycopy(datas, 0, array, 0, array.length);
        }

    }

    //合并两个数组
    static int[] merge(int[] list1, int[] list2) {

        int[] list3 = new int[list1.length + list2.length];

        int count1 = 0;
        int count2 = 0;
        int count3 = 0;

        while (count1 < list1.length && count2 < list2.length) {

            if (list1[count1] < list2[count2]) {
                list3[count3++] = list1[count1++];
            } else {
                list3[count3++] = list2[count2++];
            }
        }

        while (count1 < list1.length) {
            list3[count3++] = list1[count1++];
        }

        while (count2 < list2.length) {
            list3[count3++] = list2[count2++];
        }

        return list3;
    }
  • 分析

归并排序的时间复杂度为O(nlogn),它是一种稳定的排序,java.util.Arrays类中的sort方法就是使用归并排序的变体来实现的。

快速排序

  • 简介

快速排序的主要思想是:在待排序的序列中选择一个称为主元的元素,将数组分为两部分,使得第一部分中的所有元素都小于或等于主元,而第二部分中的所有元素都大于主元,然后对两部分递归地应用快速排序算法。

  • 实现
// 快速排序
static void funQuickSort(int[] mdata, int start, int end) {
    if (end > start) {
        int pivotIndex = quickSortPartition(mdata, start, end);
        funQuickSort(mdata, start, pivotIndex - 1);
        funQuickSort(mdata, pivotIndex + 1, end);
    }
}

// 快速排序前的划分
static int quickSortPartition(int[] list, int first, int last) {

    int pivot = list[first];
    int low = first + 1;
    int high = last;

    while (high > low) {

        while (low <= high && list[low] <= pivot) {
            low++;
        }

        while (low <= high && list[high] > pivot) {
            high--;
        }

        if (high > low) {
            int temp = list[high];
            list[high] = list[low];
            list[low] = temp;
        }
    }

    while (high > first && list[high] >= pivot) {
        high--;
    }

    if (pivot > list[high]) {
        list[first] = list[high];
        list[high] = pivot;
        return high;
    } else {
        return first;
    }
}
  • 分析

在快速排序算法中,比较关键的一个部分是主元的选择。在最差情况下,划分由n个元素构成的数组需要进行n次比较和n次移动,因此划分需要的时间是O(n)。在最差情况下,每次主元会将数组划分为一个大的子数组和一个空数组,这个大的子数组的规模是在上次划分的子数组的规模上减1,这样在最差情况下算法需要(n-1)+(n-2)+…+1= ** O(n^2) **时间。

最佳情况下,每次主元将数组划分为规模大致相等的两部分,时间复杂度为** O(nlogn) **。

堆排序

  • 简介

在介绍堆排序之前首先需要了解堆的定义,n个关键字序列K1,K2,…,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质):(1) ki <= k(2i)且 ki <= k(2i+1) (1 ≤ i≤ n/2),当然,这是小根堆,大根堆则换成>=号。

如果将上面满足堆性质的序列看成是一个完全二叉树,则堆的含义表明,完全二叉树中所有的非终端节点的值均不大于(或不小于)其左右孩子节点的值。

堆排序的主要思想是:给定一个待排序序列,首先经过一次调整,将序列构建成一个大顶堆,此时第一个元素是最大的元素,将其和序列的最后一个元素交换,然后对前n-1个元素调整为大顶堆,再将其第一个元素和末尾元素交换,这样最后即可得到有序序列。

  • 实现
//堆排序
public class TestHeapSort {

    public static void main(String[] args) {
        int arr[] = { 5, 6, 1, 0, 2, 9 };
        heapsort(arr, 6);
        System.out.println(Arrays.toString(arr));
    }

    static void heapsort(int arr[], int n) {

        // 先建大顶堆
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapAdjust(arr, i, n);
        }

        for (int i = 0; i < n - 1; i++) {
            swap(arr, 0, n - i - 1);
            heapAdjust(arr, 0, n - i - 1);
        }
    }

    // 交换两个数
    static void swap(int arr[], int low, int high) {
        int temp = arr[low];
        arr[low] = arr[high];
        arr[high] = temp;
    }

    // 调整堆
    static void heapAdjust(int arr[], int index, int n) {

        int temp = arr[index];

        int child = 0;

        while (index * 2 + 1 < n) {
                        
            child = index * 2 + 1;
                        
            // child为左右孩子中较大的那个
            if (child != n - 1 && arr[child] < arr[child + 1]) {
                child++;
            }
            // 如果指定节点大于较大的孩子 不需要调整
            if (temp > arr[child]) {
                break;
            } else {
                // 否则继续往下判断孩子的孩子 直到找到合适的位置
                arr[index] = arr[child];
                index = child;
            }
        }

        arr[index] = temp;
    }
}

  • 分析

由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。堆排序时间复杂度也为O(nlogn),空间复杂度为O(1)。它是不稳定的排序方法。与快排和归并排序相比,堆排序在最差情况下的时间复杂度优于快排,空间效率高于归并排序。

四、其它算法

在上面的篇幅中,主要是对查找和常见的几种排序算法作了介绍,这些内容都是基础的但是必须掌握的内容,尤其是二分查找、快排、堆排、归并排序这几个更是面试高频考察点。(这里不禁想起百度一面的时候让我写二分查找和堆排序,二分查找还行,然而堆排序当时一脸懵逼…)下面主要是介绍一些常见的其它算法。

递归

  • 简介

在平常解决一些编程或者做一些算法题的时候,经常会用到递归。程序调用自身的编程技巧称为递归。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。上面介绍的快速排序和归并排序都用到了递归的思想。

  • 经典例子

斐波那契数列,又称黄金分割数列、因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入,故又称为“兔子数列”,指的是这样一个数列:0、1、1、2、3、5、8、13、21、34、……在数学上,斐波纳契数列以如下被以递归的方法定义:F(0)=0,F(1)=1,F(n)=F(n-1)+F(n-2)(n≥2,n∈N*)。

//斐波那契数列 递归实现
static long funFib(long index) {

    if (index == 0) {
        return 0;
    } else if (index == 1) {
        return 1;
    } else {
        return funFib(index - 1) + funFib(index - 2);
    }
}

上面代码是斐波那契数列的递归实现,然而我们不难得到它的时间复杂度是O(2^n),递归有时候可以很方便地解决一些问题,但是它也会带来一些效率上的问题。下面的代码是求斐波那契数列的另一种方式,效率比递归方法的效率高。

static long funFib2(long index) {

    long f0 = 0;
    long f1 = 1;
    long f2 = 1;

    if (index == 0) {
        return f0;
    } else if (index == 1) {
        return f1;
    } else if (index == 2) {
        return f2;
    }

    for (int i = 3; i <= index; i++) {
        f0 = f1;
        f1 = f2;
        f2 = f0 + f1;
    }

    return f2;
}

分治算法

分治算法的思想是将待解决的问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立最终的解。分治算法中关键地一步其实就是递归地求解子问题。关于分治算法的一个典型例子就是上面介绍的归并排序。查看更多关于分治算法的内容

动态规划

动态规划与分治方法相似,都是通过组合子问题的解来求解待解决的问题。但是,分治算法将问题划分为互不相交的子问题,递归地求解子问题,再将它们的解组合起来,而动态规划应用于子问题重叠的情况,即不同的子问题具有公共的子子问题。动态规划方法通常用来求解最优化问题。查看更多关于动态规划的内容

动态规划典型的一个例子是最长公共子序列问题。

常见的算法还有很多,比如贪心算法,回溯算法等等,这里都不再详细介绍,想要熟练掌握,还是要靠刷题,刷题,刷题,然后总结。

五、常见算法题

下面是一些常见的算法题汇总。

不使用临时变量交换两个数

static void funSwapTwo(int a, int b) {

    a = a ^ b;
    b = b ^ a;
    a = a ^ b;

    System.out.println(a + " " + b);
}

判断一个数是否为素数

static boolean funIsPrime(int m) {

    boolean flag = true;

    if (m == 1) {
        flag = false;
    } else {

        for (int i = 2; i <= Math.sqrt(m); i++) {
            if (m % i == 0) {
                flag = false;
                break;
            }
        }
    }

    return flag;
}

其它算法题

1、15道使用频率极高的基础算法题
2、二叉树相关算法题
3、链表相关算法题
4、字符串相关算法问题

六、总结

以上就是自己对常见的算法相关内容的总结,算法虐我千百遍,我待算法如初恋,革命尚未成功,同志仍需刷题,加油。

常见数据结构与算法整理总结(上)

数据结构是以某种形式将数据组织在一起的集合,它不仅存储数据,还支持访问和处理数据的操作。算法是为求解一个问题需要遵循的、被清楚指定的简单指令的集合。下面是自己整理的常用数据结构与算法相关内容,如有错误,欢迎指出。

为了便于描述,文中涉及到的代码部分都是用Java语言编写的,其实Java本身对常见的几种数据结构,线性表、栈、队列等都提供了较好的实现,就是我们经常用到的Java集合框架,有需要的可以阅读这篇文章。Java – 集合框架完全解析

一、线性表
  1.数组实现
  2.链表
二、栈与队列
三、树与二叉树
  1.树
  2.二叉树基本概念
  3.二叉查找树
  4.平衡二叉树
  5.红黑树
四、图
五、总结

一、线性表

线性表是最常用且最简单的一种数据结构,它是n个数据元素的有限序列。

实现线性表的方式一般有两种,一种是使用数组存储线性表的元素,即用一组连续的存储单元依次存储线性表的数据元素。另一种是使用链表存储线性表的元素,即用一组任意的存储单元存储线性表的数据元素(存储单元可以是连续的,也可以是不连续的)。

数组实现

数组是一种大小固定的数据结构,对线性表的所有操作都可以通过数组来实现。虽然数组一旦创建之后,它的大小就无法改变了,但是当数组不能再存储线性表中的新元素时,我们可以创建一个新的大的数组来替换当前数组。这样就可以使用数组实现动态的数据结构。

  • 代码1 创建一个更大的数组来替换当前数组
int[] oldArray = new int[10];
        
int[] newArray = new int[20];
        
for (int i = 0; i < oldArray.length; i++) {
    newArray[i] = oldArray[i];
}

// 也可以使用System.arraycopy方法来实现数组间的复制     
// System.arraycopy(oldArray, 0, newArray, 0, oldArray.length);
        
oldArray = newArray;
  • 代码2 在数组位置index上添加元素e
//oldArray 表示当前存储元素的数组
//size 表示当前元素个数
public void add(int index, int e) {

    if (index > size || index < 0) {
        System.out.println("位置不合法...");
    }

    //如果数组已经满了 就扩容
    if (size >= oldArray.length) {
        // 扩容函数可参考代码1
    }

    for (int i = size - 1; i >= index; i--) {
        oldArray[i + 1] = oldArray[i];
    }

    //将数组elementData从位置index的所有元素往后移一位
    // System.arraycopy(oldArray, index, oldArray, index + 1,size - index);

    oldArray[index] = e;

    size++;
}

上面简单写出了数组实现线性表的两个典型函数,具体我们可以参考Java里面的ArrayList集合类的源码。数组实现的线性表优点在于可以通过下标来访问或者修改元素,比较高效,主要缺点在于插入和删除的花费开销较大,比如当在第一个位置前插入一个元素,那么首先要把所有的元素往后移动一个位置。为了提高在任意位置添加或者删除元素的效率,可以采用链式结构来实现线性表。

链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成,这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next,Next指向下一个节点,这样当添加或者删除时,只需要改变相关节点的Next的指向,效率很高。

单链表的结构

下面主要用代码来展示链表的一些基本操作,需要注意的是,这里主要是以单链表为例,暂时不考虑双链表和循环链表。

  • 代码3 链表的节点
class Node<E> {

    E item;
    Node<E> next;
    
    //构造函数
    Node(E element) {
       this.item = element;
       this.next = null;
   }
}
  • 代码4 定义好节点后,使用前一般是对头节点和尾节点进行初始化
//头节点和尾节点都为空 链表为空
Node<E> head = null;
Node<E> tail = null;
  • 代码5 空链表创建一个新节点
//创建一个新的节点 并让head指向此节点
head = new Node("nodedata1");

//让尾节点也指向此节点
tail = head;
  • 代码6 链表追加一个节点
//创建新节点 同时和最后一个节点连接起来
tail.next = new Node("node1data2");

//尾节点指向新的节点
tail = tail.next;
  • 代码7 顺序遍历链表
Node<String> current = head;
while (current != null) {
    System.out.println(current.item);
    current = current.next;
}
  • 代码8 倒序遍历链表
static void printListRev(Node<String> head) {
//倒序遍历链表主要用了递归的思想
    if (head != null) {
        printListRev(head.next);
        System.out.println(head.item);
    }
}
  • 代码 单链表反转
//单链表反转 主要是逐一改变两个节点间的链接关系来完成
static Node<String> revList(Node<String> head) {

    if (head == null) {
        return null;
    }

    Node<String> nodeResult = null;

    Node<String> nodePre = null;
    Node<String> current = head;

    while (current != null) {

        Node<String> nodeNext = current.next;

        if (nodeNext == null) {
            nodeResult = current;
        }

        current.next = nodePre;
        nodePre = current;
        current = nodeNext;
    }

    return nodeResult;
}

上面的几段代码主要展示了链表的几个基本操作,还有很多像获取指定元素,移除元素等操作大家可以自己完成,写这些代码的时候一定要理清节点之间关系,这样才不容易出错。

链表的实现还有其它的方式,常见的有循环单链表,双向链表,循环双向链表。 循环单链表 主要是链表的最后一个节点指向第一个节点,整体构成一个链环。 双向链表 主要是节点中包含两个指针部分,一个指向前驱元,一个指向后继元,JDK中LinkedList集合类的实现就是双向链表。** 循环双向链表** 是最后一个节点指向第一个节点。

二、栈与队列

栈和队列也是比较常见的数据结构,它们是比较特殊的线性表,因为对于栈来说,访问、插入和删除元素只能在栈顶进行,对于队列来说,元素只能从队列尾插入,从队列头访问和删除。

栈是限制插入和删除只能在一个位置上进行的表,该位置是表的末端,叫作栈顶,对栈的基本操作有push(进栈)和pop(出栈),前者相当于插入,后者相当于删除最后一个元素。栈有时又叫作LIFO(Last In First Out)表,即后进先出。

栈的模型

下面我们看一道经典题目,加深对栈的理解。

关于栈的一道经典题目

上图中的答案是C,其中的原理可以好好想一想。

因为栈也是一个表,所以任何实现表的方法都能实现栈。我们打开JDK中的类Stack的源码,可以看到它就是继承类Vector的。当然,Stack是Java2前的容器类,现在我们可以使用LinkedList来进行栈的所有操作。

队列

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。

队列示意图

我们可以使用链表来实现队列,下面代码简单展示了利用LinkedList来实现队列类。

  • 代码9 简单实现队列类
public class MyQueue<E> {

    private LinkedList<E> list = new LinkedList<>();

    // 入队
    public void enqueue(E e) {
        list.addLast(e);
    }

    // 出队
    public E dequeue() {
        return list.removeFirst();
    }
}

普通的队列是一种先进先出的数据结构,而优先队列中,元素都被赋予优先级。当访问元素的时候,具有最高优先级的元素最先被删除。优先队列在生活中的应用还是比较多的,比如医院的急症室为病人赋予优先级,具有最高优先级的病人最先得到治疗。在Java集合框架中,类PriorityQueue就是优先队列的实现类,具体大家可以去阅读源码。

三、树与二叉树

树型结构是一类非常重要的非线性数据结构,其中以树和二叉树最为常用。在介绍二叉树之前,我们先简单了解一下树的相关内容。

** 树 是由n(n>=1)个有限节点组成一个具有层次关系的集合。它具有以下特点:每个节点有零个或多个子节点;没有父节点的节点称为节点;每一个非根节点有且只有一个 父节点 **;除了根节点外,每个子节点可以分为多个不相交的子树。

树的结构

二叉树基本概念

  • 定义

二叉树是每个节点最多有两棵子树的树结构。通常子树被称作“左子树”和“右子树”。二叉树常被用于实现二叉查找树和二叉堆。

  • 相关性质

二叉树的每个结点至多只有2棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。

二叉树的第i层至多有2(i-1)个结点;深度为k的二叉树至多有2k-1个结点。

一棵深度为k,且有2^k-1个节点的二叉树称之为** 满二叉树 **;

深度为k,有n个节点的二叉树,当且仅当其每一个节点都与深度为k的满二叉树中,序号为1至n的节点对应时,称之为** 完全二叉树 **。

若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

  • 三种遍历方法

在二叉树的一些应用中,常常要求在树中查找具有某种特征的节点,或者对树中全部节点进行某种处理,这就涉及到二叉树的遍历。二叉树主要是由3个基本单元组成,根节点、左子树和右子树。如果限定先左后右,那么根据这三个部分遍历的顺序不同,可以分为先序遍历、中序遍历和后续遍历三种。

(1) 先序遍历 若二叉树为空,则空操作,否则先访问根节点,再先序遍历左子树,最后先序遍历右子树。
(2) 中序遍历 若二叉树为空,则空操作,否则先中序遍历左子树,再访问根节点,最后中序遍历右子树。
(3) 后序遍历 若二叉树为空,则空操作,否则先后序遍历左子树访问根节点,再后序遍历右子树,最后访问根节点。

给定二叉树写出三种遍历结果
  • 树和二叉树的区别

(1) 二叉树每个节点最多有2个子节点,树则无限制。
(2) 二叉树中节点的子树分为左子树和右子树,即使某节点只有一棵子树,也要指明该子树是左子树还是右子树,即二叉树是有序的。
(3) 树决不能为空,它至少有一个节点,而一棵二叉树可以是空的。

上面我们主要对二叉树的相关概念进行了介绍,下面我们将从二叉查找树开始,介绍二叉树的几种常见类型,同时将之前的理论部分用代码实现出来。

二叉查找树

  • 定义

二叉查找树就是二叉排序树,也叫二叉搜索树。二叉查找树或者是一棵空树,或者是具有下列性质的二叉树:

(1) 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2) 若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3) 左、右子树也分别为二叉排序树;
(4) 没有键值相等的结点。

典型的二叉查找树的构建过程
  • 性能分析

对于二叉查找树来说,当给定值相同但顺序不同时,所构建的二叉查找树形态是不同的,下面看一个例子。

不同形态平衡二叉树的ASL不同

可以看到,含有n个节点的二叉查找树的平均查找长度和树的形态有关。最坏情况下,当先后插入的关键字有序时,构成的二叉查找树蜕变为单支树,树的深度为n,其平均查找长度(n+1)/2(和顺序查找相同),最好的情况是二叉查找树的形态和折半查找的判定树相同,其平均查找长度和log2(n)成正比。平均情况下,二叉查找树的平均查找长度和logn是等数量级的,所以为了获得更好的性能,通常在二叉查找树的构建过程需要进行“平衡化处理”,之后我们将介绍平衡二叉树和红黑树,这些均可以使查找树的高度为O(log(n))。

  • 代码10 二叉树的节点

class TreeNode<E> {

    E element;
    TreeNode<E> left;
    TreeNode<E> right;

    public TreeNode(E e) {
        element = e;
    }
}

二叉查找树的三种遍历都可以直接用递归的方法来实现:

  • 代码12 先序遍历
protected void preorder(TreeNode<E> root) {

    if (root == null)
        return;

    System.out.println(root.element + " ");

    preorder(root.left);

    preorder(root.right);
}
  • 代码13 中序遍历
protected void inorder(TreeNode<E> root) {

    if (root == null)
        return;

    inorder(root.left);

    System.out.println(root.element + " ");

    inorder(root.right);
}
  • 代码14 后序遍历
protected void postorder(TreeNode<E> root) {

    if (root == null)
        return;

    postorder(root.left);

    postorder(root.right);

    System.out.println(root.element + " ");
}
  • 代码15 二叉查找树的简单实现
/**
 * @author JackalTsc
 */
public class MyBinSearchTree<E extends Comparable<E>> {

    // 根
    private TreeNode<E> root;

    // 默认构造函数
    public MyBinSearchTree() {
    }

    // 二叉查找树的搜索
    public boolean search(E e) {

        TreeNode<E> current = root;

        while (current != null) {

            if (e.compareTo(current.element) < 0) {
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                current = current.right;
            } else {
                return true;
            }
        }

        return false;
    }

    // 二叉查找树的插入
    public boolean insert(E e) {

        // 如果之前是空二叉树 插入的元素就作为根节点
        if (root == null) {
            root = createNewNode(e);
        } else {
            // 否则就从根节点开始遍历 直到找到合适的父节点
            TreeNode<E> parent = null;
            TreeNode<E> current = root;
            while (current != null) {
                if (e.compareTo(current.element) < 0) {
                    parent = current;
                    current = current.left;
                } else if (e.compareTo(current.element) > 0) {
                    parent = current;
                    current = current.right;
                } else {
                    return false;
                }
            }
            // 插入
            if (e.compareTo(parent.element) < 0) {
                parent.left = createNewNode(e);
            } else {
                parent.right = createNewNode(e);
            }
        }
        return true;
    }

    // 创建新的节点
    protected TreeNode<E> createNewNode(E e) {
        return new TreeNode(e);
    }

}

// 二叉树的节点
class TreeNode<E extends Comparable<E>> {

    E element;
    TreeNode<E> left;
    TreeNode<E> right;

    public TreeNode(E e) {
        element = e;
    }
}

上面的代码15主要展示了一个自己实现的简单的二叉查找树,其中包括了几个常见的操作,当然更多的操作还是需要大家自己去完成。因为在二叉查找树中删除节点的操作比较复杂,所以下面我详细介绍一下这里。

  • 二叉查找树中删除节点分析

要在二叉查找树中删除一个元素,首先需要定位包含该元素的节点,以及它的父节点。假设current指向二叉查找树中包含该元素的节点,而parent指向current节点的父节点,current节点可能是parent节点的左孩子,也可能是右孩子。这里需要考虑两种情况:

  1. current节点没有左孩子,那么只需要将parent节点和current节点的右孩子相连。
  2. current节点有一个左孩子,假设rightMost指向包含current节点的左子树中最大元素的节点,而parentOfRightMost指向rightMost节点的父节点。那么先使用rightMost节点中的元素值替换current节点中的元素值,将parentOfRightMost节点和rightMost节点的左孩子相连,然后删除rightMost节点。
    // 二叉搜索树删除节点
    public boolean delete(E e) {

        TreeNode<E> parent = null;
        TreeNode<E> current = root;

        // 找到要删除的节点的位置
        while (current != null) {
            if (e.compareTo(current.element) < 0) {
                parent = current;
                current = current.left;
            } else if (e.compareTo(current.element) > 0) {
                parent = current;
                current = current.right;
            } else {
                break;
            }
        }

        // 没找到要删除的节点
        if (current == null) {
            return false;
        }

        // 考虑第一种情况
        if (current.left == null) {
            if (parent == null) {
                root = current.right;
            } else {
                if (e.compareTo(parent.element) < 0) {
                    parent.left = current.right;
                } else {
                    parent.right = current.right;
                }
            }
        } else { // 考虑第二种情况
            TreeNode<E> parentOfRightMost = current;
            TreeNode<E> rightMost = current.left;
            // 找到左子树中最大的元素节点
            while (rightMost.right != null) {
                parentOfRightMost = rightMost;
                rightMost = rightMost.right;
            }

            // 替换
            current.element = rightMost.element;

            // parentOfRightMost和rightMost左孩子相连
            if (parentOfRightMost.right == rightMost) {
                parentOfRightMost.right = rightMost.left;
            } else {
                parentOfRightMost.left = rightMost.left;
            }
        }

        return true;
    }

平衡二叉树

平衡二叉树又称AVL树,它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。

平衡二叉树

AVL树是最先发明的自平衡二叉查找树算法。在AVL中任何节点的两个儿子子树的高度最大差别为1,所以它也被称为高度平衡树,n个结点的AVL树最大深度约1.44log2n。查找、插入和删除在平均和最坏情况下都是O(log n)。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

红黑树

红黑树是平衡二叉树的一种,它保证在最坏情况下基本动态集合操作的事件复杂度为O(log n)。红黑树和平衡二叉树区别如下:

(1) 红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。
(2) 平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。点击查看更多

四、图

  • 简介

图是一种较线性表和树更为复杂的数据结构,在线性表中,数据元素之间仅有线性关系,在树形结构中,数据元素之间有着明显的层次关系,而在图形结构中,节点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。图的应用相当广泛,特别是近年来的迅速发展,已经渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其他分支中。

  • 相关阅读

因为图这部分的内容还是比较多的,这里就不详细介绍了,有需要的可以自己搜索相关资料。

(1) 《百度百科对图的介绍》
(2) 《数据结构之图(存储结构、遍历)》

五、总结

到这里,关于常见的数据结构的整理就结束了,断断续续大概花了两天时间写完,在总结的过程中,通过查阅相关资料,结合书本内容,收获还是很大的,在下一篇博客中将会介绍常用数据结构与算法整理总结(下)之算法篇,欢迎大家关注。