Fighter's Blog

深度沉迷学习


  • 首页

  • 关于

  • 标签

  • 分类

  • 归档

类文件

发表于 2018-02-17 | 分类于 Java笔记

class 文件结构

  • class 文件是一组以 8 位字节为基础单位的二进制流,各个数据项目严格按照顺序紧凑的排列在 class 文件之中,中间没有添加任何分隔符,整个 class 文件中存储的内容几乎全部是程序运行的必要数据,没有空隙存在。
  • 当遇到 8 位字节以上的空间的数据项时,则会按照高位在前的方式分割成若干个 8 位字节进行存储。
  • class 文件中有两种数据类型,分别是无符号数和表(引用类型)。
  • 魔数
  • class 文件版本
  • 常量池
  • 访问标志
  • 类索引,父类索引,接口索引集合
  • 字段表集合
  • 方法表集合
  • 属性表集合

魔数

  • 版本
  • JDK 1.8=52
  • JDK 1.7=51
  • JDK 1.6=50
  • JDK 1.5=49
  • JDK 1.4=48
  • JDK 1.3=47
  • JDK 1.2=46
  • JDK 1.1=45

class 文件以 cafebabe 开头,后面跟着的是 JDK 次版本号和主版本号

常量池

  • CP_info

  • CONSTANT_Methodref_info 用于记录方法信息(包括类中定义的方法以及代码中使用到的方法)

查看 class 文件信息:javap -verbose HelloWorld.class

访问标志

类索引

字段表集合

字段表用于描述接口或者类中声明的变量

方法表集合

属性表集合

字节码指令

  • Java 虚拟机的指令由一个字节长度的,代表着某种特定操作含义的数字,称之为操作码,以及跟随其后的零至多个代表此操作所需参数的操作数而构成。
  • 操作码长度为 1 个字节,因此最大只有 256 条。
  • 基于栈的指令集架构

字节码与数据类型

  • 在虚拟机的指令集中,大多数的指令都包含了其操作所对应的数据类型信息。
  • lload fload
  • 大多数指令是包含类型信息的
  • 也有不包含类型信息的
    • goto 与类型无关
    • Arraylength 操作数组类型
  • 类型多,指令少

加载和存储指令

  • 加载和存储指令用于将数据在栈帧中的局部变量表和操作数栈之间来回传输。
  • 将局部变量表加载到操作数栈:iload lload fload dload aload
  • 将一个数值从操作数栈存储到局部变量表:istore lfda
  • 将一个常量加载到操作数栈:bipush sipush ldc ldc_w_ldc2_w aconst_null iconst_m1 iconst
  • 扩充局部变量表的访问索引的指令:wide

运算指令

  • 运算或算术指令用于对两个操作数栈上的值进行某种特定的运算,并把结果存储到操作数栈顶。
  • 加法指令:add
  • 减法指令:sub
  • 乘法指令:mul
  • 除法指令:div
  • 取余指令:rem
  • 取反指令:neg

类型转换指令

  • 类型转换指令可以将两种不同的数值类型进行相互转换,这些转换操作一般用于实现用户代码中的显示类型转换操作以及用来处理字节码指令集中数据类型相关指令无法与数据类型一一对应的问题。
  • 宽化类型处理和窄化类型处理
  • i2b i2c i2s l2i
1
2
3
4
问题:
Animal animal = getAnimal()
Object obj = animal;
User u = (User) obj;
1
2
3
4
5
6
int hour = 24;
//计算过程都按 int 计算,int 越界
long mi = hour * 60 * 60 * 1000;
long mic = hour * 60 * 60 * 1000*1000;
//最后执行一次 i2l
System.out.println(mic / mi);

对象创建与访问指令

  • 创建类实例的指令:new
  • 创建数组的指令:newarray anewarray multianewarray
  • 访问类字段:getfield putfield getstatic putstatic
  • 把数组元素加载到操作数栈的指令:baload c s i l f d a
  • 将操作数栈的值存储到数组元素:astore
  • 取数组长度的指令:arraylength
  • 检查实例类型的指令:instanceof checkcast

操作数栈管理指令

  • 操作数栈指令用于直接操作操作数栈
  • 将操作数栈的一个或两个元素出栈:pop pop2
  • 复制栈顶一个或两个数值并将复制或双份复制值重新压入栈顶:dup dup2 dup_x1 dup_x2
  • 将栈顶的两个数值替换:swap

控制转移指令

  • 控制转移指令可以让 Java 虚拟机有条件或无条件的从指定的位置指令而不是控制转移指令的下一条指令继续执行程序。可以认为控制转移指令就是在修改 pc 寄存器的值。
  • 条件分支:ifeq iflt ifle ifne ifgt ifnull ifcmple
  • 复合条件分支:tableswitch lookupswitch
  • 无条件分支:goto goto_w jsr jsr_w ret

方法调用和返回指令

方法调用

  • invokevirtual 指令用于调用对象的实例方法,根据对象的实际类型进行分派(虚方法分派),这也是 Java 语言中最常见的方法分派方式。
  • invokeinterface 指令用于调用接口方法,它会在运行时搜索一个实现了这个接口方法的对象,找出适合的方法进行调用。
  • invokespecial 指令用于调用一些需要特殊处理的实例方法,包括实例初始化方法、私有方法和父类方法。
  • invokestatic 指令用于调用类方法(static 方法)

方法的返回指令

  • 方法的调用指令与数据类型无关,而方法返回指令则是根据返回值的类型区分的,包括 ireturn(当返回值是 boolean、byte、char、short 和 int 类型时使用)、lreturn、freturn、dreturn 和 areturn,另外还有一条 return 指令供声明为 void 的方法、实例初始化方法、类和接口的类初始化方法使用。

异常处理指令

在程序中显式抛出异常的操作会由 athrow 指令实现,除了这种情况,还有别的异常会在其他 Java 虚拟机指令检测到异常状况时由虚拟机自动抛出。

新 jdk 不再使用字节码指令执行 catch 语句了,而使用 exception table 执行 catch 下语句。

Java虚拟机是如何处理异常的?
How the Java virtual machine handles exceptions

同步指令

同步指令

  • Java 虚拟机可以支持方法级的同步和方法内部一段指令序列的同步,这两种同步结构都是使用管程(monitor)来支持的。
  • 方法级的同步是隐式的,即无需通过字节码指令来控制,它实现在方法调用和返回操作中。虚拟机可以从方法常量池中的方法表结构(method info structure)中的 ACC_SYNCHRONIZED 访问标志是否被设置,如果设置了,执行线程将先持有管程,然后再执行方法,最后在方法完成(无论正常完成还是非正常完成)时释放管程。在方法执行期间,执行线程持有了管程,其他任何线程都无法再获得同一个管程。如果一个同步方法执行期间抛出了异常,并在方法内部无法处理此异常,那这个同步方法所持有的管程将在异常抛到同步方法外时自动释放。
  • 同步一段指令集序列通常是由 Java 语言中的 synchronized 块表示,Java 虚拟机的指令集中有 monitorenter 和 monitorexit 两条指令来支持 synchronized 关键字的语义,正确实现 synchronized 关键字需要编译器与 Java 虚拟机两者协作支持。

管程

  • 管程 (英语:Monitors,也称为监视器) 是一种程序结构,结构内的多个子程序(对象或模块)形成的多个工作线程互斥访问共享资源。这些共享资源一般是硬件设备或一群变量。
  • 管程实现了在一个时间点,最多只有一个线程在执行管程的某个子程序。与那些通过修改数据结构实现互斥访问的并发程序设计相比,管程实现很大程度上简化了程序设计。
  • 系统中的各种硬件资源和软件资源,均可用数据结构抽象地描述其资源特性,即用少量信息和对资源所执行的操作来表征该资源,而忽略了它们的内部结构和实现细节。
  • 利用共享数据结构抽象地表示系统中的共享资源,而把对该共享数据结构实施的操作定义为一组过程。

性能调优

发表于 2018-02-16 | 分类于 Java笔记

性能调优

  • 知识
  • 工具
  • 数据
  • 经验

虚拟机工具

发表于 2018-02-13 | 分类于 Java笔记

简介

  • jps
  • jstat
  • jinfo
  • jmap
  • jhat
  • jstack
  • jconsole

jps(java process status)

本地虚拟机唯一id:lvmid(local virtual machine id)

jps -l:查看运行的 java 进程的主类全名或 jar 包名称
jps -m:查看运行的 java 进程传入主类的参数
jps -v:查看运行的 java 进程接收的vm参数

jstat

监控——类装载,内存,垃圾收集,JIT 编译的信息

jstat -gcutil 查看垃圾收集统计信息

元空间的本质和永久代类似,都是对 JVM 规范中方法区的实现。不过元空间与永久代之间最大的区别在于:元空间并不在虚拟机中,而是使用本地内存。因此,默认情况下,元空间大小仅受本地内存限制。

jinfo

实时查看和调整虚拟机各项参数

jinfo -flag UseSerialGC 8264
jinfo -flag UseG1GC 8264

jmap

JVM Memory Map 命令用于生成 heap dump 文件,如果不使用这个命令,还可以使用 -XX:+HeapDumpOnOutOfMemoryError 参数来让虚拟机出现 OOM 的时候自动生成 dump 文件。 jmap 不仅能生成 dump 文件,还可以查询 finalize 执行队列、Java 堆和永久代的详细信息,如当前使用率、当前使用的是哪种收集器等。

jmap -dump:format=b,file=f:\a.bin 13660:生成堆快照文件
jmap -histo 13660:查看指定 java 进程的类数量和实例数量

jhat(jvm heap analysis tool)

对上述 jmap 产生的文件进行分析,但太耗 CPU 和内存,因此一般不常用。
jhat f:\a.bin
Execute Object Query Language (OQL) query
select s from java.lang.String s where s.value.length > 1000

jstack 打印线程堆栈信息

Thread.getAllStackTrace()

jconsole 内存监控

jconsole 内存监控

jconsole 线程监控

jconsole 死锁监控

点击检测死锁,会看到 等待线程数

VisualVM 与 idea 集成

安装 VisualVM 插件后,选择本地 jdk 下 bin 目录下的 jvisualvm.exe

垃圾回收与内存分配

发表于 2018-02-12 | 分类于 Java笔记

垃圾回收

概述

  • 如何判定对象为垃圾对象
    • 引用计数法
    • 可达性分析
  • 如何回收
    • 回收策略
      • 标记-清除算法
      • 复制算法
      • 标记-整理算法
      • 分代收集算法
    • 常见垃圾回收器
      • Serial
      • Parnew
      • Cms
      • G1
  • 何时回收

如何判定对象为垃圾对象

引用计数法

在对象中添加一个引用计数器,当有地方引用这个对象的时候,引用计数器的值就+1,当引用失效的时候,计数器的值就+1

打印 GC 日志 jvm 参数:-verbose:gc -XX:+PrintGCDetails

可达性分析法

  • 作为 GCRoots 的对象
    • 虚拟机栈(虚拟机栈中的局部变量表)
    • 方法区类属性所引用的对象
    • 方法区常量所引用的对象
    • 本地方法栈中所引用的对象

回收策略

标记-清除算法

  • 效率问题
    • 申请内存时找不到可用空间会再触发一次 GC
  • 空间问题
    • 回收空间不连续

复制算法

解决标记-清除算法的效率问题

回顾内存结构:
  • 堆
    • 新生代
      • Eden 伊甸园
      • Survivor 存货区
      • Tenured Gen
    • 老年代
  • 方法区
  • 栈 本地方法栈 程序计数器

标记-整理-清除算法

主要为了回收老年代

分代收集算法

针对新生代、老年代分别采用不同的垃圾回收算法,如
新生代:复制算法(回收率高)
老年代:标记-整理算法(回收率低)

常见垃圾回收器

不同垃圾回收器适用的场景和区域不同

Serial(串行)收集器

  • 最基本,发展最悠久
  • 单线程垃圾收集器
  • 主要针对新生代内存
  • 桌面应用

ParNew 收集器

  • 多线程垃圾收集器
  • 若用 CMS 收集老年代内存,则要用 Serial 或 ParNew 收集新生代内存

Parallel Scavenge 收集器

与 ParNew 收集器的异同:

  • 复制算法(同,新生代收集器)
  • 多线程收集器(同)
  • 达到可控制的吞吐量(CPU 运行用户代码的时间与 CPU 消耗总时间的比值,不同),此处 吞吐量 = (执行用户代码时间)/ (执行用户代码时间 + 垃圾回收所占时间)
  • 服务端一般更注重吞吐量,而客户端对响应时间要求更高,因此更适合交互较少的服务端

-XX:MaxGCPauseMillis 垃圾收集器停顿时间
-XX:GCTimeRatio 吞吐量大小 (0, 100)

CMS(Concurrent Mark Sweep,并发-标记-清除)收集器

用在老年代,减少延迟

  • 工作过程
    • 初始标记
    • 并发标记
    • 重新标记
    • 并发清理
  • 优点
    • 并发收集
    • 低停顿
  • 缺点
    • 占用大量 CPU 资源
    • 无法处理浮动垃圾
    • 出现 Concurrent Mode Failure(如在清除时再创建对象但申请内存失败)
    • 空闲碎片(标记-清除算法导致的)

G1 收集器

历史
优势
  • 并行与并发
  • 分代收集
  • 空间整合
  • 可预测的停顿
步骤
  • 初始标记
  • 并发标记
  • 最终标记
  • 筛选回收

RememberSet 表记录对外引用,再加上单独一块区域(region)来进行垃圾回收

与 CMS 比较

内存分配

  • 优先分配到 eden
  • 大对象直接分配到老年代
  • 长期存活的对象分配到老年代
  • 空间分配担保
  • 动态对象年龄判断

对象优先在 Eden 上分配

java -version 查看 jdk 所处运行环境为 Server VM(多核、内存 > 2G)

  • 添加虚拟机参数 -verbose:gc -XX:+PrintGCDetails 可看到默认为 Parallel 垃圾收集器,看到其新生代为 PSYoungGen
  • 添加虚拟机参数 -XX:+UseSerialGC 启用 Serial 垃圾收集器,看到其新生代为 def new generation

GC:主要回收新生代,执行很频繁,耗时短
Full GC:主要回收老年代,可以人为触发或自动触发,耗时很长

大对象直接进入老年代

大对象一般是大字符串、大数组等,Eden 区域 GC 频率很高,所以每次 GC 移动大对象很耗时,故将其直接分配在老年代,老年代回收频率低

-XX:PretenureSizeThreshold

长期存活的对象进入老年代

一般采用复制算法,当对象被移到 Survivor 区域,对象年龄+1,达到下面设定的阈值后,则将对象移动到老年代

-XX:MaxTenuringThreshold=15

空间分配担保

默认启用了空间分配担保,新生代内存不够向老年代借用内存

-XX:+HandlePromotionFailure

逃逸分析与栈上分配

方法的栈帧随方法结束而出栈被销毁,那么方法体内对象的内存就自然而然被回收,因此若对象没有逃逸,则可随方法结束而被回收。
逃逸分析:分析对象作用域。
只要对象在方法作用域内就没逃逸。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class StackAllocation {
public StackAllocation obj;
//方法返回 StackAllocation 对象,发生逃逸
public StackAllocation getInstance() {
return obj == null ? new StackAllocation() : obj;
}
//为成员属性赋值,发生逃逸
public void setObj() {
this.obj = new StackAllocation();
}
//对象作用域尽在当前方法中有效,没有发生逃逸
public void useStackAllocation() {
StackAllocation s = new StackAllocation();
}
// 引用成员变量的值,发生逃逸
public void useStackAllocation2() {
StackAllocation s = getInstance();
}
}

Java内存区域

发表于 2018-02-11 | 分类于 Java笔记

Java内存区域

内存区域简介

程序计数器

  • 程序计数器是一块较小的内存空间,它可以看作是当前线程所执行的字节码的行号指示器
  • 程序计数器处于线程独占区
  • 如果线程执行的是 Java 方法,这个计数器记录的是正在执行的虚拟机字节码指令的地址。如果正在执行的是 native 方法,这个计数器的值是 undefined
  • 此区域是唯一一个在 Java 虚拟机规范没有设定任何 OutOfMemoryError 情况的区域(因为虚拟机内部处理,开发者不用处理)

Java 虚拟机栈

  • 虚拟机栈描述的是 Java 方法执行的动态内存模型
  • 栈帧

    • 每个方法执行都会创建一个栈帧,伴随着方法从创建到执行完成。用于存储局部变量表,操作数栈,动态链接,方法出口等。
  • 局部变量表

    • 存放编译期可知的各种基本数据类型,引用类型,returnAddress 等
    • 局部变量表的内存空间在编译期完成分配,当进入一个方法时,这个方法需要在帧分配多少内存是固定的,在方法运行期间是不会改变局部变量表的大小
  • 大小
    • StackOverflowError
    • OutOfMemory

限制堆大小 jvm 参数:-XX:+HeapDumpOnOutOfMemoryError -Xmx5m -Xms5m

本地方法栈

HotSpot 虚拟机的 Java 虚拟机栈和本地方法栈实际上是在一起的,并没有分开

  • 虚拟机栈为虚拟机执行 Java 方法服务
  • 本地方法栈为虚拟机执行 native 方法服务

Java 堆

  • 存放对象实例
  • 垃圾收集器管理的主要区域
  • 新生代,老年代,Eden 空间
  • OutOfMemory 异常
  • -Xmx -Xms

方法区

  • 存储虚拟机加载的类信息,常量,静态变量,即时编译器编译后的代码等数据
    • 类的版本
    • 字段
    • 方法
    • 接口
  • 方法区和永久代
    • 两者并不等价,只是为了节省为方法区单独编写内存管理代码
  • 垃圾回收在方法区的行为
  • 异常的定义
    • OutOfMemoryError

运行时常量池

属于方法区,

1
2
3
4
5
6
7
8
public void fun(){
String s1 = "abc";//字节码常量,在常量池创建对象
String s2 = "abc";//在常量池创建对象
System.out.println(s1 == s2);//true
String s3 = new String("abc");//在堆创建对象
System.out.println(s1 == s3);//false
System.out.println(s1 == s3.intern());//true,intern() 方法产生运行时常量,将对象从堆搬到常量池
}

直接内存

对象的创建

  • 给对象分配内存
    • 指针碰撞
    • 空闲列表
  • 线程安全性问题
    • 线程同步
    • 本地线程分配缓冲 TLAB
  • 初始化对象
  • 执行构造方法

对象的结构

  • Header
    • 自身运行时数据(Mark Word,32位 / 64位)
      • 哈希值
      • GC 分代年龄
      • 线程持有的锁
      • 偏向线程ID
      • 偏向时间戳
    • 类型指针
  • InstanceData
    • 相同宽度类型数据放一起:long/double short/char
  • Padding
    • 要求对象起始地址必须是 8 的整数倍

比较著名的垃圾回收算法:

  1. 标记-清除算法
  2. 复制算法
  3. 分代收集算法

对象的访问定位

  • 使用句柄
  • 直接指针

保存两个:

  • 到对象实例数据的指针
  • 到对象类型数据的指针

(三)查找

发表于 2018-02-08 | 分类于 算法与数据结构

符号表

符号表最主要目的就是将一个键和一个值联系起来。用例能将一个键值对插入符号表并之后能从符号表的所有键值对中按键直接找到对应的值。

符号表是一种存储键值对的数据结构,支持两种操作:插入(put),即将一组新的键值对存入表中;查找(get),即根据给定的键得到对应的值。

阅读全文 »

JDK8-新特性

发表于 2018-02-08 | 分类于 Java笔记

JDK8的新特性

Java 8 使用两个概念扩展了接口的含义:默认方法和静态方法。
默认方法使得开发者可以在不破坏二进制兼容性的前提下,往现存接口中添加新的方法,即不强制那些实现了该接口的类也同时实现这个新加的方法。

接口的默认方法和静态方法

Lambda 表达式和函数式编程

Lambda 表达式可以来代替匿名内部类

Date API

重复注解

更好的类型推断

Java 8 编译器在类型判断方面有很大的提升,在很多场景下编译器可以推导出某个参数的数据类型,从而使得代码更为简洁。

Nashorn JavaScript引擎

使用 Metaspace(JEP 122)代替持久代(PermGen space)。在 JVM 参数方面,使用 -XX:MetaSpaceSize 和 -XX:MaxMetaspaceSize 代替原来的 -XX:PermSize 和 -XX:MaxPermSize。

Java 虚拟机发展

  • Sun Classic VM
    • 世界上第一款商用的 Java 虚拟机
    • 只能用纯解释器的方式来执行 Java 代码
  • Exact VM
    • Exact Memory Management 准确试内存管理(知道虚拟机某个位置数据的类型,如整数是数值还是地址,在垃圾回收时可判断堆上内存是否还被使用)
    • 编译器和解释器混合工作以及两级即时编译器
    • 只在 Solaris 平台发布
  • HotSpot VM
    • HotSpot VM 的热点代码探测能力可通过执行计数器找出最具有编译价值的代码,然后通知 JIT 编译器以方法为单位进行编译。若一个方法被频繁调用,或方法中有效循环次数很多,将会分别触发标准编译和 OSR (栈上替换) 编译动作。通过编译器和解释器恰当地协同工作,可在最优化的程序响应时间与最佳执行性能中取得平衡,而且无须等待本地代码输出才能执行程序,即时编译压力也相对减小,这样有助于引入更多代码优化技术,输出质量更高的本地代码。
  • KVM(Kilobyte)
    • Kilobyte 简单,轻量,高度可移植
    • 在手机平台运行
  • JRockit
    • BEA
    • 世界上最快的 Java 虚拟机
    • 专注服务器端应用
    • 优势
      • 垃圾收集器
      • MissionControl 服务套件
  • J9
  • Azul VM
  • Liquid VM
  • Dalvik VM
  • Microsoft VM

(三)排序

发表于 2018-01-29 | 分类于 算法与数据结构

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
28
29
30
31
public class Example{
public static void sort(Comparable a[]){}
private static boolean less(Comparable a, Comparable b){
return a.compareTo(b) < 0;
}
private static void exch(Comparable[] a, int i, int j){
Comparable t = a[i];
a[i] = a[j];
a[j] = t;
}
private static void show(Comparable[] a){
for(int i = 0; i < a.length; i++){
System.out.print(a[i] + " ");
}
System.out.println();
}
public static boolean isSort(Comparable[] a){
for(int i = 1; i < a.length; i++){
if(less(a[i], a[i - 1]))
return false;
}
return true;
}
public static void main(String[] args){
//从标准输入读入字符串,排序后输出
Integer[] a = new Integer[]{1,34,55,66,7};
sort(a);
assert isSort(a);
show(a);
}
}
  • 排序成本模型:研究排序算法时,需要计算比较和交换的次数。对于不交换元素的算法,计算访问数组的次数。
  • 额外内存使用:排序算法的额外内存开销和运行时间同等重要。排序算法可分两类:除了函数调用所需的栈和固定数目的实例变量之外无需额外内存的原地排序算法,以及需要额外内存空间来存储另一份数组副本的其它排序算法。
  • 数据类型:上述排序算法模板适用于任何实现了Comparable接口的数据类型。例如,Java中封装的Integer和Double,以及String和其他许多高级数据类型(如File和URL)都实现了Comparable接口,因此可以直接调用这些类型的数组作为参数调用我们自己实现的排序方法。

例如——用快排对N个随机的Double数据进行排序:

1
2
3
4
5
Doulbe[] a = new Double[N];
for(int i = 0; i < N; i++){
a[i] = StdRandom.uniform();
Quick.sort(a);
}
阅读全文 »

(二)基础(Fundamentals):算法分析

发表于 2017-12-30 | 分类于 算法与数据结构

观察

运行时间和输入本身相对无关,主要取决于问题规模
例:统计文件中三个数和为0的数量

1
2
3
4
5
6
7
8
9
10
11
12
13
public class ThreeSum{
public static int count(int a[]){
int N = a.length, cnt = 0;
for(int i = 0; i < N; i++){
for(int j = i + 1; j < N; j++){
for (int k = j + 1; k < N; k++){
if(a[i] + a[j] + a[k] == 0)
cnt += 1;
}
}
}
}
}

一种表示计时器的抽象数据类型:

1
2
3
4
5
6
7
8
9
10
public class StopWatch{
private final long start;
public StopWatch(){
start = System.currentTimeMillis();
}
public double elapsedTime(){
long now = System.currentTimeMillis();
return (now - start) / 1000.0;
}
}
阅读全文 »

(一)基础(Fundamentals):数据结构

发表于 2017-12-27 | 分类于 算法与数据结构

1 基础编程模型

Java 四类八种类型

  • 整型:byte, short, int, long
  • 浮点型:float, double
  • 布尔型:boolean
  • 字符型:char
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int binarySearch(int[] a, int key){
int left = 0;
int right = a.length - 1;
while(left <= right){
int mid = left + ((right - left) >>1);
if(a[mid] > key){
right = mid -1;
}
else if(a[mid] < key){
left = mid + 1;
}
else{
return mid;
}
}
return -1;
}

数组

  1. 颠倒数组中元素顺序

    1
    2
    3
    4
    5
    6
    7
    //注意 n 值、for 循环边界、以及循环体内 n - 1 - i
    int n = a.length;
    for(int i = 0; i < n/2; i++){
    int temp = a[i];
    a[i] = a[n - 1 - i];
    a[i - 1 - i] = temp;
    }
  2. 矩阵相乘

    1
    2
    3
    4
    5
    6
    7
    8
    9
    //假设a[n][n], b[n][n], c[n][n]
    int n = a.length;
    for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
    for(int k = 0; k < n; k++){
    c[i][j] += a[i][k] * b[k][j];
    }
    }
    }
阅读全文 »
123
Fighter.

Fighter.

学习 | 分享 | 交流 | 进步

26 日志
6 分类
28 标签
GitHub Weibo
© 2016 - 2018 Fighter.
   |    Hosted by GitHub Pages