Spring入门学习

Spring 学习

Spring 基础介绍

学习轻量级的控制反转(IOC),面向切面(AOP)

什么是 Spring?

  • 通过 IOC 的技术达到松耦合的目的
  • AOP 的支持,允许通过分离应用的业务逻辑与系统级服务进行内聚性的开发。系统级的服务:与具体的业务代码无关,无论什么都需要应用的服务
  • 包含并管理应用对象的配置和生命周期,这个意义上是一种容器
  • 将简单的组件组合称为复杂的应用,这个意义上是框架

Why Spring?

我们将对象的生命周期的管理交给了 Spring,所有的对象都叫做 bean,管理对象的容器叫做 bean 容器,省去了对象的创建和开销的过程。

作用

  • 容器
  • 对多种技术的支持
  • AOP:事务管理,日志等
  • 提供了众多方便的辅助类(JDBC 等)

适用范围

  • 单独使用 Bean 容器,Bean 管理
  • 使用 AOP 进行切面处理
  • 其他的,如对消息的支持

Spring 框架

框架与类库

  • 框架封装了逻辑、高内聚的,类库则是松散的工具的组合
  • 框架专注于某一领域,类库更通用

Spring IOC 容器

接口及面向接口编程

接口:声明没有实现
抽象类:与一般的一样,除了不能实例化

什么是 IOC

控制反转,控制权的转移,我们并不负责依赖对象的创建和维护,而是需要使用的时候,由外部容器负责创建和维护。

DI(依赖注入),负责对象组装功能。在 IOC 容器在运行期间,动态的将某种依赖关系注入到对象当中。

目的 :创建对象并且组装对象之间的关系。

获得依赖对象的过程被反转了。

Spring 的 Bean 配置和初始化

Spring 对于 Bean 整个的使用有两种方式:一种是通过注解,一种是基于 xml 的配置。

xml 里面 id,class(地址)

初始化过程,基础,两个包

  • BeanFactory 提供配置结构和基本功能,加载并初始化 Bean
  • ApplicationContext 保存了 Bean 对象,也就是容器。加载方式:
    加载本地文件;绝对路径
    Classpath;相对路径
    web 应用中依赖 servlet 或者 Listener

Spring 注入

容器加载 bean 的时候,完成对变量的赋值行为。

常用的两种方式:设值注入,构造注入

设值注入

也就是通过 set 的方式注入。

1
2
3
4
5
6
<bean id="injection" class="top.wuxiya.spring.Hello">
//ref指向的是id,也就是一个bean的引用,赋值给命名叫$name的变量
<property name="injectionDAO" ref="injectionDAO"></property>
</bean>

<bean id="injectionDAO" class="top.wuxiya.spring.HelloDAO"></bean>

构造注入

也就是通过 构造方法的方式注入。

注意:当通过构造注入的时候,构造器传入的变量名称必须与 name 设定的一致。

构造中,看 name。name 名称与传入的变量名匹配。

set 注入中,看类型。

一般来说最好都一样就不用区分了。

1
2
3
4
5
6
7
    <bean id="injectionService" class="top.wuxiya.spring.Hello">
//ref指向的是id,也就是一个bean的引用,赋值给命名叫$name的变量
<constructor-arg name="injectionDAO" ref="injectionDAO"></constructor-arg>
</bean>

<bean id="injectionDAO" class="top.wuxiya.spring.HelloDAO"></bean>
`

DAO——数据库
service——业务逻辑的部分

Bean 的配置

Bean 的配置项

获取 Bean 的两种方式:通过 Id 来获取,通过 Bean 的类型来获取

  • Id:唯一标识
  • Class:实例化的具体类——必须
  • Scope:作用域
  • 构造器参数
  • Properties:属性
  • 懒加载模式
  • 自动装配的模式
  • 初始化和销毁的方法

Bean 的作用域

:两种模式,singleton(默认),prototype

  • singleton:单例模式,一个 Bean 容器中只存在一个。默认
  • prototype:每次请求都创建新的实例,destroy 方式不生效
  • request:每次 http 请求创建一个实例且仅在但钱 request 内有效
  • session:同上,当前 session 中有效
  • glodbal session:单点登陆??

Bean 的生命周期

初始化两种

  • 一种为在 Bean 声明中添加 init-method=”methodName”
  • 实现 InitializingBean 接口,覆盖 afterPropertiesSet(),自动调用这个方法

销毁两种

  • 一种为在 Bean 声明中添加 destory-method=”methodName,cleanup”
  • 实现 DisposableBean 接口,覆盖 destroy(),自动调用这个方法

全局初始化和销毁方法
在 beans 中添加,default-init-method=”name”,default-destory-method=”name”

默认的方法可以不被实现,并且只要局部有一种实现就被覆盖。

局部初始化的两种方式,必须实现,其中接口的优先级大于方法的添加。

Aware 接口

  • 实现了 Aware 接口的 bean 在初始化之后,可以获取对应资源
  • 对 Spring 进行简单的扩展提供了方便的入口
  • 可以对 Spring 对应资源进行操作(慎重)

比如得到加载当前 bean 的上下文

Bean 的自动装配(Autowiring)

  • No 不做任何操作,默认
  • byname:根据属性名。设置,并且需要设置 set 方法。这个和 set 注入类似(看传入名),只不过不用再每一个 bean 里面显示声明 property。
  • byType:bean 的类型。多个类型抛异常。和 bean 的 ID 没有关系,在 set 方法(看类型)中匹配类型。
  • constructor:应用于构造器参数。在构造方法中查找构造器方法传入的类型。没有找到抛异常

Resources

针对资源文件的统一接口

Bean 的注解

Bean 管理的类注解实现

类的注解

  • @Component 是一个通用注解,可用于任何 bean
  • @Repository:用于注解 DAO 类,即持久层
  • @Service:Service 类,服务层
  • @Controller 用于 Controller 类,即控制层(MVC)

元注解:许多注解可以作为自己的代码,即“元数据注解”。可以用于领域给注解。还可以定制注解

类的自动检测及 Bean 的注册

  • 默认情况下,类被自动发现并注册 bean 的条件是:使用@Component,@Repository,@Service,@Controller 注解或者使用@Component 的自定义注解
  • 使用过滤器进行自定义扫描,修改自动发现的行文
  • 还可以禁用自动发现与注册

定义 bean

  • 可以显示指定 Bean 的 name。否则默认是类名的小写。
  • 还可以自定义命名的规则(一定要包含一个无参的构造器)。

作用域@Scope

  • @Scope(“prototype”)
    @Repository
  • 也可以自定义设置 scope

代理方式

使用 scoped-proxy 属性指定代理,有三个值可选:no,interfaces,targetClass

Bean 的(Autowiring)注解说明

@Required(不常用)

  • 是用于 bean 属性的 setter 方法
  • 表示受影响的 bean 属性必须在配置时被填充,通过在 bean 定义或通过自动装配一个明确的属性值

@Autowired

使用 1

  • 传统的 setter 方法
  • 也可以用于构造器或者成员变量
  • 我们可以注解那些众所周知的解析依赖性接口,比如:BeanFactory,MessageSource 等

注意

  • 默认情况下,如果找不到和实施的 bean 会抛出异常,所有可以用@Autowired(required=false)来避免
  • 每一个类只能有一个构造器被标注为 true
  • 如果为 true 的必要属性,那么建议用@Resource

使用 2

  • 可以通过添加注解给需要该类型实例的数组的字段和方法,以提供 ApplicationContext 中所有特定类型的 bean
    public void setFunc(Set name){
    this.name=name;
    }
    List;
    Map<String,BeanType>(String 为 bean 的 id)
  • 如果希望数组有序,可以让 bean 实现@Order 注解(Order 只针对 List 或 set)

注意
@Autowired 是由两种类型的 Bean 进行处理的,因此自定义这两种类的时候,我们需要通过

@Qualifier

可以指定特定的唯一的 bean,当子类有多个类型的时候。

我们一般用@Resource 来通过注解,这是一个与所声明类型无关的匹配过程。

  • @Auto 用于属性,构造器,多参数方法,允许在参数级别使用@Qual 缩小范围
  • @Resource 适用于成员变量、只有一个参数的 setter 方法,使用构造器,多参数用@Qual
1
2
3
@Autowired()
@Qualifier("beanImplTwo")
private BeanInterface beanInterface;

基于 Java 的容器注解

@Configuration

  • @Configuration(类注解,相当于一个配置类)
    @Bean(方法注解)
    public Myservice myService(){
    return new MyserviceImpl();
    //相当于定义了一个 id 叫做 myService 的 Bean
    }

@Bean(默认单例)

  • 自定义 Bean 的那么@Bean(name=”myName”)。默认的是方法的名称
    @Bean(init-method=””)
    @Bean(destroyMethod=””)

@ImportResource,加载资源文件

配置数据库
在 xml 中,用<context:property-placeholder location=”…./jdbc.properties”>

下面用${jdbc.url}(username,password)

仍然

@Configuration
@ImportResource(“classpath:…”)

@Value(“${jdbc.url}”)
@Value(“${jdbc.username}”)

  • 需要注意的是,username 拿到的是登录系统的用户名,因此一般来说数据库的用户名都加 jdbc

也就说与操作系统重复的都需要进行性注意

@Scope

  • @Bean
    @Scope(value=”session”,proxyMode=)

基于泛型的自动装配

@Resource

  • 注解变量或者 setter
  • @–(name=””),默认是属性名和 setter 方法得出

XML学习手册

基础语法

声明

  • version
  • encoding:默认是 UTF-8
  • 如果 encoding=”GB2312”,就可以在其中使用简体中文。还有 ISO-8858-1
  • 注释用 来包含。不能放在第一项,因为声明必须第一行,不能放在任何一个标记中

形式良好的 XML 文档

  • 对大小写敏感
  • 必须有根元素
  • 属性值必须加引号
  • 不可以加特殊字符,需要引用
  • 会保留空格

命名规则

元素

  • 字母数字和其他
  • 不能以数字或者标点开始
  • 不能以 xml(各种大小写)开始
  • 名称不能包含空格

最佳
比较短;
避免:- . :等,用下划线

属性

尽量避免使用属性,与数据有关的都用元素来描述,属性来提供与数据无关的信息。

元数据(有关数据的数据)应当存储为属性,而数据本身应当存储为元素。

xml 验证

拥有正确语法的 XML 被称为“形式良好”的 XML。

通过 DTD 验证的 XML 是“合法”的 XML。

XML DTD(Document Type Definition)

XML 使用 DTD 来描述数据

1
2
<?xml version="1.0" encoding="ISO-8859-1"?>
<!DOCTYPE note SYSTEM "Note.dtd">

XML Schema

W3C 支持一种基于 XML 的 DTD 代替者,它名为 XML Schema:

显示

我们可以采用 CSS 和 XSLT 来显示 XML,一般提倡 XSLT

1
2
<?xml version="1.0" encoding="ISO-8859-1"?>
<?xml-stylesheet type="text/xsl" href="simple.xsl"?>

命名空间

当发生冲突的时候,我们可以采用两种方式解决

使用前缀来避免命名冲突

1
2
3
4
5
6
<h:table>
<h:tr>
<h:td>Apples</h:td>
<h:td>Bananas</h:td>
</h:tr>
</h:table>

使用命名空间(Namespaces)

    xmlns:namespace-prefix="namespaceURI"

与仅仅使用前缀不同,我们为

标签添加了一个 xmlns 属性,这样就为前缀赋予了一个与某个命名空间相关联的限定名称。

1
2
3
4
5
6
<h:table xmlns:h="http://www.w3.org/TR/html4/">
<h:tr>
<h:td>Apples</h:td>
<h:td>Bananas</h:td>
</h:tr>
</h:table>

默认的命名空间

    xmlns="namespaceURI"
1
2
3
4
5
6
<table xmlns="http://www.w3.org/TR/html4/">
<tr>
<td>Apples</td>
<td>Bananas</td>
</tr>
</table>

XML CDATA 忽略解析

PCDATA 指的是被解析的字符数据(Parsed Character Data)。

XML 解析器通常会解析 XML 文档中所有的文本。

非法的 XML 字符必须被替换为实体引用(entity reference)。
术语 CDATA 指的是不应由 XML 解析器进行解析的文本数据(Unparsed Character Data)。

在 XML 元素中,”<” 和 “&” 是非法的。

“<” 会产生错误,因为解析器会把该字符解释为新元素的开始。

“&” 也会产生错误,因为解析器会把该字符解释为字符实体的开始。

某些文本,比如 JavaScript 代码,包含大量 “<” 或 “&” 字符。为了避免错误,可以将脚本代码定义为 CDATA。

CDATA 部分中的所有内容都会被解析器忽略。

CDATA 部分由 结束:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<script>
<![CDATA[
function matchwo(a,b)
{
if (a < b && a < 0) then
{
return 1;
}
else
{
return 0;
}
}
]]>
</script>

关于 CDATA 部分的注释:

  • CDATA 部分不能包含字符串 “]]>”。也不允许嵌套的 CDATA 部分。
  • 标记 CDATA 部分结尾的 “]]>” 不能包含空格或折行。

XSL(Extensible Stylesheet Language)显示 XSL

XSLT 是一种用来转换 XML 文档结构的语言,一个 XSL 文件本身就是一个 XML 文档。

XSL 包含三部分:

XSLT——转换 XML 文档
XPath——浏览定位 XML 文档
XSL-FO——格式化 XML 文档

CSS 与 XSL

CSS 很多缺点:不能重排序,不能判断哪个元素显示;不能统计计算元素中的数据

技术难题

  • 从源 XML 文档读取信息:
    XPath:定位
    XSLT:定位之后读取
  • 目标 XML 写入信息
    XSLT 元素

模板驱动模型

XSL 提供了一种归并功能。XSL 样式表包含了一个描述结果结构的模板。

XPath

1
2
3
4
5
6
7
8
9
10
11
12
13
14
<root>
<item>
<title></title>
<definition><title></title></definition>
</item>
<item>
<title></title>
<definition><title></title></definition>
</item>
<item version="9.9">
<title></title>
<definition><title></title></definition>
</item>
</root>

/root/item[position()=1](第一个 title)
/root/item/definition/title(第二个 title)
/root/item(全部 item)
./@version(选择属性节点)

XSLT

  • 有 37 个元素

  • 本身是一个 xml 文件

  • 在源 xml 文件中引用样式表

      <?xml-stylesheet type="text/xsl href="URI""?>
    

声明

从根元素开始

  • <xsl:stylesheet version=”1.0” xmlns:xsl=”URI”> 表明这是一个样式表文件,URI 提供了定义的命名空间
  • <xsl:output encoding=””>指定输出的 HTML 使用的编码
  • <xsl:template match=”/“>指明了根

Java 处理 XML

SAX,DOM 是解析器所采用的两种重要的解析 API

DOM(文档对象模型)

用于描述节点与节点之间的关系
较好的随机访问性能
平台无关
基于树的整颗对象树,建立在内存中

  • 创建 DocumentBuilderFactory,用该对象创建 DocumentBuilder。
  • 创建 DocumentBuilder。用它来解析得到 Document 对象。
  • 解析文件以创建 Document 对象。

SAX(Simple API for XML)

顺序遍历文档,然后产生所有节点事件,在内存中只保留当前处理部分。

适用

大数据量有优势
在文档中检索一个特定的值
创建文档子集,以便后继 DOM 处理

基于事件的机制

优点
与 xml 文件大小无关;不需要等到文档解析结束,就可以开始处理

缺点
不允许随机访问,比 DOM 复杂,不可能对数据进行更改,或者返回数据流之前的数据

两个可以结合使用

Make学习

Make

Make 功能简介

通过比较对应文件(目标,规则的依赖)的最后修改时间,来决定哪些文件需要更新。只更改修改的源文件。

  • 没有被编译过的源文件,进行编译并且进行链接
  • 在上次执行 make 之后修改过的 C 源代码文件,会重新编译
  • 头文件在上一次执行 make 之后被修改,那么所有包含此头文件的 C 源文件会被重新编译

Makefile 规则介绍

target :prerequisites
command

target:目标。可以是目标文件,也可以是动作的名称(比如 clean),称之为伪目标。
prerequisites:规则的依赖。就是需要的文件列表(多个)。太长用反斜杠,后面不能有空格。
command:规则的命令行。

Make 的工作方式

默认情况下执行第一个规则,第一个目标称为最终目的。当修改了任何的源文件和头文件后,执行 make 会重建终极目标。(这里 make 决定哪些需要更新,只要依赖更新,自己也要更新)
注意,.o 文件之所以更新,是因为它出现在了终极目标的依赖列表里面,如果某个规则不是终极目标所依赖的,那么它就不会被执行,除非明确指出需要执行这个规则。
处理 edit 的三种情况:

  • edit 不存在,执行规则创建 edit
  • 存在,依赖文件比他更新,根据规则重新链接生成 edit
  • 它比任何一个依赖文件都更新,那么什么也不做

从最终目的的第一个依赖文件寻找规则(main.o,kbd.o…),如果第一个依赖其他的,同样为它寻找规则。。。通常源文件和头文件已经存在,不需要重建他们的规则,所有都找到之后,从最好一个开始回退执行,最终完成 edit 的第一个依赖文件的创建和更新,然后是第二个,第三个。
整个过程 make 只是负责执行规则,对依赖关系的正确性和规则所定义的命令的正确性不做任何判断 。就是说,make 不做错误检查。
我们需要在提供给 make 程序的 Makefile 中保证其依赖关系的正确性,和执行命令的正确性。

有变量,基本的元素,规则,rules 可以有 if,else,也可以有 shell 语言。
任何文件都可以有依赖,
第一层:main;第二层:.o;第三层:.c,.h 文件。需要分开编译,效率问题。
makefile 描述编译的层次结构,可以分析修改的时间。
makefile 自动更新,自更新指令,目标 makefile(git pull),自己本身的命令出现变化。在运行 make 的时候,首先自动扫描 makefile 进行更新。直到没有 makefile 更新才停止。
make 后来加了 if,变量的东西。也有 function,还有自动匹配的功能。
ant,build(java),another neat tool,吐槽 make,解决 tab 的问题,用 xml 来描述规则,默认的是 build.xml,可以 import 一些包,可以进行扩展。
make 的问题,移植性的问题。
vc++微软的 c++和一般的不同,windows 用 vc++写的。

shell 的 build in

首先判断是否为内建,会更快。
命令行;为占位,相当于 nop。
.用来执行文件,相当于 source。bash 会新打开一个 shell,source 相当于 include。子 shell 相当于子进程,用 source 会得到子 shell 的改变。
break 和 continue。break 可以带 1、2、3 等,也就是打破几层的循环。
evol echo “$$n”,也就是替换两次。指令强大,但是不安全。
exec,执行跳转到另外一个再也不回来。
export,调整当前 shell 的环境变量,新增环境变量。变量和环境变量不同,环境变量,export 会将普通变量变为环境变量。
hash 表相对于 shell 临时。
getoptions,带:一定要读参数,否则要报错。是对命令行的一个抽象。

多线程

背景

以前一个 cpu 一个核,一个核一个线程。
单核时代的多线和单线,有一点区别。
js 只能单线程(同一个页面),代码是异步的,很容易。但是 C 里面不容易用异步。

单核时代:单线程时代异步特别复杂的问题,代码难写;写成多进程,分时。单核多线程,利用分时技术,将时间分配给不同的任务,相当于线程的切换。

多核时代:可以提高计算效率。分时系统出现了进程的概念,没有数据共享。

进程、线程竞争

又出现了多线程的问题,线程之间的关系和同步等的问题。

  • 线程调度的问题,死锁。
  • state,状态。竞争,数据竞争。

都可以归结为竞争条件,risk condition,情况与执行的先后顺序有关。解决办法,同步,一段操作原子化。由于 data conruption。

cache,两个 cpu,cache 不共享,但是内存共享。数据没有写到内存中,还在 cache 中。Java 中的关键字 GuardedBy,要求原子化和数据同步,但是很慢,将 cache 中的数据既回去。
一个 cpu,一个核 1,2 级缓存,多核 3 级缓存共享。开始是多读数据,后来用 signal。

对线程来说,堆是共享的,栈私有。statelist,只有操作,没有数据,也就没有 risk condition。
重入锁以线程为单位;pthread 是互斥锁;Java 中是重入锁。

Python学习

实用技巧

继承与多态

python 是动态类型,可以动态绑定属性;java 是静态类型

在传入类型中:如 Animal,里面有 run 方法,java 必须为 Animal 类型或者其子类,python 不要求,只要里面有 run 方法就行

类型检查

  • 字符串用:not in(‘male’,’female’)类似来判断固定的输入
  • 数据类型的检查: not isinstance(x,(int,float,str)),来固定类型
  • getImage:首先看传入的有没有 read 方法,hasattr()

面向对象

参数

  • 类属性:在函数中调用用类名+变量名
  • 实例属性:self.变量名
  • 私有属性:__name
  • 变量的域:父类加入__slots__可以规定自己的变量是什么;子类如果没有,那么不继承,子类如果设置了它,那么继承父类的它

使用netty构建websocket服务器

手段

  • ajax 轮询:异步每隔一定时间发消息问服务器有没有消息,死循环获取后端数据
  • Long pull:阻塞的模型,一直卡住,直到服务器返回 response
  • websocket:一直保持链接,持久化协议

websocket 的 api

  • let socket=new WebSocket(“ws://[ip]:[port]”)
  • 生命周期:onopen(),onmessage(),onerror(),onclose()
  • 主动方法:Socket.send(),Socket.close()

Hash表平均查找长度ASL计算

问题描述

ASL 指的是平均查找时间

关键字序列:(7、8、30、11、18、9、14)

散列函数: H(Key) = (key x 3) MOD 7

装载因子: 0.7


处理冲突: 线性探测再散列法

查找成功的 ASL 计算方法:

因为现在的数据是 7 个,填充因子是 0.7。所以数组大小=7/0.7=10,即写出来的散列表大小为 10,下标从 0~9。
第一个元素 7,带入散列函数,计算得 0。
第二个元素 8,带入散列函数,计算得 3。
第三个元素 30,带入散列函数,计算得 6。
第四个元素 11,带入散列函数,计算得 5。
第五个元素 18,带入散列函数,计算得 5;此时和 11 冲突,使用线性探测法,得 7。
第六个元素 9,带入散列函数,计算得 6;此时和 30 冲突,使用线性探测法,得 8。
第七个元素 14,带入散列函数,计算得 0;此时和 7 冲突,使用线性探测法,得 1。
所以散列表:

地址 0 1 2 3 4 5 6 7 8 9
key 7 14 8 11 30 18 9
成功 1 2 1 1 1 3 3
不成功 3 2 1 2 1 5 4

所以查找成功的计算:
如果查找 7,则需要查找 1 次。
如果查找 8,则需要查找 1 次。
如果查找 30,则需要查找 1 次。
如果查找 11,则需要查找 1 次。
如果查找 18,则需要查找 3 次:第一次查找地址 5,第二次查找地址 6,第三次查找地址 7,查找成功。
如果查找 9,则需要查找 3 次:第一次查找地址 6,第二次查找地址 7,第三次查找地址 8,查找成功。
如果查找地址 14,则需要查找 2 次:第一次查找地址 0,第二次查找地址 1,查找成功。
所以,ASL=(1+2+1+1+1+3+3)/ 7=12/ 7


查找不成功的 ASL 计算方法

1. 定义什么叫查找不成功
举个例子来说吧。在已知上面散列表的基础上,如果要查找 key 为 4 的关键字。根据散列函数可以计算 Hash(key)=Hash(4)=5。此时在地址为 5 的地方取出那个数字,发现 key=11,不等于 4。这就说明在装填的时候会发生冲突。根据冲突处理方法,会继续检测地址为 6 的值,发现 key=30,依然不等。这个时候到了地址为 6,但是依然没有找到。那么就说明根本就没有 key=4 这个关键字,说明本次查找不成功。注意:为什么到地址 6?因为散列函数中有 mod7 ,对应的地址为 0~6,即 0~6 查找失败的查找次数。
再举一个例子。查找 key 为 0的关键字,根据散列函数可以计算 Hash(key)=Hash(0)=0。此时在地址为 0 的地方取出那个数字,发现 key=7,不等于 0。这就说明在装填的时候会发生冲突。根据冲突处理方法,会继续检测地址为 1 的值,发现 key=14,依然不等。这个时候到了 地址为 2,发现为空,依然没有找到。所以停止查找,本次查找不成功。因为如果 key=0 这个关键字存在的话,依照冲突处理函数,就一定能找到它。总不能丢了吧。

2. 根据第一点定义的不成功,依次推下去:
查找地址为 0 的值所需要的次数为 3,
查找地址为 1 的值所需要的次数为 2,
查找地址为 2 的值所需要的次数为 1,
查找地址为 3 的值所需要的次数为 2,
查找地址为 4 的值所需要的次数为 1,
查找地址为 5 的值所需要的次数为 5,
查找地址为 6 的值所需要的次数为 4。 3.计算
查找不成功 ASL=(3+2+1+2+1+5+4)/ 7=18/ 7

原博客地址:https://www.cnblogs.com/qixinbo/p/7782314.html


链地址法

假设散列表的长度是 13,散列函数为 H(K) = k % 13,给定的关键字序列为{32, 14, 23, 01, 42, 20, 45, 27, 55, 24, 10, 53}。

拉链法
查找成功时的平均查找长度:

ASL = (1*6+2*4+3*1+4*1)/12 = 7/4

查找不成功时的平均查找长度:

ASL = (4+2+2+1+2+1)/13

注意:查找成功时,分母为哈希表元素个数,查找不成功时,分母为 mod 的 K 值。

Java字符串相关知识点

Java intern() 方法

首先,对于不是 new 的字符串,如果是静态字符串,那么会直接添加到常量池中,如 str3;如果带有变量,那么不会入常量池,比如 str4。

str.intern(),内容与字符串相同,但一定取自具有唯一字符串的池。也就是说,每次到常量池中找字符串,如果存在,返回引用,不存在,添加后返回引用。

1
2
3
4
5
6
7
8
String str1="a";
String str2="b";
String str3="a"+"b";
String str4=str1+str2;
String str5=new String("ab");

str5.intern()==str3==str4.intern()

LeetCode回溯法经典题目

SubSet

Given a set of distinct integers, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S =[1,2,3], a solution is:

[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}

private void backtrack(List<List<Integer>> list , List<Integer> tempList, int [] nums, int start){
list.add(new ArrayList<>(tempList));
for(int i = start; i < nums.length; i++){
tempList.add(nums[i]);
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}

SubSet-ii

Given a collection of integers that might contain duplicates, S, return all possible subsets.

Note:

Elements in a subset must be in non-descending order.
The solution set must not contain duplicate subsets.

For example,
If S =[1,2,2], a solution is:

[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, 0);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, int start){
list.add(new ArrayList<>(tempList));
for(int i = start; i < nums.length; i++){
if(i > start && nums[i] == nums[i-1]) continue; // skip duplicates
tempList.add(nums[i]);
backtrack(list, tempList, nums, i + 1);
tempList.remove(tempList.size() - 1);
}
}

Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3]have the following permutations:

[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], and[3,2,1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
// Arrays.sort(nums); // not necessary
backtrack(list, new ArrayList<>(), nums);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){
if(tempList.contains(nums[i])) continue; // element already exists, skip
tempList.add(nums[i]);
backtrack(list, tempList, nums);
tempList.remove(tempList.size() - 1);
}
}
}

Permutations-ii

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example,
[1,1,2]have the following unique permutations:

[1,1,2],[1,2,1], and[2,1,1].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> list = new ArrayList<>();
Arrays.sort(nums);
backtrack(list, new ArrayList<>(), nums, new boolean[nums.length]);
return list;
}

private void backtrack(List<List<Integer>> list, List<Integer> tempList, int [] nums, boolean [] used){
if(tempList.size() == nums.length){
list.add(new ArrayList<>(tempList));
} else{
for(int i = 0; i < nums.length; i++){
if(used[i] || i > 0 && nums[i] == nums[i-1] && !used[i - 1]) continue;
//!used[i - 1]保证了i-1和i这个字母在同一层遍历中,used[i - 1]=true表明当前i是下一层
used[i] = true;
tempList.add(nums[i]);
backtrack(list, tempList, nums, used);
used[i] = false;
tempList.remove(tempList.size() - 1);
}
}
}

对于排列的问题,我们每次都要遍历整个 num,如果他有重复的字母,正因为需要遍历所有的 num,因此我们需要记录每一个字母的状态,保证在一个 epoch 里面,这一个和上一个字母一样的情况下,我们只使用一次当前的字母。

而其他的情况,不规定每一次要用所有的字母,从们按照顺序执行,已经在顺序中去除了重新遍历可能会得到之前用过的字母的情况,因此只需要 skip 掉重复的字母即可。

树的遍历

path-sum-li

Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.

For example:
Given the below binary tree andsum = 22,

1
2
3
4
5
6
7
      5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1

return

1
2
3
4
[
[5,4,11,2],
[5,8,4,5]
]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;
public class Solution {
ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
public ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int sum) {
if(root==null) return result;

dfs(root,sum,new ArrayList<>());
return result;
}
public void dfs(TreeNode node,int target,ArrayList<Integer> list){
if(node==null) return;
list.add(node.val);
if(node.left==null&&node.right==null&&target==node.val){
result.add(new ArrayList<>(list));
list.remove(list.size()-1);//注意此时必须进行回溯,因为left和right共同指向了list,当左节点符合时,有可能右节点也符合,因此必须撤销这一点
return;
}
dfs(node.left,target-node.val,list);
dfs(node.right,target-node.val,list);
list.remove(list.size()-1);//同理,这里回溯是因为node的父节点的左右节点指向了同一个list,我们必须保证右节点,即node的兄弟的list不跟在node节点之后。
}
}

对于树的回溯与遍历,从根节点到叶子节点,我们必须注意 path 中,在最后的叶子节点,对于新加入的点的回溯,因为 left 和 right 共同指向了 list,当左节点符合时,有可能右节点也符合,因此必须撤销这一点。

binary-tree-maximum-path-sum

任意 node 到任意 node

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

1
2
3
  1
/ \
2 3

Return 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
int max=0;
public int maxPathSum(TreeNode root) {
if(root==null) return 0;
//当只有一个节点的时候,直接返回root的值
if(root.left==null&&root.right==null) return root.val;

max=Integer.MIN_VALUE;
getMax(root);
return max;
}
public int getMax(TreeNode node){
if(node==null) return 0;
int left=Math.max(0,getMax(node.left));
int right=Math.max(0,getMax(node.right));
max=Math.max(max,node.val+left+right);
//返回当前节点下的最大路径,用于给上一层的left或者right
//临时变量通过return传递,最大值通过全局max变量保存
return Math.max(left,right)+node.val;
}
}

Linux系统管理

介绍

清理,编译,测试,运行,打包,集成测试,验证,部署整个周期

目录结构

  • groupId:(公司反写网址.项目名)【主项目的标识,实际的项目】
  • artiFactId:(项目名-模块名)【maven 的项目和我们的实际的项目不一样,maven 是模块化的,一个实际的项目被划分为多个模块。一个模块的标识】
  • version:【当前版本号,一般三个数字组成。第一个 0 表示大版本号,第二个 0 表示分支版本号,第三个 0 表示小版本号】
    snapshot 快照
    alpha 内部测试
    beta 公测
    Release 稳定
    GA 正式发布
  • packaging:【maven 项目的打包方式,默认是 jar,还可以其他的 war,zip,pom 等等】

maven 常用的构建命令

mvn -v
mvn compile:编译
mvn test:测试
mvn package:打包

mvn clean :删除 target
mvn install:安装 jar 包到本地仓库,一般是将自己 compile 的 jar 包加入到本地仓库中,也就是如果一个项目用到另一个项目中的文件,我们可以这样使用

自动创建目录骨架

mvn archetype:generate -DgroupId=top.wuxiya.maven04 -DartifactId=maven04-demo -Dversion=1.0.0SNAPSHOT -Dpackage=top.wuxiya.maven04-demo

坐标和仓库

坐标是地址,用于找到对应的 jar 包,也就是 dependence

包括:groupId,artiFactId,version

仓库:本地和远程

maven 声明周期

每个证明周期是相互独立的,每个周期的内部有一定的依赖和顺序,运行之后的命令,自动执行之前的依赖

clean 清理项目 分为三个阶段:

pre-clean 执行清理前的工作
clean 清理上一次构建生成的所有文件
post-clean 执行清理后的文件

default 构建项目

compile test package install

site 生成项目站点,根据 pom

pre-site 之前的工作
site 生成项目的站点文档
post-site 生成之后的工作
site-deploy 发布生成的站点到服务器上

对于 maven 而言,所有的命令都是调用插件来使用的

pom.xml 常用元素介绍

  • :根元素,包含了一些约束信息

  • :指定了 pom 的版本,固定的 4.0.0

  • 坐标信息:

  • 项目坐标信息:

  • :项目的描述名,一般在产生项目文档的时候使用

  • :项目的地址

  • :项目的描述

  • :开发人员的列表

  • :开源框架的许可证信息

  • :组织信息

  • :依赖列表 >
    依赖包的坐标信息:

    :依赖的范围,如 test,表示只在测试的范围有用;:true/false,用来设置依赖是否可选,默认是 false;
    :排除依赖传递列表 > :A->B->C,那么 C 对于 A 来说就是传递依赖

  • :依赖的管理 > > (并不会运行,而是用于子模块的继承)

  • > 插件信息 > > 坐标信息

  • :用于在子模块中对于父模块的继承

  • :用于聚合多个 maven 项目,如果我们有很多个 maven 模块,那么可以一次性编译,而不是一个一个编译

依赖的范围

重点来看 >
如果要使用某一个框架,需要将框架加入到 classPath 中,这样就可以使用该框架。

maven 中有三种 classpath,分别是 编译,测试,运行
junit 只存在于 test 的范围。

由此可见范围是用于管理依赖包的使用范围。

  • compile:默认,三种都有效
  • provided:测试和编译,如发布的时候容器里面已经有 API 了
  • runtime:测试和运行,JDBC 的应用
  • test:junit 的应用
  • system:
  • import:只在 management 中使用

依赖的传递

A->B->C

如果 A 引入 B 的 jar 包,那么会默认导入 C 包,这个时候如果不需要 C 包,我们在 > B 中,加入:排除依赖传递列表 > :C 的坐标

依赖冲突

如果 A 依赖了同一个构件的不同版本,那么会产生冲突

  • 短路优先:优先解析路径段的版本
    A->B->C->X(jar)
    A->D->X(jar)
    那么优先解析短的路径
  • 路径相同,优先解析先声明的版本

聚合和继承

聚合

对于不同的 maven 项目,我们需要相互调用的时候必须一个一个 install 到本地的仓库中才可以调用。

我们可以将不同的 maven 项目聚合一次性运行。

新建一个 maven 项目,packaging 用 pom,用:用于聚合多个 maven 项目,如果我们有很多个 maven 模块,那么可以一次性编译,而不是一个一个编译。

继承
新建一个 maven 项目,packaging 用 pom,删除 main 和 test,依赖放在 manegement 中。

在子项目中,中引入父亲

Docker学习

docker 的技术实现

命名空间,控制组(CGgroups),联合文件系统(union file system)

  • CGgroups:资源的隔离,和资源的分配

docker 组成

镜像 image,容器 container,网络 network,数据卷 volume

优势:利用 AUFS 对镜像进行增量更新,方便共用镜像;写时复制更快

image

只读的文件包,包含了虚拟环境运行的最原始文件系统的内容

数据卷

为保证数据的独立性,可以基于 docker 的 unionfs,建立独立的目录持久存放数据,或者在文件中共享;通过这几种方式实现持久化,或者数据共享,我们称之为数据卷

container

启动与 PID 为 1 的进程共生命;写时复制的机制,启动时,利用 unionfs 将镜像以只读的方式挂载到沙盒文件中。

network

容器网络模型核心组成:沙盒(Sandbox),网络(Network),端点(Endpoint)

有五种驱动,其中两种常用 Bridge Driver,Overlay Driver

Bridge,是默认网络驱动可以通过软硬件来实现网桥;Overlay 通过 Docker 集群模块来搭建,可以跨物理主机的虚拟网络。

docker 指令

启动 docker:sudo systemctl start docker
开机自启动:sudo systemctl enable docker
docker info

镜像

拉取镜像:docker pull (默认为 latest 版本)
docker images
docker search name:version
docker rmi name:version

容器

创建:docker create –name name:version
运行: docker start name
二合一: docker run -d –name name:version(合并指令,run 为前台,-d 转为后台运行)
docker rm (docker 记得随用随删)
docker ps
docker ps -a
查看容器具体信息:docker inspect
进入容器启动 bash:docker exec -it bash
nginx -s top/quit(进入后停止)
exit(进入后退出)

容器网络

(network 暴露接口)(https://blog.csdn.net/Michaelwubo/article/details/82493006)

–expose(暴露容器 port),EXPOSE 与-P(dockersfile 中使用),-p(指定宿主机的 port 与容器 port 的映射)
创建新的虚拟子网:docker network create -d (-d 可以指定新的网络驱动,默认是 bridge)
docker network ls/rm /..
docker run -d –name –link –network –expose –expose name:version
docker -d –name -p port:port -p port:port name:version

管理存储数据

数据有三种挂载方式:Bind Mount,Volume,Tmpfs Mount

  • Bind Mount:指定宿主系统文件目录,以及容器内部的路径
  • Volume:指定容器内部的路径,
  • Tmpfs Mount:系统内存中的一部分早容器的文件系统中,并不是持久的,其中的内容会随着容器的停止而消失

Bind Mount

必须使用绝对路径不能相对路径,默认是 RW,如果只读,加:ro

docker run -d –name -v :(:ro) name:version(或者是–volume )

使用的场景:

  • 当我们需要从宿主系统共享配置的时候
  • 把代码挂载进入容器,每次对代码的修改都可以直接在容器外部进行

Tmpfs Mount 临时文件

docker run -d –name –tmpfs name:version

Volume 使用数据卷

无需知道数据存储在了宿主的哪里,一般默认在 docker 的资源区域(/var/lib/docker)

docker run -d –name -v (:) name:version

共用数据卷

我们用-v 来挂载的时候,如果数据卷不存在,那么会创建,否则直接引用

-v html:…
-v html:…
直接创建数据卷:docker volume create
docker volume ls
docker volume rm
删除容器的时候,加 -v 删除关联的数据卷: docker volume rm -v
删除没有容器引用的数据卷,用 prune:docker volume prune

数据卷容器

数据卷容器不需要运行,用一个系统的镜像就可以

是容器间的文件系统的桥梁,可以像引用 network 一样引用,用–volumes-from 就可以

docker create –name -v (name:) ubuntu
docker run -d –name –volumes-from name:version

迁移和备份数据卷

对于临时容器,我们在 run 的时候加入 –rm,让容器在停止的时候自动删除

docker run –rm –volumes-from appdata -v /backup:/backup ubuntu tar cvf /backup/backup.tar /webapp/storage
docker run –rm –volumes-from appdata -v /backup:/backup ubuntu tar xvf /backup/backup.tar -C /webapp/storage –strip

保存和共享数据

1、容器–>提交新的镜像:docker commit -m “desc” name:version
2、导出镜像,可批量:docker save > .tar
docker save -o ./.tar
3、恢复镜像,可批量:docker load < .tar
docker load -i ./.tar
合并 1 和 2:docker export -o ./
docker import ./ (注意 load 不可以指定名称,import 可以指定名称)

DockerFile

变量

  • 使用变量:用 来传参,在构建的时候传入指令
    传入:docker build –build-arg arg=value
    只影响构建过程
  • 环境变量:用来指定
    可以影响基于此镜像创建的容器,因此可以在运行容器的时候,加入<-e/–env arg=value>来覆盖环境变量,如之前的 mysql

ARG 和 ENV 在使用的时候,采用$arg 来占位,如出现冲突,ENV 的一直都会覆盖 ARG

合并命令

由于镜像是由多个镜像叠加而得,它是由 dockerfile 中的每条指令生成的,因此适度的合并 RUN 到一条指令中,会减少镜像层的数量,较少反复创建容器的次数,提高了镜像构建的速度。

建议将不容易变化的搭建过程放到前面,充分利用构建缓存提高镜像构建的速度。

合并指令的时候,将易变的和不易变的拆分,放到不同的指令里。

Docker Compose 管理容器

Dockerfile 是将容器内部运行环境的搭建固化下来,那么 Docker Compose 是将多个容器运行的方式和配置固化下来。

使用步骤:

1、编写容器所需要的 Dockerfile
2、编写配置容器的 docker-compose.yml
3、使用 docker-compose 命令启动

启动:docker-compose -f ./name.yml -p pj-name up -d
(-f 指令 yml,否则是当前目录下的 yml;-p 指定项目名字;-d 在后台)
删除:docker-compose down