发表于

一、分布式任务调度的背景

无论是互联网应用或者企业级应用，都充斥着大量的批处理任务。我们常常需要一些任务调度系统来帮助解决问题。随着微服务化架构的逐步演进，单体架构逐渐演变为分布式、微服务架构。在此背景下，很多原先的任务调度平台已经不能满足业务系统的需求，于是出现了一些基于分布式的任务调度平台。

1.1 分布式任务调度的演进

在实际业务开发过程中，很多时候我们无可避免地需要使用一些定时任务来解决问题。通常我们会有多种解决方案：使用 Crontab 或 SpringCron (当然这种情况可能机器很少而且任务简单又不是很多的情况下)。然而，当应用复杂度升高、定时任务数量增多且任务之间产生依赖关系时，Crontab 进行定时任务的管理配置就会非常混乱，严重影响工作效率。这时就会产生一系列问题：

  • 任务管理混乱，生命周期无法统一协调管理；
  • 任务之间如果存在依赖关系，难以编排。

随着互联网的发展，分布式服务架构势越来越流行。相应的也需要一个分布式任务调度系统来管理分布式架构中的定时任务。

1.2 分布式任务调度架构

分布式任务调度设计

当垂直应用越来越多，应用之间交互也会越来越复杂，通常我们采用分布式或者微服务架构，将核心业务抽取出来，形成单独的服务。一个独立的微服务群体逐渐形成稳定的服务中心，使得业务应用能更快地响应多变的市场需求。

此时，用于提高业务复用及整合的分布式服务框架成为关键。同时，由于服务独立，一般能做到定时任务独立的情况，任务的更改对于整体系统的影响小之又小。通常我们会采用任务与调度分离的方式（如上图所示），任务的执行逻辑无需关注调度与编排，同时可以保证执行器和调度的高可用，易于开发和维护。

1.3 分布式任务调度优势

在分布式服务架构的基础上，由于独立业务的数量可能很多，此时如果定时任务单独在该服务中实现，很可能会出现难以管理的情况，且避免不了由于定时任务的更改而导致的业务重启。因此，一个独立的分布式任务调度系统是很必要的，可以用来全局统筹管理所有的定时任务。同时，将任务的配置单独抽离出来，作为该分布式任务调度系统的功能，就能做到定时任务的更改不影响任何业务，也不影响整个系统：

  • 通过调度与任务分离的方式进行管理，大大降低了开发和维护成本；
  • 分布式部署，保证了系统的高可用性、伸缩性、负载均衡，提高了容错性；
  • 可以通过控制台部署和管理定时任务，方便灵活高效；
  • 任务都可以持久化到数据库，避免了宕机和数据丢失带来的隐患，同时有完善的任务失败重做机制和详细的任务跟踪及告警策略。

二、分布式任务调度技术选型

2.1 分布式任务调度考虑因素

sia-task-设计图

  • 任务编排：多个业务之间的定时任务存在流程次序。
  • 任务分片：对于一个大型任务，需要分片并行执行。
  • 跨平台：除了使用 Java 技术栈（SpringBoot、Spring等）的项目之外，还有使用其他语言的应用。
  • 无侵入：业务不希望与调度高耦合，只关注业务的执行逻辑。
  • 故障转移：任务执行过程中遇到问题有补偿措施，减少人工介入。
  • 高可用：调度系统自身必须保证高可用。
  • 实时监控：实时获取任务的执行状态。
  • 可视化：任务调度的操作提供可视化页面，方便使用。
  • 动态编辑：业务的任务时钟参数可能变动，不希望停机部署。

2.2 SIA-TASK与其它分布式任务调度技术比较

SIA是宜信公司基础开发平台Simple is Awesome的简称，SIA-TASK（微服务任务调度平台）是其中的一项重要产品，SIA-TASK契合当前微服务架构模式，具有跨平台、可编排、高可用、无侵入、一致性、异步并行、动态扩展、实时监控等特点。

开源地址：github.com/siaorg/sia-…

我们先对比市场上主流的开源分布式任务调度框架，分析其优缺点，然后再介绍我们的技术选型。

  • Quartz: Quartz 是 OpenSymphony 开源组织在任务调度领域的一个开源项目，完全基于 Java 实现。该项目于 2009 年被 Terracotta 收购，目前是 Terracotta 旗下的一个项目。相比于 JDK 或 Spring 提供的定时任务，Quartz 对单个任务的控制基本做到了极致，以其强大功能和应用灵活性，在企业应用中发挥了巨大的作用。然而 Quartz 并不支持任务的编排（任务之间有依赖），而且不支持任务分片。
  • TBSchedule: TBSchedule 是一个支持分布式的调度框架，能让一种批量任务或者不断变化的任务，被动态地分配到多个主机的 JVM 中，不同的线程组中并行执行。基于 ZooKeeper 的纯 Java 实现，由 Alibaba 开源。TBSchedule 侧重于任务的分发，支持任务分片，但是没有任务编排，也不是跨平台的。
  • Elastic-Job: Elastic-Job 是当当开源的一个分布式调度解决方案，由两个相互独立的子项目Elastic-Job-Lite 和 Elastic-Job-Cloud 组成。Elastic-Job 支持任务分片（作业分片一致性），但是没有任务编排，也不是跨平台的。
  • Saturn: Saturn 是唯品会开源的分布式，高可用的调度服务。Saturn 在 Elastic-Job 做二次开发，支持监控、任务分片、跨平台，但是没有任务编排。
  • Antares: Antares 是基于 Quartz 的分布式调度，支持分片、支持树形任务依赖，但不是跨平台的。
  • Uncode-Schedule: Uncode-Schedule 是基于 Zookeeper 的分布式任务调度组件。支持所有任务在集群中不重复、不遗漏的执行。支持动态添加和删除任务。但是不支持任务分片，也没有任务编排，还不是跨平台的。
  • XXL-JOB: XXL-JOB 是一个轻量级分布式任务调度平台，其核心设计目标是开发迅速、学习简单、轻量级、易扩展。XXL-JOB 支持分片，简单支持任务依赖，支持子任务依赖，不是跨平台的。

下面我们简单对比下 SIA-TASK 与这些任务调度框架：

任务编排 任务分片 跨平台 高可用 故障转移 实时监控
SIA-TASK √ √ √ √ √ √
Quartz × × .NET √ × API监控
TBSchedule × √ × √ √ √
Elastic-Job × √ × √ √ √
Saturn × √ √ √ √ √
Antares √ √ × √ √ √
Uncode-Schedule × × × √ √ √
XXL-JOB 子任务依赖 √ × √ √ √

可以发现，这些调度框架基本上都支持高可用、故障转移与实时监控等功能，但是对于任务编排、任务分片与跨平台等功能的支持各有侧重点。SIA-TASK 将全面支持这些功能。

三、SIA-TASK介绍

3.1 SIA-TASK技术选型

sia-task-technology

  • REST：一种软件架构风格。要求执行器暴露 Http 调用接口来达到跨平台的目的。
  • AOP：切面编程技术。在 Spring 项目扩展包 Hunter 中使用，保证 Task 被串行调用（单例单线程）。
  • Quartz：功能强大，应用灵活，对单个任务的控制基本做到了极致，用来作为调度中心时钟组件。
  • MySQL：用于元数据存储与（暂时）日志存取。
  • Elastic：基于 Lucene 的搜索服务器，提供了一个分布式多用户能力的全文搜索引擎，用于日志的存储与查询。
  • SpringCloud：社区活跃的开发框架，也是公司指定的统一开发框架。用于快速开发，快速迭代。
  • MyBatis：一款优秀的持久层框架，支持定制化 SQL，存储过程以及高级映射。用于简化持久层开发。
  • Zookeeper：久经考验的注册中心。用来解决调度中心高可用，分布式一致性等问题。

3.2 SIA-TASK设计思想

SIA-TASK借鉴微服务设计思想，获取分布在每个执行器节点上的任务（Task）元数据，进行汇报，上传注册中心。利用在线可编辑方式支持任务在线编排、动态修改任务时钟；使用 Http 协议作为交互传输协议。数据交互格式统一使用Json。用户通过编排器(下文会做介绍)进行操作，触发事件，调度器接收事件，由调度中心进行时钟解析，执行任务流程，进行任务通知。

3.3 SIA-TASK基本概念

SIA-TASK 采用任务和调度分离的方式，业务的执行任务逻辑和调度逻辑完全分离。系统组成共涉及以下几个核心概念：

  • 任务（Task）: 基本执行单元，执行器对外暴露的一个HTTP调用接口。
  • 作业（Job）: 由一个或者多个存在相互逻辑关系（串行/并行）的任务组成，任务调度中心调度的最小单位。
  • 计划（Plan）: 由若干个顺序执行的作业组成，每个作业都有自己的执行周期，计划没有执行周期。
  • 任务调度中心（Scheduler）: 根据每个的作业的执行周期进行调度，即按照计划、作业、任务的逻辑进行HTTP请求。
  • 任务编排中心（Config）: 编排中心使用任务来创建计划和作业。
  • 任务执行器（Executer）: 接收HTTP请求进行业务逻辑的执行。
  • Hunter：Spring项目扩展包，负责执行器中的任务抓取，上传注册中心，业务可依赖该组件进行Task编写。

3.4 SIA-TASK系统架构

SIA-TASK 可以分为三大模块（调度中心、编排中心和执行器）、两大组件（持久化存储和注册中心）。这三大模块和两大组件的作用如下：

  • 任务调度中心：负责抢占Job和任务调度以及任务迁移等，是SIA-TASK 的核心功能模块。
  • 任务编排中心：负责对在线任务进行逻辑编排，提供日志查看和实时监控功能。
  • 任务执行器：负责接收调度请求并执行任务逻辑。
  • 任务注册中心（ZK）：协调Job和Task、调度器等的工作流程。
  • 持久化存储（DB）：记录项目的Job和Task数据，并提供日志存储。

SIA-TASK 使用 SpringBoot 体系作为架构选型，基于Quartz及Zookeeper进行二次开发，支持相应的特性功能，SIA-TASK 的逻辑架构图如下图所示：

逻辑架构图

3.5 SIA-TASK模块说明

3.5.1 任务调度中心

任务调度中心负责任务调度，管理调度信息，按照调度配置发出调度请求，自身不承担业务代码。调度系统与任务解耦，提高了系统可用性和稳定性，同时调度系统性能不再受限于任务模块；支持可视化、简单且动态地管理调度信息，包括任务新建，更新，删除和任务报警等，所有上述操作都会实时生效，同时支持监控调度结果以及执行日志，支持执行器故障恢复。

3.5.2 任务编排中心

任务编排中心是分布式调度中心支持在线任务模型编排的组件；依托于UI可进行web端任务编排。

我们可以通过上述基础模型来编排一些复杂的调度模型，例如：

调度模型

SIA-TASK的UI编排界面：

UI编排界面

编排结束后查看task的编排信息如下图所示：

编排信息

同时，编排中心还提供首页统计数据查看、调度监控、Job管理、Task管理以及日志管理功能。

3.5.3 任务执行器

负责接收调度请求并执行任务逻辑。任务模块专注于任务的执行等操作，开发和维护更加简单和高效；

执行器支持两种类型：

(1) 如果使用 sia-task-hunter，支持SpringBoot项目和Spring项目， 引入 sia-task-hunter，任务（Task）抓取客户端。合规的HTTP接口（称之为Task）任务会自动被抓取并上传注册中心；

(2) 如果不使用 sia-task-hunter，只需提供任务可调用的HTTP接口，此时需要业务手动录入，且自行控制该任务的并发调用控制。

3.5.4 任务注册中心（Zookeeper）

分布式框架采用Zookeeper作为注册中心。

注册中心

(1) 任务注册

调度中心和执行集群都以Zookeeper作为注册中心，所有数据以节点及节点内容的形式注册，通过定时汇报主机状态保持存活在Zookeeper上。

(2) 元数据存储

注册中心不仅仅提供注册服务，并且存储每个执行器的信息（包括执行器实例信息，执行器上传的Task元数据，以及任务运行时的一些临时状态数据）。

(3) 事件发布

基于Zookeeper事件推送机制，进行任务的发布，通过平衡算法保证调度器任务抢占的分布均衡。

(4) 负载均衡

保证调度器获取执行Job的个数均衡，避免单一节点压力。

3.5.5 持久化存储（DB）

这里采用MySQL作为数据持久化解决方案。

除了Task动态元数据保存在注册中心之外，其他相关的元数据都存入MySQL，包括但不限于：手动录入的Task、配置的Job信息、编排的Task依赖信息、调度日志、业务人员操作日志、Task执行日志等。

3.6 SIA-TASK关键运行流程

3.6.1 任务发布流程

任务发布流程

(1) 用户可以通过UI进行Job创建。可以选择Job类型，设置预警邮箱，设置Job描述。然后为创建的Job进行任务Task编排。

(2) Job创建完毕并且设置Task编排关系后可进行任务发布，通过UI对相应的Job进行操作（激活，执行一次，停止以及删除操作）。

(3) 用户的Task任务可以是通过抓取器抓取的，亦可以使用UI手动创建。

3.6.2 执行流程

执行流程

(1) Job创建完成之后，可以选择激活触发定时任务；

(2) Job到达预订时间后，调度中心触发Job，然后按照预定的Task编排逻辑通过http通知Task执行器进行执行，并异步监听任务执行结果；

(3) 若执行结果成功，则判断是否存在后置Task，若存在，则继续下一次调度，若不存在，则说明该Job执行完毕，结束本次调用；若执行结果失败，则触发故障恢复策略：立即停止、忽略本次失败、多次尝试、转到其它执行器执行。

3.6.3 状态流转

Job在整个生命周期内存在四种状态，分别是：已停止（NULL）、准备中（READY）、开始运行（RUNNING）、异常停止（STOP），状态流转及流转条件如下图所示。

状态流转

3.7 SIA-TASK模块设计

SIA-TASK 的物理网络拓扑图如下所示：

网络拓扑图

SIA-TASK 的模块间交互设计思路：

(1) 通过编排中心创建Task任务或通过Hunter自动抓取，并将 Task 信息异步保存到DB；创建Job并激活，在zookeeper中创建JobKey。

(2) 调度中心会监听zookeeper中JobKey创建事件，然后抢占创建的Job，抢占成功后加入quartz定时任务，当时间到达即触发Job运行。调度中心异步调用执行器服务执行Job中的 Task （可能存在多个 Task ，遵循 Task 失败策略），并将结果返回到调度中心。

(3) 将Job执行状态随时在zookeeper上更改，通过编排中心的查询接口可以进行查询。

(4) Job执行结束后，等待下一次执行。

3.7.1 任务编排中心设计

编排中心可以与DB和zookeeper进行数据交互，其主要功能可分为三方面：

  • 数据持久化接口服务；
  • zookeeper上元数据变更；
  • 数据可视化：查看系统各种统计数据等。

编排中心首页监控展示如下：

首页监控

3.7.2 任务调度中心设计

调度中心主要与DB、ZK和执行器进行交互，其主要功能可分为以下几个方面：

  • Job执行日志记录
  • ZK中Job状态变更
  • 调用执行器服务执行Job
  • 调度中心高可用
  • Job 调度线程池

3.7.3 任务执行器设计

执行器可以与ZK和调度中心进行交互，其主要功能可分为两个方面：

  • 接受调度中心的调度，执行定时任务，并将结果返回到调度中心；
  • 自动抓取执行器上的 Task 任务，提交到ZK。

执行器 Task示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
复制代码@OnlineTask(description = "在线任务示例",enableSerial=true)
@RequestMapping(value = "/example", method = { RequestMethod.POST }, produces = "application/json;charset=UTF-8")
@CrossOrigin(methods = { RequestMethod.POST }, origins = "*")
@ResponseBody
public String example(@RequestBody String json) {   
    /**
     * TODO：客户端业务逻辑处理
     */
    Map<String, String> info = new HashMap<String, String>();
    info.put("status", "success");
    info.put("result", "as you need");
    return JSONHelper.toString(info);
}

由此可见，任务 Task 编写非常简单。

3.8 SIA-TASK高可用设计

分布式服务一般都要考虑高可用方案，同样 SIA-TASK 为了保证高可用，针对不同的服务组件进行了不同维度增强。

3.8.1 任务编排中心的高可用

SIA-TASK 通过前后端分离、服务拆分等措施实现了编排中心的高可用。当集群中某实例失效后，不会影响集群的其它实例，因此无需特殊操作即可使用集群中其它的可用编排中心。

3.8.2 任务调度中心的高可用

3.8.2.1 异常转移

如果调度中心集群中的某个实例节点服务宕机后，这个实例节点上的所有Job会平滑迁移到集群中可用的实例上，不会造成定时任务的执行缺失，同时，当崩溃后的实例修复成功重新接入该集群时，会继续抢占Job提供服务。

3.8.2.2 配置线程池

调度采用线程池方式实现，避免单线程因阻塞而引起任务调度延迟。程池里的线程数，默认值是10，当执行任务会并发执行多个耗时任务时，要根据业务特点选择线程池的大小。

1
2
3
复制代码org.quartz.threadPool.class = org.quartz.simpl.SimpleThreadPool org.quartz.threadPool.threadCount = 60
org.quartz.threadPool.threadPriority = 5
org.quartz.threadPool.threadsInheritContextClassLoaderOfInitializingThread = true

SIA-TASK 根据quartz自身提供的threadPool再次进行线程池的利用。进行线程池重新定义，针对每个Job去分配一个独有的线程池。线程池的大小可根据Job自身编排的 Task 个数的大小进行动态伸缩，从而保证每个Job的调度线程完全独立，不在会因为编排 Task 个数的陡增而耗尽线程资源。同时提供线程池资源的回收逻辑，在Job进行永久性终止时回收为期分配的线程池资源。

1
2
3
4
5
6
7
8
9
10
11
复制代码public static ExecutorService getExecutorService(String JobKey) {

    ExecutorService exec = executorPool.get(JobKey);
     if (exec == null) {
        LOGGER.info(Constants.LOG_PREFIX + "Initialize thread pool for running Jobs,Job is {}",JobKey);
      exec = Executors.newCachedThreadPool();
      executorPool.putIfAbsent(JobKey, exec);
      exec = executorPool.get(JobKey);
  }
    return exec;
}
3.8.2.3 全日志跟踪

SIA-TASK 针对Job的整个调度生命周期进行全面跟踪，利用AOP进行日志增强，调度中心每触发一次Job调度就会进行日志记录。同时针对Job编排的 Task 执行也会进行记录任务日志。

日志分为Job日志和 Task 日志：

  • Job日志：包含调度器信息、调度时间、调度状态以及其他附加属性。
  • Task日志：包含执行器信息、执行时间、执行状态、返回信息以及其他附加属性。
3.8.2.4 异步封装
  • SIA-TASK 从一开始设计就考虑了任务进行远程调用对调度中心并发线程资源的损耗。对于Job封装的 Task 远程调度，全部采用异步调用，每次任务请求逻辑的耗时非常的轻量化。只仅仅一次见到的http请求。
  • 支持 Task 进行用户自定义超时设置，支持两种模式的超时：connecttimeout、readtimeout。支持用户根据业务的具体执行周期来进行超时设置。
1
2
3
4
5
6
7
8
9
10
复制代码public interface RestTemplate {

/**
 * 异步Post方法 * @param request
 * @param responseType
 * @param uriVariables
 * @param <T>
 * @return
 */
 <T> ListenableFuture<ResponseEntity<T>> postAsyncForEntity(Request request, Class<T> responseType, Object... uriVariables); }
3.8.2.5 自定义调度器资源池

调度器资源池

SIA-TASK 从物理资源角度设计了调度资源池，出于一些特殊情况的考量我们针对调度器进行了池化；调度器可以通过不同的操作进行状态的转变，从而进行能力的转化。

  • 工作调度器资源池：管理具备获取任务能力并且可以实际获取任务的调度器资源。
  • 下线调度器资源池：管理具备获取任务能力但是实际不允许获取的调度器资源。
  • 离线调度器资源池：管理下线调度器资源池中已经宕机的调度器资源。

3.8.3 任务执行器的高可用

  • 考虑网络的不稳定性，SIA-TASK 针对网络的不稳定性也做出了非常重要的设计，对于节点的连通性的测试支持以及针对 Task 运行实例节点健康的预感知，保证提前感知 Task 实例节点的健康情况，保证调度 Task 高可用。
  • 同时也保证了执行器实例针对网络导致链接中断的问题，SIA-TASK 重新设计了zookeeper的重连机制，保证 Task 运行实例节点因网络问题丢失链接后还能进行恢复重试，直到恢复正常后并入执行池中正常接收任务的调度。
  • 一般来说，执行器也是集群部署的。作为 Task 的执行单元，如果在执行器集群中一台机器上执行失败，调度中心会根据失败策略来做故障转移。这里提供了两种故障转移策略：轮询转移和最大补偿转移。轮询转移为对可用的执行器列表进行轮询，若有一个执行器执行成功，则 Task 执行成功，若全部执行失败，则 Task 执行失败。最大补偿转移为首先在本执行器再次执行若干次，若执行成功，则不会转移，若还是执行失败，则执行轮询转移策略。

四、总结

至此对微服务任务调度平台 SIA-TASK 做了一个简要的介绍，包括设计背景、架构设计以及产品组件功能与特性。微服务任务调度平台 SIA-TASK 基本上解决了当前的业务需求，提供简单高效的编排调度服务。SIA-TASK 会持续迭代，提供更为完善的服务。之后也会提供相关技术文档和使用文档。

链接指南

开源地址：github.com/siaorg/sia-…

作者：毛正卫/李鹏飞/梁鑫

原文首发：SpringCloud社区

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

大一从一个小白一路走过来，也在 leetcode 刷了几年了题，也是有点经验，也走过很多坑，在此分享我的一波经验，请耐心看完一定会有所帮助。

切勿盲目刷题：刷题前的知识积累

说实话，想要提高自己的算法，我觉得就是脚踏实地着多动手去刷题，多刷题。

但是，如果你是小白，也就是说，你连常见的数据结构，如链表、树以及常见的算法思想，如递归、枚举、动态规划这些都没学过，那么，我不建议你盲目疯狂着去刷题的。而是先去找本书先去学习这些必要的知识，然后再去刷题。
因为，如果这些基础都不懂的话，估计一道题做了几个小时，然后看答案都不不懂，做题没有任何思路，这是很难受的。久而久之，估计没啥动力了，我刚开始就是这样，一道题答案看一天，然而还是不大懂，什么回溯啊，暴力啊，还不知道是啥意思。

也就是说，假如你要去诸如leetcode这些网站刷题，那么，你要先具备一定的基础，这些基础包括：

1、常见数据结构：链表、树(如二叉树)。（是的，链表和二叉树是重点，图这些可以先放着）

2、常见算法思想：贪婪法、分治法、穷举法、动态规划，回溯法。（贪婪、穷举、分治是基础，动态规划有难度，可以先放着）

以上列出来的算是最基本的吧。就是说你刷题之前，要把这些过一遍再去刷题。如果你连这些最基本的都不知道的话，那么你再刷题的过程中，会很难受的，思路也会相对比较少。

总之，千万不要急，先把这些基本的过一遍，力求理解，再去刷题。这些基础的数据结构与算法，我是在大一第二学期学的，我没看视频，我是通过看书学的，那时候看的书是：

1、数据结构与算法分析（c 语言描述版）

我相信大部分人大学看的教程都是清华大学出版社严蔚敏写的那本书，说实话，作为初学者，那本书我没能坚持看下去，可能比较适合大佬看吧。我自己买了一本《数据结构与算法分析（c 语言描述版）》，挺薄的，不过感觉很棒，这本书让我学到了很多，个人感觉也挺容易懂的，代码实现是采用 C 语言来实现的，不是伪代码，如果你想学习数据结构，我觉得这本书是个不错的选择。班级里有挺多人看了《大话数据结构》，挺他们说也挺不错，不过我没看过。

2、挑战程序设计竞赛

这边书也是大一时看的，如果你想刷题，我挺推荐这本书，里面分初级、中级到高级。虽然每道题没有讲的特别详细，但当时都看懂了，真心不错。不过高级那部分我是没看，初级和中级看着挺舒服。也是学到挺多的，推荐给大家。

3、编程之美

不用说，很美，这本书是我今年刚入手看的，只能用强烈推荐来形容，在这本书里，学到了挺多技巧，里面列举的题也不是特别难，目前看了 80%，真香。刚开始我听别人说如果要准备面试谷歌什么的建议看，我以为很难，迟迟没买来看，不过，我看的过程中，感觉还好，相信你也能看的懂，想学习算法、刷题的，强烈推荐。
4、编程珠玑

这本老早就听别人说过了，去年看的，不过也是看了80%左右，和编程之美一样，强烈推荐，这本书里的题，说实话，感觉比编程之美有意思，
5、程序员代码面试指南：IT 名企算法与数据结构题目最优解

这本书是牛客网的左程云写的，这本书重在带你刷题，每道题的解法也是讲的挺详细的，而且，这本书是一个专题一个专题带你刷题的，从栈和队列、链表、二叉树、递归与动态规划、字符串等等。我之前的链表打卡就是从这里找的。大家可以按照自己的弱点挑着刷。对了，代码是采用 Java 实现的，不过你会 C 语言的话，一样能看懂。真心不过，递归和动态规划里面好几道题都命中这次春招笔试了，当然，类似而已。然而，那时我还没有去看这本书动态相关的专题。推荐给大家。
做个补充：这些书籍我都有保存了电子版的，不过百度云发出来经常会链接失效，我不好及时更新，不过你可以关注我的公众号：苦逼的码农，回复**“电子书“**即可获取。我的公众号也有100多原创文章，有很多是讲解算法的，
也非常欢迎你来关注，共同学习。

说实话，我那一学期的时间几乎都花在数据结构与算法上，但刷的题很少，只是书本上的一些例题。所以当我把这些基本的过一遍之后，再去一些网站刷题依旧非常菜。

所以你们千万别指望以为自己把这些思想学完之后刷题会很牛，只有多刷题，只有多动手实践，你的灵敏度才会提高起来。

总结下：

提高数据结构与算法没啥捷径，最好的捷径就是多刷题。但是，刷题的前提是你要先学会一些基本的数据结构与算法思想。

AC不是目的，我们要追求完美

如何刷题？如何对待一道算法题？

我觉得，在做题的时候，一定要追求完美，千万不要把一道题做出来之后，提交通过，然后就赶紧下一道。我认为这意义不大，因为一道题的解法太多了，有些解法态粗糙了，我们应该要寻找最优的方法。

算法能力的提升和做题的数量是有一定的关系，但并不是线性关系。也就是说，在做题的时候，要力求一题多解，如果自己实在想不出来其他办法了，可以去看看别人是怎么做的，千万不要觉得模仿别人的做法是件丢人的事。

我做题的时候，我一看到一道题，可能第一想法就是用很粗糙的方式做，因为很多题采用暴力法都会很容易做，就是时间复杂度很高。之后，我就会慢慢思考，看看有没其他方法来降低时间复杂度或空间复杂度。最后，我会去看一下别人的做法，当然，并不是每道题都会这样执行。

衡量一道算法题的好坏无非就是时间复杂度和空间复杂度，所以我们要力求完美，就要把这两个降到最低，令他们相辅相成。

我举道例题吧：

问题： 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法？

这道题我在以前的分章分析过，不懂的可以先看下之前写的：递归与动态规划—基础篇1

方法1：：暴力递归

这道题不难，或许你会采取下面的做法：

1
2
3
4
5
6
7
8
9
复制代码public static int solve(int n){
    if(n == 1 || n == 2){
        return n;
    }else if(n <= 0){
        return 0;
    }else{
        return solve(n-1) + solve(n-2);
    }
}

这种做法的时间复杂度很高，指数级别了。但是如果你提交之后侥幸通过了，然后你就接着下一道题了，那么你就要好好想想了。

方法二：空间换时间

力求完美，我们可以考虑用空间换时间：这道题如何你去仔细想一想，会发现有很多是重复执行了。所以可以采取下面的方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
复制代码//用一个HashMap来保存已经计算过的状态
static Map<Integer,Integer> map = new HashMap();
public static int solve(int n){
    if(n <= 0)return 0;
    else if(n <= 2){
        return n;
    }else{//是否计算过
        if(map.containsKey(n)){
            return map.get(n);
        }else{
            int m = solve(n-1) + solve(n-2);
            map.put(n, m);
            return m;
        }
    }
}

这样，可以大大缩短时间。也就是说，当一道题你做了之后，发现时间复杂度很高，那么可以考虑下，是否有更好的方法，是否可以用空间换时间。

方法三：斐波那契数列

实际上，我们可以把空间复杂度弄的更小，不需要HashMap来保存状态：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
复制代码public static int solve(int n){
    if(n <= 0)
       return 0;
    if(n <= 2){
        return n;
    }
    
    int f1 = 0;
    int f2 = 1;
    int sum = 0;
    for(int i = 1; i<= n; i++){
        sum = f1 + f2;
        f1 = f2;
        f2 = sum;
    }
    return sum;
}

我弄这道题给你们看，并不是在教你们这道题怎么做，而是有以下目的：

1、在刷题的时候，我们要力求完美。

2、我想不到这些方法啊，怎么办？那么你就可以去看别人的做法，之后，遇到类似的题，你就会更有思路，更知道往哪个方向想。

3、可以从简单暴力入手做一道题，在考虑空间与时间之间的衡量，一点点去优化。

挑战自己，跳出舒适区

什么叫舒适区？在刷题的时候，可能有一类题是你比较懂的，你每次一看就有思路，然后半个小时就撸好代码，提交代码，然后通过了，然后，哇，又多刷了一道题，心里很舒服。

但是，记住，前期你可以多刷这种题练手，提升自己的乐趣，但，我还是建议你慢慢跳出舒适区，去做一些自己不擅长的题，并且找段时间一直刷这种题。例如，我觉得我在递归方面的题还是挺强的，
但是，我对动态规划的题，很菜，每次都要想好久，每次遇到这种题都有点害怕，没什么信心。不过有段时间我觉得只刷动态规划的题，直接在 leetcode 选定专题，连续做了七八十道，刚开始很难受，
后来就慢慢知道了套路了，一道题从两三个小时最后缩到半小时，简单的十几分钟就搞定。感觉自己对这类型的题也不惧怕的。

所以，建议你，一定要学好跳出自己的舒适区。

推荐一些刷题网站

我一般是在leetcode和牛客网刷题，感觉挺不错，题目难度不是很大。

在牛客网那里，我主要刷剑指Offer,不过那里也有个在线刷leetcode，不过里面的题量比较少。牛客网刷题有个非常方便的地方就是有个讨论区，那里会有很多大佬分享他们的解题方法，不用我们去百度找题解。所以你做完后，实在想不出，可以很方便着去看别人是怎么做的。

至于leetcode，也是大部分题目官方都有给出答案，也是个不错的刷题网站。你们可以两个挑选一个，或者两个都刷。

当然，还有其他刷题的网站，不过，其他网站没刷过，不大清除如何。

至于leetcode，有中文版和英文版，个人建议英文版，英文版里面有各种大佬的解法分析。

leetcode有中文版

英文版

根据自己的兴趣选。

学习一些解题技巧

说实话，有些题在你没看别人的解法前，你好不知道有这么美妙优雅的解法，看了之后，卧槽，居然还可以这样。而我们在刷题的过程中，就要不断累积这些技巧，当你累计多了，你就会形成一种
神经反应，一下子就想到了某种方法。解题技巧很多，例如数组下标法、位图法、双指针等等，我自己也分享过一篇总结一些算法技巧的文章。给你举个例子吧，有时候有些技巧真让你大喊“卧槽”。

1、找出没有重复的数

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。

这道题可能很多人会用一个哈希表来存储，每次存储的时候，记录 某个数出现的次数，最后再遍历哈希表，看看哪个数只出现了一次。这种方法的时间复杂度为 O(n)，空间复杂度也为 O(n)了。

然而我想告诉你的是，采用位运算来做，绝对高逼格！

我们刚才说过，两个相同的数异或的结果是 0，一个数和 0 异或的结果是它本身，所以我们把这一组整型全部异或一下，例如这组数据是：1， 2， 3， 4， 5， 1， 2， 3， 4。其中 5 只出现了一次，其他都出现了两次，把他们全部异或一下，结果如下：

由于异或支持交换律和结合律，所以:

1^2^3^4^5^1^2^3^4 = （1^1)^(2^2)^(3^3)^(4^4)^5= 0^0^0^0^5 = 5。

也就是说，那些出现了两次的数异或之后会变成0，那个出现一次的数，和 0 异或之后就等于它本身。就问这个解法牛不牛逼？所以代码如下

1
2
3
4
5
6
7
复制代码int find(int[] arr){
    int tmp = arr[0];
    for(int i = 1;i < arr.length; i++){
        tmp = tmp ^ arr[i];
    }
    return tmp;
}

时间复杂度为 O(n)，空间复杂度为 O(1)，而且看起来很牛逼。

2、m的n次方

如果让你求解 2 的 n 次方，并且不能使用系统自带的 pow 函数，你会怎么做呢？这还不简单，连续让 n 个 m 相乘就行了，代码如下：

1
2
3
4
5
6
7
复制代码int pow(int n){
    int tmp = 1;
    for(int i = 1; i <= n; i++) {
        tmp = tmp * m;
    }
    return tmp;
}

不过你要是这样做的话，我只能呵呵，时间复杂度为 O(n) 了，怕是小学生都会！如果让你用位运算来做，你会怎么做呢？

我举个例子吧，例如 n = 13，则 n 的二进制表示为 1101, 那么 m 的 13 次方可以拆解为:

m^1101 = m^0001 * m^0100 * m^1000。

我们可以通过 & 1和 >>1 来逐位读取 1101，为1时将该位代表的乘数累乘到最终结果。直接看代码吧，反而容易理解：

1
2
3
4
5
6
7
8
9
10
11
12
13
复制代码int pow(int n){
    int sum = 1;
    int tmp = m;
    while(n != 0){
        if(n & 1 == 1){
            sum *= tmp;
        }
        tmp *= tmp;
        n = n >> 1;
    }
    
    return sum;
}

时间复杂度近为 O(logn)，而且看起来很牛逼。

更多算法技巧，欢迎大家关注我的头条号，一定会让你有所收获滴。

再说数据结构发重要性

前面我主要是说了我平时都是怎么学习算法的。在数据结构方法，我只是列举了你们一定要学习链表和树(二叉堆)，但这是最基本的，刷题之前要掌握的，对于数据结构，我列举下一些比较重要的：

1、链表（如单向链表、双向链表）。

2、树（如二叉树、平衡树、红黑树）。

3、图（如最短路径的几种算法）。

4、队列、栈、矩阵。

对于这些，自己一定要动手实现一遍。你可以看书，也可以看视频，新手可以先看视频，不过前期可以看视频，之后我建议是一定要看书。

例如对于平衡树，可能你跟着书本的代码实现之后，过阵子你就忘记，不过这不要紧，虽然你忘记了，但是如果你之前用代码实现过，理解过，那么当你再次看到的时候，会很快就记起来，很快就知道思路,而且你的抽象能力等等会在不知不觉中提升起来。之后再学习红黑树啊，什么数据结构啊，都会学的很快。

最最重要

动手去做，动手去做，动手去做。重要的话说三遍。

千万不要找了一堆资源，订好了学习计划，我要留到某某天就来去做…..

千万不要这样，而是当你激情来的时候，就马上去干，千万不要留到某个放假日啊什么鬼了，很多这种想法的人，最后会啥也没做的。

也不要觉得要学习的有好多啊，不知道从哪学习起。我上面说了，可以先学习最基本的，然后刷题，刷题是一个需要长期坚持的事情，一年，两年。在刷题的过程中，可以穿插和学习其他数据结构。

有收获？希望老铁们来个三连击，给更多的人看到这篇文章

1、给俺点个赞呗，可以让更多的人看到这篇文章，顺便激励下我，嘻嘻。

2、老铁们，关注我的原创微信公众号「帅地玩编程**」，专注于写算法 + 计算机基础知识（计算机网络+ 操作系统+数据库+Linux）。保存让你看完有所收获，不信你打我。

最后，给大家推荐一个珍藏已久的 github，该 github 上收藏了几百本常用电子书，并且还提供了下载的地址，部分截图如下

在这里插入图片描述

地址在这里：点击前往Github

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

在 Redis 出现之前，我们的缓存框架各种各样，有了 Redis ，缓存方案基本上都统一了，关于 Redis，松哥之前有一个系列教程，尚不了解 Redis 的小伙伴可以参考这个教程：

使用 Java 操作 Redis 的方案很多，Jedis 是目前较为流行的一种方案，除了 Jedis ，还有很多其他解决方案，如下：

除了这些方案之外，还有一个使用也相当多的方案，就是 Spring Data Redis。

在传统的 SSM 中，需要开发者自己来配置 Spring Data Redis ，这个配置比较繁琐，主要配置 3 个东西：连接池、连接器信息以及 key 和 value 的序列化方案。

在 Spring Boot 中，默认集成的 Redis 就是 Spring Data Redis，默认底层的连接池使用了 lettuce ，开发者可以自行修改为自己的熟悉的，例如 Jedis。

Spring Data Redis 针对 Redis 提供了非常方便的操作模板 RedisTemplate 。这是 Spring Data 擅长的事情，那么接下来我们就来看看 Spring Boot 中 Spring Data Redis 的具体用法。

方案一：Spring Data Redis

创建工程

创建工程，引入 Redis 依赖：

创建成功后，还需要手动引入 commos-pool2 的依赖，因此最终完整的 pom.xml 依赖如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
复制代码<dependencies>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-data-redis</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>
</dependencies>
<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-pool2</artifactId>
</dependency>

这里主要就是引入了 Spring Data Redis + 连接池。

配置 Redis 信息

接下来配置 Redis 的信息，信息包含两方面，一方面是 Redis 的基本信息，另一方面则是连接池信息:

1
2
3
4
5
6
7
8
9
复制代码spring.redis.database=0
spring.redis.password=123
spring.redis.port=6379
spring.redis.host=192.168.66.128
spring.redis.lettuce.pool.min-idle=5
spring.redis.lettuce.pool.max-idle=10
spring.redis.lettuce.pool.max-active=8
spring.redis.lettuce.pool.max-wait=1ms
spring.redis.lettuce.shutdown-timeout=100ms

自动配置

当开发者在项目中引入了 Spring Data Redis ，并且配置了 Redis 的基本信息，此时，自动化配置就会生效。

我们从 Spring Boot 中 Redis 的自动化配置类中就可以看出端倪：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
复制代码@Configuration
@ConditionalOnClass(RedisOperations.class)
@EnableConfigurationProperties(RedisProperties.class)
@Import({ LettuceConnectionConfiguration.class, JedisConnectionConfiguration.class })
public class RedisAutoConfiguration {
        @Bean
        @ConditionalOnMissingBean(name = "redisTemplate")
        public RedisTemplate<Object, Object> redisTemplate(
                        RedisConnectionFactory redisConnectionFactory) throws UnknownHostException {
                RedisTemplate<Object, Object> template = new RedisTemplate<>();
                template.setConnectionFactory(redisConnectionFactory);
                return template;
        }
        @Bean
        @ConditionalOnMissingBean
        public StringRedisTemplate stringRedisTemplate(
                        RedisConnectionFactory redisConnectionFactory) throws UnknownHostException {
                StringRedisTemplate template = new StringRedisTemplate();
                template.setConnectionFactory(redisConnectionFactory);
                return template;
        }
}

这个自动化配置类很好理解：

  1. 首先标记这个是一个配置类，同时该配置在 RedisOperations 存在的情况下才会生效(即项目中引入了 Spring Data Redis)
  2. 然后导入在 application.properties 中配置的属性
  3. 然后再导入连接池信息（如果存在的话）
  4. 最后，提供了两个 Bean ，RedisTemplate 和 StringRedisTemplate ，其中 StringRedisTemplate 是 RedisTemplate 的子类，两个的方法基本一致，不同之处主要体现在操作的数据类型不同，RedisTemplate 中的两个泛型都是 Object ，意味者存储的 key 和 value 都可以是一个对象，而 StringRedisTemplate 的 两个泛型都是 String ，意味者 StringRedisTemplate 的 key 和 value 都只能是字符串。如果开发者没有提供相关的 Bean ，这两个配置就会生效，否则不会生效。

使用

接下来，可以直接在 Service 中注入 StringRedisTemplate 或者 RedisTemplate 来使用：

1
2
3
4
5
6
7
8
9
10
11
复制代码@Service
public class HelloService {
    @Autowired
    RedisTemplate redisTemplate;
    public void hello() {
        ValueOperations ops = redisTemplate.opsForValue();
        ops.set("k1", "v1");
        Object k1 = ops.get("k1");
        System.out.println(k1);
    }
}

Redis 中的数据操作，大体上来说，可以分为两种：

  1. 针对 key 的操作，相关的方法就在 RedisTemplate 中
  2. 针对具体数据类型的操作，相关的方法需要首先获取对应的数据类型，获取相应数据类型的操作方法是 opsForXXX

调用该方法就可以将数据存储到 Redis 中去了，如下：

k1 前面的字符是由于使用了 RedisTemplate 导致的，RedisTemplate 对 key 进行序列化之后的结果。

RedisTemplate 中，key 默认的序列化方案是 JdkSerializationRedisSerializer 。

而在 StringRedisTemplate 中，key 默认的序列化方案是 StringRedisSerializer ，因此，如果使用 StringRedisTemplate ，默认情况下 key 前面不会有前缀。

不过开发者也可以自行修改 RedisTemplate 中的序列化方案，如下:

1
2
3
4
5
6
7
8
9
10
11
12
复制代码@Service
public class HelloService {
    @Autowired
    RedisTemplate redisTemplate;
    public void hello() {
        redisTemplate.setKeySerializer(new StringRedisSerializer());
        ValueOperations ops = redisTemplate.opsForValue();
        ops.set("k1", "v1");
        Object k1 = ops.get("k1");
        System.out.println(k1);
    }
}

当然也可以直接使用 StringRedisTemplate：

1
2
3
4
5
6
7
8
9
10
11
复制代码@Service
public class HelloService {
    @Autowired
    StringRedisTemplate stringRedisTemplate;
    public void hello2() {
        ValueOperations ops = stringRedisTemplate.opsForValue();
        ops.set("k2", "v2");
        Object k1 = ops.get("k2");
        System.out.println(k1);
    }
}

另外需要注意 ，Spring Boot 的自动化配置，只能配置单机的 Redis ，如果是 Redis 集群，则所有的东西都需要自己手动配置，关于如何操作 Redis 集群，松哥以后再来和大家分享。

方案二：Spring Cache

通过 Spring Cache 的形式来操作 Redis，Spring Cache 统一了缓存江湖的门面，这种方案，松哥之前有过一篇专门的文章介绍，小伙伴可以移步这里：Spring Boot中，Redis缓存还能这么用！。

方案三：回归原始时代

第三种方案，就是直接使用 Jedis 或者 其他的客户端工具来操作 Redis ，这种方案在 Spring Boot 中也是支持的，虽然操作麻烦，但是支持，这种操作松哥之前也有介绍的文章，因此这里就不再赘述了，可以参考 Jedis 使用。

总结

Spring Boot 中，Redis 的操作，这里松哥给大家总结了三种方案，实际上前两个使用广泛一些，直接使用 Jedis 还是比较少，基本上 Spring Boot 中没见过有人直接这么搞。

好了，本文就说到这里，有问题欢迎留言讨论。

关注公众号【江南一点雨】，专注于 Spring Boot+微服务以及前后端分离等全栈技术，定期视频教程分享，关注后回复 Java ，领取松哥为你精心准备的 Java 干货！

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

本文主要翻译Spring的官方文档，主要介绍SS的基本概念和基本接口和原理。

Spring Security中的两个核心的概念：Authentication（验证）；Authorization（授权）；
Spring Security可以用来实现诸如，OAuth、OpenID、LDAP、CAS、JAAS等系统间的认证很授权。如我们可以使用Spring Security配合OAuth实现单点登录。

Authentication验证

Authentication主要的接口是AuthenticationManager

1
2
3
复制代码public interface AuthenticationManager {
  Authentication authenticate(Authentication authentication) throws AuthenticationException;
}

authenticate()方法调用有三种情况：

  1. 验证通过，正常返回一个Authentication实例
  2. 验证不通过，抛出AuthenticationException
  3. 无法决定，返回null
    最常用的AuthenticationManager接口实现类是ProviderManager，ProviderManager内部将验证委托给一系列AuthenticationProvider。AuthenticationProvider接口有点像AuthenticationManager接口，但是他有一个额外的方法，允许调用者来判断是否支持验证时给定的Authentication实例类型，该方法就是下面的supports方法。
1
2
3
4
复制代码public interface AuthenticationProvider {
	Authentication authenticate(Authentication authentication) throws AuthenticationException;
	boolean supports(Class<?> authentication);
}

ProviderManager将验证委托给一系列AuthenticationProvider，实际是一个AuthenticationProvider列表，所以他可以在一个应用中支持多种验证策略。在验证的时候会遍历所有的AuthenticationProvider逐个验证，调用supports方法判断是否验证该类型的Authentication，是则验证否则跳过。如果所有的AuthenticationProvider都无法决定返回了null，那就调用父级的AuthenticationManager验证（如果父级不为空）。
有时在应用中有验证的逻辑分组，每个分组有自己的AuthenticationManager（通常就是ProviderManager），这些分组共享一个父级AuthenticationManager。

自定义AuthenticationManager

SpringSecurity提供了一些配置帮助类来快去获取AuthenticationManager的功能，最常用的就是AuthenticationManagerBuilder，它可以以in-memory、JDBC、LDAP方式配置user details，或者添加自定义UserDetailService。eg.

1
2
3
4
5
6
7
8
9
10
复制代码@Configuration
public class ApplicationSecurity extends WebSecurityConfigurerAdapter {
  @Autowired
  DataSource dataSource;
   ... // web stuff here
  @Override
  public configure(AuthenticationManagerBuilder builder) {
    builder.jdbcAuthentication().dataSource(dataSource).withUser("dave").password("secret").roles("USER");
  }
}

??? spring官方给的代码实例有问题吧，configure方法没有返回类型

Authorization授权

Authorization授权的主要接口是AccessDecisionManager，框架提供了3个实现类：UnanimousBased（全部通过）、ConsensusBased（少数服从多数）、AffirmativeBased（无人反对则通过），所有这些实现类都是把授权委托给一系列的AccessDecisionVoter，这有点像ProviderManager样验证委托给AuthenticationProvider。此处AccessDecisionVoter就是抽象的投票人。

1
2
3
4
5
复制代码public interface AccessDecisionVoter<S> {
    boolean supports(ConfigAttribute attribute);    
    boolean supports(Class<?> clazz);
    int vote(Authentication authentication, S object, Collection<ConfigAttribute> attributes);
}

一个AccessDecisionVoter会考虑验证主体Authentication和一个被ConfigAttributes修饰的安全对象Object。
Object在AccessDecisionManager和AccessDecisionVoter的签名中是完全通用的，Object代表一切用户可能要访问的东西（通常情况是网络资源或者Java类的方法调用这两种情况）。ConfigAttributes也是通用的，用一些元数据来表示对安全对象的修饰，这些元数据决定访问安全对象所需要的权限级别。ConfigAttribute是一个接口，它只有一个非常通用的方法，并返回String，因此这些字符串以某种方式编码了资源所有者的意图，表达关于谁被允许访问安全对象的规则。一个典型的ConfigAttribute就是用户的角色名（如 ROLE_ADMIN 或者 ROLE_AUDIT），并且它们通常会有特殊的格式（如 ROLE_ 前缀）或者表示需要评估的表达式。
大部分人只是用AccessDecisionManager的默认实现类AffirmativeBased（无人反对则允许通过），任何定制都会发生在投票者身上，要么添加新的，要么修改现有的工作方式。
使用EL表达式的ConfigAttribute是非常常见的，例如 isFullyAuthenticated() && hasRole('FOO')， 这是有一个可以处理表达式并为他们创建上下文的AccessDecisionVoter支持的。要扩展可处理的表达式的范围，需要自定义SecurityExpressionRoot来实现，有时还需要SecurityExpressionHandler。

Web Security

Spring Security在web层的使用是基于Servlet过滤器的，下图是单个HTTP请求处理程序的典型分层。

当客户端向应用发送一个请求，应用容器会根据请求的URI路径来觉得应用那个过滤器和Servlet。最多只能有一个Servlet处理请求，但是过滤器是链式的，所以过滤器处理是有顺序的，实际上一个过滤器如果想要自己处理请求可以断开过滤链。过滤器也可以修改下流过滤器使用的Request和Response。过滤器链的顺序非常重要，Spring boot为其提供了2中机制：第一个是使用@Order注解或着实现Ordered接口，另一个是作为FilterRegistrationBean的一部分，FilterRegistrationBean本身的API是有顺序的。一些现成的过滤器通过定义常数，来表示他们系统彼此之间的相对顺序(例如，SessionRepositoryFilter中的常数DEFAULT_ORDER = Integer.MIN_VALUE + 50，这告诉我们它喜欢在链的早期，但是它不排除其他过滤器在它之前)。
Spring Security是过滤器链上一个节点作为Spring Security接入的入口，该过滤器就是FilterChainProxy，如下图：

Spring Security在请求处理过滤器链中插入了一个过滤器节点FilterChainProxy，看名字就知道是个代理过滤器链，它过处理过程委托给内部的过滤器（这里就进入Spring Security的内部，下文称安全过滤器）。事实上，在安全过滤器中甚至还有一层DelegatingFilterProxy，它通常在标准顾虑器和安全过滤器之间做代理，它将委托给FilterChainProxy，它没有必要必须是Spring的bean，而FilterChainProxy是Spring的bean，也就是说一般FilterChainProxy的生命周期交给Spring容器来管理。
FilterChainProxy中包含了一个过滤器链列表，会将请求分发到第一个匹配的过滤器链中去，下图显示了基于匹配请求路径的调度，这很常见，但不是匹配请求的唯一方式。这个调度过程最重要的特征是只有一个链处理一个请求。

创建自定义过滤器链

Spring Boot应用中的默认的回退过滤器链（匹配/**）预先定义了顺序（SecurityProperties.BASIC_AUTH_ORDER），你可以通过security.basic.enabled=false来关闭它，或者你可以使用它作为回退过滤器你只定义较低顺序的匹配其他规则的过滤器。为此，只需要添加一个WebSecurityConfigurerAdapter（或者WebSecurityConfigurer）类型的@Bean，并且使用@Order注解修饰这个Class。例如：

1
2
3
4
5
6
7
8
9
复制代码@Configuration
@Order(SecurityProperties.BASIC_AUTH_ORDER - 10)
public class ApplicationConfigurerAdapter extends WebSecurityConfigurerAdapter {
  @Override
  protected void configure(HttpSecurity http) throws Exception {
    http.antMatcher("/foo/**")
     ...;
  }
}

调度和授权的请求匹配

安全过滤器链(或等同于WebSecurityConfigurerAdapter)有一个请求匹配器，用于决定是否将其应用于一个HTTP请求。一旦决定应用特定的过滤器链，就不会应用其他过滤器链。但是在过滤器链中，您可以通过在HttpSecurity配置器中设置额外的匹配器来对授权进行更细粒度的控制。示例:

1
2
3
4
5
6
7
8
9
10
11
12
复制代码@Configuration
@Order(SecurityProperties.BASIC_AUTH_ORDER - 10)
public class ApplicationConfigurerAdapter extends WebSecurityConfigurerAdapter {
  @Override
  protected void configure(HttpSecurity http) throws Exception {
    http.antMatcher("/foo/**")
        .authorizeRequests()
        .antMatchers("/foo/bar").hasRole("BAR")
        .antMatchers("/foo/spam").hasRole("SPAM")
       .anyRequest().isAuthenticated();
  }
}

配置Spring Security最容易犯的一个错误是忘记这些匹配器适用于不同的进程，一个是整个过滤链的请求匹配器，另一个只是选择要应用的访问规则。

将应用安全规则与执行器规则相结合
涉及到Spring Boot Actuator内容，暂且略过

方法安全

除了支持web应用，Spring Security还支持将访问规则应用到Java方法执行。对于Sping Security来说只是不通的类型的资源保护。对于用户来说，这意味着使用相同格式的ConfigAttribute字符串(例如角色或表达式)声明访问规则，但是在代码中的不同位置。第一步是让方法安全生效，例如：

1
2
3
4
复制代码@SpringBootApplication
@EnableGlobalMethodSecurity(securedEnabled = true)
public class SampleSecureApplication {
}

然后我们可以直接修饰方法资源，例如：

1
2
3
4
5
6
7
复制代码@Service
public class MyService {
  @Secured("ROLE_USER")
  public String secure() {
    return "Hello Security";
  }
}

此示例是一个具有安全方法的服务。如果Spring创建了这种类型的@Bean，那么它将被代理，调用方将必须在方法实际执行之前通过安全拦截器。如果访问被拒绝，调用方将获得AccessDeniedException异常，而不是实际的方法结果。
还有其他注释可以用于强制安全约束的方法，特别是@PreAuthorize和@PostAuthorize，它们允许您分别编写包含对方法参数和返回值的引用的表达式。

Working with Threads

Spring Security从根本上说是线程绑定的，因为它需要使当前经过身份验证的主体对各种各样的下游消费者可用，基本的构建模块是SecurityContext，它可能包含Authentication(当用户登录时，它将是一个验证通过的Authentication)。您始终可以通过SecurityContextHolder里的静态方便方法访问和操作SecurityContext。例如：

1
2
3
复制代码SecurityContext context = SecurityContextHolder.getContext();
Authentication authentication = context.getAuthentication();
assert(authentication.isAuthenticated);

如果您需要访问网络端点中当前经过身份验证的用户，可以在@RequestMapping中使用方法参数，例如：

1
2
3
4
复制代码@RequestMapping("/foo")
public String foo(@AuthenticationPrincipal User user) {
  ... // do stuff with user
}

此注释将当Authentication从SecurityContext中拉出，并在其上调用getPrincipal()方法以产生方法参数。Authentication中Principal的类型取决于用于验证身份验证的AuthenticationManager，因此这对于获取对用户数据的类型安全引用可能是一个有用的小技巧。
如果Spring Security正在使用来自HttpServletRequest的Principal，将会是Authentication类型，因此你可以直接使用它：

1
2
3
4
5
6
复制代码@RequestMapping("/foo")
public String foo(Principal principal) {
  Authentication authentication = (Authentication) principal;
  User = (User) authentication.getPrincipal();
  ... // do stuff with user
}

Processing Secure Methods Asynchronously

由于SecurityContext是线程绑定的，如果您想要执行任何调用安全方法的后台处理，例如使用@Async，您需要确保上下文得到传播。这可以归结为用任务(Runnable、Callable等)包装SecurityContext，在后台执行。Spring Security提供了一些助手来简化这一过程，比如Runnable和Callable的包装器。要将SecurityContext传播到@Async方法，您需要提供一个AsyncConfigurer，并确Executor的类型正确:

1
2
3
4
5
6
7
复制代码@Configuration
public class ApplicationConfiguration extends AsyncConfigurerSupport {
  @Override
  public Executor getAsyncExecutor() {
    return new DelegatingSecurityContextExecutorService(Executors.newFixedThreadPool(5));
  }
}

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

安装注册中心

首先安装注册中心，这里我们选用zookeeper，直接去Apache官网下载，下载地址Apache ZooKeeper™ Releases

安装后进入bin目录，启动zkServer.cmd即可，如果是在linux上，就启动zkServer.sh即可，默认端口为2181

搭建管理控制台（可选）

首先，在空白目录下，打开控制台，输入（需要已安装maven）：

1
复制代码	git clone https://github.com/apache/incubator-dubbo-admin.git

接下来进入incubator-dubbo-admin，在目录下执行（需要已安装node.js）：

1
复制代码	mvn clean package

因为采用了前后端分离的项目构建方式，如果这里没有安装node.js，会在npm下载依赖的时候报错

如果刚才打包失败，报错如下异常，或其他类似的与SLF4J有关的异常：

异常

这是由于日志版本太低或日志缺失导致的bug，进入incubator-dubbo-admin\dubbo-admin-server\pom.xml中，在标签下添加以下依赖

1
2
3
4
5
6
7
8
9
10
复制代码	<dependency>
	   <groupId>ch.qos.logback</groupId>
	   <artifactId>logback-classic</artifactId>
	   <version>1.2.3</version>
	</dependency>
	<dependency>
	   <groupId>ch.qos.logback</groupId>
	   <artifactId>logback-core</artifactId>
	   <version>RELEASE</version>
	</dependency>

然后返回上一级目录重新进行打包，打包中如果报其他异常可以无视，只要最后提示BUILD SUCCESS即可，打包完成后进入incubator-dubbo-admin\dubbo-admin-distribution\target目录下，执行以下命令运行jar包：

1
复制代码	java -jar dubbo-admin-0.1.jar

接着访问 http://localhost:8080，出现类似下面界面就说明我们的管理控制台搭建成功：

管理控制台

搭建Dubbo项目

接下来我们就要搭建一个简易的Dubbo项目，首先我们创建一个空目录（注意，不要新建项目），名字任意，这里我就用创建一个dubbo-annotation-demo文件夹，然后用idea打开（eclipse或sts操作类似）

创建接口

接下来我们创建公用接口模块，右键项目，创建module：

创建module

我们选择创建Maven项目，名字任意，但是最好按照规范，这里：
步骤1

步骤2

然后打开pom.xml，设置打包方式和编码格式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
复制代码<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>com.akira</groupId>
    <artifactId>dubbo-service-user-api</artifactId>
    <version>1.0.0-SNAPSHOT</version>
    <packaging>jar</packaging>

    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding>
        <java.version>1.8</java.version>
    </properties>

</project>

然后，进入源码目录src\main\java，创建包com.akira.dubbo.service.user.api，在包下创建我们的接口类，这里我们就采用dubbo官方的示例：

1
2
3
4
复制代码public interface UserService {

    String sayHi();
}
创建Provider

按照刚才的步骤创建Module，不过这里我们选择创建spring-boot项目，名字任意，而且不用添加任何依赖，我们一会儿手动添加：

步骤1

步骤2

然后我们打开pom.xml，添加以下依赖：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
复制代码		<!-- spring-boot -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter</artifactId>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
        </dependency>
        
        <!-- 系统健康监控 -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-actuator</artifactId>
        </dependency>
		
		<!-- dubbo in spring-boot -->
        <dependency>
            <groupId>com.alibaba.boot</groupId>
            <artifactId>dubbo-spring-boot-starter</artifactId>
            <version>0.2.0</version>
        </dependency>

        <!-- 我们自己的接口 -->
        <dependency>
            <groupId>com.akira</groupId>
            <artifactId>dubbo-service-user-api</artifactId>
            <version>${project.version}</version>
        </dependency>

如果我们自己的接口依赖报红，就进入dubbo-service-user-api目录下（接口模块目录），打开cmd，执行mvn clean install即可

然后我们进入resources目录下，修改配置文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
复制代码spring:
  application:
    name: dubbo-service-user-provider

# 因为8080端口已经被管理台占用，所以要换一个端口
server:
  port: 8180 
   
# 自定义配置，接口的版本号
user:
  service:
    version: 1.0.0
  
dubbo:
  scan:
    basePackages: com.akira.dubbo.service.user.provider.api
  application:
    id: dubbo-service-user-provider
    name: dubbo-service-user-provider
    qos-port: 22222
    qos-enable: true
  protocol:
    id: dubbo
    name: dubbo
    port: 12345
    status: server
  # 与注册中心保持一致
  registry:
    id: zookeeper
    address: zookeeper://127.0.0.1:2181

接着我们进入源码目录下，创建api.impl包，在包下创建UserServiceImpl我们接口的实现类：

目录结构

1
2
3
4
5
6
7
8
复制代码@Service(version = "${user.service.version}")
public class UserServiceImpl implements UserService {

    @Override
    public String sayHi() {
        return "Hello Dubbo";
    }
}

注意，这个@Service注解是com.alibaba.dubbo.config.annotation.Service包下的，千万别导错了

最后，我们在DubboServiceUserProviderApplication中的main方法最后添加一行代码，用于启动Provider，要注意两点：

  • 一定要先启动注册中心，这里我们使用zookeeper，就一定要先启动zookeeper，再启动我们的provider项目
  • 这个Main对象是com.alibaba.dubbo.container.Main包下的类，不要导错了
1
2
3
4
5
6
7
8
9
复制代码@SpringBootApplication
public class DubboServiceUserProviderApplication {

    public static void main(String[] args) {
        SpringApplication.run(DubboServiceUserProviderApplication.class, args);

        Main.main(args);
    }
}

然后启动该应用模块，我们的服务提供者就完成了

创建consumer

和创建provider的步骤大致相同，这里我就不再赘述了，模块名字我这里使用dubbo-serivce-user-consumer，需要注意的是，在pom.xml文件中的plugin中，需要配置入口类，如下：

1
2
3
4
5
6
7
8
9
10
11
复制代码    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
                <configuration>
                    <mainClass>com.akira.dubbo.service.user.consumer.DubboServiceUserConsumerApplication</mainClass>
                </configuration>
            </plugin>
        </plugins>
    </build>

同时，因为我们服务消费者是一个web应用，所以需要把spring-boot-start的依赖改为spring-boot-starter-web，同时要添加dubbo和api的依赖：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
复制代码        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
        
        <!-- dubbo -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-actuator</artifactId>
        </dependency>

        <dependency>
            <groupId>com.alibaba.boot</groupId>
            <artifactId>dubbo-spring-boot-starter</artifactId>
            <version>0.2.0</version>
        </dependency>
        
         <!-- self-api -->
        <dependency>
            <groupId>com.akira</groupId>
            <artifactId>dubbo-service-user-api</artifactId>
            <version>${project.version}</version>
        </dependency>

接着修改配置文件，这里我采用的yml配置方式，配置内容和provider基本一致，需要注意两点：

  • 因为默认端口8080和管理中心端口冲突，所以需要修改端口
  • 需要去掉dubbo.protocol.status的配置，否则会认为该模块为服务提供者

具体配置如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
复制代码spring:
  application:
    name: dubbo-service-user-consumer

server:
  port: 8077

user:
  service:
    version: 1.0.0

dubbo:
  scan:
    basePackages: com.akira.dubbo.service.user.consumer.controller
  application:
    id: dubbo-service-user-consumer
    name: dubbo-service-user-consumer
  protocol:
    id: dubbo
    name: dubbo
    port: 12345
  registry:
    id: zookeeper
    address: zookeeper://127.0.0.1:2181

然后回到源码目录下，创建controller包，添加UserController类：

1
2
3
4
5
6
7
8
9
10
11
复制代码@RestController
public class UserController {

    @Reference(version = "${user.service.version}")
    private UserService userService;

    @GetMapping("hi")
    public String sayHi() {
        return userService.sayHi();
    }
}

注意，这里@Reference是dubbo包下的注解，可以把它当成@Autowired注解来使用
最后启动该应用模块，就完成了服务消费者的构建，注意启动顺序是：

  1. zookeeper注册中心
  2. dubbo-admin管理控制台
  3. provider服务提供者
  4. consumer服务消费者

显示结果

结果

这样，我们的样例就完成了

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

本文为原创作品，首发于微信公众号：【坂本先生】，如需转载请在文首明显位置标明“转载于微信公众号：【坂本先生】”，否则追究其法律责任。

微信文章地址：实战算法——多叉树全路径遍历

前言

本文研究的是如何对一个多叉树进行全路径的遍历，并输出全路径结果。该问题的研究可以用在：Trie树中查看所有字典值这个问题上。本文将对该问题进行详细的模拟及进行代码实现，讨论了递归和非递归两种方法优劣并分别进行实现，如果读者对这两种方法的优劣不感兴趣可直接跳到问题构建章节进行阅读。文章较长，推荐大家先收藏再进行阅读。

文章目录

递归和非递归比较

这个问题知乎上已经有了很多答案（www.zhihu.com/question/20…

递归

将一个问题分解为若干相对小一点的问题，遇到递归出口再原路返回，因此必须保存相关的中间值，这些中间值压入栈保存，问题规模较大时会占用大量内存。

非递归

执行效率高，运行时间只因循环次数增加而增加，没什么额外开销。空间上没有什么增加

递归的劣势和优势

递归的劣势

  • 递归容易产生”栈溢出”错误（stack overflow）。因为需要同时保存成千上百个调用记录，所以递归非常耗费内存。
  • 效率方面，递归可能存在冗余计算。使用递归的方式会有冗余计算（比如最典型的是斐波那契数列，计算第6个需要计算第4个和第5个，而计算第5个还需要计算第4个，所处会重复）。迭代在这方面有绝对优势。

递归的优势

递归拥有较好的代码可读性，对于数据量不算太大的运算，使用递归算法绰绰有余。

问题构建

现在存在一个多叉树，其结点情况如下图，需要给出方法将叶子节点的所有路径进行输出。

最终输出结果应该有5个，即[rad,rac,rbe,rbf,rg]

问题解决

首先我们对结点进行分析，构建一个结点类（TreeNode），然后我们需要有一个树类（MultiTree），包含了全路径打印的方法。最后我们需要建立一个Main方法进行测试。最终的项目结构如下：

注意：本文使用了lombok注解，省去了get，set及相关方法的实现。如果读者没有使用过lombok也可以自己编写对应的get，set方法，后文会对每个类进行说明需要进行实现的方法，对核心代码没有影响。

TreeNode类

节点类，主要包含两个字段：

  • content：用于存储当前节点存储的内容
  • childs：用于存储子节点信息，HashMap的string存储的是子节点内容，childs采用HashMap实现有利于实现子节点快速查找

该类中包含了必要的get，set方法，一个无参构造器，一个全参构造器

1
2
3
4
5
6
7
复制代码@Data
@RequiredArgsConstructor
@AllArgsConstructor
public class TreeNode {
    private String content;
    private HashMap<String,TreeNode> childs;
}

MultiTree类

包含的字段只有两个：

  • root：根节点
  • pathList：用于存储遍历过程中得到的路径

该类中的构造函数中我手动创建问题构建中的树，相关代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
复制代码    public MultiTree(){
        //创建根节点
        HashMap rootChilds = new HashMap();
        this.root = new TreeNode("r",rootChilds);

        //第一层子节点
        HashMap aChilds = new HashMap();
        TreeNode aNode = new TreeNode("a",aChilds);

        HashMap bChilds = new HashMap();
        TreeNode bNode = new TreeNode("b",bChilds);

        HashMap gChilds = new HashMap();
        TreeNode gNode = new TreeNode("g",gChilds);

        //第二层结点
        HashMap dChilds = new HashMap();
        TreeNode dNode = new TreeNode("d",dChilds);

        HashMap cChilds = new HashMap();
        TreeNode cNode = new TreeNode("c",cChilds);

        HashMap eChilds = new HashMap();
        TreeNode eNode = new TreeNode("e",eChilds);

        HashMap fChilds = new HashMap();
        TreeNode fNode = new TreeNode("f",fChilds);

        //建立结点联系
        rootChilds.put("a",aNode);
        rootChilds.put("b",bNode);
        rootChilds.put("g",gNode);

        aChilds.put("d",dNode);
        aChilds.put("c",cNode);

        bChilds.put("e",eNode);
        bChilds.put("f",fNode);
    }

在这个树中，每个节点都有childs，如果是叶子节点，则childs中的size为0，这是下面判断一个节点是否为叶子节点的重要依据接下来我们会对核心算法代码进行实现。

Main类

1
2
3
4
5
6
7
8
9
复制代码public class Main {
    public static void main(String[] args) {
        MultiTree tree = new MultiTree();
        List<String> path1 = tree.listAllPathByRecursion();
        System.out.println(path1);
        List<String> path2 = tree.listAllPathByNotRecursion();
        System.out.println(path2);
    }
}

递归方法

需要完善MultiTree类中的listAllPathByRecursion方法和listPath方法

递归过程方法：listAllPathByRecursion

算法流程图如下：

代码实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
复制代码public void listPath(TreeNode root,String path){

    if(root.getChilds().isEmpty()){//叶子节点
        path = path + root.getContent();
        pathList.add(path); //将结果保存在list中
        return;
    }else{ //非叶子节点
        path = path  + root.getContent() + "->";

        //进行子节点的递归
        HashMap<String, TreeNode> childs = root.getChilds();
        Iterator iterator = childs.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry entry = (Map.Entry)iterator.next();
            TreeNode childNode  = (TreeNode) entry.getValue();
            listPath(childNode,path);
        }
    }
}

递归调用方法：listAllPathByRecursion

1
2
3
4
5
6
复制代码public List<String> listAllPathByRecursion(){
    //清空路径容器
    this.pathList.clear();
    listPath(this.root,"");
    return this.pathList;
}

非递归方法

非递归方法的代码量和递归方法一比，简直是太多了，而且内容不好理解，不知道大家能不能看懂我写的代码，我已经尽力写上相关注释了。

首先建立了两个栈，示意图如下，栈的实现使用Deque，需要注意的是代码中的空指针情况。

  • 主栈：用于处理节点和临时路径的存储，主栈为空时说明，节点处理完毕
  • 副栈：用于存放待处理节点，副栈为空时说明，节点遍历完毕

其他相关变量介绍：

  • popCount ：用于存储一个节点的子节点的弹出个数。例如r有3个子节点，如果r对应的弹出个数为3，说明r的叶子节点处理完毕，可以弹出r。因为r弹出后，主栈没有元素，故处理完毕。
  • curString：用于存储临时路径，当主栈元素变化时，curString也会进行变化，例如上图curString为“r->g->”，当栈顶元素弹出时，需要减去”g->”。如果栈顶元素是叶子节点说明该条路径已经遍历完成，需要添加到path路径容器中。

程序流程图：

具体实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
复制代码/**
 * 非递归方法输出所有路径
 */
public List<String> listAllPathByNotRecursion(){
    //清空路径容器
    this.pathList.clear();
    //主栈，用于计算处理路径
    Deque<TreeNode> majorStack = new ArrayDeque();
    //副栈，用于存储待处理节点
    Deque<TreeNode> minorStack = new ArrayDeque();
    minorStack.addLast(this.root);

    HashMap<String,Integer> popCount = new HashMap<>();
    String curString  = "";

    while(!minorStack.isEmpty()){
        //出副栈，入主栈
        TreeNode minLast = minorStack.pollLast();
        majorStack.addLast(minLast);
        curString+=minLast.getContent()+"->";
        //将该节点的子节点入副栈
        if(!minLast.getChilds().isEmpty()){
            HashMap<String, TreeNode> childs = minLast.getChilds();
            Iterator iterator = childs.entrySet().iterator();
            while(iterator.hasNext()){
                Map.Entry entry = (Map.Entry)iterator.next();
                TreeNode childNode  = (TreeNode) entry.getValue();
                minorStack.addLast(childNode);
            }
        }
        //出主栈
        TreeNode majLast = majorStack.peekLast();
        //循环条件：栈顶为叶子节点 或 栈顶节点孩子节点遍历完了（需要注意空指针问题）
        while(majLast.getChilds().size() ==0 ||
                (popCount.get(majLast.getContent())!=null && popCount.get(majLast.getContent()).equals(majLast.getChilds().size()))){

            TreeNode last = majorStack.pollLast();
            majLast = majorStack.peekLast();

            if(majLast == null){ //此时主栈为空，运算完毕
                return this.pathList;
            }
            if(popCount.get(majLast.getContent())==null){//第一次弹出孩子节点，弹出次数设为1
                popCount.put(majLast.getContent(),1);
            }else{ //非第一次弹出孩子节点，在原有基础上加1
                popCount.put(majLast.getContent(),popCount.get(majLast.getContent())+1);
            }
            String lastContent = last.getContent();
            if(last.getChilds().isEmpty()){//如果是叶子节点才将结果加入路径集中
                this.pathList.add(curString.substring(0,curString.length()-2));
            }
            //调整当前curString，减去2是减的“->”这个符号
            curString = curString.substring(0,curString.length()-lastContent.length()-2);
        }
    }
    return this.pathList;
}

测试

调用Main类中的main方法，得到执行结果，和预期结果相同，代码通过测试

1
2
复制代码listAllPathByRecursion[r->a->c, r->a->d, r->b->e, r->b->f, r->g]
listAllPathByNotRecursion[r->g, r->b->f, r->b->e, r->a->d, r->a->c]

结论

其实该文章是我在研究《基于Trie树的敏感词过滤算法实现》的一个中间产物，其实原来应该也实现过多叉树的路径遍历问题，但是因为时间原因加之原来没有较好的知识管理系统，代码和笔记都丢了，今天趁机再进行一波总结。希望该文章能够帮助到需要的人。

参考资料

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

前言

代码优化，一个很重要的课题。可能有些人觉得没用，一些细小的地方有什么好修改的，改与不改对于代码的运行效率有什么影响呢？这个问题我是这么考虑的，就像大海里面的鲸鱼一样，它吃一条小虾米有用吗？没用，但是，吃的小虾米一多之后，鲸鱼就被喂饱了。代码优化也是一样，如果项目着眼于尽快无BUG上线，那么此时可以抓大放小，代码的细节可以不精打细磨；但是如果有足够的时间开发、维护代码，这时候就必须考虑每个可以优化的细节了，一个一个细小的优化点累积起来，对于代码的运行效率绝对是有提升的。

代码优化的目标是：

1、减小代码的体积

2、提高代码运行的效率

代码优化细节

1、尽量指定类、方法的final修饰符

带有final修饰符的类是不可派生的。在Java核心API中，有许多应用final的例子，例如java.lang.String，整个类都是final的。为类指定final修饰符可以让类不可以被继承，为方法指定final修饰符可以让方法不可以被重写。如果指定了一个类为final，则该类所有的方法都是final的。Java编译器会寻找机会内联所有的final方法，内联对于提升Java运行效率作用重大，具体参见Java运行期优化。此举能够使性能平均提高50%。

2、尽量重用对象

特别是String对象的使用，出现字符串连接时应该使用StringBuilder/StringBuffer代替。由于Java虚拟机不仅要花时间生成对象，以后可能还需要花时间对这些对象进行垃圾回收和处理，因此，生成过多的对象将会给程序的性能带来很大的影响。

3、尽可能使用局部变量

调用方法时传递的参数以及在调用中创建的临时变量都保存在栈中速度较快，其他变量，如静态变量、实例变量等，都在堆中创建，速度较慢。另外，栈中创建的变量，随着方法的运行结束，这些内容就没了，不需要额外的垃圾回收。

4、及时关闭流

Java编程过程中，进行数据库连接、I/O流操作时务必小心，在使用完毕后，及时关闭以释放资源。因为对这些大对象的操作会造成系统大的开销，稍有不慎，将会导致严重的后果。

5、尽量减少对变量的重复计算

明确一个概念，对方法的调用，即使方法中只有一句语句，也是有消耗的，包括创建栈帧、调用方法时保护现场、调用方法完毕时恢复现场等。所以例如下面的操作：

1
复制代码for (int i = 0; i < list.size(); i++){...}

建议替换为：

1
复制代码for (int i = 0, int length = list.size(); i < length; i++){...}

这样，在list.size()很大的时候，就减少了很多的消耗

6、尽量采用懒加载的策略，即在需要的时候才创建

例如：

1
2
3
4
5
复制代码String str = "aaa";if (i == 1)
{
list.add(str);
    
}

建议替换为：

1
2
3
4
5
6
复制代码if (i == 1)
{
String str = "aaa";
list.add(str);
    
}

7、慎用异常

异常对性能不利。抛出异常首先要创建一个新的对象，Throwable接口的构造函数调用名为fillInStackTrace()的本地同步方法，fillInStackTrace()方法检查堆栈，收集调用跟踪信息。只要有异常被抛出，Java虚拟机就必须调整调用堆栈，因为在处理过程中创建了一个新的对象。异常只能用于错误处理，不应该用来控制程序流程。

8、不要在循环中使用try…catch…，应该把其放在最外层

除非不得已。如果毫无理由地这么写了，只要你的领导资深一点、有强迫症一点，八成就要骂你为什么写出这种垃圾代码来了

9、如果能估计到待添加的内容长度，为底层以数组方式实现的集合、工具类指定初始长度

比如ArrayList、LinkedLlist、StringBuilder、StringBuffer、HashMap、HashSet等等，以StringBuilder为例：

（1）StringBuilder()      // 默认分配16个字符的空间

（2）StringBuilder(int size)  // 默认分配size个字符的空间

（3）StringBuilder(String str) // 默认分配16个字符+str.length()个字

符空间

可以通过类（这里指的不仅仅是上面的StringBuilder）的来设定它的初始化容量，这样可以明显地提升性能。比如StringBuilder吧，length表示当前的StringBuilder能保持的字符数量。因为当StringBuilder达到最大容量的时候，它会将自身容量增加到当前的2倍再加2，无论何时只要StringBuilder达到它的最大容量，它就不得不创建一个新的字符数组然后将旧的字符数组内容拷贝到新字符数组中—-这是十分耗费性能的一个操作。试想，如果能预估到字符数组中大概要存放5000个字符而不指定长度，最接近5000的2次幂是4096，每次扩容加的2不管，那么：

（1）在4096 的基础上，再申请8194个大小的字符数组，加起来相当于一次申请了12290个大小的字符数组，如果一开始能指定5000个大小的字符数组，就节省了一倍以上的空间

（2）把原来的4096个字符拷贝到新的的字符数组中去
这样，既浪费内存空间又降低代码运行效率。所以，给底层以数组实现的集合、工具类设置一个合理的初始化容量是错不了的，这会带来立竿见影的效果。但是，注意，像HashMap这种是以数组+链表实现的集合，别把初始大小和你估计的大小设置得一样，因为一个table上只连接一个对象的可能性几乎为0。初始大小建议设置为2的N次幂，如果能估计到有2000个元素，设置成new HashMap(128)、new HashMap(256)都可以。

10、当复制大量数据时，使用System.arraycopy()命令

11、乘法和除法使用移位操作

例如：

1
2
3
4
5
6
复制代码for (val = 0; val < 100000; val += 5)
{
a = val * 8;
b = val / 2;
    
}

用移位操作可以极大地提高性能，因为在计算机底层，对位的操作是最方便、最快的，因此建议修改为：

1
2
3
4
5
6
复制代码for (val = 0; val < 100000; val += 5)
{
a = val << 3;
b = val >> 1;
    
}

移位操作虽然快，但是可能会使代码不太好理解，因此最好加上相应的注释。

12、循环内不要不断创建对象引用

例如：

1
2
3
4
5
复制代码for (int i = 1; i <= count; i++)
{
Object obj = new Object();
    
}

这种做法会导致内存中有count份Object对象引用存在，count很大的话，就耗费内存了，建议为改为：

1
2
3
4
复制代码Object obj = null;for (int i = 0; i <= count; i++)
{ 
obj = new Object();
}

这样的话，内存中只有一份Object对象引用，每次new
Object()的时候，Object对象引用指向不同的Object罢了，但是内存中只有一份，这样就大大节省了内存空间了。

13、基于效率和类型检查的考虑，应该尽可能使用array，无法确定数组大小时才使用ArrayList

14、尽量使用HashMap、ArrayList、StringBuilder，除非线程安全需要，否则不推荐使用Hashtable、Vector、StringBuffer，后三者由于使用同步机制而导致了性能开销

15、不要将数组声明为public static final

因为这毫无意义，这样只是定义了引用为static final，数组的内容还是可以随意改变的，将数组声明为public更是一个安全漏洞，这意味着这个数组可以被外部类所改变

16、尽量在合适的场合使用单例

使用单例可以减轻加载的负担、缩短加载的时间、提高加载的效率，但并不是所有地方都适用于单例，简单来说，单例主要适用于以下三个方面：

（1）控制资源的使用，通过线程同步来控制资源的并发访问

（2）控制实例的产生，以达到节约资源的目的

（3）控制数据的共享，在不建立直接关联的条件下，让多个不相关的进程或线程之间实现通信

17、尽量避免随意使用静态变量

要知道，当某个对象被定义为static的变量所引用，那么gc通常是不会回收这个对象所占有的堆内存的，如：

1
2
3
4
5
6
7
8
9
复制代码/**
 * Java学习交流QQ群：956011797 我们一起学Java！
 */
public class A
{ 

private static B b = new B();

}

此时静态变量b的生命周期与A类相同，如果A类不被卸载，那么引用B指向的B对象会常驻内存，直到程序终止

18、及时清除不再需要的会话

为了清除不再活动的会话，许多应用服务器都有默认的会话超时时间，一般为30分钟。当应用服务器需要保存更多的会话时，如果内存不足，那么操作系统会把部分数据转移到磁盘，应用服务器也可能根据MRU（最近最频繁使用）算法把部分不活跃的会话转储到磁盘，甚至可能抛出内存不足的异常。如果会话要被转储到磁盘，那么必须要先被序列化，在大规模集群中，对对象进行序列化的代价是很昂贵的。因此，当会话不再需要时，应当及时调用HttpSession的invalidate()方法清除会话。

19、实现RandomAccess接口的集合比如ArrayList，应当使用最普通的for循环而不是foreach循环来遍历

这是JDK推荐给用户的。JDK API对于RandomAccess接口的解释是：实现RandomAccess接口用来表明其支持快速随机访问，此接口的主要目的是允许一般的算法更改其行为，从而将其应用到随机或连续访问列表时能提供良好的性能。实际经验表明，实现RandomAccess接口的类实例，假如是随机访问的，使用普通for循环效率将高于使用foreach循环；反过来，如果是顺序访问的，则使用Iterator会效率更高。可以使用类似如下的代码作判断：

1
2
3
4
5
6
7
8
9
复制代码if (list instanceof RandomAccess)

{ for (int i = 0; i < list.size(); i++){}

}else{

Iterator<?> iterator = list.iterable(); while (iterator.hasNext()){iterator.next()}

}

foreach循环的底层实现原理就是迭代器Iterator，参见Java语法糖1：可变长度参数以及foreach循环原理。所以后半句”反过来，如果是顺序访问的，则使用Iterator会效率更高”的意思就是顺序访问的那些类实例，使用foreach循环去遍历。

20、使用同步代码块替代同步方法

这点在多线程模块中的synchronized锁方法块一文中已经讲得很清楚了，除非能确定一整个方法都是需要进行同步的，否则尽量使用同步代码块，避免对那些不需要进行同步的代码也进行了同步，影响了代码执行效率。

21、将常量声明为static final，并以大写命名

这样在编译期间就可以把这些内容放入常量池中，避免运行期间计算生成常量的值。另外，将常量的名字以大写命名也可以方便区分出常量与变量

说到这里顺便给大家推荐一个Java架构方面的交流学习群：956011797，点击立即加入里面会免费分享一些资深架构师录制的视频录像：有Spring，MyBatis，Netty源码分析，高并发、高性能、分布式、微服务架构的原理，JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源和前辈的面试经验和面试题，相信对于已经工作和遇到技术瓶颈的码友，在这个群里会有你需要的内容。

22、不要创建一些不使用的对象，不要导入一些不使用的类

这毫无意义，如果代码中出现”The value of the local variable i is not used”、”The import java.util is never used”，那么请删除这些无用的内容

23、程序运行过程中避免使用反射

关于，请参见反射。反射是Java提供给用户一个很强大的功能，功能强大往往意味着效率不高。不建议在程序运行过程中使用尤其是频繁使用反射机制，特别是Method的invoke方法，如果确实有必要，一种建议性的做法是将那些需要通过反射加载的类在项目启动的时候通过反射实例化出一个对象并放入内存—-用户只关心和对端交互的时候获取最快的响应速度，并不关心对端的项目启动花多久时间。

24、使用数据库连接池和线程池

这两个池都是用于重用对象的，前者可以避免频繁地打开和关闭连接，后者可以避免频繁地创建和销毁线程

25、使用带缓冲的输入输出流进行IO操作

带缓冲的输入输出流，即BufferedReader、BufferedWriter、BufferedInputStream、BufferedOutputStream，这可以极大地提升IO效率

26、顺序插入和随机访问比较多的场景使用ArrayList，元素删除和中间插入比较多的场景使用LinkedList

这个，理解ArrayList和LinkedList的原理就知道了

27、不要让public方法中有太多的形参

public方法即对外提供的方法，如果给这些方法太多形参的话主要有两点坏处：

1、违反了面向对象的编程思想，Java讲求一切都是对象，太多的形参，和面向对象的编程思想并不契合

2、参数太多势必导致方法调用的出错概率增加

至于这个”太多”指的是多少个，3、4个吧。比如我们用JDBC写一个insertStudentInfo方法，有10个学生信息字段要插如Student表中，可以把这10个参数封装在一个实体类中，作为insert方法的形参

28、字符串变量和字符串常量equals的时候将字符串常量写在前面

这是一个比较常见的小技巧了，如果有以下代码：

1
2
3
4
5
6
复制代码String str = "123";
if (str.equals("123")) {

...

}

建议修改为：

1
2
3
4
5
6
7
8
复制代码String str = "123";
if ("123".equals(str))

{

...

}

这么做主要是可以避免空指针异常

29、请知道，在java中if (i == 1)和if (1 == i)是没有区别的，但从阅读习惯上讲，建议使用前者

平时有人问，”if (i == 1)”和”if (1== i)”有没有区别，这就要从C/C++讲起。

在C/C++中，”if (i == 1)”判断条件成立，是以0与非0为基准的，0表示false，非0表示true，如果有这么一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
复制代码int i = 2;
if (i == 1)

{

...

}else{

...

}

C/C++判断”i==1″不成立，所以以0表示，即false。但是如果：

1
复制代码int i = 2;if (i = 1) { ... }else{ ... }

万一程序员一个不小心，把”if (i == 1)”写成”if (i = 1)”，这样就有问题了。在if之内将i赋值为1，if判断里面的内容非0，返回的就是true了，但是明明i为2，比较的值是1，应该返回的false。这种情况在C/C++的开发中是很可能发生的并且会导致一些难以理解的错误产生，所以，为了避免开发者在if语句中不正确的赋值操作，建议将if语句写为：

1
复制代码int i = 2;if (1 == i) { ... }else{ ... }

这样，即使开发者不小心写成了”1 = i”，C/C++编译器也可以第一时间检查出来，因为我们可以对一个变量赋值i为1，但是不能对一个常量赋值1为i。

但是，在Java中，C/C++这种”if (i = 1)”的语法是不可能出现的，因为一旦写了这种语法，Java就会编译报错”Type mismatch: cannot convert from int to boolean”。但是，尽管Java的”if (i == 1)”和”if (1 == i)”在语义上没有任何区别，但是从阅读习惯上讲，建议使用前者会更好些。

30、不要对数组使用toString()方法

看一下对数组使用toString()打印出来的是什么：

1
2
3
4
5
6
7
复制代码public static void main(String[] args)

{ int[] is = new int[]{1, 2, 3};

System.out.println(is.toString());

}

结果是：

1
复制代码[I@18a992f

本意是想打印出数组内容，却有可能因为数组引用is为空而导致空指针异常。不过虽然对数组toString()没有意义，但是对集合toString()是可以打印出集合里面的内容的，因为集合的父类AbstractCollections重写了Object的toString()方法。

31、不要对超出范围的基本数据类型做向下强制转型

这绝不会得到想要的结果：

1
2
3
4
5
6
7
8
9
10
复制代码public static void main(String[] args)
{ 

long l = 12345678901234L;

int i = (int)l;

System.out.println(i);

}

我们可能期望得到其中的某几位，但是结果却是：

1
复制代码1942892530

解释一下。Java中long是8个字节64位的，所以12345678901234在计算机中的表示应该是：

0000 0000 0000 0000 0000 1011 0011 1010 0111 0011 1100 1110 0010 1111 1111 0010

一个int型数据是4个字节32位的，从低位取出上面这串二进制数据的前32位是：

0111 0011 1100 1110 0010 1111 1111 0010

这串二进制表示为十进制1942892530，所以就是我们上面的控制台上输出的内容。从这个例子上还能顺便得到两个结论：

1、整型默认的数据类型是int，long l = 12345678901234L，这个数字已经超出了int的范围了，所以最后有一个L，表示这是一个long型数。顺便，浮点型的默认类型是double，所以定义float的时候要写成””float f = 3.5f”

2、接下来再写一句”int ii = l + i;”会报错，因为long + int是一个long，不能赋值给int

32、公用的集合类中不使用的数据一定要及时remove掉

如果一个集合类是公用的（也就是说不是方法里面的属性），那么这个集合里面的元素是不会自动释放的，因为始终有引用指向它们。所以，如果公用集合里面的某些数据不使用而不去remove掉它们，那么将会造成这个公用集合不断增大，使得系统有内存泄露的隐患。

33、把一个基本数据类型转为字符串，基本数据类型.toString()是最快的方式、String.valueOf(数据)次之、数据+””最慢

把一个基本数据类型转为一般有三种方式，我有一个Integer型数据i，可以使用i.toString()、String.valueOf(i)、i+””三种方式，三种方式的效率如何，看一个测试：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
复制代码public static void main(String[] args)

{ 

int loopTime = 50000;

Integer i = 0; long startTime = System.currentTimeMillis(); for (int j = 0; j < loopTime; j++)

{

String str = String.valueOf(i);

}

System.out.println("String.valueOf()：" + (System.currentTimeMillis() - startTime) + "ms");

startTime = System.currentTimeMillis(); for (int j = 0; j < loopTime; j++)

{

String str = i.toString();

}

System.out.println("Integer.toString()：" + (System.currentTimeMillis() - startTime) + "ms");

startTime = System.currentTimeMillis(); for (int j = 0; j < loopTime; j++)

{

String str = i + "";

}

System.out.println("i + \"\"：" + (System.currentTimeMillis() - startTime) + "ms");

}

运行结果为：

1
复制代码String.valueOf()：11ms Integer.toString()：5ms i + ""：25ms

所以以后遇到把一个基本数据类型转为String的时候，优先考虑使用toString()方法。至于为什么，很简单：

1、String.valueOf()方法底层调用了Integer.toString()方法，但是会在调用前做空判断

2、Integer.toString()方法就不说了，直接调用了

3、i + “”底层使用了StringBuilder实现，先用append方法拼接，再用toString()方法获取字符串

三者对比下来，明显是2最快、1次之、3最慢

34、使用最有效率的方式去遍历Map

遍历Map的方式有很多，通常场景下我们需要的是遍历Map中的Key和Value，那么推荐使用的、效率最高的方式是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
复制代码public static void main(String[] args)

{

HashMap<String, String> hm = new HashMap<String, String>();

hm.put("111", "222");

Set<Map.Entry<String, String>> entrySet = hm.entrySet();

Iterator<Map.Entry<String, String>> iter = entrySet.iterator(); while (iter.hasNext())

{

Map.Entry<String, String> entry = iter.next();

System.out.println(entry.getKey() + "\t" + entry.getValue());

}

}

如果你只是想遍历一下这个Map的key值，那用”Set keySet = hm.keySet();”会比较合适一些

35、对资源的close()建议分开操作

意思是，比如我有这么一段代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
复制代码try{

XXX.close();

YYY.close();

}catch (Exception e)

{

...

}

建议修改为：

1
复制代码try{ XXX.close(); }catch (Exception e) { ... }try{ YYY.close(); }catch (Exception e) { ... }

虽然有些麻烦，却能避免资源泄露。我们想，如果没有修改过的代码，万一XXX.close()抛异常了，那么就进入了cath块中了，YYY.close()不会执行，YYY这块资源就不会回收了，一直占用着，这样的代码一多，是可能引起资源句柄泄露的。而改为下面的写法之后，就保证了无论如何XXX和YYY都会被close掉。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

1.hashCode介绍

hashCode() 的作用是获取哈希码，也称为散列码；它实际上是返回一个int整数。这个散列码的作用是确定该对象在散列表中的索引位置，如果有看我的上一篇文章 什么是散列表，那么这里的散列码就相当于上文中根据首字母查询散列表例子中 人名关键字k在散列表中的具体地址。hashCode() 定义在JDK的Object.java中，这就意味着Java中的任何类都包含有hashCode() 函数。

2.hashCode 的作用

数组是java中效率最高的数据结构，但是“最高”是有前提的。第一我们需要知道所查询数据的所在位置。第二：如果我们进行迭代查找时，数据量一定要小，对于大数据量而言一般推荐集合。

在 Java 集合中有两类，一类是 List，一类是 Set 他们之间的区别就在于 List 集合中的元素师有序的，且可以重复，而 Set 集合中元素是无序不可重复的。对于 List 好处理，但是对于 Set 而言我们要如何来保证元素不重复呢？通过迭代来 equals() 是否相等。数据量小还可以接受，当我们的数据量大的时候效率可想而知（当然我们可以利用算法进行优化）。比如我们向 HashSet 插入 1000 数据，难道我们真的要迭代 1000 次，调用 1000 次 equals() 方法吗？hashCode 提供了解决方案。怎么实现？我们先看 hashCode 的源码(Object)。

1
复制代码    public native int hashCode();

它是一个本地方法，它的实现与本地机器有关。当我们向一个集合中添加某个元素，集合会首先调用 hashCode 方法，这样就可以直接定位它所存储的位置，若该处没有其他元素，则直接保存。若该处已经有元素存在，就调用 equals 方法来匹配这两个元素是否相同，相同则不存，不同则散列到其他位置。这样处理，当我们存入大量元素时就可以大大减少调用 equals() 方法的次数，极大地提高了效率。

所以 hashCode 在上面扮演的角色为寻域（寻找某个对象在集合中区域位置）。hashCode 可以将集合分成若干个区域，每个对象都可以计算出他们的 散列码，可以将 散列码分组，每个分组对应着某个存储区域（散列表），根据一个对象的 散列码就可以确定该对象所存储区域，这样就大大减少查询匹配元素的数量，提高了查询效率。

3.hashCode 对于一个对象的重要性

hashCode 重要么？不重要，对于 List 集合、数组而言，但是对于 HashMap、HashSet、HashTable 而言，它变得异常重要。所以在使用 HashMap、HashSet、HashTable 时一定要注意 hashCode。对于一个对象而言，其 hashCode 过程就是一个简单的 Hash 算法的实现，其实现过程对你实现对象的存取过程起到非常重要的作用。

以 HashTable 为例阐述 hashCode 对于一个对象的重要性。

一个对象势必会存在若干个属性，如何选择属性来进行散列考验着一个人的设计能力。如果我们将所有属性进行散列，这必定会是一个糟糕的设计，因为对象的 hashCode 方法无时无刻不是在被调用，如果太多的属性参与散列，那么需要的操作数时间将会大大增加，这将严重影响程序的性能。但是如果较少属相参与散列，散列的多样性会削弱，会产生大量的散列“冲突”，除了不能够很好的利用空间外，在某种程度也会影响对象的查询效率。其实这两者是一个矛盾体，散列的多样性会带来性能的降低。

那么如何对对象的 hashCode 进行设计，本人 也没有经验。从网上查到了这样一种解决方案：设置一个缓存标识来缓存当前的散列码，只有当参与散列的对象改变时才会重新计算，否则调用缓存的 hashCode，这样就可以从很大程度上提高性能。

在 HashTable 计算某个对象在 table[] 数组中的索引位置，其代码如下：

1
复制代码    int index = (hash & 0x7FFFFFFF) % tab.length;

为什么要 &0x7FFFFFFF？因为某些对象的 hashCode 可能会为负值，与 0x7FFFFFFF 进行与运算可以确保 index 为一个正数。通过这步我可以直接定位某个对象的位置，所以从理论上来说我们是完全可以利用 hashCode 直接定位对象的散列表中的位置，但是为什么会存在一个 key-value 的键值对，利用 key 的 hashCode 来存入数据而不是直接存放 value 呢？这就关系 HashTable 性能问题的最重要的问题: Hash 冲突！(详见上篇)

我们知道冲突的产生是由于不同的对象产生了相同的散列码， hashcode 返回的是 int，它的值只可能在 int 范围内。如果我们存放的数据超过了 int 的范围呢？这样就必定会产生两个相同的 散列码，这时在 散列码 位置处会存储两个对象，我们就可以利用 key 本身来进行判断。所以具有相索引的对象，在该 散列码 位置处存在多个对象，我们必须依靠 key 的 hashCode 和key 本身来进行区分。而Key的比较就用到了equals

4.hashCode 与 equals

简而言之就是：

  • 如果两个对象相等，则hashcode一定也是相同的
  • 两个对象相等,对两个对象分别调用equals方法都返回true
  • 两个对象有相同的hashcode值，它们也不一定是相等的
  • 因此，equals 方法被覆盖过，则 hashCode 方法也必须被覆盖
  • hashCode() 的默认行为是对堆上的对象产生独特值。如果没有重写 hashCode()，则该 class 的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）

对象的比较过程如下：

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于 
1
复制代码发表文章是为了记录自己的学习。

运行环境：mac

安装地址：docs.docker.com/docker-for-… \

一、启动Nginx服务器

1
复制代码启动Nginx服务器，并进入模拟终端

docker run -p 8080:80 --name nginx_web -it nginx /bin/bash

1
2
3
4
复制代码-p是端口映射，本地端口：docker启动服务的内部端口
--name 是给启动的容器设置一个名称
- i 让容器的标准输入打开
- t 让docker分配一个伪终端并绑定到标准输入上

二、了解Nginx镜像的配置文件位置

1
2
3
4
5
复制代码日志文件位置：/var/log/nginx
配置文件位置：/etc/nginx
资源存放位置：/usr/share/nginx/html

上面的配置路径是我电脑上的虚拟linux中地址，请各位读者，也自己去看下自己的配置位置

三、访问Nginx服务

1
2
3
4
复制代码现在通过localhost:8080 端口，就可以访问我们构建的Nginx服务了。
运行 docker exec -it nginx_web /bin/bash 进入容器
进入 /usr/share/nginx/html 目录
可以把我们的web文件放到此目录下面。这样一个docker构建的Nginx服务就完成了

四、docker的一些常用指令

1
复制代码查看我们正在运行的容器

docker ps

1
复制代码查看运行过的所有容器

docker ps -a

1
复制代码重新启动刚刚启动过的容器

docker restart nginx_web

1
复制代码进入容器内部

docker attach nginx_web / docker exec -it nginx_web /bin/bash

1
复制代码退出容器内部

ctrl + P + Q

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

发表于

一、前言

为什么要用Sanic，请见 让你的Python（Web应用）飞起来，（异步/协程）全家桶

废话不多讲，直接进入正题，我会按照正常的Web应用程序架构来讲Sanic的用法

二、进入正题

基本操作

  1. 安装Sanic

pip install sanic

  1. 导入Sanic
1
2
复制代码from sanic import Sanic
app = Sanic(__name__)

中间件（Middleware And Listeners）

服务启动之前

1
2
3
4
5
复制代码@app.listener('before_server_start')
async def start_connection(app, loop):
    # 执行一些初始化任务
    # 例如初始化 Redis 连接池
    await RedisPool.init_redis_conn_pool(loop)

服务停止之前

1
2
3
4
5
6
复制代码@app.listener('after_server_stop')
async def start_connection(app, loop):
    # 执行一些备份、应急、关闭任务
    # 例如关闭连接池
    await RedisPool.close_redis_conn_pool()
    await close_connection(app, loop)

请求（Request）中间件

1
2
3
4
5
复制代码@app.middleware('request')
async def add_tokrn_to_request(request):
    # 每次请求会经过此方法，可以做一些对request的处理
    # 例如添加token，secret，token
    await session_interface.open(request)

响应（Response）中间件

1
2
3
4
5
6
复制代码@app.middleware('response')
async def save_session(request, response):
    logger = logging.getLogger('response')
    # 每次服务器响应会经过此方法，可以做一些异常，cookie，logger等的处理
    # 例如写入cookie，记录用户日志
    await session_interface.save(request, response)

蓝图（Blueprint）

类似Flask，用来组织应用程序，也就是大多数我们mvc模式中的controller，

  1. 首先声明一个BP
1
2
3
复制代码order_bp = Blueprint('orders', url_prefix='v1/api/order')
# url_prefix：定义路由修正，
# 例如当前蓝图下你定义了一个 query/id 的路由，那么你应该这样访问它 v1/api/order/query/id
  1. 在主程序中（main.py）引用
1
2
3
复制代码from controller.order_controller import order_bp
app.blueprint(order_bp)
# 这样order_bp就被注册到sanic中，可以通过浏览器 http://example.com/v1/api/order/query/id 访问
  1. 使用蓝图处理异常
1
2
3
复制代码@bp.exception(NotFound)
def ignore_404(request, exception):
    return text("Yep, I totally found the page: {}".format(request.url))

路由（Routing）

1
2
3
4
5
6
7
复制代码# GET 路由参数的方式
@order_bp.route('/delete/<oid:int>', methods=['GET'])
async def delete_order(request, oid):
    result = await OrderModel().del_order_by_id(oid)
    if result:
        return json({'status': 'ok', 'result': result})
    return json({'status': 'fail', 'errmsg': '获取数据失败'})
1
2
3
4
5
6
7
8
9
10
11
复制代码# Get params的方式
@service_bp.route('/message/send', methods=['GET'])
async def send_message(request):
    uuid = request.args['uuid'][0]
    page = request.args['page'][0]
    result = await MessageService().send_message_2_user(uuid,page)
    if result:
        return json({'status': 'ok', 'result': result})
    return json({'status': 'fail', 'errmsg': '获取数据失败'})

    return raw(result)
1
2
3
4
5
6
7
8
9
10
11
12
13
复制代码# 修改价格
@order_bp.route('/price/modify', methods=['POST'])
async def price_modify(request):
    order_id = request.json['order_id']
    price = request.json['price']
    postage = request.json['postage']
    show_price = request.json['show_price']
    is_shipping = request.json['is_shipping']
    result = await OrderModel().modify_price(order_id, price, postage, show_price, is_shipping)

    if result:
        return json({'status': 'ok', 'result': result})
    return json({'status': 'fail', 'errmsg': '获取数据失败'})

响应类型

1
2
3
4
5
6
7
8
9
10
11
复制代码from sanic.response import json
# text
response.text('hello world')
# html
response.html('<p>hello world</p>')
# json
response.json({'hello': 'world'})
# file
response.file('/srv/www/hello.txt')
# stream
response.stream(stream_ctx, content_type='text/plain')

如果我想在Sanic启动之后额外运行任务怎么办？

1
2
复制代码app.add_task(notify_server_started())
app.add_task(notify_html_spider())

三、启动Sanic服务

1
2
3
4
复制代码if __name__ == "__main__":
    app.add_task(notify_server_started())
    app.add_task(notify_html_spider())
    app.run(host="0.0.0.0", port=settings.PORT, workers=settings.workers, debug=settings.DEBUG, access_log=True)

在启动时可以传入一些参数，其他的都是字面意思，很好理解，这里讲一下 Workers

workers 接受 integer 类型，默认为1，传入4意味着Sanic会为你复制四份，创建四个进程来运行你的Sanic App

如图

多进程状态下，路由会进行自动分配，从而增加吞吐量，workers的个数依据自身服务器性能而定，如果创建太多会出现占用情况，同样多进程模式下，你的数据库连接或者数据库连接池的数量也要适当调大，否则会出现连接数过多而拒绝连接的情况

四、获奖感言

Sanic的介绍就这么多，只是一个基本入门，至于其他类似订阅发布监听等等功能大家可以移步 Sanic官网 进行学习和查阅

下期我可能会联合Sanic讲解关于异步Redis(aioredis)的使用，例子打算用类似订单倒计时的功能，结合redis的订阅发布通知来讲

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%