开发者博客 – IT技术 尽在开发者博客

开发者博客 – 科技是第一生产力


  • 首页

  • 归档

  • 搜索

SpringSecurity学习 - 记住我

发表于 2021-11-22

「这是我参与11月更文挑战的第22天,活动详情查看:2021最后一次更文挑战」

作者:汤圆

个人博客:javalover.cc

前言

前面介绍了基于SpringSecurity的表单登录例子;

本篇介绍怎么给表单登录添加一个记住我的功能;

有了这个功能,那么在token失效后,系统会自动获取最新token,而不用重新登录;

这里需要注意一点:这里的token并不是普通的token,而是JSESSIONID;这个JSESSIONID会在前端第一次请求后端时返回,以后这个JSESSION就是前后台通讯的凭证

目录

  1. 安全配置
  2. 前端组件
  3. 实践-不勾选rememberMe
  4. 实践-勾选rememberMe
  5. 更多配置

正文

1. 安全配置

这里我们做一个最简单的配置,如下所示:添加一个rememberMe()方法

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
java复制代码@Configuration
@EnableWebSecurity
@Slf4j
public class SecurityConfiguration extends WebSecurityConfigurerAdapter {

@Autowired
public void configureGlobal(AuthenticationManagerBuilder auth) throws Exception {
// 数据没有持久化,只是保存在内存中
auth.inMemoryAuthentication()
.withUser("javalover").password(passwordEncoder().encode("123456")).roles("USER")
.and()
.withUser("admin").password(passwordEncoder().encode("123456")).roles("ADMIN");
}
// 授权相关操作
@Override
protected void configure(HttpSecurity http) throws Exception {
log.info("=== SecurityConfiguration.authorize ===");
http
// 登出 所有用户都可以访问
.logout().permitAll()
.deleteCookies("JSESSIONID")
.and()
.rememberMe()
// ...省略其他配置
;
}


}

可以看到,我们要做的只是提供一个rememberMe()方法,前台就可以在token失效后自动获取最新的token,而不用再重新输入用户名密码进行登录操作;

2. 前端组件

这里我们前端也尽可能简化,在之前的表单登录基础上,只增加一个复选框 rememberMe,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
html复制代码<form action="/login" method="post">
<table>
<tr>
<input name="username" placeholder="用户名">
</tr>
<tr>
<input name="password" placeholder="密码">
</tr>
<tr>
<td>记住我:</td>
<td><input type="checkbox" name="remember-me" /></td>
</tr>
</table>
<button type="submit">登录</button>
</form>

3. 实践-不勾选rememberMe

下面我们就可以基于上面的代码,进行一个简单的测试:看一下 勾选rememberMe和不勾选的差别

完整代码见文末地址

第一步:启动程序,界面如下所示:javalover/123456

image-20211122152245002

这里我们先不勾选记住我,点击登录,跳转到如下的主页:

image-20211122152555706

第二步:接下来是重点,这里我们删除本地cookie中的JSESSIONID,如下所示:F12->应用程序->cookies->JSESSION->右键-删除

image-20211122152731372

第三步:刷新页面,可以看到,自动跳转到登录页面,因为token失效了,前后端通讯的凭证没了:

image-20211122152901019

其实上面我们也可以不删除cookie,等着session失效也可以(默认30分钟,可以在application.yml中配置:server.servlet.session.timeout=60,默认单位秒)

后端的session都失效了,那session产生的JSESSIONID肯定也无效了;

4. 实践-勾选rememberMe

下面我们勾选记住我,重复上面的步骤,会发现在删除cookie中的JSESSIONID时,看到多了一个remember-me;

image-20211122153751334

其实这里我们可以换个角度来理解:虽然删了JSESSIONID,但是因为还有一个remember-me,所以前后端的通讯还是没有断开;

所以此时我们刷新页面,还是停留在主页,不会跳转到登录界面;

但是如果我们把remember-me也一起删掉,那么结果很明显,还是会跳到登陆界面。

5. 更多配置

失效时间:

上面我们配置的remember-me,默认的token失效时间是两周,下面我们可以配置的短一点,比如一天:

1
2
3
4
5
6
java复制代码.logout().permitAll()
.deleteCookies("JSESSIONID")
.and()
.rememberMe()
.tokenValiditySeconds(86400)
.and()

失效时间:严格意义上来说,上面这个失效时间 应该是remember-me的失效时间;

这样的话,如果超过一天后,你再去删除JSESSIONID或者session失效,那么刷新页面还是会跳转到登录界面;

加密的密钥:

前面我们在调试界面看到的remember-me cookie值,它的值是由:MD5(用户名+过期时间+密码+密钥)合成的;

这里的密钥我们可以自己配置,如下所示:

1
2
3
java复制代码.rememberMe()
.key("privateKey")
.tokenValiditySeconds(86400)

总结

上面介绍了rememberMe的相关知识,了解了其实rememberMe就是:用新的通讯凭证remember-me来管理旧的通讯凭证JSESSIONID;

当JSESSIONID被删除或者session过期时,如果rememberMe cookie还没过期(默认两周),那么系统就可以自动登录

remember-me真实的过期时间可以在调试界面看到,如下所示:

image-20211122162553634

源码地址

本文转载自: 掘金

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

Python的五大奇淫技巧,带你掌握高效编程技巧的充实感

发表于 2021-11-22

下面整理的五个有关Python的奇淫实用小技巧,代码最多七行,每一行都仔细带有注释,希望能对刚学习Python的新手有所帮助。

在这里插入图片描述

一、根据条件在序列中筛选数据

  • 假设有一个数字列表 data, 过滤列表中的负数
1
2
3
4
5
6
7
python复制代码data = [1, 2, 3, 4, -5]

# 使用列表推导式
result = [i for i in data if i >= 0]

# 使用 fliter 过滤函数
result = filter(lambda x: x >= 0, data)
  • 学生的数学分数以字典形式存储,筛选其中分数大于 80 分的同学
1
2
3
4
python复制代码from random import randint

d = {x: randint(50, 100) for x in range(1, 21)}
r = {k: v for k, v in d.items() if v > 80}

二、对字典的键值对进行翻转

  • 使用 zip() 函数

zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表。

1
2
3
4
python复制代码from random import randint, sample

s1 = {x: randint(1, 4) for x in sample("abfcdrg", randint(1, 5))}
d = {k: v for k, v in zip(s1.values(), s1.keys())}

三、统计序列中元素出现的频度

  • 某随机序列中,找到出现次数最高的3个元素,它们出现的次数是多少

方法1:

1
2
3
4
5
6
7
8
9
10
11
python复制代码# 可以使用字典来统计,以列表中的数据为键,以出现的次数为值
from random import randint

# 构造随机序列
data = [randint(0, 20) for _ in range(30)]

# 列表中出现数字出现的次数
d = dict.fromkeys(data, 0)

for v in d:
d[v] += 1

方法2:

1
2
3
4
5
6
7
8
9
10
11
12
13
python复制代码# 直接使用 collections 模块下面的 Counter 对象
from collections import Counter
from random import randint

data = [randint(0, 20) for _ in range(30)]

c2 = Counter(data)

# 查询元素出现次数
c2[14]

# 统计频度出现最高的3个数
c2.most_common(3)
  • 对某英文文章单词进行统计,找到出现次数最高的单词以及出现的次数
1
2
3
4
5
6
7
8
9
10
11
python复制代码import re
from collections import Counter

# 统计某个文章中英文单词的词频
with open("test.txt", "r", encoding="utf-8") as f:
d = f.read()

# 所有的单词列表
total = re.split("\W+", d)
result = Counter(total)
print(result.most_common(10))

四、根据字典中值的大小,对字典中的项进行排序

  • 比如班级中学生的数学成绩以字典的形式存储,请按数学成绩从高到底进行排序

方法1:

1
2
3
4
5
6
python复制代码# 利用 zip 将字典转化为元组,再用 sorted 进行排序
from random import randint

data = {x: randint(60, 100) for x in "xyzfafs"}
sorted(data)
data = sorted(zip(data.values(), data.keys()))

方法2:

1
2
3
4
5
6
python复制代码# 利用 sorted 函数的 key 参数
from random import randint

data = {x: randint(60, 100) for x in "xyzfafs"}
data.items()
sorted(data.items(), key=lambda x: x[1])

五、在多个字典中找到公共键

  • 实际场景:在足球联赛中,统计每轮比赛都有进球的球员

第一轮:{“C罗”: 1, “苏亚雷斯”:2, “托雷斯”: 1..}

第二轮:{“内马尔”: 1, “梅西”:2, “姆巴佩”: 3..}

第三轮:{“姆巴佩”: 2, “C罗”:2, “内马尔”: 1..}

1
2
3
4
5
6
7
8
9
10
11
12
13
python复制代码from random import randint, sample
from functools import reduce

# 模拟随机的进球球员和进球数
s1 = {x: randint(1, 4) for x in sample("abfcdrg", randint(1, 5))}
s2 = {x: randint(1, 4) for x in sample("abfcdrg", randint(1, 5))}
s3 = {x: randint(1, 4) for x in sample("abfcdrg", randint(1, 5))}

# 首先获取字典的 keys,然后取每轮比赛 key 的交集。由于比赛轮次数是不定的,所以使用 map 来批量操作
# map(dict.keys, [s1, s2, s3])

# 然后一直累积取其交集,使用 reduce 函数
reduce(lambda x, y: x & y, map(dict.keys, [s1, s2, s3]))

你们的支持是我持续更新下去的动力,(点赞,关注,评论)

在这里插入图片描述

点击领取🎁 q群: 675240729(纯技术交流和资源共享)以自助拿走。

①行业咨询、专业解答
②Python开发环境安装教程
③400集自学视频
④软件开发常用词汇
⑤最新学习路线图
⑥3000多本Python电子书

本文转载自: 掘金

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

JAVA虚拟机运行时数据区域与内存溢出异常 运行时数据区域与

发表于 2021-11-22

「这是我参与11月更文挑战的第3天,活动详情查看:2021最后一次更文挑战」

运行时数据区域与内存溢出异常

Java虚拟机在执行Java程序的过程中会把它所管理的内存划分为若干个不同的数据区域。这些区域 有各自的用途,以及创建和销毁的时间,有的区域随着虚拟机进程的启动而一直存在,有些区域则是 依赖用户线程的启动和结束而建立和销毁

image.png

程序计数器

定义

程序计数器(Program Counter Register)是一块较小的内存空间,它可以看作是当前线程所执行的 字节码的行号指示器。

作用

在Java虚拟机的概念模型里[1],字节码解释器工作时就是通过改变这个计数器 的值来选取下一条需要执行的字节码指令,它是程序控制流的指示器,分支、循环、跳转、异常处 理、线程恢复等基础功能都需要依赖这个计数器来完成。

为什么程序计数器是线程私有的

由于Java虚拟机的多线程是通过线程轮流切换、分配处理器执行时间的方式来实现的,在任何一 个确定的时刻,一个处理器(对于多核处理器来说是一个内核)都只会执行一条线程中的指令。因 此,为了线程切换后能恢复到正确的执行位置,每条线程都需要有一个独立的程序计数器,各条线程 之间计数器互不影响,独立存储,我们称这类内存区域为“线程私有”的内存。 如果线程正在执行的是一个Java方法,这个计数器记录的是正在执行的虚拟机字节码指令的地 址;如果正在执行的是本地(Native)方法,这个计数器值则应为空(Undefined)。

可能产生的异常

此内存区域是唯 一一个在《Java虚拟机规范》中没有规定任何OutOfMemoryError情况的区域。

Java虚拟机栈

定义

与程序计数器一样,Java虚拟机栈(Java Virtual Machine Stack)也是线程私有的,它的生命周期 与线程相同。

image.png

虚拟机栈描述的是Java方法执行的线程内存模型:每创建一个线程,虚拟机就会为这个线程创建一个虚拟机栈 每个方法被执行的时候,Java虚拟机都 会同步创建一个栈帧[1](Stack Frame)用于存储局部变量表、操作数栈、动态连接、方法出口等信 息。每一个方法被调用直至执行完毕的过程,就对应着一个栈帧在虚拟机栈中从入栈到出栈的过程。
与对象内存分配关系最密切的区 域是“堆”和“栈”两块。其中,“堆”在稍后笔者会专门讲述,而“栈”通常就是指这里讲的虚拟机栈,或 者更多的情况下只是指虚拟机栈中局部变量表部分。

image.png

可能产生的异常

在《Java虚拟机规范》中,对这个内存区域规定了两类异常状况:如果线程请求的栈深度大于虚 拟机所允许的深度,将抛出StackOverflowError异常;如果Java虚拟机栈容量可以动态扩展[2],当栈扩 展时无法申请到足够的内存会抛出OutOfMemoryError异常。

本地方法栈

定义

本地方法栈(Native Method Stacks)与虚拟机栈所发挥的作用是非常相似的,其区别只是虚拟机 栈为虚拟机执行Java方法(也就是字节码)服务,而本地方法栈则是为虚拟机使用到的本地(Native) 方法服务。

可能产生的异常

与虚拟机栈一样,本地方法栈也会在栈深度溢出或者栈扩展失 败时分别抛出StackOverflowError和OutOfMemoryError异常。

Java堆

定义

Java堆(Java Heap)是虚拟机所管理的内存中最大的一块。Java堆是被所 有线程共享的一块内存区域,在虚拟机启动时创建。此内存区域的唯一目的就是存放对象实例,Java 世界里“几乎”所有的对象实例都在这里分配内存。

可能产生的异常

Java堆既可以被实现成固定大小的,也可以是可扩展的,不过当前主流的Java虚拟机都是按照可扩 展来实现的(通过参数-Xmx和-Xms设定)。如果在Java堆中没有内存完成实例分配,并且堆也无法再 扩展时,Java虚拟机将会抛出OutOfMemoryError异常。

方法区

定义

方法区(Method Area)与Java堆一样,是各个线程共享的内存区域,它用于存储已被虚拟机加载 的类型信息、常量、静态变量、即时编译器编译后的代码缓存等数据。虽然《Java虚拟机规范》中把 方法区描述为堆的一个逻辑部分,但是它却有一个别名叫作“非堆”(Non-Heap),目的是与Java堆区 分开来。

可能产生的异常

这区域的内存回 收目标主要是针对常量池的回收和对类型的卸载,一般来说这个区域的回收效果比较难令人满意,尤 其是类型的卸载,条件相当苛刻,但是这部分区域的回收有时又确实是必要的。
如果方法区无法满足新的内存分配需求时,将抛出 OutOfMemoryError异常。

运行时常量池

定义

运行时常量池(Runtime Constant Pool)是方法区的一部分。Class文件中除了有类的版本、字 段、方法、接口等描述信息外,还有一项信息是常量池表(Constant Pool Table),用于存放编译期生 成的各种字面量与符号引用,这部分内容将在类加载后存放到方法区的运行时常量池中。
运行时常量池相对于Class文件常量池的另外一个重要特征是具备动态性,Java语言并不要求常量 一定只有编译期才能产生,也就是说,并非预置入Class文件中常量池的内容才能进入方法区运行时常 量池,运行期间也可以将新的常量放入池中,这种特性被开发人员利用得比较多的便是String类的 intern()方法。

存在的异常

既然运行时常量池是方法区的一部分,自然受到方法区内存的限制,当常量池无法再申请到内存 时会抛出OutOfMemoryError异常。

本文转载自: 掘金

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

如何在微服务中设计用户权限策略?

发表于 2021-11-22

在当今的软件工程领域,微服务架构占主导地位。虽然这种基础设施方法有很多优点,但它已经形成了一个非常复杂的管理网络。IBM 确认了这一点,共享该应用程序包含“数十个、数百甚至数千个不同的、可独立部署和可更新的服务”。除保持服务可靠性外,管理员还必须有效地管理数百个甚至数千个用户的权限。

这就是说,在用户访问特定服务之前,后端必须对其进行身份验证和授权。关键是,用户实际上是以自己的身份登录的,并且在此之后拥有执行特定操作所需的权限。决定权限、基于角色的访问控制(role-based access control,RBAC)以及其他控制已经变得非常棘手。另外,你管理服务相关权限的粒度是可变的。

为保证长期安全性、服务可用性和微服务可扩展性,设计清晰的用户权限策略是必不可少的。你无法使用“一扇摇摆的门”来保护你的 API 端点。在会话过程中控制用户看到和执行的操作是应用程序管理的基础。

\

1评估标准

本文介绍了微服务中一些有用的用户权限策略,并对其进行了分解。这样做可以帮助你了解哪些策略最适合你的组织的服务。对于每个权限策略,我们将基于以下要点评估:

  • 易用性:这种方法对用户的友好程度如何?每天使用基本功能有多简单?
  • 可维护性:管理员如何能够在需要扩展或更改之后,快速地更改权限、组和结构?
  • 稳定性:解决方案对于非预期故障的弹性有多大,以及其背后的 API 或机制是否能够长期有效地发挥作用?

这些标准构成了衡量策略有效性的强大基线。

\

2权限策略简介

对你的权限进行管理时,有两种主要途径,每一种都有其细微差别。首先,你可以选择自己管理所有的权限,换句话说,你不需要依靠集中的第三方工具。这就是所谓的细粒度方法。采用这种方法的团队通常想要对他们的部署有不受约束的控制。

无需深入研究策略(稍后将详细介绍),可以根据用户和应用程序之间的关系、会话设计、服务器安排和 API 依赖关系等因素选择许多子方法。

相反,还有一种集中式服务的方法。一般情况下,这取决于对外部工具的集成和第三方服务的集成,这些服务在一定程度上保留了你的后端访问的权限。这样,你就可以使用统一的界面(包括命令行界面)来管理权限和角色。通常,对更改实际服务代码的依赖较少;你的重点是配置。

每一个策略都各有利弊。用例也随基础设施的不同而不同。在这种情况下,让我们深入研究。

策略 1:管理自己的权限

免责声明:自我管理你的权限可能是一个费力的过程。但是,还需要做一些权宜之计,根据特定服务,对权限进行粒度控制。因为你将承担大部分设置工作,所以理解自我管理微服务架构所带来的挑战是值得的。

请记住,用户的权限首先与身份验证和授权密切相关。你的权限设置直接影响用户会话从登陆到注销的过程。如果将这些行为扩展到多个用户账户,则会出现一些明显的障碍:

  • 一种应用程序将多个微服务流程统一使用,因此,有必要在权限方面对这些服务进行隔离。必须在后端分别处理用户对每个服务的访问请求。
  • 你必须协调服务级身份验证和授权逻辑与全局逻辑之间的关系;尽管代码重用是可能的,但是它会产生依赖性,最终会阻碍系统的灵活性。
  • 微服务必须处理其自身的业务逻辑,并且维护全局权限逻辑存在的单一责任。
  • HTTP 的无状态设计非常适合于服务器和节点的负载平衡,但是为了与有状态登录会话兼容,所需的漏洞会降低服务的可扩展性。
  • 身份验证和授权本质上变得更加复杂,因为支持应用程序功能的交互是多样的。

任何自治权限策略的前提是进行创造性地避开这些限制。有多种方法可以做到这一点,我们现在来探讨一下。

无状态会话管理

微服务通常最好是保持无状态。多个容器都为共享的资源池而竞争,尤其是当服务经历了大量的用户活动时。这些使用高峰将产生大量内存需求;因此,无状态请求所需的内存开销要小得多。这些新事物是轻量级和敏捷的。服务器还可以并行处理大量请求,提高了稳定性和性能。这在多个用户同时登陆并访问资源时非常重要。这对所有用户来说都是相同的。

这就是说,我们可以通过三种方式将无状态方法的好处与会话结合起来。

第一种是通过使用称为粘性会话(sticky session)的方法,在这个方法中,服务器会处理用户最初请求,从而 ping 任何后续请求。负载均衡器对允许这种情况的发生至关重要,但只允许水平向扩展集群。但是,这种添加机器的实例(而不是通过升级当前机器来向上扩展)更可取,因为它允许成百上千的并发用户会话。当然,这些会话需要基于它们的行为进行身份验证和重复授权。切记,在这种情况下,强制的服务器交换将转储用户会话数据——要求重新登陆并访问授权服务器。

第二种是会话复制(session replication),它是在网络上保存用户会话数据并同步的。对用户数据的任何更改将自动推送到所有机器。所以,这种处理用户的方法会消耗更多的资源,通常采用带宽形式。这里有很好的一致性;服务器不会忘记用户的权限,或者忘记一个账户的后端关联。遗憾的是,可扩展性相对有限。

第三种是集中式会话存储(centralized session storage),它将用户凭证和相关数据放在一个共享位置。登录状态保持不透明,这意味着服务器不会将凭证解释为纯文本。这样做对安全性来说是很好的。尽管可以扩展,但是这种方法需要共享存储的保护机制。

客户端令牌

令牌可以帮助微服务及其服务器之间的无状态 - 有状态冲突。令牌并非将用户会话存储在服务器上,而是作为用户身份细节的存储容器。这在利用 cookie 的基于 Web 的服务中最为常见。用户将其令牌和会话信息保存在设备上。

通过使用这个令牌来确认所有用户对服务器的请求,然后决定每个用户的权限如何配合。这样,用户就可以看到、交互甚至修改哪些内容。不透明令牌是在某些情况下使用的专门令牌;对于 OAuth 来说,这些令牌是专有的,并且不可访问,同时指向服务器上持久存储的信息。OAuth 是一家流行的身份验证服务供应商,它提供了管理 API 和自定义 API 访问令牌。

此外,JSON Web 令牌(JWT)是一种流行的令牌格式,它是标准化的,并且基于三个元素构建。头部包含了类型和哈希算法(因为令牌必须加密)。有效负载包含用户 ID、用户名和到期日期。它还可以包含角色。最后,签名将验证令牌身份并为客户端提供验证。令牌通常会在短时间后刷新来保持安全性,以防攻击者窃取它们。

令牌化过程如下:

  1. 发出初始化登录的 API 请求。
  2. 服务器创建令牌。
  3. 令牌返回到存储它的客户端浏览器。
  4. 当执行操作时,用户通过头部将令牌发送给服务器。
  5. 验证签名,并传唤用户信息。
  6. 向客户端发送适当的响应。

令牌化还可以与 API 网关配对。请求并不直接进入服务器,而是通过中间网关审查操作并将其传递。微服务不会向用户公开,不管是检测出问题还是用户注销,网关可以撤销令牌。在客户端隐藏了授权令牌,因此无法如此轻松地解密。

单点登录

单点登录(Single sign-on,SSO)可能是最简化的访问管理方法,因为它允许用户的登录验证(身份验证步骤)在一系列捆绑的服务中对同一个用户进行认证。目前,应用程序通常在其功能范围内承载多个服务。逐一登录所有的服务,对用户来说是非常乏味的。对所有服务的访问都通过一个集中的认证服务进行路由。尽管在很多方面都很方便,但是这种方法很容易出错或网络流量激增。

互助式身份验证

当服务处于活动状态时,微服务通常彼此通信。这样,互联的微服务就会在用户开展业务时共享大量流量。由于每个服务唯一的身份验证证书是通过 TLS 交换的,所以双向 SSL 连接允许相互身份验证。应用实例不断变化的的性质会对这个身份验证过程造成麻烦,但是也有一些好消息:私有证书中心可以帮助确定如何为所有适用的服务进行颁发、撤销和更新证书。

忠告

所有这些选项中的共同缺点是易用性。每一种选项都有一定的取舍,并需要一定程度的手工设置才能成功。虽然内置的自动化可以间接地或直接简化权限处理过程,但在你的团队中需要特定的专业知识。合理地执行这些策略需要熟练掌握 API、安全性和微服务架构。经验不足的人更容易犯错,而这些错误会破坏权限处理。

诸如基于角色的访问控制和基于属性的访问控制(attribute-based access control,ABAC)这样的机制,都是活的概念,需要在服务的生命周期内持续地维护。很多情况下,自我管理的身份验证和授权都可能会出问题。以不可见的方式实施(就用户而言),也是系统安全的核心。糟糕的编码解决方案可能会提供过多关于后端权限结构的信息。

开源资源能否缓解开发之痛?尽管在很多情况下答案是肯定的,但事实是,成功的整合仍然是一个挑战。文档并非“百发百中”,跨语言的逻辑共享令人怀疑,而编码工作可能很大。

身份验证后授权用户

当你的服务确定你(或你的用户)是谁之后,它们将决定在应用程序中实际可以做什么。可以单独对每一个服务执行此操作,尽管这一过程需要一些时间,并且会带来潜在的问题。

尽管有利安全性和细粒度控制,但这要求为所有微服务重写安全逻辑。这样会导致臃肿的重复构建。这也会将每个服务与它没有的外部授权数据连接起来。最终,随着服务规模的扩展,这些零碎的设计在监控上变得更加复杂。

为了避开这些核心问题,团队通常会采用一个与每个服务共享的身份验证库的形式。他们还可以建立起将授权和身份验证连接起来的全局服务——通常是通过授权数据库。不幸的是,后一种方法使用全局服务来处理单个用户角色。这些检查会引起安全问题,并且会增加延迟。

有没有更好的办法处理授权呢?很多人认为,集中式的服务对监督他们的团队很有效,而且不需要太多的维护。这样就避免了传统 API 网关和单端点之间的强耦合问题。现有的第三方服务显然简化了这些步骤。

策略 2:使用集中式服务

虽然单个管理可能很复杂,但是集中式的方法可以提供你急需的简单性。这种策略使用一个中央微服务,将部署到现有应用程序中。这种形式一般采用补充式容器。

一些第三方服务,比如 Cerbos,甚至可以作为 sidecar 来运行:它与相关的应用程序松散耦合,同时以锁步方式完成基于权限的工作。这些 sidecar 很有用,因为它们是基于现有服务进行扩展的。

attachments-2021-11-CX5e39fL619b44b5599b4.jpg

提出授权和身份验证请求的所有服务都是通过这种专门的权限微服务进行路由的。该响应返回到客户端,以确定其请求是否成功。这个集中的部分强制执行了所有基于权限的决定。但是,如果同事运行多个节点,并且其中一个节点被分区,就可能会出现问题。

假定节点与其他系统节点有效分离。在集中式设置中,这个节点无法接受外部服务的任何权限决定。可能会失败关闭——拒绝所有的身份验证请求,或者失败开放。后者是非常有问题的,因为所有的身份验证请求都被批准。失败关闭会引起连锁反应,即所有客户对分区服务的请求都被拒绝。

在考虑像 Cerbos 这样的东西时,值得庆幸的是,情况会变得更清晰一些。对于非开发者来说,这个解决方案非常友好,因为它不需要了解任何规则和语言。权限逻辑的更改会自动推送到你的基础设施的每个角落,从而节省时间和精力。这个解决方案没有任何依赖性,仍然包含在本地网络中。像这样的集中式工具甚至可以在促进 GitOps 的同时确定角色。

集中式的服务在让事情变得简单时很有用。它们是微服务权限规则的单一真相来源,运行时不会使原本错综复杂的系统复杂化。现代衍生产品被设计用于容器化环境,并利用流行的 API 协议来有效地运行。

使用集中式服务会使没有深厚权限安全知识的小团队受益良多。尽管配置仍然很强大,但是在执行身份验证和授权时,需要做的工作更少。如果你在整个部署过程中使用多个框架或语言,那么集中式解决方案将使你能够快速实施你所需的不可知性。其中甚至包括了一些非常有用的测试,因为权限和微服务会随着时间而变化。

维护成本自然也降低了。因为中央服务可以向所有服务推送更改,你不必花费开发资源来分别更新每个服务。运行大量服务的组织可以从这一事实中得到一些安慰。

\

3结论

在自我管理与集中化的较量中,选出一个赢家并不是那么非黑即白。一个团队对其基础设施的舒适程度、某些技术和预算将决定适当的行动方案。即使是像 OAuth + JWT 这样的流行设置,也是安全和可靠的,但它们并非万无一失。一个集中式服务可以为让团队在不太挑剔或者打扰的情况下检查很多功能框。为微服务设计强大的权限策略,通常是公司能采取的最困难的安全措施。这样,集中化可以让不是用普通的无状态方法的团队更容易地做到这一点。

本文转载自: 掘金

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

MySQL入门系列 --- 2 DDL 操作数据库和数据表

发表于 2021-11-22

「这是我参与11月更文挑战的第15天,活动详情查看:2021最后一次更文挑战」

数据库、数据表、数据的关系

截屏2021-11-22 上午11.26.29.png

SQL分类:

1
2
3
4
scss复制代码DDL(Data Definition Language): 数据定义语言。用来操作数据库,表,列等。
DML(Data Manipulation Language): 数据操作语言。用来对数据库中表的数据进行增删改。
DQL(Data Query Language): 数据查询语言。用来查询数据库中表的记录(数据)。
DCL(Data Control Language): 数据控制语言。用来定义数据库的访问权限和安全级别,及创建用户。

DDL 查询和创建数据库

1
2
3
4
5
6
7
8
9
10
11
12
13
14
sql复制代码查询所有数据库
SHOW DATABASES;

查询数据库的创建语句
SHOW CREATE DATABASE 数据库名称;

创建数据库
CREATE DATABASE 数据库名称;

创建数据库(判断,如果不存在则创建)
CREATE DATABASE IF NOT EXISTS 数据库名称;

创建数据库(指定字符集)
CREATE DATABASE 数据库名称 CHARACTER SET 字符集名称;
1
ini复制代码SHOW DATABASES;
1
2
3
sql复制代码SHOW CREATE DATABASE mysql;
// 执行效果
CREATE DATABASE `mysql` /*!40100 DEFAULT CHARACTER SET utf8 */
1
sql复制代码CREATE DATABASE IF NOT EXISTS db2;
1
2
3
4
sql复制代码CREATE DATABASE db3 CHARACTER SET utf8;

SHOW CREATE DATABASE db3;
CREATE DATABASE `db3` /*!40100 DEFAULT CHARACTER SET utf8 */
1
2
3
4
sql复制代码-- 练习:创建db4数据库、如果不存在则创建,指定字符集为gbk
Create database if not exists db4 character set gbk;
-- 查看db4数据库的字符集
SHOW CREATE DATABASE db4;

DDL 修改、删除、使用数据库

1
2
3
4
5
6
7
8
9
10
sql复制代码修改数据库(修改字符集)
ALTER DATABASE 数据库名称 CHARACTER SET 字符集名称;
删除数据库
DROP DATABASE 数据库名称;
删除数据库(判断,如果存在则删除)
DROP DATABASE IF EXISTS 数据库名称;
使用数据库
USE 数据库名称;
查看当前使用的数据库
SELECT DATABASE();
1
2
3
4
5
6
sql复制代码ALTER DATABASE db4 CHARACTER SET utf8;
SHOW CREATE DATABASE db4;
DROP DATABASE db2;
DROP DATABASE IF EXISTS db2;
USE db4;
SELECT DATABASE();

DDL 查询数据表

1
2
3
4
5
6
7
8
sql复制代码查询所有的数据表
show tables;

查询表结构
desc 表名;

查询表字符集
show table status from 库名 like '表名';
1
2
3
4
sql复制代码USE mysql;
show tables;
desc user;
show table status from mysql like 'user';

DDL 创建数据表

1
2
3
4
5
6
7
8
lua复制代码创建数据表

create table 表名(
列名 数据类型 约束,
列名 数据类型 约束,
.......
列名 数据类型 约束,
);

数据类型:

截屏2021-11-22 下午3.49.59.png

1
2
3
4
5
6
7
8
9
10
11
12
sql复制代码-- 创建一个product 商品表 (商品编号、商品名称、商品价格、商品库存、上架时间)
use db3;
create table product(
id int,
NAME varchar(20),
price double,
stock int,
insert_time DATE
);

-- 查看product表详细结构
desc product;

截屏2021-11-22 下午3.55.05.png

DDL 修改数据表

1
2
3
4
5
6
7
8
9
10
11
12
sql复制代码修改表名
alter table 表名 rename to 新表名;
修改表的字符集
alter table 表名 character set 字符集名称;
单独添加一列
alter table 表名 add 列名 数据类型;
修改某列的数据类型
alter table 表名 modify 列名 新数据类型;
修改列名和数据类型
alter table 表名 change 列名 新列名 新数据类型;
删除某一列
alter table 表名 drop 列名;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
sql复制代码-- 修改product表名为product2
alter table product rename to product2;
-- 查看db3 数据库中product2数据表字符集
show table status from db3 like 'product2';
-- 修改product2数据表字符集为gbk
alter table product2 character set gbk;
-- 查看db3 数据库中product2数据表字符集
show table status from db3 like 'product2';

-- 给product2表添加一列color
alter table product2 add color varchar(10);

-- 将color数据类型修改为int
alter table product2 modify color int;

desc product2;

-- 将color修改为address
alter table product2 change color address varchar(200);

-- 删除address列
alter table product2 drop address;

DDL 删除数据表

1
2
3
4
5
sql复制代码删除数据表
DROP table 表名;

删除数据表(判断,如果存在则删除)
drop table if exists 表名;
1
2
3
4
sql复制代码-- 删除product2 表
DROP table product2;
-- 删除Product2表,如果存在则删除
DROP table if exists product2;

本文转载自: 掘金

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

分布式事务(六)之可靠消息最终一致性 可靠消息最终一致性 可

发表于 2021-11-22

消息发送一致性:是指产生消息的业务动作与消息发送的一致。也就是说,如果业务操作成功,那么由这个业务操作所产生的消息一定要成功投递出去(一般是发送到kafka、rocketmq、rabbitmq等消息中间件中),否则就丢消息。

可靠消息最终一致性

发送消息不可靠性

既然提到了可靠消息的最终一致性,那么说明现有的消息发送逻辑存在不可靠性,我们用下面的几种情况来演示消息的不可靠性。

  • 先进行数据库操作,再发送消息:
1
2
3
4
java复制代码public void test1(){
//1 数据库操作
//2 发送MQ消息
}

这种情况下无法保证数据库操作与发送消息的一致性,因为可能数据库操作成功,发送消息失败

  • 先发送消息,再操作数据库:
1
2
3
4
java复制代码public void test1(){
//1 发送MQ消息
//2 数据库操作
}

这种情况下无法保证数据库操作与发送消息的一致性,因为可能发送消息成功,数据库操作失败。

  • 在数据库事务中,先发送消息,后操作数据库:
1
2
3
4
5
java复制代码@Transactional
public void test1(){
//1 发送MQ消息
//2 数据库操作
}

这里使用spring 的@Transactional注解,方法里面的操作都在一个事务中。同样无法保证一致性,因为发送消息成功了,数据库操作失败的情况下,数据库操作是回滚了,但是MQ消息没法进行回滚。

  • 在数据库事务中,先操作数据库,后发送消息:
1
2
3
4
5
java复制代码@Transactional
public void test1(){
//1 数据库操作
//2 发送MQ消息
}

这种情况下,貌似没有问题,如果发送MQ消息失败,抛出异常,事务一定会回滚(加上了@Transactional注解后,spring方法抛出异常后,会自动进行回滚)。
这只是一个假象,因为发送MQ消息可能事实上已经成功,如果是响应超时导致的异常。这个时候,数据库操作依然回滚,但是MQ消息实际上已经发送成功,导致不一致。

  • 使用JTA事务管理器:

前面通过spring的@Transactional注解加在方法上,来开启事务。其实有一个条件没有明确的说出来,就是我们配置的事务管理器是DataSourceTransactionManager。

事实上,Spring还提供了另外一个分布式事务管理器JtaTransactionManager。这个是使用XA两阶段提交来保证事务的一致性。当然前提是,你的消息中间件是实现了JMS规范中事务消息相关API(回顾前面我们介绍JTA规范时,提到DB、MQ都只是资源管理器RM,对于事务管理器来说,二者是等价的)。

因此如果你满足了2个条件:1、使用JtaTransactionManager 2、DB、MQ分别实现了JDBC、JMS规范中规定的RM应该实现的两阶段提交的API,就可以保证消息发送的一致性。

DB作为RM,一般都是支持两阶段提交的。不过,一些MQ中间件并不支持,所以你要找到支持两阶段提交的MQ中间件。另外,JtaTransactionManager只是一个代理,你需要提供一个真实的事务管理器(TM)实现。如前面提到了atomikos公司,就有这样的产品。

但是笔者依然不建议,这样做。因为XA两阶段提交性能低,我们使用消息中间件就是为了异步解耦,这种情况,虽然保证了一致性,但是响应时间却大大增加,系统可用性降低。

可靠发送消息的解决方案

有两种方法可以实现可靠消息发送:基于MQ的事务消息和本地事务表。

基于MQ的事务消息

以RocketMQ的事务消息为例,如下图所示,消息的可靠发送由发送端 Producer进行保证(消费端无需考虑),可靠发送消息的步骤如下:

  1. 发送一个事务消息,这个时候,RocketMQ将消息状态标记为Prepared,注意此时这条消息消费者是无法消费到的;
  2. 执行业务代码逻辑,可能是一个本地数据库事务操作;
  3. 确认发送消息,这个时候,RocketMQ将消息状态标记为可消费,这个时候消费者,才能真正的保证消费到这条数据。

如果确认消息发送失败了怎么办?RocketMQ会定期扫描消息集群中的事务消息,如果发现了Prepared消息,它会向消息发送端(生产者)确认。RocketMQ会根据发送端设置的策略来决定是回滚还是继续发送确认消息。这样就保证了消息发送与本地事务同时成功或同时失败。

如果消费失败怎么办?阿里提供给我们的解决方法是:人工解决。

RocketMQ

本地事务表

并不是所有的mq都支持事务消息。也就是消息一旦发送到消息队列中,消费者立马就可以消费到。此时可以使用独立消息服务、或者本地事务表。

本地事务

可以看到,其实就是将消息先发送到一个我们自己编写的一个”独立消息服务”应用中,刚开始处于prepare状态,业务逻辑处理成功后,确认发送消息,这个时候”独立消息服务”才会真正的把消息发送给消息队列。消费者消费成功后,ack时,除了对消息队列进行ack(图中没有画出),对于独立消息服务也要进行ack,”独立消息服务”一般是把这条消息删除。而定时扫描prepare状态的消息,向消息发送端(生产者)确认的工作也由独立消息服务来完成。

对于”本地事务表”,其实和”独立消息服务”的作用类似,只不过”独立消息服务”是需要独立部署的,而”本地事务表”是将”独立消息服务”的功能内嵌到应用中。

我是御狐神,欢迎大家关注我的微信公众号:wzm2zsd

qrcode_for_gh_83670e17bbd7_344-2021-09-04-10-55-16

参考文档

柔性事务:可靠消息最终一致性

本文最先发布至微信公众号,版权所有,禁止转载!

本文转载自: 掘金

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

【python】 字典 dict、defaultdict、O

发表于 2021-11-22

「这是我参与11月更文挑战的第2天,活动详情查看:2021最后一次更文挑战」

defaultdict

位于 collections 模块内。

在实例化一个 defaultdict 的时候,需要给构造方法提供一个可调用对象,这个可调用对象会在 __getitem__ 碰到找不到的键的时候被调用,让 __getitem__ 返回某种默认值。这个用来生成默认值的可调用对象存放在名为 default_factory 的实例属性里。

举个栗子

1
2
3
4
python复制代码d = collections.defaultdict(list)		# 一个空字典

d['key'] # []
d.get('key') # None

OrderedDict

位于 collections 模块内。

这个类型在添加键的时候会保持顺序,因此键的迭代次序总是一致的。

OrderedDict 的 popitem 方法默认删除并返回的是字典里的最后一个元素,但是如果像 my_odict.popitem(last=False) 这样调用它,那么它删除并返回第一个被添加进去的元素。

字典们的抽象基类

collections.abc 模块中有 Mapping 和 MutableMapping 这两个抽象基类,它们的作用是为 dict 和其他类似的类型定义形式接口。

表中斜体为抽象方法/类。

类名 方法/属性 父类
Container __contains__ -
Iterable __iter__ -
Sized __len__ -
Mapping __getitem__ , __contains__ , __eq__ , __ne__ , get , items , keys, values Container , Iterable , Sized
MutableMappint __setitem__ , __delitem__ , clear , pop , popitem , setdefault , update Mapping

dict 、defaultdict 、OrderDict 方法对比

[] 中为可选参数。

方法/对象 dict defaultdict OrderDict 说明
d.clear() 有 有 有 移除所有元素
d.__contains__(k) 有 有 有 检查 k 是否包含在 d 中
d.copy() 有 有 有 潜复制
d.__copy__() 有 用于支持 copy.copy
d.default_factory 有 在 __missing__ 函数中被调用的函数, 用以给未找到的元素设置值
d.__missing__(k) 有 当 __getitem__ 方法找不到对应键时,调用该方法
d.__delitem__(k) 有 有 有 移除键为 k 的元素
d.fromkeys(it, [initial]) 有 有 有 将迭代器 it 里的元素设置为映射里的键,如果有 initial 参数, 就把它作为这些键对应的值(默认是 None )
d.get(k, [default]) 有 有 有 返回键 k 对应的值,没有 k 时返回 default 或 None
d.__getitem__(k) 有 有 有 使字典能用 d[k] 的形式返回键 k 对应的值
d.items() 有 有 有 返回所有键值对
d.__iter__() 有 有 有 获取键的迭代器
d.keys() 有 有 有 返回所有键
d.__len__() 有 有 有 可以用 len(d) 形式得到字典键值对数量
d.move_to_end(k, [last]) 有 将键为 k 的元素移动到最考前或最靠后位置 (last 默认为 True )
d.pop(k, [default] 有 有 有 返回键 k 对应的值,并移除该键值对。没有 k 时返回 default 或 None
d.popitem() 有 有 有 (有可选参数 last ,默认为 False ,此时移除最早插入的键值对,否则移除最后插入的键值对) 随机返回一个键值对并从字典中移除
d.__reversed__() 有 返回倒序的键的迭代器
d.setdefault(k, [default]) 有 有 有 若字典里有键 k ,则把它对应的值设置为 default ,然后返回这个 值;若无,则让 d[k] = default ,然后返回 default
d.__setitem__(k, v) 有 有 有 实现 d[k] = v 操作
d.update(m, [**kargs]) 有 有 有 m 可以是映射或键值对迭代器,用来更新 d 里对应的条目
d.values() 有 有 有 返回字典里的所有值

本文转载自: 掘金

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

把Java多学一点 ------Java异步编程工具:Exe

发表于 2021-11-22

同步、异步

同步:Synchronous

异步:Asynchronous

大家可以多看几遍这两个单词,熟记于心,因为不管是阅读异步框架代码,调用异步API,或者说编写异步UI程序、异步服务器程序,或多或少都会碰到这两个单词或者变体。

接下来我们简单了解一下这两个概念:

我们把处理器所要处理的计算称之为任务。

同步任务,即以同步方式执行任务,其任务的发起与任务的执行是同一条时间线上进行的,也就是说任务的发起与任务的执行是串行的。

异步任务,即以异步方式执行任务,其任务的发起和任务的执行是在不同的时间线上执行的,也就是说任务的发起与任务的执行是并发的。

再来说一下同步、异步任务的表现:

同步任务的发起线程在其发起该任务之后必须等待该任务执行结束才能执行其他操作,这种等待往往意味着阻塞。

异步任务的发起线程在其发起该任务之后不必等待该任务结束便可以继续执行其他操作,所以异步任务可以使发起线程不必因等待其执行结束而被阻塞,异步任务往往伴随着非阻塞。

💡这里说一个问题:同步任务一定表现为阻塞?异步任务一定表现为非阻塞?

答案是不对的。阻塞、非阻塞只是任务执行方式的一种属性,与任务的执行方式没有必然的联系。

同步任务也可能是非阻塞的:Polling。轮询指的是任务的发起线程在发起任务之后并不是等待任务执行结束再去执行后续的操作,而是不断地检查其发起的任务是否执行结束,如果任务执行结束则继续执行后续的操作,如果没有执行结束,则继续检查。所以说轮询状态下,发起线程的状态仍然是Runnable,并非阻塞状态下Blocked或Waiting状态,只是此时发起线程主要做的工作是检查其发起任务是否执行结束。

异步任务也可能伴随着阻塞。如果向线程池提交一个任务之后便马上获取任务的执行结果,而此时线程池中的工作线程并没有将任务执行完成,就会导致主线程阻塞等待。

💡再说一个问题:同步与异步取决于什么?

任务是同步执行还是异步执行是取决于任务的执行方式。

如果直接调用task的run方法执行任务,则该任务肯定是同步执行。

如果创建一个专门的线程来执行该任务:new Thread(Task).start(),或者说将该任务提交给线程池执行,那么该任务是异步执行。

另外:任务是同步还是异步还取决于我们的观察角度。

📎推荐阅读:

异步编程

unix5种IO模型

Executor框架

上面介绍同步异步提到了任务是同步还是异步与任务本身无关,而是由任务的执行方式决定的。

任务本身处理逻辑由Runnable和Callable接口进行抽象,表现为具体的方法签名:Runnable.run() Callable.call()。

Executor接口则是对任务的执行方式进行了抽象,将任务的提交与任务执行细节进行解耦,可以屏蔽同步任务与异步任务执行的差异。任务的执行细节对任务的提交方来说是透明的,不管是同步执行还是异步执行,这也使得任务的提交方可以轻松更改任务的执行方式。

下面是JUC中Executor的实现类图:

Executor实现类图

可以看到,线程池ThreadPoolExecutor也是Executor的实现。

下面我们分析Executor接口是如何实现任务的执行方式与任务的处理逻辑解耦:

1
2
3
csharp复制代码public interface Executor {
   void execute(Runnable command);
}

可以看到,Executor接口很简单,内部只提供了一个execute方法。command参数代表要执行的任务,这个任务在将来某个时间会被执行,该任务可以在线程池、新线程和执行线程中执行。

Executor接口使得任务提交方只需要调用executor.execute方法便可以使得指定的任务被执行,而无需关心任务将如何运行,包括线程使用,调用机制等。

如何使用Executor的execute方法?任务的执行都有哪几种方式?

  1. Executor并没有严格规定任务的执行必须是异步的,所以可以直接在调用线程中执行任务。
1
2
3
4
5
typescript复制代码class DirectExecutor implements Executor {
 public void execute(Runnable r) {
   r.run();
}
}}
  1. 使用新线程执行任务,下面的Executor为每个任务生成一个新线程来执行任务。
1
2
3
4
5
typescript复制代码class ThreadPerTaskExecutor implements Executor {
 public void execute(Runnable r) {
   new Thread(r).start();
}
}}
  1. 许多Executor对任务的调度方式和时间加了限制,例如ThreadPoolExecutor。下面是将任务的提交序列化到另一个Executor,是一个复合Executor。
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
java复制代码 class SerialExecutor implements Executor {
  final Queue<Runnable> tasks = new ArrayDeque<>();
  final Executor executor;
  Runnable active;
 
  SerialExecutor(Executor executor) {
    this.executor = executor;
  }
 
  public synchronized void execute(Runnable r) {
    tasks.add(() -> {
      try {
        r.run();
      } finally {
        scheduleNext();
      }
    });
    if (active == null) {
      scheduleNext();
    }
  }
​
  protected synchronized void scheduleNext() {
    if ((active = tasks.poll()) != null) {
      executor.execute(active);
    }
}
}}

ExecutorService

Executor接口很简单,仅提供了execute方法供客户端调用,并且不能返回任务执行结果给客户端,其次,Executor接口实现类内部一般需要一些工作者线程来执行任务,当没有任务提交需要执行时,则需要主动关闭这些工作者线程,释放其资源。ExecutorService实现了Executor接口,主要为Executor补充了这两个功能。

ExecutorService提供了关闭的方法,关闭之后拒绝新任务提交。

1
2
3
4
5
6
7
8
9
10
csharp复制代码void shutdown();
​
List<Runnable> shutdownNow();
​
boolean isShutdown();
​
boolean isTerminated();
​
boolean awaitTermination(long timeout, TimeUnit unit)
       throws InterruptedException;

提供了两个方法来关闭Executor:

shutdown方法是有序关闭,对先前提交的任务进行执行,但是不会再接受新的任务。

💡shutdown方法不会等待先前提交的任务执行完成,不是阻塞方法,使用awaitTermination方法可以做到这一点。

shutdownNow方法会尝试停止正在执行的任务,并取消等待任务的执行,返回等待任务列表。

💡shutdownNow方法通常是通过Thread.interrupt方法来取消正在执行的任务,所以说任何不能响应interrupt方法的任务都不会被取消,同样,shutdownNow方法也不会等待正在执行的任务终止,使用awaitTermination方法可以做到这一点。

另外ExecutorService提供了awaitTermination方法,该方法是阻塞方法,阻塞等待直到所有的任务在关闭请求后执行完成,或者超时,或者当前线程执行被中断。

ExecutorService还提供了两个方法来判断状态:isShutdown方法判断Executor是否已经关闭,isTerminated方法判断shutdown之后是否所有任务都已完成。

以下示例分两个阶段关闭ExecutorService,首先调用shutdown方法拒绝传入任务,然后在必要时候调用shutdownNow取消延时任务。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
scss复制代码void shutdownAndAwaitTermination(ExecutorService pool) {
 pool.shutdown(); // Disable new tasks from being submitted
 try {
   // Wait a while for existing tasks to terminate
   if (!pool.awaitTermination(60, TimeUnit.SECONDS)) {
     pool.shutdownNow(); // Cancel currently executing tasks
     // Wait a while for tasks to respond to being cancelled
     if (!pool.awaitTermination(60, TimeUnit.SECONDS))
         System.err.println("Pool did not terminate");
  }
} catch (InterruptedException ie) {
   // (Re-)Cancel if current thread also interrupted
   pool.shutdownNow();
   // Preserve interrupt status
   Thread.currentThread().interrupt();
}
}}

ExecutorService提供了生成Future跟踪异步任务进度的方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
swift复制代码<T> Future<T> submit(Callable<T> task);
<T> Future<T> submit(Runnable task, T result);
Future<?> submit(Runnable task);
​
<T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks)
       throws InterruptedException;
<T> List<Future<T>> invokeAll(Collection<? extends Callable<T>> tasks,
                                 long timeout, TimeUnit unit)
       throws InterruptedException;
<T> T invokeAny(Collection<? extends Callable<T>> tasks)
       throws InterruptedException, ExecutionException;
<T> T invokeAny(Collection<? extends Callable<T>> tasks,
                   long timeout, TimeUnit unit)
       throws InterruptedException, ExecutionException, TimeoutException;

submit方法跟踪一个任务进度,invoke方法可以跟踪多个异步任务进度。

submit方法返回Future对象,泛型取决于提供的任务执行方法Runnable.run或者Callable.call方法的返回类型。任务完成后可以通过Future.get方法获取任务执行结果。

💡与Executor的execute方法对比,ExecutorService的submit方法最终也是通过执行execute方法来执行,但是submit可以捕获提交的任务执行过程抛出的异常,当调用Future.get获取任务执行结果时,会抛出RejectedExecutionException异常,而execute方法不能捕获异常。

ThreadPoolExecutor是ExecutorService的默认实现类。

工具类:Executors

Executors类是一个实用的工具类,为Executor、ExecutorService、ScheduledExecutorService、ThreadFactory、Callable都提供了工厂方法和一些实用方法。

下面列举看下Executors创建和返回ExecutorService实例的快捷方法:

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
java复制代码public static ExecutorService newCachedThreadPool() {
 return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                               60L, TimeUnit.SECONDS,
                               new SynchronousQueue<Runnable>());
}
public static ExecutorService newCachedThreadPool(ThreadFactory threadFactory) {
 return new ThreadPoolExecutor(0, Integer.MAX_VALUE,
                               60L, TimeUnit.SECONDS,
                               new SynchronousQueue<Runnable>(),
                               threadFactory);
}
public static ExecutorService newSingleThreadExecutor() {
 return new FinalizableDelegatedExecutorService
  (new ThreadPoolExecutor(1, 1,
                           0L, TimeUnit.MILLISECONDS,
                           new LinkedBlockingQueue<Runnable>()));
}
public static ExecutorService newSingleThreadExecutor(ThreadFactory threadFactory) {
 return new FinalizableDelegatedExecutorService
  (new ThreadPoolExecutor(1, 1,
                           0L, TimeUnit.MILLISECONDS,
                           new LinkedBlockingQueue<Runnable>(),
                           threadFactory));
}
public static ExecutorService newFixedThreadPool(int nThreads) {
 return new ThreadPoolExecutor(nThreads, nThreads,
                               0L, TimeUnit.MILLISECONDS,
                               new LinkedBlockingQueue<Runnable>());
}
public static ExecutorService newFixedThreadPool(int nThreads, ThreadFactory threadFactory) {
 return new ThreadPoolExecutor(nThreads, nThreads,
                               0L, TimeUnit.MILLISECONDS,
                               new LinkedBlockingQueue<Runnable>(),
                               threadFactory);
}

异步计算结果:Future

JUC提供了Future接口,表示异步计算的结果。提供了检查计算是否完成、等待计算完成以及检索计算结果的方法。计算结果只能在计算完成后使用get进行检索,否则阻塞,直到结果准备好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
java复制代码public interface Future<V> {
​
 // 尝试取消任务
 // 1. 任务已经完成、任务已经取消、任务由于其他原因不能被取消 都将返回失败
 // 2. 在调用cancle时,该任务尚未启动,则不运行任务
 // 3. 如果任务已经启动,则mayInterruptIfRunning参数确定是否应该中断执行该任务的线程来取消任务
 // 4. 该方法返回后,不管是否返回成功,后续调用isDone方法都返回true
 // 5. 该方法返回成功后,后续调用isCancleed方法都返回true
 boolean cancel(boolean mayInterruptIfRunning);
 
 // 判断计算是否在执行完之前被取消了
boolean isCancelled();  
 
 // 判断计算是否已经执行完成
 boolean isDone();
 
 // 阻塞检索计算结果
 V get() throws InterruptedException, ExecutionException;
 
 // 阻塞检索计算结果或者超时后返回
 V get(long timeout, TimeUnit unit)
   throws InterruptedException, ExecutionException, TimeoutException;
}

FutureTask

Runnable和Callbale都是对任务进行抽象,任务的处理逻辑分别表现为Runnable.run()和Callable.call()两个方法签名,对比这两个类分别表示任务:

Runnable来表示任务,任务既可以交给一个专门的线程执行,也可以交给一个线程池或者Executor的任何实现类来执行(Executor的execute方法参数类型为Runnable),但是不能获得任务的执行结果。

Callable来代表任务,虽然可以通过ExecutorService.submit方法获取任务的执行结果,但是Callable只能交给ExecutorService的实现类,比如线程池来执行,而无法交给一个专门的工作线程或者Executor的实现类来执行,这使得Callable表示异步任务会使任务的执行方式大大受限。

JUC提供了FutureTask组合了Runnable和Callable分别代表任务的优势。

FutureTask实现了RunnableFuture接口,而RunnableFuture接口继承了Runnable接口和Future接口:

由于继承了Runnable接口,FutureTask代表任务既可以交给专门的工作者线程执行,也可以交给Executor的其他任何实现类来执行。

由于继承了Future接口,FutureTask能够启动和取消异步任务、查看任务是否完成、检索任务结果。

💡当我们将FutureTask类型的任务作为参数传递给Executor.execute(Runnable task)方法的时候也可以获得任务的执行结果,一个工作者线程执行FutureTask的run方法,而另一个线程调用FutureTask的get方法来获取任务的执行结果。

分析ExecutorService的源代码的时候,我们可以看到submit方法参数类型既可以是Runnable也可以是Callable接口,下面我们看AbstractExecutorService.submit(Callable task)的实现:

1
2
3
4
5
6
7
8
9
scss复制代码public <T> Future<T> submit(Callable<T> task) {
 if (task == null) throw new NullPointerException();
 RunnableFuture<T> ftask = newTaskFor(task);
 execute(ftask);
 return ftask;
}
protected <T> RunnableFuture<T> newTaskFor(Callable<T> callable) {
 return new FutureTask<T>(callable);
}

该方法的返回实例便是FutureTask类型,通过FutureTask的构造方法FutureTask(Callable callable)将callable代表的任务实例转换为Runnable实例,然后提交给Executors.execute方法来执行,返回FutureTask实例,以便后面可以获取任务的执行结果。

FutureTask支持以回调的方式处理任务的执行结果,FutureTask.done方法在任务执行结束后会被调用,该方法是protected方法,所以可以在实现子类中覆盖该方法实现对任务结果的处理。

💡注意:如果在Future.done方法中的代码通过Future.get方法获取任务的处理结果,这个时候由于任务已经执行结束了,所以get方法不会阻塞,但是由于任务的结束任务的执行结束包括正常终止、异常终止、以及任务被取消而导致的终止,所以应该在调用FutureTask.get方法之前调用Future.isCanceld来判断任务是否被取消。​

完结

首先带大家回顾了同步、异步的概念,这两种编程模型的优缺点。然后深入了解了JUC中提供的两大异步编程工具:Executor和Future。这两个组件以及实现是Java异步编程或者说多线程编程的基础。

以上纯属个人阅读和分析所分享,如有不正确的地方欢迎指正。

本文转载自: 掘金

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

Docker常用命令 备忘单

发表于 2021-11-22

Docker 是一个用于开发、传送和运行应用程序的开放平台。Docker 使您能够将应用程序与基础设施分开,以便您可以快速交付软件。使用 Docker,您可以像管理应用程序一样管理基础设施。通过利用 Docker 的快速交付、测试和部署代码的方法,您可以显着减少编写代码和在生产中运行代码之间的延迟。在这篇文章中,我将提到我们需要或大多数用例的 docker 命令。

生命周期命令

创建一个容器(不启动它)

1
2
3
4
shell复制代码docker create [OPTIONS] IMAGE [COMMAND] [ARG...]

# 使用docker镜像nginx:latest创建一个容器,并将容器命名为mynginx
# docker create --name mynginx nginx:latest

创建一个新的容器并运行一个命令

1
2
3
4
shell复制代码docker run [OPTIONS] IMAGE [COMMAND] [ARG...]

# 使用docker镜像nginx:latest以后台模式启动一个容器,并将容器命名为mynginx
# docker run --name mynginx -d nginx:latest

OPTIONS说明:

  • -a stdin: 指定标准输入输出内容类型,可选 STDIN/STDOUT/STDERR 三项;
  • -d: 后台运行容器,并返回容器ID;
  • -i: 以交互模式运行容器,通常与 -t 同时使用;
  • -P: 随机端口映射,容器内部端口随机映射到主机的端口
  • -p: 指定端口映射,格式为:主机(宿主)端口:容器端口
  • -t: 为容器重新分配一个伪输入终端,通常与 -i 同时使用;
  • –name=”nginx-lb”: 为容器指定一个名称;
  • –dns 8.8.8.8: 指定容器使用的DNS服务器,默认和宿主一致;
  • –dns-search example.com: 指定容器DNS搜索域名,默认和宿主一致;
  • -h “mars”: 指定容器的hostname;
  • -e username=”ritchie”: 设置环境变量;
  • –env-file=[]: 从指定文件读入环境变量;
  • –cpuset=”0-2” or –cpuset=”0,1,2”: 绑定容器到指定CPU运行;
  • **-m :**设置容器使用内存最大值;
  • –net=”bridge”: 指定容器的网络连接类型,支持 bridge/host/none/container: 四种类型;
  • –link=[]: 添加链接到另一个容器;
  • –expose=[]: 开放一个端口或一组端口;
  • –volume , -v: 绑定一个卷

重命名现有容器

1
shell复制代码docker rename [CONTAINER_NAME] [NEW_CONTAINER_NAME]

在新容器中运行命令

1
shell复制代码docker run [IMAGE] [COMMAND]

退出后移除容器

1
shell复制代码docker run --rm [IMAGE]

启动一个容器并保持运行

1
shell复制代码docker run -td [IMAGE]

启动一个容器并在容器中创建一个交互式 bash shell

1
shell复制代码docker run -it [IMAGE]

在容器内创建、启动和运行命令,并在执行命令后移除容器。

1
shell复制代码docker run -it-rm [IMAGE]

在已经运行的容器内执行命令。

1
shell复制代码docker exec -it [container]

删除一个容器(如果它没有运行)

1
shell复制代码docker rm [CONTAINER]

更新容器的配置

1
shell复制代码docker update [CONTAINER]

启动和停止容器

启动容器

1
shell复制代码docker start [CONTAINER]

停止运行容器

1
shell复制代码docker stop [CONTAINER]

停止运行容器并重新启动它

1
shell复制代码docker restart [CONTAINER]

暂停正在运行的容器中的进程

1
shell复制代码docker pause [CONTAINER]

取消暂停正在运行的容器中的进程

1
shell复制代码docker unpause [CONTAINER]

阻塞一个容器直到其他容器停止

1
shell复制代码docker wait [CONTAINER]

通过向正在运行的容器发送 SIGKILL 来杀死容器

1
shell复制代码docker kill [CONTAINER]

将本地标准输入、输出和错误流附加到正在运行的容器

1
shell复制代码docker attach [CONTAINER]

Docker 镜像命令

从 Dockerfile 创建镜像

1
shell复制代码docker build [URL/FILE]

从带有标签的 Dockerfile 创建镜像

1
shell复制代码docker build -t <tag> [URL/FILE]

从注册表中心拉取镜像

1
shell复制代码docker pull [IMAGE]

将镜像推送到注册中心

1
shell复制代码docker push [IMAGE]

从 tarball 创建镜像

1
shell复制代码docker import [URL/FILE]

从容器创建镜像

1
shell复制代码docker commit [CONTAINER] [NEW_IMAGE_NAME]

删除镜像

1
shell复制代码docker rmi [IMAGE]

从 tar 存档或标准输入加载镜像

1
shell复制代码docker load [TAR_FILE/STDIN_FILE]

将镜像保存到 tar 存档

1
shell复制代码docker save [IMAGE] > [TAR_FILE]

Docker 容器和镜像信息

列出正在运行的容器

1
shell复制代码docker ps

列出正在运行的容器和已停止的容器

1
shell复制代码docker ps -a

列出正在运行的容器中的日志

1
shell复制代码docker logs [CONTAINER]

列出 Docker 对象的低级信息

1
shell复制代码docker inspect [OBJECT_NAME/ID]

列出来自容器的实时事件

1
shell复制代码docker events [CONTAINER]

显示容器的端口映射

1
shell复制代码docker port [CONTAINER]

显示容器中正在运行的进程

1
shell复制代码docker top [CONTAINER]

显示容器的实时资源使用统计

1
shell复制代码docker stats [CONTAINER]

显示文件系统上文件(或目录)的更改

1
shell复制代码docker diff [CONTAINER]

列出本地使用 docker 引擎存储的所有镜像

1
shell复制代码docker [image] ls

显示镜像的历史

1
shell复制代码docker history [IMAGE]

网络命令

列出网络

1
shell复制代码docker network ls

删除一个或多个网络

1
shell复制代码docker network rm [NETWORK]

显示一个或多个网络的信息

1
shell复制代码docker network inspect [NETWORK]

将容器连接到网络

1
shell复制代码docker network connect [NETWORK] [CONTAINER]

断开容器与网络的连接

1
shell复制代码docker network disconnect [NETWORK] [CONTAINER]

容器rootfs命令

从容器里面拷文件到宿主机

1
2
shell复制代码# docker cp 容器名:要拷贝的文件在容器里面的路径   要拷贝到宿主机的相应路径 
docker cp testtomcat:/usr/local/tomcat/webapps/test/js/test.js /root

从宿主机拷文件到容器里面

1
2
shell复制代码# docker cp 要拷贝的文件路径 容器名:要拷贝到容器里面对应的路径
docker cp /root/test.js testtomcat:/usr/local/tomcat/webapps/test/js

本文转载自: 掘金

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

leetcode--字符串专栏

发表于 2021-11-22

题目速览

附有leetcode的链接

344. 反转字符串

541. 反转字符串II

剑指 Offer 05.替换空格

151. 翻转字符串里的单词

剑指Offer58-II.左旋转字符串

28.实现 strStr()

459. 重复的子字符串

859. 亲密字符串

748. 最短补全词

分题讲解

344反转字符串

如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数

如果库函数仅仅是 解题过程中的一小部分,并且你已经很清楚这个库函数的内部实现原理的话,可以考虑使用库函数。

1
2
3
4
5
6
7
8
9
10
11
12
java复制代码    public void reverseString(char[] s) {
int head = 0;
int end = s.length - 1;
char tmp;
while (head < end){
tmp = s[end];
s[end] = s[head];
s[head] = tmp;
head++;
end--;
}
}

541反转字符串ii

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
java复制代码class Solution {
public String reverseStr(String s, int k) {
char[] arr = s.toCharArray();
int len = s.length();
int head = 0;
int last = 2 * k - 1;
while (last <= len - 1){
reverse(head, head + k - 1, arr);
last += 2 * k;
head += 2 * k;
}
int end = (len - 1 - head < k) ? len - 1 : head + k - 1;
reverse(head, end, arr);
return String.valueOf(arr);
}

public void reverse(int first, int end, char[] arr){
while (first < end){
char tmp = arr[first];
arr[first] = arr[end];
arr[end] = tmp;
first++;
end--;
}
}
}

谋而后定
先分块

  • 够2k
    交换函数
  • 不够2k
    小于k—交换函数
    大于k,小于2k—交换函数

剑指Offer5替换空格

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
java复制代码class Solution {
public String replaceSpace(String s) {
//用StringBuffer单线程更快
StringBuffer stb = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
char point = s.charAt(i);
if (point == ' '){
stb.append("%20");
}else {
stb.append(point);
}
}
return stb.toString();
}
}

这里提供另一种思路:
1.可以扩充原始字符串空间变成可以装下新变化的字符。
2.定位原始字符串的最后一个字符
3.定位新字符串最后一个字符
4.对比复制

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
java复制代码public String replaceSpace(String s) {
if(s == null || s.length() == 0){
return s;
}
//扩充空间,空格数量2倍
StringBuilder str = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == ' '){
str.append(" ");
}
}
//若是没有空格直接返回
if(str.length() == 0){
return s;
}
//有空格情况 定义两个指针
int left = s.length() - 1;//左指针:指向原始字符串最后一个位置
s += str.toString();
int right = s.length()-1;//右指针:指向扩展字符串的最后一个位置
char[] chars = s.toCharArray();
while(left>=0){
if(chars[left] == ' '){
chars[right--] = '0';
chars[right--] = '2';
chars[right] = '%';
}else{
chars[right] = chars[left];
}
left--;
right--;
}
return new String(chars);
}

151. 翻转字符串里的单词

法一:比较水,利用字符串中split函数,额外O(N)空间,最后串起来,要注意,去掉最后的空格,以及存在连续的分割符的时候例如两个空格,分割之后就是“”,用.equals()判断
法二:反转全部的字符,最后在反转其中的单词,这个最后的时间复杂度是O(1)。分步骤执行,最开始要除去多余的空格。反转全部字符串。反转其中的单词。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
java复制代码	//法一
public static String reverseWords(String s) {
String[] s1 = s.split(" ");
StringBuffer stb = new StringBuffer();
for (int i = s1.length - 1; i >= 0; i--){
if (!s1[i].equals("")) {
stb.append(s1[i] + " ");
}
}
//移除最后一个空格
return stb.toString().substring(0,stb.length() - 1);
}

public static void main(String[] args) {
System.out.println(reverseWords("We are happy"));//happy are We
}
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
58
59
60
61
62
63
64
65
66
67
java复制代码//法二
class Solution {
/**
* 不使用Java内置方法实现
* <p>
* 1.去除首尾以及中间多余空格
* 2.反转整个字符串
* 3.反转各个单词
*/
public String reverseWords(String s) {
// System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
// 1.去除首尾以及中间多余空格
StringBuilder sb = removeSpace(s);
// 2.反转整个字符串
reverseString(sb, 0, sb.length() - 1);
// 3.反转各个单词
reverseEachWord(sb);
return sb.toString();
}

private StringBuilder removeSpace(String s) {
// System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') start++;
while (s.charAt(end) == ' ') end--;
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
// System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
return sb;
}

/**
* 反转字符串指定区间[start, end]的字符
*/
public void reverseString(StringBuilder sb, int start, int end) {
// System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
// System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
}

private void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while (end < n && sb.charAt(end) != ' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1;
}
}
}

剑指Offer58-II.左旋转字符串

法一:比较水,就是利用substring
其实使用substr 和 反转 时间复杂度是一样的 ,都是O(n),但是使用substr申请了额外空间,所以空间复杂度是O(n),而反转方法的空间复杂度是O(1)。
法二:不使用substring可以直接利用反转来,一个比较有意思的思路就是:
在这里插入图片描述

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
java复制代码//法一:
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
sb.append(s.substring(n)+s.substring(0,n));
return sb.toString();
}
//法二:
class Solution {
public String reverseLeftWords(String s, int n) {
int len=s.length();
StringBuilder sb=new StringBuilder(s);
reverseString(sb,0,n-1);
reverseString(sb,n,len-1);
return sb.reverse().toString();
}
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
}
}

28. 实现 strStr()

暴力解法必定是不行的,这里有一个好的api,就是KMP算法,很重要,建议背住
KMP算法

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
java复制代码    public static int strStr(String haystack, String needle) {
if (needle.equals("")) return 0;//每个题目要求不一样,伺机而动
if (haystack.length() == 0 || needle.length() == 0 || haystack.length() < needle.length()) return -1;
char[] str1 = haystack.toCharArray();
char[] str2 = needle.toCharArray();
//建立next[i]数组,存储在str2第i个字符前,最长的(前缀和后缀相等)的长度。注意字符串本身不会包括在里面
int[] next = new int[str2.length];
next[0] = -1;
if (str2.length > 1){//防止str2只有一个字符
next[1] = 0;
}
int i = 2;
//初始cn记录的是next[i- 1]的值,因为这里i的初始是2,所以next[i-1] = 0,所以cn = 0;
int cn = 0;
while (i < str2.length){
if (str2[i - 1] == str2[cn]){
next[i++] = ++cn;
}else if (cn == 0){
next[i++] = 0;
}else {
cn = next[cn];
}
}
//利用next[] 数组求解字符串匹配问题
int t1 = 0; int t2 = 0;
while (t1 < str1.length && t2 < str2.length){
if (str1[t1] == str2[t2]){
t1++;
t2++;
}else if (t2 == 0){
t1++;
}else {
t2 = next[t2];
}
}
return t2 == str2.length ? t1 - t2 : -1;
}

public static void main(String[] args) {
String haystack = "abcdeabcfee";
String needle = "d";
System.out.println(strStr(haystack,needle));
}

29. 重复的子字符串

自己一上来还真的是不知道要用KMP算法,但是因为是要看是不是重复的组成字符串,那么next[]的数组绝对是有规律的。可以运行几个next[]数组看看可以得到如下的规律:
在这里插入图片描述

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
java复制代码public static boolean repeatedSubstringPattern(String s) {
if (s.length() < 2) return false;
//可以利用KMP算法,以为next[]数组中一定会有相应的规律
char[] arr = s.toCharArray();
int n = s.length();
int[] next = new int[n + 1];
next[0] = -1;
next[1] = 0;
int i = 2;
int cn = 0;
while (i <= n){
if (arr[i - 1] == arr[cn]){
next[i++] = ++cn;
}else if (cn == 0){
next[i++] = 0;
}else {
cn = next[cn];
}
}
for (int h : next){
System.out.println(h);
}
if (next[n] != 0 && n % (n - (next[n])) == 0){
return true;
}
return false;
}

public static void main(String[] args) {
String haystack = "abcabcabc";
System.out.println(repeatedSubstringPattern(haystack));
}

859. 亲密字符串

思路:
自己第一次只想到了遍历,知道这是必定错误的做法。
现在看来,可以想想,满足什么条件,就可以充分的得出结果,不需要模拟遍历
满足亲密字符串的条件:

  1. str1 和 str2的长度、词频必然相同
  2. 对于每一个i位置,只能有两个词不同 || 当没有不同词的时候,重复的词大于1

代码:

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
java复制代码    public static boolean buddyStrings(String s, String goal) {
int len1 = s.length();
int len2 = goal.length();
if (len1 != len2) return false;
int[] count1 = new int[26];
int[] count2 = new int[26];
int dif = 0;
for(int i = 0; i < len1; i++){
count1[s.charAt(i) - 'a']++;
count2[goal.charAt(i) - 'a']++;
//记录不同的次数
if (s.charAt(i) != goal.charAt(i)){
dif++;
//这里会有一个很大的漏洞,就是如果是aaabb,aaacc就会返回正确,
//判断的太早了,还需要判断词频是不是一样,就可以杜绝这个现象
// if (dif > 2) return false;
}
}
//判断词频
boolean ok = false;
for (int i = 0; i < 26; i++){
if (count1[i] != count2[i]) return false;
//判断谁都一样,保证词频相同的话
if (count1[i] > 1) ok = true;
}
return dif == 2 || (dif == 0 && ok == true);
}

748. 最短补全词

思路:
自己第一次想到了如下的步骤:

  1. lisense字频统计
  2. 遍历words中的每一个word,然后字符统计
  3. 比较(并记录最小符合条件的word长度)

但是在3中,自己为了追求空间复杂度,想着复用一个int[26],在这个基础上加加减减,但是显得代码很乱。还不如每次新建一个每次刷新,也是用的一个int[26],所以代码看的清楚也很重要

代码:
注意:
Character.isLetter(licensePlate.charAt(i)) 判断字符是不是字母
Character.toLowerCase(licensePlate.charAt(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
java复制代码class Solution {
public String shortestCompletingWord(String licensePlate, String[] words) {
int[] charNum = new int[26];
for (int i = 0; i < licensePlate.length(); i++) {
if (Character.isLetter(licensePlate.charAt(i))) {
++charNum[Character.toLowerCase(licensePlate.charAt(i)) - 'a'];
}
}
int len = Integer.MAX_VALUE;
int idx = -1;
for (int i = 0; i < words.length; i++){
int[] charNum2 = new int[26];
for (int j = 0; j < words[i].length(); j++){
++charNum2[words[i].charAt(j) - 'a'];
}

boolean ok = true;
for (int k = 0; k < 26; k++){
if (charNum[k] > charNum2[k]){
ok = false;
break;
}
}
if (ok && (idx < 0 || words[i].length() < words[idx].length())){
idx = i;
}
}
return words[idx];
}
}

总结

  1. 建议如果题目关键的部分直接用库函数就可以解决,建议不要使用库函数。如果库函数仅仅是 解题过程中的一小部分,并且你已经很清楚这个库函数的内部实现原理的话,可以考虑使用库函数。
  2. 双指针法在数组,链表和字符串中很常用。很多数组填充类的问题,都可以先预先给数组扩容带填充后的大小,然后在从后向前进行操作
  3. 当需要固定规律一段一段去处理字符串的时候,要想想在在for循环的表达式上做做文章,有一个思路:先整体反转再局部反转、先局部反转再整体反转
  4. KMP的主要思想是当出现字符串不匹配时,可以知道一部分之前已经匹配的文本内容,可以利用这些信息避免从头再去做匹配了。—-字符串中最重要的算法

本文转载自: 掘金

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

1…236237238…956

开发者博客

9558 日志
1953 标签
RSS
© 2025 开发者博客
本站总访问量次
由 Hexo 强力驱动
|
主题 — NexT.Muse v5.1.4
0%