根搜索算法
❶ 搜索算法的运算原理
搜索算法实际上是根据初始条件和扩展规则构造一棵“解答树”并寻找符合目标状态的节点的过程。所有的搜索算法从最终的算法实现上来看，都可以划分成两个部分——控制结构（扩展节点的方式）和产生系统（扩展节点），而所有的算法优化和改进主要都是通过修改其控制结构来完成的。其实，在这样的思考过程中，我们已经不知不觉地将一个具体的问题抽象成了一个图论的模型——树，即搜索算法的使用第一步在于搜索树的建立。
由图一可以知道，这样形成的一棵树叫搜索树。初始状态对应着根结点，目标状态对应着目标结点。排在前的结点叫父结点，其后的结点叫子结点，同一层中的结点是兄弟结点，由父结点产生子结点叫扩展。完成搜索的过程就是找到一条从根结点到目标结点的路径，找出一个最优的解。这种搜索算法的实现类似于图或树的遍历，通常可以有两种不同的实现方法，即深度优先搜索（DFS——Depth First search）和广度优先搜索（BFS——Breadth First Search）。
❷ java垃圾回收：GC在什么时候对什么做了什么
GC在什么时候对什么做了什么？
要回答这个问题，先了解下GC的发展史、jvm运行时数据区的划分、jvm内存分配策略、jvm垃圾收集算法等知识。
先说下jvm运行时数据的划分，粗暴的分可以分为堆区(Heap)和栈区(Stack)，但jvm的分法实际上比这复杂得多，大概分为下面几块：
1、程序计数器(Program Conuter Register)
程序计数器是一块较小的内存空间，它是当前线程执行字节码的行号指示器，字节码解释工作器就是通过改变这个计数器的值来选取下一条需要执行的指令。它是线程私有的内存，也是唯一一个没有OOM异常的区域。
2、Java虚拟机栈区(Java Virtual Machine Stacks)
也就是通常所说的栈区，它描述的是Java方法执行的内存模型，每个方法被执行的时候都创建一个栈帧(Stack Frame)，用于存储局部变量表、操作数栈、动态链接、方法出口等。每个方法被调用到完成，相当于一个栈帧在虚拟机栈中从入栈到出栈的过程。此区域也是线程私有的内存，可能抛出两种异常：如果线程请求的栈深度大于虚拟机允许的深度将抛出StackOverflowError；如果虚拟机栈可以动态的扩展，扩展到无法动态的申请到足够的内存时会抛出OOM异常。
3、本地方法栈(Native Method Stacks)
本地方法栈与虚拟机栈发挥的作用非常相似，区别就是虚拟机栈为虚拟机执行Java方法，本地方法栈则是为虚拟机使用到的Native方法服务。
4、堆区(Heap)
所有对象实例和数组都在堆区上分配，堆区是GC主要管理的区域。堆区还可以细分为新生代、老年代，新生代还分为一个Eden区和两个Survivor区。此块内存为所有线程共享区域，当堆中没有足够内存完成实例分配时会抛出OOM异常。
5、方法区(Method Area)
方法区也是所有线程共享区，用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译后的代码等数据。GC在这个区域很少出现，这个区域内存回收的目标主要是对常量池的回收和类型的卸载，回收的内存比较少，所以也有称这个区域为永久代(Permanent Generation)的。当方法区无法满足内存分配时抛出OOM异常。
6、运行时常量池(Runtime Constant Pool)
运行时常量池是方法区的一部分，用于存放编译期生成的各种字面量和符号引用。
垃圾收集(Garbage Collection)并不是Java独有的，最早是出现在Lisp语言中，它做的事就是自动管理内存，也就是下面三个问题：
1、什么时候回收
2、哪些内存需要回收
3、如何回收
1、什么时候回收？
上面说到GC经常发生的区域是堆区，堆区还可以细分为新生代、老年代，新生代还分为一个Eden区和两个Survivor区。
1.1 对象优先在Eden中分配，当Eden中没有足够空间时，虚拟机将发生一次Minor GC，因为Java大多数对象都是朝生夕灭，所以Minor GC非常频繁，而且速度也很快；
1.2 Full GC，发生在老年代的GC，当老年代没有足够的空间时即发生Full GC，发生Full GC一般都会有一次Minor GC。大对象直接进入老年代，如很长的字符串数组，虚拟机提供一个-XX:PretenureSizeThreadhold参数，令大于这个参数值的对象直接在老年代中分配，避免在Eden区和两个Survivor区发生大量的内存拷贝；
1.3 发生Minor GC时，虚拟机会检测之前每次晋升到老年代的平均大小是否大于老年代的剩余空间大小，如果大于，则进行一次Full GC，如果小于，则查看HandlePromotionFailure设置是否允许担保失败，如果允许，那只会进行一次Minor GC，如果不允许，则改为进行一次Full GC。
2、哪些内存需要回收
jvm对不可用的对象进行回收，哪些对象是可用的，哪些是不可用的？Java并不是采用引用计数算法来判定对象是否可用，而是采用根搜索算法(GC Root Tracing)，当一个对象到GC Roots没有任何引用相连接，用图论的来说就是从GC Roots到这个对象不可达，则证明此对象是不可用的，说明此对象可以被GC。对于这些不可达对象，也不是一下子就被GC，而是至少要经历两次标记过程：如果对象在进行根搜索算法后发现没有与GC Roots相连接的引用链，那它将会第一次标记并且进行一次筛选，筛选条件是此对象有没有必要执行finalize()方法，当对象没有覆盖finalize()方法或者finalize()方法已经被虚拟机调用执行过一次，这两种情况都被视为没有必要执行finalize()方法，对于没有必要执行finalize()方法的将会被GC，对于有必要有必要执行的，对象在finalize()方法中可能会自救，也就是重新与引用链上的任何一个对象建立关联即可。
3、如何回收
选择不同的垃圾收集器，所使用的收集算法也不同。
在新生代中，每次垃圾收集都发现有大批对象死去，只有少量存活，则使用复制算法，新生代内存被分为一个较大的Eden区和两个较小的Survivor区，每次只使用Eden区和一个Survivor区，当回收时将Eden区和Survivor还存活着的对象一次性的拷贝到另一个Survivor区上，最后清理掉Eden区和刚才使用过的Survivor区，Eden和Survivor的默认比例是8：1，可以使用-XX:SurvivorRatio来设置该比例。
而老年代中对象存活率高，没有额外的空间对它进行分配担保，必须使用“标记-清理”或“标记-整理”算法。
❸ bfs算法是什么
广度优先搜索算法（英语：Breadth-First Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。
简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。
作法
BFS是一种暴力搜索算法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能地址，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。
从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。
一般的实现里，其邻居节点尚未被检验过的节点会被放置在一个被称为open的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为closed的容器中。
(3)根搜索算法扩展阅读：
广度优先搜索算法的应用
广度优先搜索算法能用来解决图论中的许多问题，例如：
1、查找图中所有连接组件（ConnectedComponent）。一个连接组件是图中的最大相连子图。
2、查找连接组件中的所有节点。
3、查找非加权图中任两点的最短路径。
4、测试一图是否为二分图。
5、（Reverse）Cuthill–McKee算法
❹ 基本算法——深度优先搜索（DFS）和广度优先搜索（BFS）
深度优先搜索和广度优先搜索，都是图形搜索算法，它两相似，又却不同，在应用上也被用到不同的地方。这里拿一起讨论，方便比较。
一、深度优先搜索
深度优先搜索属于图算法的一种，是一个针对图和树的遍历算法，英文缩写为DFS即Depth First Search。深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的相应拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如最大路径问题等等。一般用堆数据结构来辅助实现DFS算法。其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。
基本步奏
（1）对于下面的树而言，DFS方法首先从根节点1开始，其搜索节点顺序是1,2,3,4,5,6,7,8（假定左分枝和右分枝中优先选择左分枝）。
（2）从stack中访问栈顶的点；
（3）找出与此点邻接的且尚未遍历的点，进行标记，然后放入stack中，依次进行；
（4）如果此点没有尚未遍历的邻接点，则将此点从stack中弹出，再按照（3）依次进行；
（5）直到遍历完整个树，stack里的元素都将弹出，最后栈为空，DFS遍历完成。
二、广度优先搜索
广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现BFS算法。
基本步奏
（1）给出一连通图，如图，初始化全是白色（未访问）；
（2）搜索起点V1（灰色）；
（3）已搜索V1（黑色），即将搜索V2，V3，V4（标灰）；
（4）对V2，V3，V4重复以上操作；
（5）直到终点V7被染灰，终止；
（6）最短路径为V1，V4，V7.
❺ JVM G1参数
采用根搜索算法，通过一系列名为”GC Roots”的对象作为起始点，从这些节点开始向下搜索，搜索所走过的路径称为引用链(Reference Chain)，当一个对象到GC Roots没有任何引用链相连时，则证明此对象是不可用的。
1. 栈中引⽤的对象
2. 静态变量、常量引⽤的对象
3. 本地⽅法栈native⽅法引⽤的对象
1.标记-复制
2.标记-清理
3.标记-整理
G1采取了不同的策略来解决并行、串行和CMS收集器的碎片、暂停时间不可控制等问题
G1会优先回收垃圾对象特别多的分区，这样可以花费较少的时间来回收这些分区的垃圾
在年轻代回收期间，G1 GC 会调整其年轻代空间（eden 和存活空间大小）以满足目标。
在混合回收期间，G1 GC 会根据混合垃圾回收的目标次数调整所回收的年老代区域数量，并调整堆的每个区域中存活对象的百分比，以及总体可接受的堆废物百分比。
G1算法将堆划分为若干个区域（Region）, 每个region可以是edon， survior， old区域，每个region大小相同为1M， 2M， 4M 2的幂次方大小，整个堆中默认有2048个region，每个Region默认按照512Kb划分成多个Card。
如果一个对象占用的空间大于一个region尺寸的一半，就会专门放入到humongous区域。G1划分了一个Humongous区，它用来专门存放巨型对象。如果一个H区装不下一个巨型对象，那么G1会寻找连续的H分区来存储。为了能找到连续的H区，有时候不得不启动Full GC。这种情况可以调整整个堆的大小，或者调整G1HeapRegionSize大小。
Remembered Set ，对应于一个region，采用point-in策略，记录该region中某card被其它region 的引用情况。RSet其实是一个Hash Table，Key是别的Region的起始地址，Value是一个集合，里面的元素是Card Table的Index。 进行垃圾回收时，如果Region1有根对象A引用了Region2的对象B，显然对象B是活的，如果没有Rset，就需要扫描整个Region1或者其它Region，才能确定对象B是活跃的，有了Rset可以避免对整个堆进行扫描。
cms中年老代也有rset，采用point-out策略，记录年老代中引用年轻代的对象，这样在ygc时就不用扫描整个年老代，只扫描年老代的rset。
G1MaxNewSizePercent 新生代最大值，默认值60%
G1MaxPauseTime 设置G1收集过程目标时间，默认值200ms
G1ReservePercent 预留百分之多少内存，防止晋升失败的情况，默认值是10
-XX:=45 – 整个堆栈使用达到百分之多少的时候，启动GC周期. 基于整个堆，不仅仅是其中的某个代的占用情况，G1根据这个值来判断是否要触发GC周期, 0表示一直都在GC，默认值是45（即45%满了，或者说占用了)，启动mix gc
MaxRAMPercentage、InitialRAMPercentage、MinRAMPercentage 应用于docker容器中，根据docker容器内存大小指定堆的初始，最大，最小比例
ParallelRefProcEnabled 默认为false，并行的处理Reference对象，如WeakReference，除非在GC log里出现Reference处理时间较长的日志，否则效果不会很明显
显式的使用-Xmn设置年轻代的大小，会干预G1的默认行为。
G1就不会再考虑设定的暂停时间目标，所以本质上说，设定了年轻代大小就相当于禁用了目标暂停时间。
G1就无法根据需要增大或者缩小年轻代的小心。既然大小固定了，就无法在大小上做任何改变了。
为了避免堆内存被耗尽，虚拟机会触发一个混合的垃圾收集器，即mixed gc
除了回收整个young region，还会回收一部分的old region
主要分为以下几个步骤：
1. initial mark: 初始标记过程，整个过程STW，标记了从GC Root可达的对象
2. concurrent marking: 并发标记过程，整个过程gc collector线程与应用线程可以并行执行，标记出GC Root可达对象衍生出去的存活对象，并收集各个Region的存活对象信息
3. remark: 最终标记过程，整个过程STW，标记出那些在并发标记过程中遗漏的，或者内部引用发生变化的对象
4. clean up: 垃圾清除过程，如果发现一个Region中没有存活对象，则把该Region加入到空闲列表中
使用范围不一样
CMS收集器是老年代的收集器，可以配合新生代的Serial和ParNew收集器一起使用
G1收集器收集范围是老年代和新生代
STW的时间
CMS收集器以最小的停顿时间为目标的收集器。
G1收集器可预测垃圾回收的停顿时间（建立可预测的停顿时间模型）
垃圾碎片
CMS收集器是使用“标记-清除”算法进行的垃圾回收，容易产生内存碎片
G1收集器使用的是“标记-整理”算法，进行了空间整合，降低了内存空间碎片
参考： https://www.jianshu.com/p/a3e6a9de7a5d
https://blog.csdn.net/u013380694/article/details/83341913
https://www.jianshu.com/p/ab54489f5d71?u_atoken=ca2d26ce-15a4-462b-9ee2-1d3dfca2d647&u_asession=-kRD0-eOdne8XcfWhUbbJUSLGdkUER_tKV6ZX0KNBwm7Lovlpxjd_P_q4JsKWYrT3W_NKPr8w6oU7K9iRp8G_&u_asig=_7vZwmCUEmowKET9soS-B3_YnquxJK1II_ufphdjR9EF5W4qBzbaQxa_DPpZ9KH_-QE6N5IgXkZa79JS7q8ZD7Xtz2Ly--WWPRPQyB_SKrj-61LB_f61u3h9VXwMyh6PgyDIVSG1W__la6lRJ-&u_aref=npKvxxWi1kDXXuw5mG2TYBN3CXA%3D
❻ 图遍历算法之DFS/BFS
在计算机科学， 图遍历（Tree Traversal，也称图搜索）是一系列图搜索的算法， 是单次访问树结构类型数据（tree data structure)中每个节点以便检查或更新的一系列机制。图遍历算法可以按照节点访问顺序进行分类，根据访问目的或使用场景的不同，算法大致可分为28种：
图遍历即以特定方式访问图中所有节点，给定节点下有多种可能的搜索路径。假定以顺序方式进行（非并行），还未访问的节点就需通过堆栈（LIFO）或队列（FIFO）规则来确定访问先后。由于树结构是一种递归的数据结构，在清晰的定义下，未访问节点可存储在调用堆栈中。本文介绍了图遍历领域最流行的广度优先搜索算法BFS和深度优先搜索算法DFS，对其原理、应用及实现进行了阐述。通常意义上而言，深度优先搜索（DFS）通过递归调用堆栈比较容易实现，广义优先搜索通过队列实现。
深度优先搜索（DFS）是用于遍历或搜索图数据结构的算法，该算法从根节点开始（图搜索时可选择任意节点作为根节点）沿着每个分支进行搜索，分支搜索结束后在进行回溯。在进入下一节点之前，树的搜索尽可能的加深。
DFS的搜索算法如下（以二叉树为例）：假定根节点（图的任意节点可作为根节点）标记为 ,
(L) : 递归遍历左子树，并在节点 结束。
(R): 递归遍历右子树，并在节点 结束。
(N): 访问节点 。
这些步骤可以以任意次序排列。如果（L）在（R）之前，则该过程称为从左到右的遍历；反之，则称为从右到左的遍历。根据访问次序的不同，深度优先搜索可分为 pre-order、in-order、out-order以及post-order遍历方式。
（a）检查当前节点是否为空；
（b）展示根节点或当前节点数据；
（c）递归调用pre-order函数遍历左子树；
（d）递归调用pre-order函数遍历右子树。
pre-order遍历属于拓扑排序后的遍历，父节点总是在任何子节点之前被访问。该遍历方式的图示如下：
遍历次序依次为：F -B -A-D- C-E-G- I-H.
（a）检查当前节点是否为空；
（b）递归调用in-order函数遍历左子树；
（c）展示根节点或当前节点数据；
（d）递归调用in-order函数遍历右子树。
在二叉树搜索中，in-order遍历以排序顺序访问节点数据。该遍历方式的图示如下：
遍历次序依次为：A -B - C - D - E - F - G -H-I
（a）检查当前节点是否为空；
（b）递归调用out-order函数遍历右子树；
（c）展示根节点或当前节点数据；
（d）递归调用out-order函数遍历左子树。
该遍历方式与LNR类似，但先遍历右子树后遍历左子树。仍然以图2为例，遍历次序依次为：H- I-G- F- B- E- D- C- A.
（a）检查当前节点是否为空；
（b）递归调用post-order函数遍历左子树；
（c）递归调用post-order函数遍历右子树；
（d）展示根节点或当前节点数据。
post-order遍历图示如下：
遍历次序依次为：A-C-E-D-B-H-I-G-F.
pre-order遍历方式使用场景：用于创建树或图的副本；
in-order遍历使用场景：二叉树遍历；
post-order遍历使用场景：删除树
遍历追踪也称树的序列化，是所访问根节点列表。无论是pre-order，in-order或是post-order都无法完整的描述树特性。给定含有不同元素的树结构，pre-order或post-order与in-order遍历方式结合起来使用才可以描述树的独特性。
树或图形的访问也可以按照节点所处的级别进行遍历。在每次访问下一层级节点之前，遍历所在高层级的所有节点。BFS从根节点（图的任意节点可作为根节点）出发，在移动到下一节点之前访问所有相同深度水平的相邻节点。
BFS的遍历方法图示如下：
遍历次序依次为： F-B-G-A-D-I-C-E-H.
图算法相关的R包为igraph，主要包括图的生成、图计算等一系列算法的实现。
使用方法：
参数说明：
示例：
结果展示：
DFS R输出节点排序：
使用方法：
参数含义同dfs
示例：
结果展示：
BFS R输出节点排序：
以寻找两点之间的路径为例，分别展示BFS及DFS的实现。图示例如下：
示例：
输出结果：
示例：
输出结果：
[1] 维基网络： https://en.wikipedia.org/wiki/Tree_traversal
[2] GeeksforGeeks: https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/
[3] http://webdocs.cs.ualberta.ca/~holte/T26/tree-traversal.html
[4]Martin Broadhurst, Graph Algorithm: http://www.martinbroadhurst.com/Graph-algorithms.html#section_1_1
[5]igraph: https://igraph.org/r/doc/dfs.html
[6]igraph: https://igraph.org/r/doc/bfs.html
[7] Depth-First Search and Breadth-First Search in python: https://eddmann.com/posts/depth-first-search-and-breadth-first-search-in-python/
❼ java有哪些垃圾回收算法
常用的垃圾回收算法有：
(1).引用计数算法：
给对象中添加一个引用计数器，每当有一个地方引用它时，计数器值就加1；当引用失效时，计数器值就减1；任何时刻计数器都为0的对象就是不再被使用的，垃圾收集器将回收该对象使用的内存。
引用计数算法实现简单，效率很高，微软的COM技术、ActionScript、Python等都使用了引用计数算法进行内存管理，但是引用计数算法对于对象之间相互循环引用问题难以解决，因此java并没有使用引用计数算法。
(2).根搜索算法：
通过一系列的名为“GC Root”的对象作为起点，从这些节点向下搜索，搜索所走过的路径称为引用链(Reference Chain)，当一个对象到GC Root没有任何引用链相连时，则该对象不可达，该对象是不可使用的，垃圾收集器将回收其所占的内存。
主流的商用程序语言C#、java和Lisp都使用根搜素算法进行内存管理。
在java语言中，可作为GC Root的对象包括以下几种对象：
a. java虚拟机栈(栈帧中的本地变量表)中的引用的对象。
b.方法区中的类静态属性引用的对象。
c.方法区中的常量引用的对象。
d.本地方法栈中JNI本地方法的引用对象。
java方法区在Sun HotSpot虚拟机中被称为永久代，很多人认为该部分的内存是不用回收的，java虚拟机规范也没有对该部分内存的垃圾收集做规定，但是方法区中的废弃常量和无用的类还是需要回收以保证永久代不会发生内存溢出。
判断废弃常量的方法：如果常量池中的某个常量没有被任何引用所引用，则该常量是废弃常量。
判断无用的类：
(1).该类的所有实例都已经被回收，即java堆中不存在该类的实例对象。
(2).加载该类的类加载器已经被回收。
(3).该类所对应的java.lang.Class对象没有任何地方被引用，无法在任何地方通过反射机制访问该类的方法。
Java中常用的垃圾收集算法：
(1).标记-清除算法：
最基础的垃圾收集算法，算法分为“标记”和“清除”两个阶段：首先标记出所有需要回收的对象，在标记完成之后统一回收掉所有被标记的对象。
标记-清除算法的缺点有两个：首先，效率问题，标记和清除效率都不高。其次，标记清除之后会产生大量的不连续的内存碎片，空间碎片太多会导致当程序需要为较大对象分配内存时无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。
(2).复制算法：
将可用内存按容量分成大小相等的两块，每次只使用其中一块，当这块内存使用完了，就将还存活的对象复制到另一块内存上去，然后把使用过的内存空间一次清理掉。这样使得每次都是对其中一块内存进行回收，内存分配时不用考虑内存碎片等复杂情况，只需要移动堆顶指针，按顺序分配内存即可，实现简单，运行高效。
复制算法的缺点显而易见，可使用的内存降为原来一半。
(3).标记-整理算法：
标记-整理算法在标记-清除算法基础上做了改进，标记阶段是相同的标记出所有需要回收的对象，在标记完成之后不是直接对可回收对象进行清理，而是让所有存活的对象都向一端移动，在移动过程中清理掉可回收的对象，这个过程叫做整理。
标记-整理算法相比标记-清除算法的优点是内存被整理以后不会产生大量不连续内存碎片问题。
复制算法在对象存活率高的情况下就要执行较多的复制操作，效率将会变低，而在对象存活率高的情况下使用标记-整理算法效率会大大提高。
(4).分代收集算法：
根据内存中对象的存活周期不同，将内存划分为几块，java的虚拟机中一般把内存划分为新生代和年老代，当新创建对象时一般在新生代中分配内存空间，当新生代垃圾收集器回收几次之后仍然存活的对象会被移动到年老代内存中，当大对象在新生代中无法找到足够的连续内存时也直接在年老代中创建。
❽ 什么是 Java 虚拟机
您好，提问者：
Java虚拟机简称JVM，它的作用如下：
1、其实Java不可跨平台，真正实现跨平台的是JVM虚拟机。
2、JVM其实就是一个编译java、运行class的一个跟操作系统的一个软件。
3、JVM的作用只针对于Java，而系统中的东西与它无关。
4、其实说白了就是一个软件，就像VMware一样。
Java虚拟机
一、什么是Java虚拟机
Java虚拟机是一个想象中的机器,在实际的计算机上通过软件模拟来实现。Java虚拟机有自己想象中的硬件,如处理器、堆栈、寄存器等,还具有相应的指令系统。
为什么要使用Java虚拟机
Java语言的一个非常重要的特点就是与平台的无关性。而使用Java虚拟机是实现这一特点的关键。一般的高级语言如果要在不同的平台上运行,至少需要编译成不同的目标代码。而引入Java语言虚拟机后,Java语言在不同平台上运行时不需要重新编译。Java语言使用模式Java虚拟机屏蔽了与具体平台相关的信息,使得Java语言编译程序只需生成在Java虚拟机上运行的目标代码(字节码),就可以在多种平台上不加修改地运行。Java虚拟机在执行字节码时,把字节码解释成具体平台上的机器指令执行。
2.谁需要了解Java虚拟机
Java虚拟机是Java语言底层实现的基础,对Java语言感兴趣的人都应对Java虚拟机有个大概的了解。这有助于理解Java语言的一些性质,也有助于使用Java语言。对于要在特定平台上实现Java虚拟机的软件人员,Java语言的编译器作者以及要用硬件芯片实现Java虚拟机的人来说,则必须深刻理解Java虚拟机的规范。另外,如果你想扩展Java语言,或是把其它语言编译成Java语言的字节码,你也需要深入地了解Java虚拟机。
3.Java虚拟机支持的数据类型
Java虚拟机支持Java语言的基本数据类型如下:
byte://1字节有符号整数的补码
short://2字节有符号整数的补码
int://4字节有符号整数的补码
long://8字节有符号整数的补码
float://4字节IEEE754单精度浮点数
double://8字节IEEE754双精度浮点数
char://2字节无符号Unicode字符
几乎所有的Java类型检查都是在编译时完成的。上面列出的原始数据类型的数据在Java执行时不需要用硬件标记。操作这些原始数据类型数据的字节码(指令)本身就已经指出了操作数的数据类型,例如iadd、ladd、fadd和dadd指令都是把两个数相加,其操作数类型别是int、long、float和double。虚拟机没有给boolean(布尔)类型设置单独的指令。boolean型的数据是由integer指令,包括integer返回来处理的。boolean型的数组则是用byte数组来处理的。虚拟机使用IEEE754格式的浮点数。不支持IEEE格式的较旧的计算机,在运行Java数值计算程序时,可能会非常慢。
虚拟机支持的其它数据类型包括:
object//对一个Javaobject(对象)的4字节引用
returnAddress//4字节,用于jsr/ret/jsr-w/ret-w指令
注:Java数组被当作object处理。
虚拟机的规范对于object内部的结构没有任何特殊的要求。在Sun公司的实现中,对object的引用是一个句柄,其中包含一对指针:一个指针指向该object的方法表,另一个指向该object的数据。用Java虚拟机的字节码表示的程序应该遵守类型规定。Java虚拟机的实现应拒绝执行违反了类型规定的字节码程序。Java虚拟机由于字节码定义的限制似乎只能运行于32位地址空间的机器上。但是可以创建一个Java虚拟机,它自动地把字节码转换成64位的形式。从Java虚拟机支持的数据类型可以看出,Java对数据类型的内部格式进行了严格规定,这样使得各种Java虚拟机的实现对数据的解释是相同的,从而保证了Java的与平台无关性和可
移植性。
二、Java虚拟机体系结构
Java虚拟机由五个部分组成:一组指令集、一组寄存器、一个栈、一个无用单元收集堆(Garbage-collected-heap)、一个方法区域。这五部分是Java虚拟机的逻辑成份,不依赖任何实现技术或组织方式,但它们的功能必须在真实机器上以某种方式实现。
Java指令集
Java虚拟机支持大约248个字节码。每个字节码执行一种基本的CPU运算,例如,把一个整数加到寄存器,子程序转移等。Java指令集相当于Java程序的汇编语言。
Java指令集中的指令包含一个单字节的操作符,用于指定要执行的操作,还有0个或多个操作数,提供操作所需的参数或数据。许多指令没有操作数,仅由一个单字节的操作符构成。
虚拟机的内层循环的执行过程如下:
do{
取一个操作符字节;
根据操作符的值执行一个动作;
}while(程序未结束)
由于指令系统的简单性,使得虚拟机执行的过程十分简单,从而有利于提高执行的效率。指令中操作数的数量和大小是由操作符决定的。如果操作数比一个字节大,那么它存储的顺序是高位字节优先。例如,一个16位的参数存放时占用两个字节,其值为:
第一个字节*256+第二个字节字节码指令流一般只是字节对齐的。指令tabltch和lookup是例外,在这两条指令内部要求强制的4字节边界对齐。
2.寄存器
Java虚拟机的寄存器用于保存机器的运行状态,与微处理器中的某些专用寄存器类似。
Java虚拟机的寄存器有四种:
pc:Java程序计数器。
optop:指向操作数栈顶端的指针。
frame:指向当前执行方法的执行环境的指针。
vars:指向当前执行方法的局部变量区第一个变量的指针。
Java虚拟机
Java虚拟机是栈式的,它不定义或使用寄存器来传递或接受参数,其目的是为了保证指令集的简洁性和实现时的高效性(特别是对于寄存器数目不多的处理器)。
所有寄存器都是32位的。
3.栈
Java虚拟机的栈有三个区域:局部变量区、运行环境区、操作数区。
(1)局部变量区 每个Java方法使用一个固定大小的局部变量集。它们按照与vars寄存器的字偏移量来寻址。局部变量都是32位的。长整数和双精度浮点数占据了两个局部变量的空间,却按照第一个局部变量的索引来寻址。(例如,一个具有索引n的局部变量,如果是一个双精度浮点数,那么它实际占据了索引n和n+1所代表的存储空间。)虚拟机规范并不要求在局部变量中的64位的值是64位对齐的。虚拟机提供了把局部变量中的值装载到操作数栈的指令,也提供了把操作数栈中的值写入局部变量的指令。
(2)运行环境区 在运行环境中包含的信息用于动态链接,正常的方法返回以及异常传播。
·动态链接
运行环境包括对指向当前类和当前方法的解释器符号表的指针,用于支持方法代码的动态链接。方法的class文件代码在引用要调用的方法和要访问的变量时使用符号。动态链接把符号形式的方法调用翻译成实际方法调用,装载必要的类以解释还没有定义的符号,并把变量访问翻译成与这些变量运行时的存储结构相应的偏移地址。动态链接方法和变量使得方法中使用的其它类的变化不会影响到本程序的代码。
·正常的方法返回
如果当前方法正常地结束了,在执行了一条具有正确类型的返回指令时,调用的方法会得到一个返回值。执行环境在正常返回的情况下用于恢复调用者的寄存器,并把调用者的程序计数器增加一个恰当的数值,以跳过已执行过的方法调用指令,然后在调用者的执行环境中继续执行下去。
·异常和错误传播
异常情况在Java中被称作Error(错误)或Exception(异常),是Throwable类的子类,在程序中的原因是:①动态链接错,如无法找到所需的class文件。②运行时错,如对一个空指针的引用
·程序使用了throw语句。
当异常发生时,Java虚拟机采取如下措施:
·检查与当前方法相联系的catch子句表。每个catch子句包含其有效指令范围,能够处理的异常类型,以及处理异常的代码块地址。
·与异常相匹配的catch子句应该符合下面的条件:造成异常的指令在其指令范围之内,发生的异常类型是其能处理的异常类型的子类型。如果找到了匹配的catch子句,那么系统转移到指定的异常处理块处执行;如果没有找到异常处理块,重复寻找匹配的catch子句的过程,直到当前方法的所有嵌套的catch子句都被检查过。
·由于虚拟机从第一个匹配的catch子句处继续执行,所以catch子句表中的顺序是很重要的。因为Java代码是结构化的,因此总可以把某个方法的所有的异常处理器都按序排列到一个表中,对任意可能的程序计数器的值,都可以用线性的顺序找到合适的异常处理块,以处理在该程序计数器值下发生的异常情况。
·如果找不到匹配的catch子句,那么当前方法得到一个"未截获异常"的结果并返回到当前方法的调用者,好像异常刚刚在其调用者中发生一样。如果在调用者中仍然没有找到相应的异常处理块,那么这种错误传播将被继续下去。如果错误被传播到最顶层,那么系统将调用一个缺省的异常处理块。
(3)操作数栈区 机器指令只从操作数栈中取操作数,对它们进行操作,并把结果返回到栈中。选择栈结构的原因是:在只有少量寄存器或非通用寄存器的机器(如Intel486)上,也能够高效地模拟虚拟机的行为。操作数栈是32位的。它用于给方法传递参数,并从方法接收结果,也用于支持操作的参数,并保存操作的结果。例如,iadd指令将两个整数相加。相加的两个整数应该是操作数栈顶的两个字。这两个字是由先前的指令压进堆栈的。这两个整数将从堆栈弹出、相加,并把结果压回到操作数栈中。
每个原始数据类型都有专门的指令对它们进行必须的操作。每个操作数在栈中需要一个存储位置,除了long和double型,它们需要两个位置。操作数只能被适用于其类型的操作符所操作。例如,压入两个int类型的数,如果把它们当作是一个long类型的数则是非法的。在Sun的虚拟机实现中,这个限制由字节码验证器强制实行。但是,有少数操作(操作符pe和swap),用于对运行时数据区进行操作时是不考虑类型的。
4.无用单元收集堆
Java的堆是一个运行时数据区,类的实例(对象)从中分配空间。Java语言具有无用单元收集能力:它不给程序员显式释放对象的能力。Java不规定具体使用的无用单元收集算法,可以根据系统的需求使用各种各样的算法。
5.方法区
方法区与传统语言中的编译后代码或是Unix进程中的正文段类似。它保存方法代码(编译后的java代码)和符号表。在当前的Java实现中,方法代码不包括在无用单元收集堆中,但计划在将来的版本中实现。每个类文件包含了一个Java类或一个Java界面的编译后的代码。可以说类文件是Java语言的执行代码文件。为了保证类文件的平台无关性,Java虚拟机规范中对类文件的格式也作了详细的说明。其具体细节请参考Sun公司的Java虚拟机规范。