is
zhou

UUID是如何保证唯一性的?

zhouchong阅读(63)评论(0)

1.UUID 简介

UUID含义是通用唯一识别码 (Universally Unique Identifier),这是一个软件建构的标准,也是被开源软件基金会 (Open Software Foundation, OSF)
的组织应用在分布式计算环境 (Distributed Computing Environment, DCE) 领域的一部分。

UUID 的目的,是让分布式系统中的所有元素,都能有唯一的辨识资讯,而不需要透过中央控制端来做辨识资讯的指定。如此一来,每个人都可以建立不与其它人冲突的 UUID。
在这样的情况下,就不需考虑数据库建立时的名称重复问题。目前最广泛应用的 UUID,即是微软的 Microsoft’s Globally Unique Identifiers (GUIDs),而其他重要的应用,
则有 Linux ext2/ext3 档案系统、LUKS 加密分割区、GNOME、KDE、Mac OS X 等等

2.UUID 组成

UUID保证对在同一时空中的所有机器都是唯一的。通常平台会提供生成的API。按照开放软件基金会(OSF)制定的标准计算,用到了以太网卡地址、纳秒级时间、芯片ID码和许多可能的数字
UUID由以下几部分的组合:
(1)当前日期和时间,UUID的第一个部分与时间有关,如果你在生成一个UUID之后,过几秒又生成一个UUID,则第一个部分不同,其余相同。
(2)时钟序列。
(3)全局唯一的IEEE机器识别号,如果有网卡,从网卡MAC地址获得,没有网卡以其他方式获得。
UUID的唯一缺陷在于生成的结果串会比较长。关于UUID这个标准使用最普遍的是微软的GUID(Globals Unique Identifiers)。在ColdFusion中可以用CreateUUID()函数很简单地生成UUID,
其格式为:xxxxxxxx-xxxx- xxxx-xxxxxxxxxxxxxxxx(8-4-4-16),其中每个 x 是 0-9 或 a-f 范围内的一个十六进制的数字。而标准的UUID格式为:xxxxxxxx-xxxx-xxxx-xxxx-xxxxxxxxxxxx (8-4-4-4-12);

3.项目实战

UUID 来作为数据库数据表主键是非常不错的选择,保证每次生成的UUID 是唯一的。

a.生成 UUID
需要用到java 自带 JDk;

import java.util.UUID;
public static void main(String[] args) {
for(int i=0;i<10;i++){
String uuid = UUID.randomUUID().toString().replaceAll("-", "");
System.out.println(uuid);
}
}

 

b.生成指定数目的 UUID

/** 
* 获得指定数目的UUID 
* @param number int 需要获得的UUID数量 
* @return String[] UUID数组 
*/ 
public static String[] getUUID(int number){ 
if(number < 1){ 
return null; 
} 
String[] retArray = new String[number]; 
for(int i=0;i<number;i++){ 
retArray[i] = getUUID(); 
} 
return retArray; 
}

/** 
* 获得一个UUID 
* @return String UUID 
*/ 
public static String getUUID(){ 
String uuid = UUID.randomUUID().toString(); 
//去掉“-”符号 
return uuid.replaceAll("-", "");
}

虚拟机里呢?生成两个完全相同的虚拟机,然后让他们在同一时间生成UUID。。。会得到相同的UUID吗?

 

UUID的应用
从UUID的不同版本可以看出,
Version 1/2适合应用于分布式计算环境下,具有高度的唯一性;
Version 3/5适合于一定范围内名字唯一,且需要或可能会重复生成UUID的环境下;
至于Version 4,个人的建议是最好不用(虽然它是最简单最方便的)。
通常我们建议使用UUID来标识对象或持久化数据,但以下情况最好不使用UUID:
映射类型的对象。比如只有代码及名称的代码表。
人工维护的非系统生成对象。比如系统中的部分基础数据。
首先,即便是虚拟机的话MAC地址也是不一样的。另外你说的统一时间还是个宏观的概念,这个仅仅是决定了UUID生产串中的某一部分相同而已,因为为了保证UUID的唯一性,规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素。
当然,你要说UUID是不是绝对的不会出现重复的,这个也不能这样说的(我下面会提到)。
UUID具有以下涵义:
经由一定的算法机器生成
为了保证UUID的唯一性,规范定义了包括网卡MAC地址、时间戳、名字空间(Namespace)、随机或伪随机数、时序等元素,以及从这些元素生成UUID的算法。UUID的复杂特性在保证了其唯一性的同时,意味着只能由计算机生成。
非人工指定,非人工识别
UUID是不能人工指定的,除非你冒着UUID重复的风险。UUID的复杂性决定了“一般人“不能直接从一个UUID知道哪个对象和它关联。
在特定的范围内重复的可能性极小
UUID的生成规范定义的算法主要目的就是要保证其唯一性。但这个唯一性是有限的,只在特定的范围内才能得到保证,这和UUID的类型有关(参见UUID的版本)。
UUID的版本
UUID具有多个版本,每个版本的算法不同,应用范围也不同。
首先是一个特例--Nil UUID--通常我们不会用到它,它是由全为0的数字组成,如下:
00000000-0000-0000-0000-000000000000
UUID Version 1:基于时间的UUID
基于时间的UUID通过计算当前时间戳、随机数和机器MAC地址得到。由于在算法中使用了MAC地址,这个版本的UUID可以保证在全球范围的唯一性。但与此同时,使用MAC地址会带来安全性问题,这就是这个版本UUID受到批评的地方。如果应用只是在局域网中使用,也可以使用退化的算法,以IP地址来代替MAC地址--Java的UUID往往是这样实现的(当然也考虑了获取MAC的难度)。
UUID Version 2:DCE安全的UUID
DCE(Distributed Computing Environment)安全的UUID和基于时间的UUID算法相同,但会把时间戳的前4位置换为POSIX的UID或GID。这个版本的UUID在实际中较少用到。
UUID Version 3:基于名字的UUID(MD5)
基于名字的UUID通过计算名字和名字空间的MD5散列值得到。这个版本的UUID保证了:相同名字空间中不同名字生成的UUID的唯一性;不同名字空间中的UUID的唯一性;相同名字空间中相同名字的UUID重复生成是相同的。
UUID Version 4:随机UUID
根据随机数,或者伪随机数生成UUID。这种UUID产生重复的概率是可以计算出来的,但随机的东西就像是买彩票:你指望它发财是不可能的,但狗屎运通常会在不经意中到来。
UUID Version 5:基于名字的UUID(SHA1)
和版本3的UUID算法类似,只是散列值计算使用SHA1(Secure Hash Algorithm 1)算法。对于具有名称不可重复的自然特性的对象,最好使用Version 3/5的UUID。比如系统中的用户。如果用户的UUID是Version 1的,如果你不小心删除了再重建用户,你会发现人还是那个人,用户已经不是那个用户了。(虽然标记为删除状态也是一种解决方案,但会带来实现上的复杂性。)

 

Java instanceof 关键字是如何实现的?

zhouchong阅读(64)评论(0)

其实面试官问你啥不重要,重要的是你觉得你概率大不大,不大的话请你随意点有的问题懒得答就甭理他.直接说不知道就行了. 大的话你要斟酌了,你对这个工作职位兴趣如何.

很多时候面试官冷不丁会冒出一个毫无意义但又本领域又极少有人研究过的技术问题. 这也没办法我通常推荐你按我开头的一句话来应付
回到这个毫无意义的问题本身.

其实反问各位JAVA程序员一句,甭说instanceof了, try catch你知道详细的内部实现吗?

及其常用的synchronized 你又知道吗?

我们不说怎么用 什么场景用,性能问题, 就问他内部怎么实现的…你知道不知道?啊.. 你知道不知道?
毕竟我们不是应试oracle的JVM开发岗位. 对吧?
知道instanceof具体实现和在正确的场景使用instanceof完全是两个工种要掌握的东西.

这两个工种都能够达到月薪50k的水平.所以我不同意RednaxelaFX用薪资来衡量对JVM底层的掌握

工种不同嘛, 还有更多嵌入式开发的东西其实你们也都不知道. 哦…不对,是我们也都不知道. 他们工资也不低呀. 他们也不了解JAVA程序员所了解的另外一些知识呀.

但根据自身的不懈努力 其实大家都能在自己职业方向上拿到不错的薪水的.

完全不懂JVM实现, 仅仅知道JVM配置参数以及丰富的开发经验一样可以进行JVM调优.
打个比方:

美术人员使用的PS软件.或者玛雅软件,他们详细的知道怎么用就行了吧?最最重要的还是他们本身的艺术修养和使用该软件的熟练度吧?

你面试的时候问一个美术人员会不会开发PS软件? 懂不懂玛雅绘制3D的技术原理?


在进入正题前先得提一句:既然楼主提问的背景是“被面试问到”,那很重要的一点是揣摩面试官提问的意图。按照楼主的简单描述,面试官问的是“Java的instanceof关键字是如何实现的”,那要选择怎样的答案就得看面试官有怎样的背景。比较安全的应对方法是请求面试官澄清/细化他的问题——他想要的“底层”底到什么程度。

———————————————————————

情形1:
你在面月薪3000以下的Java码农职位。如果面试官也只是做做Java层开发的,他可能只是想让你回答Java语言层面的 instanceof 运算符的语义。Java语言的“意思”就已经是“底层”。这样的话只要参考Java语言规范对 instanceof 运算符的定义就好:
15.20.2 Type Comparison Operator instanceof, Java语言规范Java SE 7版
当然这实际上回答的不是“如何实现的”,而是“如何设计的”。但面试嘛⋯

如果用Java的伪代码来表现Java语言规范所描述的运行时语义,会是这样:

// obj instanceof T
boolean result;
if (obj == null) {
  result = false;
} else {
  try {
      T temp = (T) obj; // checkcast
      result = true;
  } catch (ClassCastException e) {
      result = false;
  }
}

用中文说就是:如果有表达式 obj instanceof T ,那么如果 obj 不为 null 并且 (T) obj 不抛 ClassCastException 异常则该表达式值为 true ,否则值为 false 。
注意这里完全没提到JVM啊Class对象啊啥的。另外要注意 instanceof 运算符除了运行时语义外还有部分编译时限制,详细参考规范。

如果这样回答被面试官说“这不是废话嘛”,请见情形2。

———————————————————————

情形2:
你在面月薪6000-8000的Java研发职位。面试官也知道JVM这么个大体概念,但知道的也不多。JVM这个概念本身就是“底层”。JVM有一条名为 instanceof 的指令,而Java源码编译到Class文件时会把Java语言中的 instanceof 运算符映射到JVM的 instanceof 指令上。

你可以知道Java的源码编译器之一javac是这样做的:

  1. instanceof 是javac能识别的一个关键字,对应到Token.INSTANCEOF的token类型。做词法分析的时候扫描到”instanceof”关键字就映射到了一个Token.INSTANCEOF token。jdk7u/jdk7u/langtools: 5c9759e0d341 src/share/classes/com/sun/tools/javac/parser/Token.java
  2. 该编译器的抽象语法树节点有一个JCTree.JCInstanceOf类用于表示instanceof运算。做语法分析的时候解析到instanceof运算符就会生成这个JCTree.JCInstanceof类型的节点。jdk7u/jdk7u/langtools: 5c9759e0d341 src/share/classes/com/sun/tools/javac/parser/JavacParser.java term2Rest()
  3. 中途还得根据Java语言规范对instanceof运算符的编译时检查的规定把有问题的情况找出来。
  4. 到最后生成字节码的时候为JCTree.JCInstanceof节点生成instanceof字节码指令。jdk7u/jdk7u/langtools: 5c9759e0d341 src/share/classes/com/sun/tools/javac/jvm/Gen.java visitTypeTest()

(Java语言君说:“instanceof 这问题直接交给JVM君啦”)
(面试官:你还给我废话⋯给我进情形3!)

其实能回答到这层面就已经能解决好些实际问题了,例如说需要手工通过字节码增强来实现一些功能的话,知道JVM有这么条 instanceof 指令或许正好就能让你顺利的使用 ASM 之类的库完成工作。

———————————————————————

情形3:
你在面月薪10000的Java高级研发职位。面试官对JVM有一些了解,想让你说说JVM会如何实现 instanceof 指令。但他可能也没看过实际的JVM是怎么做的,只是臆想过一下而已。JVM的规定就是“底层”。这种情况就给他JVM规范对 instanceof 指令的定义就好:
Chapter 6. The Java Virtual Machine Instruction Set, JVM规范Java SE 7版
根据规范来臆想一下实现就能八九不离十的混过这题了。

该层面的答案就照

前面给出的就差不多了,这边不再重复。

———————————————————————

情形4:
你可能在面真的简易JVM的研发职位,或许是啥嵌入式JVM的实现。面试官会希望你对简易JVM的实现有所了解。JVM的直观实现就是“底层”。这个基本上跟情形3差不多,因为简易JVM通常会用很直观的方式去实现。但对具体VM实现得答对一些小细节,例如说这个JVM是如何管理类型信息的。

这个情形的话下面举点例子来讲讲。

———————————————————————

情形5:
你在面试月薪10000以上的Java资深研发职位,注重性能调优啥的。这种职位虽然不直接涉及JVM的研发,但由于性能问题经常源自“抽象泄漏”,对实际使用的JVM的实现的思路需要有所了解。面试官对JVM的了解可能也就在此程度。对付这个可以用一篇论文:Fast subtype checking in the HotSpot JVM。之前有个讨论帖里讨论过对这篇论文的解读:请教一个share/vm/oops下的代码做fast subtype check的问题

———————————————————————

情形6:
你在面试真的高性能JVM的研发职位,例如 HotSpot VM 的研发。JVM在实际桌面或服务器环境中的具体实现是“底层”。呵呵这要回答起来就复杂了,必须回答出JVM实现中可能做的优化具体的实现。另外找地方详细写。

———————————————————————

我觉得会问这种问题的还是情形1和2的比例比较大,换句话说面试官也不知道真的JVM是如何实现这instanceof指令的,可能甚至连这指令的准确语义都无法描述对。那随便忽悠忽悠就好啦不用太认真。说不定他期待的答案本身就雾很大(逃

碰上情形4、6的话,没有忽悠的余地,是怎样就得怎样。
情形5可能还稍微有点忽悠余地呃呵呵。

==============================================================

看俩实际存在的简易JVM的实现,Kaffe和JamVM。它们都以解释器为主,JIT的实现非常简单,主要功能还是在VM runtime里实现,所以方便考察。
主要考察的是:它们中Java对象的基本结构(如何找到类型信息),类型信息自身如何记录(内部用的类型信息与Java层的java.lang.Class对象的关系),以及instanceof具体是怎样实现的。

———————————————————————

Kaffe

github.com/kaffe/kaffe/
Kaffe中Java对象由Hjava_lang_Object结构体表示,里面有个struct _dispatchTable*类型的字段vtable,下面再说。

github.com/kaffe/kaffe/
Java层的java.lang.Class实例在VM里由Hjava_lang_Class结构体表示。Kaffe直接使用Hjava_lang_Class来记录VM内部的类型信息。也就是说在Kaffe上运行的Java程序里持有的java.lang.Class的实例就是该JVM内部存类型信息的对象。
前面提到的_dispatchTable结构体也在该文件里定义。它是一个虚方法分派表,主要用于高效实现invokevirtual。
假如有Hjava_lang_Object* obj,要找到它对应的类型信息只要这样:

obj->vtable->class

github.com/kaffe/kaffe/
instanceof的功能由soft.c的soft_instanceof()函数实现。该函数所调用的函数大部分都在这个文件里。

github.com/kaffe/kaffe/
这边定义了softcall_instanceof宏用于在解释器或者JIT编译后的代码里调用soft_instanceof()函数

github.com/kaffe/kaffe/
这边定义了instanceof字节码指令的处理要调用softcall_instanceof宏

———————————————————————

JamVM

jamvm.cvs.sourceforge.net
JamVM中Java对象由Object结构体表示,Java层的java.lang.Class实例在VM里由Class表示(是个空Object),VM内部记录的类信息由ClassBlock结构体表示(类型名、成员、父类、实现的接口、类价值器啥的都记录在ClassBlock里)。比较特别的是每个Class与对应的ClassBlock实际上是粘在一起分配的,所以Class*与ClassBlock*可以很直接的相互转换。例如说如果有Class* c想拿到它对应的ClassBlock,只要:

ClassBlock* cb = CLASS_CB(c);

即可。
Object结构体里有Class*类型的成员class,用于记录对象的类型。

jamvm.cvs.sourceforge.net
instanceof的功能由cast.c第68行的isInstanceOf()函数实现。该函数所调用的函数大部分都在这个文件里。
jamvm.cvs.sourceforge.net
解释器主循环的代码主要在interp.c里。把instanceof指令的参数所指定的常量池索引解析为实际类指针的逻辑在OPC_INSTANCEOF的实现里。JamVM做了个优化,在解析好类之后会把instanceof字节码改写为内部字节码instanceof_quick;调用isInstanceOf()的地方在2161行OPC_INSTANCEOF_QUICK的实现里,可以看到它调用的是isInstanceOf(class, obj->class)。

———————————————————————

上面介绍了Kaffe与JamVM里instanceof字节码的实现相关的代码在哪里。接下来简单分析下它们的实现策略。

两者的实现策略其实几乎一样,基本上按照下面的步骤:
(假设要检查的对象引用是obj,目标的类型对象是T)

  1. obj如果为null,则返回false;否则设S为obj的类型对象,剩下的问题就是检查S是否为T的子类型
  2. 如果S == T,则返回true;
  3. 接下来分为3种情况,S是数组类型、接口类型或者类类型。之所以要分情况是因为instanceof要做的是“子类型检查”,而Java语言的类型系统里数组类型、接口类型与普通类类型三者的子类型规定都不一样,必须分开来讨论。到这里虽然例中两个JVM的具体实现有点区别,但概念上都与JVM规范所描述的 instanceof的基本算法 几乎一样。其中一个细节是:对接口类型的instanceof就直接遍历S里记录的它所实现的接口,看有没有跟T一致的;而对类类型的instanceof则是遍历S的super链(继承链)一直到Object,看有没有跟T一致的。遍历类的super链意味着这个算法的性能会受类的继承深度的影响。

关于Java语言里子类型关系的定义,请参考:Chapter 4. Types, Values, and Variables
类类型和接口类型的子类型关系大家可能比较熟悉,而数组类型的子类型关系可能会让大家有点意外。

4.10.3. Subtyping among Array Types
The following rules define the direct supertype relation among array types:

  • If S and T are both reference types, then S[] >1 T[] iff S >1 T.
  • Object >1 Object[]
  • Cloneable >1 Object[]
  • java.io.Serializable >1 Object[]
  • If P is a primitive type, then:
    • Object >1 P[]
    • Cloneable >1 P[]
    • java.io.Serializable >1 P[]

这里稍微举几个例子。以下子类型关系都成立(“<:”符号表示左边是右边的子类型,“=>”符号表示“推导出”):

  1. String[][][] <: String[][][] (数组子类型关系的自反性)
  2. String <: CharSequence => String[] <: CharSequence[] (数组的协变)
  3. String[][][] <: Object (所有数组类型是Object的子类型)
  4. int[] <: Serializable (原始类型数组实现java.io.Serializable接口)
  5. Object[] <: Serializable (引用类型数组实现java.io.Serializable接口)
  6. int[][][] <: Serializable[][] <: Serializable[] <: Serializable (上面几个例子的延伸⋯开始好玩了吧?)
  7. int[][][] <: Object[][] <: Object[] <: Object

好玩不?实际JVM在记录类型信息的时候必须想办法把这些相关类型都串起来以便查找。

另外补充一点:楼主可能会觉得很困惑为啥说到这里只字未提ClassLoader——因为在这个问题里还轮不到它出场。
在一个JVM实例里,”(类型的全限定名, defining class loader)”这个二元组才可以唯一确定一个类。如果有两个类全限定名相同,也加载自同一个Class文件,但defining class loader不同,从VM的角度看它们就是俩不同的类,而且相互没有子类型关系。instanceof运算符只关心“是否满足子类型关系”,至于类型名是否相同之类的不需要关心。

通过Kaffe与JamVM两个例子我们可以看到简单的JVM实现很多地方就是把JVM规范直观的实现了出来。这就解决了前面提到的情形4的需求。

==============================================================

至于情形5、6,细节讲解起来稍麻烦所以这里不想展开写。高性能的JVM跟简易JVM在细节上完全不是一回事。

简单来说,优化的主要思路就是把Java语言的特点考虑进来:由于Java的类所继承的超类与所实现的接口都不会在运行时改变,整个继承结构是稳定的,某个类型C在继承结构里的“深度”是固定不变的。也就是说从某个类出发遍历它的super链,总是会遍历到不变的内容。
这样我们就可以把原本要循环遍历super链才可以找到的信息缓存在数组里,并且以特定的下标从这个数组找到我们要的信息。同时,Java的类继承深度通常不会很深,所以为这个缓存数组选定一个固定的长度就足以优化大部分需要做子类型判断的情况。

HotSpot VM具体使用了长度为8的缓存数组,记录某个类从继承深度0到7的超类。HotSpot把类继承深度在7以内的超类叫做“主要超类型”(primary super),把所有其它超类型(接口、数组相关以及超过深度7的超类)叫做“次要超类型”(secondary super)。
对“主要超类型”的子类型判断不需要像Kaffe或JamVM那样沿着super链做遍历,而是直接就能判断子类型关系是否成立。这样,类的继承深度对HotSpot VM做子类型判断的性能影响就变得很小了。
对“次要超类型”,则是让每个类型把自己的“次要超类型”混在一起记录在一个数组里,要检查的时候就线性遍历这个数组。留意到这里把接口类型、数组类型之类的子类型关系都直接记录在同一个数组里了,只要在最初初始化secondary_supers数组时就分情况填好了,而不用像Kaffe、JamVM那样每次做instanceof运算时都分开处理这些情况。

举例来说,如果有下述类继承关系:
Apple <: Fruit <: Plant <: Object
并且以Object为继承深度0,那么对于Apple类来说,它的主要超类型就有:
0: Object
1: Plant
2: Fruit
3: Apple
这个信息就直接记录在Apple类的primary_supers数组里了。Fruit、Plant等类同理。

如果我们有这样的代码:

Object f = new Apple();
boolean result = f instanceof Plant;

也就是变量f实际指向一个Apple实例,而我们要问这个对象是否是Plant的实例。
可以知道f的实际类型是Apple;要测试的Plant类的继承深度是1,拿Apple类里继承深度为1的主要超类型来看是Plant,马上就能得出结论是true。
这样就不需要顺着Apple的继承链遍历过去一个个去看是否跟Plant相等了。

对此感兴趣的同学请参考前面在情形5提到的两个链接。先读第一个链接那篇论文,然后看第二个链接里的讨论(没有ACM帐号无法从第一个链接下载到论文的同学可以在第二个链接里找到一个镜像)。

JDK6至今的HotSpot VM实际采用的算法是:

S.is_subtype_of(T) := {
  int off = T.offset;
  if (S == T) return true;
  if (T == S[off]) return true;
  if (off != &cache) return false;
  if ( S.scan_secondary_subtype_array(T) ) {
    S.cache = T;
    return true;
  }
  return false;
}

(具体是什么意思请务必参考论文)

这边想特别强调的一点是:那篇论文描述了HotSpot VM做子类型判断的算法,但其实只有HotSpot VM的解释器以及 java.lang.Class.isInstance() 的调用是真的完整按照那个算法来执行的。HotSpot VM的两个编译器,Client Compiler (C1) 与 Server Compiler (C2) 各自对子类型判断的实现有更进一步的优化。实际上在这个JVM里,instanceof的功能就实现了4份,VM runtime、解释器、C1、C2各一份。

VM runtime的:
jdk7u/jdk7u/hotspot: e087a2088970 src/share/vm/oops/oop.inline.hpp oopDesc::is_a()
jdk7u/jdk7u/hotspot: e087a2088970 src/share/vm/oops/klass.hpp is_subtype_of()
jdk7u/jdk7u/hotspot: e087a2088970 src/share/vm/oops/klass.cpp Klass::search_secondary_supers()

inline bool oopDesc::is_a(klassOop k)        const { return blueprint()->is_subtype_of(k); }
  bool is_subtype_of(klassOop k) const {
    juint    off = k->klass_part()->super_check_offset();
    klassOop sup = *(klassOop*)( (address)as_klassOop() + off );
    const juint secondary_offset = in_bytes(secondary_super_cache_offset());
    if (sup == k) {
      return true;
    } else if (off != secondary_offset) {
      return false;
    } else {
      return search_secondary_supers(k);
    }
  }
  bool search_secondary_supers(klassOop k) const;
bool Klass::search_secondary_supers(klassOop k) const {
  // Put some extra logic here out-of-line, before the search proper.
  // This cuts down the size of the inline method.

  // This is necessary, since I am never in my own secondary_super list.
  if (this->as_klassOop() == k)
    return true;
  // Scan the array-of-objects for a match
  int cnt = secondary_supers()->length();
  for (int i = 0; i < cnt; i++) {
    if (secondary_supers()->obj_at(i) == k) {
      ((Klass*)this)->set_secondary_super_cache(k);
      return true;
    }
  }
  return false;
}

解释器的(以x86-64的template interpreter为例):
jdk7u/jdk7u/hotspot: e087a2088970 src/cpu/x86/vm/templateTable_x86_64.cpp TemplateTable::instanceof()
jdk7u/jdk7u/hotspot: e087a2088970 src/cpu/x86/vm/interp_masm_x86_64.cpp InterpreterMacroAssembler::gen_subtype_check()
(太长,不把代码贴出来了。要看代码请点上面链接)

C1和C2对instanceof的优化分散在好几个地方,以C1为例,
C1把Java字节码parse成HIR(High-level Intermediate Representation)的逻辑在GraphBuilder::iterate_bytecodes_for_block(),它先把instanceof字节码解析成了InstanceOf节点:
jdk7u/jdk7u/hotspot: e087a2088970 src/share/vm/c1/c1_GraphBuilder.cpp
然后在优化过程中,InstanceOf节点会观察它的对象参数是否为常量null或者是固定的已知类型,并相应的尝试做常量折叠:
jdk7u/jdk7u/hotspot: e087a2088970 src/share/vm/c1/c1_Canonicalizer.cpp Canonicalizer::do_InstanceOf
如果已经常量折叠了的话就没后续步骤了。反之则继续下去生成LIR:
jdk7u/jdk7u/hotspot: e087a2088970 src/cpu/x86/vm/c1_LIRGenerator_x86.cpp LIRGenerator::do_InstanceOf
jdk7u/jdk7u/hotspot: e087a2088970 src/share/vm/c1/c1_LIR.cpp LIR_List::instanceof
最后生成机器码:
jdk7u/jdk7u/hotspot: e087a2088970 src/cpu/x86/vm/c1_LIRAssembler_x86.cpp LIR_Assembler::emit_opTypeCheck
jdk7u/jdk7u/hotspot: e087a2088970 src/cpu/x86/vm/c1_LIRAssembler_x86.cpp LIR_Assembler::emit_typecheck_helper
生成的机器码逻辑跟解释器版本基本上是一样的,只是寄存器使用上稍微不同。

而在C2中,
最初处理instanceof字节码生成C2的内部节点的逻辑主要在:
jdk7u/jdk7u/hotspot: e087a2088970 src/share/vm/opto/graphKit.cpp GraphKit::gen_instanceof()
它会调用 GraphKit::gen_subtype_check() 来生成检查逻辑的主体,而后者会根据代码的上下文所能推导出来的类型信息把类型检查尽量优化到更简单的形式,甚至直接就得出结论。

对这部分细节感兴趣的同学请单独联系我或者另外开帖讨论吧。

下面两个patch是我对HotSpot VM在子类型检查相关方面做的小优化,两个都在JDK7u40/JDK8里发布:

[#JDK-7170463] C2 should recognize “obj.getClass() == A.class” code pattern
Request for review (S): C2 should recognize “obj.getClass() == A.class” code pattern
hg.openjdk.java.net/hsx

[#JDK-7171890] C1: add Class.isInstance intrinsic
Request for review (M): 7171890: C1: add Class.isInstance intrinsic
hsx/hotspot-comp/hotspot: 8f37087fc13f
lambda/lambda/hotspot: e1635876b206

举个例子,经过JDK-7170463的patch之后,HotSpot VM的C2会把下面这样的代码:

if (obj.getClass() == A.class) {
  boolean isInst = obj instanceof A;
}

优化为:

if (obj.getClass() == A.class) {
  boolean isInst = true;
}

那个instanceof运算就直接被常量折叠掉了。楼主可以看看,当时面试你的面试官是否了解到这种细节了,而他又是否真的要在面试种考察这种细节。

==============================================================

楼主的问题原本有提到 BytecodeInstanceOf.java 。它是 Serviceability Agent 的一部分,不是 HotSpot VM 内的逻辑。关于 Serviceability Agent 请从这帖里的链接找资料来读读:记GreenTeaJUG第二次线下活动(杭州)

SA是HotSpot VM自带的一个用来调试、诊断HotSpot VM运行状态的工具。它是一个“进程外”条调试器,也就是说假如我们要调试的HotSpot VM运行在进程A里,那么SA要运行在另一个进程B里去调试进程A。这样做的好处是SA与被调试进程不会相互干扰,于是调试就可以更干净的进行;就算SA自己崩溃了也(通常)不会连带把被调试进程也弄崩溃。

SA在HotSpot VM内部的C++代码里嵌有一小块,主要是把HotSpot的C++类的符号信息记录下来;SA的主体则是用Java来实现的,把可调试的HotSpot里C++的类用Java再做一层皮。楼主看到的BytecodeInstanceOf类就是这样的一层皮,它并不包含HotSpot的执行逻辑,纯粹是为调试用的。

直接放些外部参考资料链接方便大家找:

The HotSpot™ Serviceability Agent: An Out-of-Process High-Level Debugger for a Java™ Virtual Machine, USENIX JVM ’01
这篇是描述 HotSpot Serviceability Agent 的原始论文,要了解 SA 的背景必读。

HotSpot source: Serviceability Agent (A. Sundararajan’s Weblog)
提到了hotspot/agent目录里的代码都是 Serviceability Agent 的实现。注意 SA 并不是 HotSpot VM 运行时必要的组成部分。

Serviceability in HotSpot, OpenJDK
这是OpenJDK馆网上的相关文档页面。

 

 

一次性搞清楚equals和hashCode

zhouchong阅读(68)评论(0)

前言

在程序设计中,有很多的“公约”,遵守约定去实现你的代码,会让你避开很多坑,这些公约是前人总结出来的设计规范。

Object类是Java中的万类之祖,其中,equals和hashCode是2个非常重要的方法。

这2个方法总是被人放在一起讨论。最近在看集合框架,为了打基础,就决定把一些细枝末节清理掉。一次性搞清楚!

下面开始剖析。

 

public boolean equals(Object obj)

 

Object类中默认的实现方式是  :   return this == obj  。那就是说,只有this 和 obj引用同一个对象,才会返回true。

而我们往往需要用equals来判断 2个对象是否等价,而非验证他们的唯一性。这样我们在实现自己的类时,就要重写equals.

 

按照约定,equals要满足以下规则。

自反性:  x.equals(x) 一定是true

对null:  x.equals(null) 一定是false

对称性:  x.equals(y)  和  y.equals(x)结果一致

传递性:  a 和 b equals , b 和 c  equals,那么 a 和 c也一定equals。

一致性:  在某个运行时期间,2个对象的状态的改变不会不影响equals的决策结果,那么,在这个运行时期间,无论调用多少次equals,都返回相同的结果。

 

一个例子

1 class Test

2 {

3     private int num;

4     private String data;

5

6     public boolean equals(Object obj)

7     {

8         if (this == obj)

9             return true;

10

11         if ((obj == null) || (obj.getClass() != this.getClass()))

12             return false;
//能执行到这里,说明obj和this同类且非null。

Test test = (Test) obj;

return num == test.num&& (data == test.data || (data != null && data.equals(test.data)));

}

public int hashCode()

{

//重写equals,也必须重写hashCode。具体后面介绍。
}

 

}

 

 

 

equals编写指导

Test类对象有2个字段,num和data,这2个字段代表了对象的状态,他们也用在equals方法中作为评判的依据。

在第8行,传入的比较对象的引用和this做比较,这样做是为了 save time ,节约执行时间,如果this 和 obj是 对同一个堆对象的引用,那么,他们一定是qeuals 的。

接着,判断obj是不是为null,如果为null,一定不equals,因为既然当前对象this能调用equals方法,那么它一定不是null,非null 和 null当然不等价。

然后,比较2个对象的运行时类,是否为同一个类。不是同一个类,则不equals。getClass返回的是 this 和obj的运行时类的引用。如果他们属于同一个类,则返回的是同一个运行时类的引用。注意,一个类也是一个对象。

1、有些程序员使用下面的第二种写法替代第一种比较运行时类的写法。应该避免这样做。

 

if((obj == null) || (obj.getClass() != this.getClass()))

return false;

 

 

if(!(obj instanceof Test))

return false; // avoid 避免!

 

 

它违反了公约中的对称原则。
例如:假设Dog扩展了Aminal类。

dog instanceof Animal      得到true

animal instanceof Dog      得到false

 

这就会导致

animal.equls(dog) 返回true
dog.equals(animal) 返回false

仅当Test类没有子类的时候,这样做才能保证是正确的。

 
2、按照第一种方法实现,那么equals只能比较同一个类的对象,不同类对象永远是false。但这并不是强制要求的。一般我们也很少需要在不同的类之间使用equals。

3、在具体比较对象的字段的时候,对于基本值类型的字段,直接用 == 来比较(注意浮点数的比较,这是一个坑)对于引用类型的字段,你可以调用他们的equals,当然,你也需要处理字段为null 的情况。对于浮点数的比较,我在看Arrays.binarySearch的源代码时,发现了如下对于浮点数的比较的技巧:

if ( Double.doubleToLongBits(d1) == Double.doubleToLongBits(d2) ) //d1 和 d2 是double类型

 

if(  Float.floatToIntBits(f1) == Float.floatToIntBits(f2)  )      //f1 和 f2 是d2是float类型

 

 

4、并不总是要将对象的所有字段来作为equals 的评判依据,那取决于你的业务要求。比如你要做一个家电功率统计系统,如果2个家电的功率一样,那就有足够的依据认为这2个家电对象等价了,至少在你这个业务逻辑背景下是等价的,并不关心他们的价钱啊,品牌啊,大小等其他参数。

5、最后需要注意的是,equals 方法的参数类型是Object,不要写错!

 

 

 

 

public int hashCode()
这个方法返回对象的散列码,返回值是int类型的散列码。
对象的散列码是为了更好的支持基于哈希机制的Java集合类,例如 Hashtable, HashMap, HashSet 等。

关于hashCode方法,一致的约定是:

重写了equals方法的对象必须同时重写hashCode()方法。

如果2个对象通过equals调用后返回是true,那么这个2个对象的hashCode方法也必须返回同样的int型散列码

如果2个对象通过equals返回false,他们的hashCode返回的值允许相同。(然而,程序员必须意识到,hashCode返回独一无二的散列码,会让存储这个对象的hashtables更好地工作。)

 

在上面的例子中,Test类对象有2个字段,num和data,这2个字段代表了对象的状态,他们也用在equals方法中作为评判的依据。那么, 在hashCode方法中,这2个字段也要参与hash值的运算,作为hash运算的中间参数。这点很关键,这是为了遵守:2个对象equals,那么 hashCode一定相同规则。

也是说,参与equals函数的字段,也必须都参与hashCode 的计算。

 
合乎情理的是:同一个类中的不同对象返回不同的散列码。典型的方式就是根据对象的地址来转换为此对象的散列码,但是这种方式对于Java来说并不是唯一的要求的
的实现方式。通常也不是最好的实现方式。

相比 于 equals公认实现约定,hashCode的公约要求是很容易理解的。有2个重点是hashCode方法必须遵守的。约定的第3点,其实就是第2点的
细化,下面我们就来看看对hashCode方法的一致约定要求。
第一:在某个运行时期间,只要对象的(字段的)变化不会影响equals方法的决策结果,那么,在这个期间,无论调用多少次hashCode,都必须返回同一个散列码。

第二:通过equals调用返回true 的2个对象的hashCode一定一样。

第三:通过equasl返回false 的2个对象的散列码不需要不同,也就是他们的hashCode方法的返回值允许出现相同的情况。

总结一句话:等价的(调用equals返回true)对象必须产生相同的散列码。不等价的对象,不要求产生的散列码不相同。

 

 

 

hashCode编写指导

 

在编写hashCode时,你需要考虑的是,最终的hash是个int值,而不能溢出。不同的对象的hash码应该尽量不同,避免hash冲突。

那么如果做到呢?下面是解决方案。

 

1、定义一个int类型的变量 hash,初始化为 7。

接下来让你认为重要的字段(equals中衡量相等的字段)参入散列运,算每一个重要字段都会产生一个hash分量,为最终的hash值做出贡献(影响)

 

运算方法参考表
重要字段var的类型 他生成的hash分量
byte, char, short , int (int)var
long  (int)(var ^ (var >>> 32))
boolean var?1:0
float  Float.floatToIntBits(var)
 double  long bits = Double.doubleToLongBits(var);
分量 = (int)(bits ^ (bits >>> 32));
 引用类型   (null == var ? 0 : var.hashCode())

 

 

 

最后把所有的分量都总和起来,注意并不是简单的相加。选择一个倍乘的数字31,参与计算。然后不断地递归计算,直到所有的字段都参与了。

int hash = 7;

 

hash = 31 * hash + 字段1贡献分量;

 

hash = 31 * hash + 字段2贡献分量;

 

…..

 

return hash;

 

关于 hashCode() 你需要了解的 3 件事

zhouchong阅读(67)评论(0)

在 Java 中,每一个对象都有一个容易理解但是仍然有时候被遗忘或者被误用的 hashCode 方法。这里有3件事情要时刻牢记以避免常见的陷阱。

一个对象的哈希码允许算法和数据结构将对象放入隔间,就象打印机类型案件中的字母类型。打印机将所有的“A”类型放到一个房间,它寻找这个“A”的时候就只需要在这个房间进行寻找。这种简单的系统让他在未排序的抽屉中寻找类型的时候更快。这也是基于哈希的集合的想法,例如 HashMap 和 HashSet。

为了使你的类与其他基于哈希的集合或其他依赖哈希码的算法一起正常工作,所有 hashCode  的实现必须遵守一个简单的契约。

hashCode 契约

这个契约在 hashCode 方法的 JavaDoc 中进行了阐述。它可以大致的归纳为下面几点:

  1. 在一个运行的进程中,相等的对象必须要有相同的哈希码
  2. 请注意这并不意味着以下常见的误解:
  3. 不相等的对象一定有着不同的哈希码——错!
  4. 有同一个哈希值的对象一定相等——错!

这个契约允许不同的对象共享相同的哈希码,例如根据上图中的的描述,“A”和“μ”对象的哈希值就一样。在数学术语中,从对象到哈希码的映射不一定为内射或者双射。这是显而易见的,因为可能的不同对象的数量经常比可能的哈希吗的数量 (2^32)更大。

编辑:在早期的版本中,我错误的认为哈希码的映射一定属于内射,但是不一定是双射,这显然是错的。感谢 Lucian 指出这个错误。

这个约定直接导致了第一个规则:

  1. 无论你何时实现 equals 方法,你必须同时实现 hashCode 方法

如果你不这样做,你将会带来损坏的对象。为什么?一个对象的 hashCode 方法需要与 equals 方法考虑同样的域。通过重写 equals 方法,你将申明一些对象与其他对象相等,但是原始的 hashCode 方法将所有的对象看做是不同的。所以你将会有不同哈希码的相同对象。例如,在 HashMap 中调用 contains 方法将会返回 false,即使这个对象已经被添加。
怎样写一个好的 hashCode 方法不在这篇文章的范围内,在 Joshua Bloch 很受欢迎的书《Effective Java》中被很好的阐释,Java 开发人员的书架上不应缺少这本书。

【你的项目需要专业意见吗?我们的 Developer Support 会为你解决问题。|在我们的 Software Craftsmanship 页面上寻找关于怎样编写简洁代码的更多提示。】

为了安全起见,让 eclipse IDE 一次产生 equals 和 hashCode 方法: Source > Generate hashCode() and equals()….

为了保护你自己,你还可以配置 Eclipse 来检测实现了 equals 方法但是没有实现 hashCode 方法的类,并显示错误。不幸的是,此选项默认是指为“忽略”:Preferences > Java >Compiler > Errors/Warnings,然后用快速筛选器来搜索“hashcode”:

更新:正如 laurent 指出,equalsverifier 是一个强大的工具,它用来验证 hashCode 和 equals 方法的约定。您应该考虑在您的单元测试中使用它。

哈希码冲突

任何时候,两个不同对象有相同的哈希码,我们称之为冲突。冲突不要紧,它只是意味着有多个对象在同一个空间里,所以 HashMap 会再检查一遍来找正确的对象。大量的冲突将会降低系统的性能,但是它们不会导致错误的结果。

但是如果你误认为哈希码是一个对象唯一的句柄,例如使用它作为Map的key,你有时会得到错误的对象。因为虽然冲突很罕见,但他们是不可避免的。例如,字符“Aa”和“BB”产生相同的哈希码:2112。因此:

  1. 永远不要把哈希码误用作一个key

你可能会反对,不像打印机的类型例子,在 Java 中,有 4,294,967,296 的空间(2^32 个可能的整型值)。40亿的插槽,发生冲突似乎是极不可能的对吗?

事实证明它不是不太可能。这是令人惊讶的冲突:请想象一下在一个房间里有 23 个随机的人。你觉得两个人是同一天生日的几率有多大 ?很低,因为一年有 365 天吗?事实上,几率是 50% 左右!50 个人是保守的估计。这个现象称为生日悖论。应用到哈希码,这意味着在 77163 个不同的对象中,有 50% 的可能性发生冲突–假设你有一个理想的哈希的函数,均匀地把对象分布在所有可用的空间里面。

例如:

安然公司的电子邮件集包含 520,924 封电子邮件。计算电子邮件内容字符串的哈希码时,我发现 50 对(甚至是 2 个三元组)不同的电子邮件有着相同的哈希码。对于五十万个字符串,这是一个很好的结果。但是这里的信息是:如果你有很多数据元素,冲突就会发生。如果你正在使用哈希码作为 key,你不会立即注意到你的错误。但是少数人会收到错误的邮件。

哈希码可变

最后,在哈希码的契约中,有一个很重要的细节是相当让人吃惊的:hashCode  并不保证在不同的应用执行中得到相同的结果。让我们看一看 Java 文档:

在一次 Java 应用的执行中,对于同一个对象,hashCode 方法必须始终返回相同的整数,但这整数不反映对象是否被修改(equals 比较)的信息。同一个应用的不同执行,该整数不必保持一致。

事实上,这是不常见的,一些类库中的类甚至指定它们用于计算哈希码的精确公式(例如字符串)。对于这些类,哈希码总是会相同。虽然大部分的哈希码的实现提供稳定的值,但你不能依赖于这一点。正如这篇文章指出的,有些类库在不同进程中会返回不同的哈希值,这有的时候会让人困惑。谷歌的 Protocol Buffers 就是一个例子。

因此,你不应该在分布式应用程序中使用哈希码。一个远程对象可能与本地对象有不同的哈希码,即使这两个对象是相等的。

  1. 在分布式应用中不要使用哈希码

此外,你应该意识到从一个版本到另一个版本哈希码的功能实现可能会更改。因此您的代码不应该依赖于任何特定的哈希码值。例如,你不应该使用哈希码来持久化状态。下次你运行程序的时候,“相同”对象的哈希码可能不同。
最好的建议可能是:完全不使用哈希码,除非你自己创造了基于哈希的算法。

一种替代方法:SHA1

你可能知道加密的哈希码 SHA1 有时被用来标识对象(例如,git这样做)。这也是不安全吗?不。SHA1 使用 160 位密钥,这使得冲突几乎是不可能的。即使有很多对象,在这个空间发生冲突的几率远远低于一颗流星撞到你正在执行程序的电脑的几率。这篇文章对冲突的概率作了很好的概述。

关于哈希码应该还有其他可谈的,但这些看起来是最重要的。如果我有什么遗漏,欢迎告诉我。

 

hashCode对于equals的作用是什么

zhouchong阅读(72)评论(0)

简单的一句话结论就是:保证你定义的“equal”的对象拥有相同的hash code。

 

equals()方法的意义比较简单就不赘言了,hashCode()的主要作用是为Hash容器提供快速索引。

如果翻阅JDK HashMap,你会发现hashCode首先被用于查找(indexFor)具有潜在相同hashCode的一个/一些对象。为什么是“潜在”?这与HashMap的实现方式有关,不同hashCode的对象仍可能被映射到同一条“拉链”上。而这些对象尽管本质上不是相同的对象(!equals),这就是所谓的碰撞(hash collision),因此如何最终确定需要操作的对象不单取决于hashCode()相同,同时取决于equals()为真。

在正常情况下,equals()较hashCode()的限定更强,体现在:

1)两个对象equals()为真,则它们的hashCode() 一定相同
2)两个对象hashCode()相同,equals()不一定为真

这两个Object方法如果没有很好的定义,可能会产生使用者不希望看到的效果。

因此:

1)实现自定义类的equlas(),一般如题主图示般进行即可,当然有特殊需求除外;
2)实现hashCode(),原则如本答案第一句话所示,并尽量使用对象自有特性作为生成因子以减小冲突的概率。

 

java中hashcode()方法有什么作用呢?最好举个例子啊!

zhouchong阅读(57)评论(0)

hashcode这个方法是用来鉴定2个对象是否相等的。
那你会说,不是还有equals这个方法吗?

不错,这2个方法都是用来判断2个对象是否相等的。但是他们是有区别的。

一般来讲,equals这个方法是给用户调用的,如果你想判断2个对象是否相等,你可以重写equals方法,然后在代码中调用,就可以判断他们是否相等了。简单来讲,equals方法主要是用来判断从表面上看或者从内容上看,2个对象是不是相等。举个例子,有个学生类,属性只有姓名和性别,那么我们可以认为只要姓名和性别相等,那么就说这2个对象是相等的。

hashcode方法一般用户不会去调用,比如在hashmap中,由于key是不可以重复的,他在判断key是不是重复的时候就判断了hashcode这个方法,而且也用到了equals方法。这里不可以重复是说equals和hashcode只要有一个不等就可以了!所以简单来讲,hashcode相当于是一个对象的编码,就好像文件中的md5,他和equals不同就在于他返回的是int型的,比较起来不直观。我们一般在覆盖equals的同时也要覆盖hashcode,让他们的逻辑一致。举个例子,还是刚刚的例子,如果姓名和性别相等就算2个对象相等的话,那么hashcode的方法也要返回姓名的hashcode值加上性别的hashcode值,这样从逻辑上,他们就一致了。

要从物理上判断2个对象是否相等,用==就可以了。

 

Java的自动拆装箱

zhouchong阅读(59)评论(0)

什么是自动装箱拆箱

定义:能够使基本类型与其对应的包装器类型之间自动相互转换。对应关系如下:

<span style=”font-size:14px;”>
byte <–> Byte
short <–> Short
int <–> Integer
long <–> Long
float <–> Float
double <–> Double
boolean <–> Boolean
char <–> Character
</span>

基本数据类型的自动装箱(autoboxing)、拆箱(unboxing)是自J2SE 5.0开始提供的功能。

一般我们要创建一个类的对象实例的时候,我们会这样:

 Class a = new Class(parameter);

 当我们创建一个Integer对象时,却可以这样:

 Integer i = 100; (注意:不是 int i = 100; )

实际上,执行上面那句代码的时候,系统为我们执行了:Integer i = Integer.valueOf(100); (感谢@黑面馒头 和 @MayDayIT 的提醒)

此即基本数据类型的自动装箱功能。

基本数据类型与对象的差别 

基本数据类型不是对象,也就是使用int、double、boolean等定义的变量、常量。

基本数据类型没有可调用的方法。

eg:  int t = 1;     t.  后面是没有方法滴。

 Integer t =1; t.  后面就有很多方法可让你调用了。

什么时候自动装箱

例如:Integer i = 100;

相当于编译器自动为您作以下的语法编译:Integer i = Integer.valueOf(100);

什么时候自动拆箱

自动拆箱(unboxing),也就是将对象中的基本数据从对象中自动取出。如下可实现自动拆箱:

Integer i = 10; //装箱
int t = i; //拆箱,实际上执行了 int t = i.intValue();

在进行运算时,也可以进行拆箱。

Integer i = 10;
System.out.println(i++);

自动拆装箱原理?

需要注意的是,自动拆装箱不是虚拟机完成的,这个过程实际上是由编译器完成的,当编译器对 .Java 源代码进行编译时,如果发现你没有进行拆箱,那么编译器来来帮你拆;如果你没有装箱,那么编译器来帮你装,而不是由虚拟机完成的。这个原理我们可以对代码进行反编译来解释,如下。

自动拆装箱举例与反编译。

还是以int 和Integer 类型来举例,.java源代码编写如下:

<span style=”font-size:14px;”>

public class Demo1 {

// 自动拆箱

@Test

public void method1() {

Integer i = new Integer(100);

int a = i;

}

// 自动装箱

@Test

public void method2() {

Integer i = 100;

}

}

</span>

对代码进行反编译(编译后的字节码文件才是被虚拟机所执行的,对字节码文件进行反编译就是得到我们能看懂的虚拟机真正执行的内容),得到反编译文件内容为:

<span style=”font-size:14px;”>

public class Demo1

{

@Test

public void method1()

{

Integer i = new Integer(100);

int a = i.intValue();

}

 

@Test

public void method2()

{

Integer i = Integer.valueOf(100);

}

}

 

</span>

发现:自动拆箱底层实际是用了Integer 对象的“.intValue()”方法,此方法返回一个int 类型的值;自动装箱实际是用了Integer 类的“.valueOf()” 方法,此方法返回一个Integer类型对象。

自动拆装箱方便了程序的编写,但是在方便的同时,也为我们隐藏了一些细节,要想了解这些细节,就需要对源代码进行探讨,希望大家也都不要满足于会使用即可,原理层次的东西还是要了解的。


String 的拆箱装箱

先看个例子:

String str1 =”abc”;
String str2 =”abc”;
System.out.println(str2==str1); //输出为 true
System.out.println(str2.equals(str1)); //输出为 true

String str3 =new String(“abc”);
String str4 =new String(“abc”);
System.out.println(str3==str4); //输出为 false
System.out.println(str3.equals(str4)); //输出为 true

这个怎么解释呢?貌似看不出什么。那再看个例子。

String d =”2″;
String e =”23″;
e = e.substring(0, 1);
System.out.println(e.equals(d)); //输出为 true
System.out.println(e==d); //输出为 false

第二个例子中,e的初始值与d并不同,因此e与d是各自创建了个对象,(e==d)为false 。
同理可知,第一个例子中的str3与str4也是各自new了个对象,而str1与str2却是引用了同一个对象。

Integer的自动装箱

//在-128~127 之外的数
Integer i1 =200;
Integer i2 =200;
System.out.println(“i1==i2: “+(i1==i2));
// 在-128~127 之内的数
Integer i3 =100;
Integer i4 =100;
System.out.println(“i3==i4: “+(i3==i4));

输出的结果是:
    i1==i2: false
    i3==i4: true

说明:

equals() 比较的是两个对象的值(内容)是否相同。

“==” 比较的是两个对象的引用(内存地址)是否相同,也用来比较两个基本数据类型的变量值是否相等。

 

前面说过,int 的自动装箱,是系统执行了 Integer.valueOf(int i),先看看Integer.java的源码:

public static Integer valueOf(int i) {
    if(i >= -128 && i <= IntegerCache.high)  // 没有设置的话,IngegerCache.high 默认是127
        return IntegerCache.cache[i + 128];
    else
        return new Integer(i);
}

对于–128到127(默认是127)之间的值,Integer.valueOf(int i) 返回的是缓存的Integer对象(并不是新建对象)

所以范例中,i3 与 i4实际上是指向同一个对象。

而其他值,执行Integer.valueOf(int i) 返回的是一个新建的 Integer对象,所以范例中,i1与i2 指向的是不同的对象。

当然,当不使用自动装箱功能的时候,情况与普通类对象一样,请看下例:

1 Integer i3 =new Integer(100);
2 Integer i4 =new Integer(100);
3 System.out.println(“i3==i4: “+(i3==i4));//显示false

Java包package

zhouchong阅读(64)评论(0)

Java包package:

为便于管理大型软件系统中数目众多的类,解决类的命名和冲突问题,Java引入包package机制,提供类的多重类命名空间。
package语句作为Java源文件的第一条语句,指明该文件中定义的类所在的包。(若缺省该语句,则指定为无名包)
Java编译器把包对应于文件系统的目录管理,package语句中,用‘.’来指明包(目录)的层次。如package com.sxt那么该文件中所有的类位于\com\sxt目录下。

方法就是一段代码,你调用他他就执行。可以有多个线程同时调用同一个方法。

动态绑定和静态绑定

zhouchong阅读(62)评论(0)

动态绑定和静态绑定:
动态绑定是指在执行期间(而非编译器)判断所引用对象的实际类型,根据其实际的类型调用其相应的方法。

 

java.lang包里的类不需要引入,可以直接用。

GC算法简介

zhouchong阅读(69)评论(0)

概述

在开始之前,需要明确的一点是,这里谈到的垃圾回收算法针对的是JVM的堆内存,栈基本上不存在垃圾回收方面的困扰。

标记-清除算法(Mark-Sweep)

最基础的收集算法是“标记-清除”(Mark-Sweep)算法,如同它的名字一样,算法分

为“标记”和“清除”两个阶段。首先标记出所有需要回收的对象,在标记完成后统一回收所有被标记的对象。之所以说它是最基础的收集算法,是因为后续的收集算法都是基于这种思路并对其不足进行改进而得到的。

它的主要不足有两个:一个是效率问题,标记和清除两个过程的效率都不高;另一个是空间问题,标记清除之后会产生大量不连续的内存碎片,空间碎片太多可能会导致以后在程序运行过程中需要分配较大对象时,无法找到足够的连续内存而不得不提前触发另一次垃圾收集动作。

我们在程序(程序也就是指我们运行在JVM上的JAVA程序)运行期间如果想进行垃圾回收,就必须让GC线程与程序当中的线程互相配合,才能在不影响程序运行的前提下,顺利的将垃圾进行回收

为了达到这个目的,标记/清除算法就应运而生了。它的做法是当堆中的有效内存空间(available memory)被耗尽的时候,就会停止整个程序(也被成为stop the world),然后进行两项工作,第一项则是标记,第二项则是清除

 标记:标记的过程其实就是,遍历所有的GC Roots,然后将所有GC Roots可达的对象标记为存活的对象。

 清除:清除的过程将遍历堆中所有的对象,将没有标记的对象全部清除掉。

就是当程序运行期间,若可以使用的内存被耗尽的时候,GC线程就会被触发并将程序暂停,随后将依旧存活的对象标记一遍,最终再将堆中所有没被标记的对象全部清除掉,接下来便让程序恢复运行

图示详解

 

这张图代表的是程序运行期间所有对象的状态,它们的标志位全部是0(也就是未标记,以下默认0就是未标记,1为已标记),假设这会儿有效内存空间耗尽了,JVM将会停止应用程序的运行并开启GC线程,然后开始进行标记工作,按照根搜索算法,标记完以后,对象的状态如下图。

可以看到,按照根搜索算法,所有从root对象可达的对象就被标记为了存活的对象,此时已经完成了第一阶段标记。接下来,就要执行第二阶段清除了,那么清除完以后,剩下的对象以及对象的状态如下图所示。

可以看到,没有被标记的对象将会回收清除掉,而被标记的对象将会留下,并且会将标记位重新归0。接下来就不用说了,唤醒停止的程序线程,让程序继续运行即可。

         其实这一过程并不复杂,甚至可以说非常简单,各位说对吗。不过其中有一点值得LZ一提,就是为什么非要停止程序的运行呢?

这个其实也不难理解,LZ举个最简单的例子,假设我们的程序与GC线程是一起运行的,各位试想这样一种场景。

假设我们刚标记完图中最右边的那个对象,暂且记为A,结果此时在程序当中又new了一个新对象B,且A对象可以到达B对象。但是由于此时A对象已经标记结束,B对象此时的标记位依然是0,因为它错过了标记阶段。因此当接下来轮到清除阶段的时候,新对象B将会被苦逼的清除掉。如此一来,不难想象结果,GC线程将会导致程序无法正常工作。

         上面的结果当然令人无法接受,我们刚new了一个对象,结果经过一次GC,忽然变成null了,这还怎么玩?

到此为止,标记/清除算法LZ已经介绍完了,下面我们来看下它的缺点,其实了解完它的算法原理,它的缺点就很好理解了。

1、首先,它的缺点就是效率比较低(递归与全堆对象遍历),而且在进行GC的时候,需要停止应用程序,这会导致用户体验非常差劲,尤其对于交互式的应用程序来说简直是无法接受。试想一下,如果你玩一个网站,这个网站一个小时就挂五分钟,你还玩吗?

2、第二点主要的缺点,则是这种方式清理出来的空闲内存是不连续的,这点不难理解,我们的死亡对象都是随即的出现在内存的各个角落的,现在把它们清除之后,内存的布局自然会乱七八糟。而为了应付这一点,JVM就不得不维持一个内存的空闲列表,这又是一种开销。而且在分配数组对象的时候,寻找连续的内存空间会不太好找。

 

复制算法

为了解决效率问题,一种称为“复制”(Copying)的收集算法出现了,它将可用内存按容

量划分为大小相等的两块,每次只使用其中的一块。 当这一块的内存用完了,就将还存活着的对象复制到另外一块上面,然后再把已使用过的内存空间一次清理掉。 这样使得每次都是对整个半区进行内存回收,内存分配时也就不用考虑内存碎片等复杂情况,只要移动堆顶指针,按顺序分配内存即可,实现简单,运行高效。 只是这种算法的代价是将内存缩小为了原来的一半,未免太高了一点。

现在的商业虚拟机都采用这种收集算法来回收新生代,IBM公司的专门研究表明,新生代中的对象98%是“朝生夕死”的,所以并不需要按照1:1的比例来划分内存空间,而是将内存分为一块较大的Eden空间和两块较小的Survivor空间,每次使用Eden和其中一块Survivor[1]。当回收时,将Eden和Survivor中还存活着的对象一次性地复制到另外一块Survivor空间上,最后清理掉Eden和刚才用过的Survivor空间。 HotSpot虚拟机默认Eden和Survivor的大小比例是8:1,也就是每次新生代中可用内存空间为整个新生代容量的90%(80%+10%),只有10%的内存会被“浪费”。 当然,98%的对象可回收只是一般场景下的数据,我们没有办法保证每次回收都只有不多于10%的对象存活,当Survivor空间不够用时,需要依赖其他内存(这里指老年代)进行分配担保(Handle Promotion)。

内存的分配担保就好比我们去银行借款,如果我们信誉很好,在98%的情况下都能按时偿还,于是银行可能会默认我们下一次也能按时按量地偿还贷款,只需要有一个担保人能保证如果我不能还款时,可以从他的账户扣钱,那银行就认为没有风险了。 内存的分配担保也一样,如果另外一块Survivor空间没有足够空间存放上一次新生代收集下来的存活对象时,这些对象将直接通过分配担保机制进入老年代。

我们首先一起来看一下复制算法的做法,复制算法将内存划分为两个区间,在任意时间点,所有动态分配的对象都只能分配在其中一个区间(称为活动区间),而另外一个区间(称为空闲区间)则是空闲的

当有效内存空间耗尽时,JVM将暂停程序运行,开启复制算法GC线程。接下来GC线程会将活动区间内的存活对象,全部复制到空闲区间,且严格按照内存地址依次排列,与此同时,GC线程将更新存活对象的内存引用地址指向新的内存地址

此时,空闲区间已经与活动区间交换,而垃圾对象现在已经全部留在了原来的活动区间,也就是现在的空闲区间。事实上,在活动区间转换为空间区间的同时,垃圾对象已经被一次性全部回收。

         听起来复杂吗?

其实一点也不复杂,有了上一章的基础,相信各位理解这个算法不会费太多力气。LZ给各位绘制一幅图来说明问题,如下所示。

其实这个图依然是上一章的例子,只不过此时内存被复制算法分成了两部分,下面我们看下当复制算法的GC线程处理之后,两个区域会变成什么样子,如下所示。

可以看到,1和4号对象被清除了,而2、3、5、6号对象则是规则的排列在刚才的空闲区间,也就是现在的活动区间之内。此时左半部分已经变成了空闲区间,不难想象,在下一次GC之后,左边将会再次变成活动区间。

       很明显,复制算法弥补了标记/清除算法中,内存布局混乱的缺点。不过与此同时,它的缺点也是相当明显的。

1、它浪费了一半的内存,这太要命了。

2、如果对象的存活率很高,我们可以极端一点,假设是100%存活,那么我们需要将所有对象都复制一遍,并将所有引用地址重置一遍。复制这一工作所花费的时间,在对象存活率达到一定程度时,将会变的不可忽视

 所以从以上描述不难看出,复制算法要想使用,最起码对象的存活率要非常低才行,而且最重要的是,我们必须要克服50%内存的浪费

标记/整理算法

复制收集算法在对象存活率较高时就要进行较多的复制操作,效率将会变低。 更关键的是,如果不想浪费50%的空间,就需要有额外的空间进行分配担保,以应对被使用的内存中所有对象都100%存活的极端情况,所以在老年代一般不能直接选用这种算法。

根据老年代的特点,有人提出了另外一种“标记-整理”(Mark-Compact)算法,标记过程仍然与“标记-清除”算法一样,但后续步骤不是直接对可回收对象进行清理,而是让所有存活的对象都向一端移动,然后直接清理掉端边界以外的内存

 

 标记/整理算法与标记/清除算法非常相似,它也是分为两个阶段:标记和整理。下面LZ给各位介绍一下这两个阶段都做了什么。

标记:它的第一个阶段与标记/清除算法是一模一样的,均是遍历GC Roots,然后将存活的对象标记。

整理:移动所有存活的对象,且按照内存地址次序依次排列,然后将末端内存地址以后的内存全部回收。因此,第二阶段才称为整理阶段。

它GC前后的图示与复制算法的图非常相似,只不过没有了活动区间和空闲区间的区别,而过程又与标记/清除算法非常相似,我们来看GC前内存中对象的状态与布局,如下图所示。

这张图其实与标记/清楚算法一模一样,只是LZ为了方便表示内存规则的连续排列,加了一个矩形表示内存区域。倘若此时GC线程开始工作,那么紧接着开始的就是标记阶段了。此阶段与标记/清除算法的标记阶段是一样一样的,我们看标记阶段过后对象的状态,如下图。

没什么可解释的,接下来,便应该是整理阶段了。我们来看当整理阶段处理完以后,内存的布局是如何的,如下图。

可以看到,标记的存活对象将会被整理,按照内存地址依次排列,而未被标记的内存会被清理掉。如此一来,当我们需要给新对象分配内存时,JVM只需要持有一个内存的起始地址即可,这比维护一个空闲列表显然少了许多开销。

不难看出,标记/整理算法不仅可以弥补标记/清除算法当中,内存区域分散的缺点,也消除了复制算法当中,内存减半的高额代价,可谓是一举两得,一箭双雕,一石两鸟,一。。。。一女两男?

不过任何算法都会有其缺点,标记/整理算法唯一的缺点就是效率也不高,不仅要标记所有存活对象,还要整理所有存活对象的引用地址。从效率上来说,标记/整理算法要低于复制算法。

 

算法总结

这里LZ给各位总结一下三个算法的共同点以及它们各自的优势劣势,让各位对比一下,想必会更加清晰。

它们的共同点主要有以下两点。

1、三个算法都基于根搜索算法去判断一个对象是否应该被回收,而支撑根搜索算法可以正常工作的理论依据,就是语法中变量作用域的相关内容。因此,要想防止内存泄露,最根本的办法就是掌握好变量作用域,而不应该使用前面内存管理杂谈一章中所提到的C/C++式内存管理方式。

       2、在GC线程开启时,或者说GC过程开始时,它们都要暂停应用程序(stop the world)。

它们的区别LZ按照下面几点来给各位展示。(>表示前者要优于后者,=表示两者效果一样)

       效率:复制算法>标记/整理算法>标记/清除算法(此处的效率只是简单的对比时间复杂度,实际情况不一定如此)。

       内存整齐度:复制算法=标记/整理算法>标记/清除算法。

       内存利用率:标记/整理算法=标记/清除算法>复制算法。

可以看到标记/清除算法是比较落后的算法了,但是后两种算法却是在此基础上建立的,俗话说“吃水不忘挖井人”,因此各位也莫要忘记了标记/清除这一算法前辈。而且,在某些时候,标记/清除也会有用武之地。

结束语

到此我们已经将三个算法了解清楚了,可以看出,效率上来说,复制算法是当之无愧的老大,但是却浪费了太多内存,而为了尽量兼顾上面所提到的三个指标,标记/整理算法相对来说更平滑一些,但效率上依然不尽如人意,它比复制算法多了一个标记的阶段,又比标记/清除多了一个整理内存的过程。

       难道就没有一种最优算法吗?

当然是没有的,这个世界是公平的,任何东西都有两面性,试想一下,你怎么可能找到一个又漂亮又勤快又有钱又通情达理,性格又合适,家境也合适,身高长相等等等等都合适的女人?就算你找到了,至少有一点这个女人也肯定不满足,那就是多半不会恰巧又爱上了与LZ相似的各位苦逼猿友们。你是不是想说你比LZ强太多了,那LZ只想对你说,高富帅是不会爬在电脑前看技术文章的,0.0。

       但是古人就是给力,古人说了,找媳妇不一定要找最好的,而是要找最合适的,听完这句话,瞬间感觉世界美好了许多。

算法也是一样的,没有最好的算法,只有最合适的算法

既然这三种算法都各有缺陷,高人们自然不会容许这种情况发生。因此,高人们提出可以根据对象的不同特性,使用不同的算法处理,类似于萝卜白菜各有所爱的原理。于是奇迹发生了,高人们终于找到了GC算法中的神级算法—–分代搜集算法

分代收集算法

当前商业虚拟机的垃圾收集都采用“分代收集”(Generational Collection)算法,这种算

法并没有什么新的思想,只是根据对象存活周期的不同将内存划分为几块。 一般是把Java堆

分为新生代和老年代,这样就可以根据各个年代的特点采用最适当的收集算法。 在新生代

中,每次垃圾收集时都发现有大批对象死去,只有少量存活,那就选用复制算法,只需要付

出少量存活对象的复制成本就可以完成收集。 而老年代中因为对象存活率高、 没有额外空间

对它进行分配担保,就必须使用“标记—清理”或者“标记—整理”算法来进行回收。

对象分类

上一章已经说过,分代搜集算法是针对对象的不同特性,而使用适合的算法,这里面并没有实际上的新算法产生。与其说分代搜集算法是第四个算法,不如说它是对前三个算法的实际应用

         首先我们来探讨一下对象的不同特性,接下来LZ和各位来一起给这些对象选择GC算法。

内存中的对象按照生命周期的长短大致可以分为三种,以下命名均为LZ个人的命名。

         1、夭折对象:朝生夕灭的对象,通俗点讲就是活不了多久就得死的对象。

             例子:某一个方法的局域变量、循环内的临时变量等等。

         2、老不死对象:这类对象一般活的比较久,岁数很大还不死,但归根结底,老不死对象也几乎早晚要死的,但也只是几乎而已。

             例子:缓存对象、数据库连接对象、单例对象(单例模式)等等。

         3、不灭对象:此类对象一般一旦出生就几乎不死了,它们几乎会一直永生不灭,记得,只是几乎不灭而已。

             例子:String池中的对象(享元模式)、加载过的类信息等等。

 

对象对应的内存区域

还记得前面介绍内存管理时,JVM对内存的划分吗?

我们将上面三种对象对应到内存区域当中,就是夭折对象和老不死对象都在JAVA堆,而不灭对象在方法区

之前的一章中我们就已经说过,对于JAVA堆,JVM规范要求必须实现GC,因而对于夭折对象和老不死对象来说,死几乎是必然的结局,但也只是几乎,还是难免会有一些对象会一直存活到应用结束。然而JVM规范对方法区的GC并不做要求,所以假设一个JVM实现没有对方法区实现GC,那么不灭对象就是真的不灭对象了。

         由于不灭对象的生命周期过长,因此分代搜集算法就是针对的JAVA堆而设计的,也就是针对夭折对象和老不死对象

JAVA堆的对象回收(夭折对象和老不死对象)

 

有了以上分析,我们来看看分代搜集算法如何处理JAVA堆的内存回收的,也就是夭折对象与老不死对象的回收。

夭折对象:这类对象朝生夕灭,存活时间短,还记得复制算法的使用要求吗?那就是对象存活率不能太高,因此夭折对象是最适合使用复制算法的

          小疑问:50%内存的浪费怎么办?

答疑:因为夭折对象一般存活率较低,因此可以不使用50%的内存作为空闲,一般的,使用两块10%的内存作为空闲和活动区间,而另外80%的内存,则是用来给新建对象分配内存的。一旦发生GC,将10%的活动区间与另外80%中存活的对象转移到10%的空闲区间,接下来,将之前90%的内存全部释放,以此类推。

          为了让各位更加清楚的看出来这个GC流程,LZ给出下面图示。

图中标注了三个区域中在各个阶段,各自内存的情况。相信看着图,它的GC流程已经不难理解了。

不过有两点LZ需要提一下,第一点是使用这样的方式,我们只浪费了10%的内存,这个是可以接受的,因为我们换来了内存的整齐排列与GC速度。第二点是,这个策略的前提是,每次存活的对象占用的内存不能超过这10%的大小,一旦超过,多出的对象将无法复制

为了解决上面的意外情况,也就是存活对象占用的内存太大时的情况,高手们将JAVA堆分成两部分来处理,上述三个区域则是第一部分,称为新生代或者年轻代。而余下的一部分,专门存放老不死对象的则称为年老代

         是不是很贴切的名字呢?下面我们看看老不死对象的处理方式。

老不死对象:这一类对象存活率非常高,因为它们大多是从新生代转过来的。就像人一样,活的年月久了,就变成老不死了。

通常情况下,以下两种情况发生的时候,对象会从新生代区域转到年老带区域。

1在新生代里的每一个对象,都会有一个年龄,当这些对象的年龄到达一定程度时(年龄就是熬过的GC次数,每次GC如果对象存活下来,则年龄加1),则会被转到年老代,而这个转入年老代的年龄值,一般在JVM中是可以设置的。

         2在新生代存活对象占用的内存超过10%时,则多余的对象会放入年老代。这种时候,年老代就是新生代的“备用仓库”。

针对老不死对象的特性,显然不再适合使用复制算法,因为它的存活率太高,而且不要忘了,如果年老代再使用复制算法,它可是没有备用仓库的。因此一般针对老不死对象只能采用标记/整理或者标记/清除算法

 

方法区的对象回收(不灭对象)

 

以上两种情况已经解决了GC的大部分问题,因为JAVA堆是GC的主要关注对象,而以上也已经包含了分代搜集算法的全部内容,接下来对于不灭对象的回收,已经不属于分代搜集算法的内容。

不灭对象存在于方法区,在我们常用的hotspot虚拟机(JDK默认的JVM)中,方法区也被亲切的称为永久代,又是一个很贴切的名字不是吗?

其实在很久很久以前,是不存在永久代的。当时永久代与年老代都存放在一起,里面包含了JAVA类的实例信息以及类信息。但是后来发现,对于类信息的卸载几乎很少发生,因此便将二者分离开来。幸运的是,这样做确实提高了不少性能。于是永久代便被拆分出来了。

         这一部分区域的GC与年老代采用相似的方法,由于都没有“备用仓库”,二者都是只能使用标记/清除和标记/整理算法。

 

回收的时机

 

 JVM在进行GC时,并非每次都对上面三个内存区域一起回收的,大部分时候回收的都是指新生代。因此GC按照回收的区域又分了两种类型,一种是普通GC(minor GC),一种是全局GC(major GC or Full GC),它们所针对的区域如下。

         普通GC(minor GC):只针对新生代区域的GC。

全局GC(major GC or Full GC):针对年老代的GC,偶尔伴随对新生代的GC以及对永久代的GC。

由于年老代与永久代相对来说GC效果不好,而且二者的内存使用增长速度也慢,因此一般情况下,需要经过好几次普通GC,才会触发一次全局GC。