JAVA代码执行过程
JAVA源码编译由三个过程组成:源码编译机制、类加载机制、类执行机制。
代码编译由JAVA源码编译器来完成,主要是将源码(java文件)编译成字节码文件(class文件)。字节码文件主要分为两部分:常量池和方法字节码。
类加载分七个阶段:加载--验证--准备--解析--初始化--使用--卸载。
加载阶段:
(1)通过一个类的全限定名来获取定义此类的二进制字节流。
(2)将这个字节流所代表的静态存储结构转化为方法区的运行时数据结构。
(3)在java堆中生成一个代表这个类的Class对象,作为访问方法区中这些数据的入口。
验证阶段:
为了确保Class文件中的字节流包含的信息符合当前虚拟机的要求,完成以下四个阶段的验证:文件格式的验证、元数据的验证、字节码验证和符号引用验证。
准备阶段:
准备阶段是正式为类变量分配内存并设置类变量初始值的阶段,这些内存都将在方法区中分配。
(1)注意这里并没有对实例变量进行内存分配,实例变量将会在对象实例化时随着对象一起分配在JAVA堆中。
(2)这里设置的初始值,通常是指数据类型的零值。
private static int a = 3;
这个类变量a在准备阶段后的值是0,将3赋值给变量a是发生在初始化阶段。
解析阶段:
解析阶段是指虚拟机将常量池中的符号引用替换为直接引用的过程。
初始化阶段:
初始化是类加载机制的最后一步,这个时候才正真开始执行类中定义的JAVA程序代码。在前面准备阶段,类变量已经赋过一次系统要求的初始值,在初始化阶段最重要的事情就是对类变量进行初始化,关注的重点是父子类之间各类资源初始化的顺序。
java类中对类变量指定初始值有两种方式:1、声明类变量时指定初始值;2、使用静态初始化块为类变量指定初始值。
JVM内存模型
运行时数据区通常包括这几个部分:程序计数器(Program Counter Register)、Java栈(VM Stack)、本地方法栈(Native Method Stack)、方法区(Method Area)、堆(Heap)。
程序计数器:
程序计数器是一块较小的内存空间,它可以看作是当前线程所执行的字节码的行号指示器。在虚拟机的概念模型里,字节码解释器工作时就是通过改变这个计数器的值来选取下一条需要执行的字节码指令,分支、循环、跳转、异常处理、线程恢复等基础功能都需要依赖这个计数器来完成。
JAVA虚拟机栈:
Java虚拟机栈也是线程私有的,它的生命周期与线程相同。虚拟机栈描述的是Java方法执行的内存模型,每个方法被执行的时候都会同时创建一个栈帧(Stack Frame)用于存储局部变量表、操作栈、动态链接、方法出口等信息。这块区域存在两种异常情况:如果线程请求的栈深度大于虚拟机允许的深度,抛出StackOverflowError异常;如果虚拟机栈可以动态扩展,且扩展时无法申请到足够的内存时会抛出OutOfMemoryError异常。
本地方法栈:
本地方法栈与虚拟机栈所发挥的作用是非常相似的,其区别不过是虚拟机栈为虚拟机执行Java方法(也就是字节码)服务,而本地方法栈则是为虚拟机使用到的Native方法服务。
JAVA堆:
Java堆(Java Heap)是被所有线程共享的一块区域,所有的对象实例以及数组都要在堆上分配。
Java堆是垃圾收集器管理的主要区域。从内存回收的角度看,由于现在收集器基本都是采用的分代收集算法,所以Java堆中还可以细分为:新生代和老年代;新生代再细致一点的有Eden空间、From Survivor空间、To Survivor空间等。
如果堆中没有内存完成实例分配,并且堆也无法再扩展时,将会抛出OutOfMemoryError异常。
方法区:
方法区是各个线程共享的内存区域,它用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译器编译后的代码等数据。这个区域的内存回收目标主要是针对常量池和对类型的卸载。当方法区无法满足内存分配需求时,将抛出OutOfMemoryError异常。
JVM垃圾回收算法
引用计数算法:
每个对象在创建时,就给这个对象绑定一个计数器。每当有一个引用指向该对象时,计数器加一;每当有一个指向它的引用被删除时,计数器减一。当没有引用指向该对象时,该对象死亡,计数器为0,这时就应该对这个对象进行垃圾回收操作。
缺点:不全面,容易漏掉循环引用对象(两个对象互相引用);并发支持较弱;计数器占用额外内存空间。
标记清除算法:
为每个对象存储一个标记位,记录对象的状态(或者或是死亡)。分为两个阶段,一个是标记阶段,为每个对象更新标记位,检查对象是否死亡;二个是清除阶段,对死亡的对象进行清除,执行GC操作。
缺点:幽灵时间长;活着的对象都要在标记阶段遍历,算法复杂度较高;没有移动对象,可能出现很多碎片空间无法利用。
标记整理算法:
标记-整理算法是标记-清除算法的改进版,在标记阶段将所有对象标记为村和和死亡状态,不同的是在第二个阶段,将所有存活对象整理,放到另一处空间,然后把剩下的所有对象全部清除。
优点:不存在大量的碎片空间。
缺点:如果存活对象过多,整理阶段将会执行较多的复制操作,导致算法效率降低。
复制算法:
将内存平均分成两部分,每次只使用其中一部分,当这部分内存满的时候,将内存中所有存活的对象复制到另一个内存中,然后将之前的内存清空,只使用者部分内容,循环下去。
缺点:每次运行,总有一半内存是空的,导致可用内存空间只有原来的一半。
分代收集算法:
分代收集算法是目前大部分JVM的垃圾收集器采用的算法。它的核心思想是根据对象存活的生命周期将内存划分为若干个不同的区域。
一般情况下将堆区划分为老年代(Tenured Generation)、新生代(Young Generation)和永久代(Permanent Generation),老年代的特点是每次垃圾收集时只有少量对象需要被回收,而新生代的特点是每次垃圾回收时都有大量的对象需要被回收,永久代(Permanet Generation),它用来存储class类、常量、方法描述等。对永久代的回收主要回收两部分内容:废弃常量和无用的类。
目前大部分垃圾收集器对于新生代都采取复制算法,因为新生代中每次垃圾回收都要回收大部分对象,也就是说需要复制的操作次数较少,但是实际中并不是按照1:1的比例来划分新生代的空间的,一般来说是将新生代划分为一块较大的Eden空间和两块较小的Survivor空间,每次使用Eden空间和其中的一块Survivor空间,当进行回收时,将Eden和Survivor中还存活的对象复制到另一块Survivor空间中,然后清理掉Eden和刚才使用过的Survivor空间。而由于老年代的特点是每次回收都只回收少量对象,一般使用的是标记整理算法。
JAVA集合
Java集合大致可以分为Set、List、Queue、Map四种体系。
Set:代表无序、不可重复 List:代表有序、重复的集合 Queue:代表一种队列集合实现 Map:代表具有映射关系的集合
HashMap工作原理
HashMap基于hashing原理,通过put()和get()方法存储和获取对象。HashMap是由数组+链表组成的,主干是一个Entry数组,每一个Entry包含一个key-value键值对,链表则是主要为了解决哈希冲突而存在的,当两个不同的键对象的hashcode相同时,它们会发生碰撞,会存储在同一个bucket位置的链表中,获取对象时,如果hashcode相同,会通过hashcode找到对应的bucket位置,然后遍历链表并通过key的equals()方法找到链表中正确的值对象。
Java8 对 HashMap 进行了一些修改,最大的不同就是利用了红黑树,所以其由 数组+链表+红黑树 组成。Java7中,根据 hash 值我们能够快速定位到数组的具体下标,但是之后的话,需要顺着链表一个个比较下去才能找到我们需要的,时间复杂度取决于链表的长度,为 O(n)。为了降低这部分的开销,在 Java8 中,当链表中的元素超过了 8 个以后,会将链表转换为红黑树,在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。
如何获取线程安全的HashMap
Map m = Collections.synchronizeMap(hashMap);
或者使用ConcurrentHashMap
ConcurrentHashMap工作原理
JAVA7中ConcurrentHashMap使用分段锁技术,将数据分成一段一段的存储,然后给每一段数据配一把锁,当一个线程占用锁访问其中一个段数据的时候,其他段的数据也能被其他线程访问,能够实现真正的并发访问。ConcurrentHashMap的主干是个Segment数组。Segment继承了ReentrantLock,所以它就是一种可重入锁(ReentrantLock)。一个Segment就是一个子哈希表,Segment里维护了一个HashEntry数组,并发环境下,对于不同Segment的数据进行操作是不用考虑锁竞争的(就按默认的ConcurrentLeve为16来讲,理论上就允许16个线程并发执行)。Segment中的put方法是要加锁的,get方法无需加锁,由于其中涉及到的共享变量都使用volatile修饰,volatile可以保证内存可见性,所以不会读取到过期数据。
JAVA8中ConcurrentHashMap采用了数组+链表+红黑树的实现方式来设计,内部大量采用CAS操作(CAS是compare and swap的缩写,即我们所说的比较交换。cas是一种基于锁的操作,而且是乐观锁)。
JAVA7和JAVA8的ConcurrentHashMap对比:
(1)数据结构:取消了Segment分段锁的数据结构,取而代之的是数组+链表+红黑树的结构。
(2)保证线程安全机制:JDK1.7采用segment的分段锁机制实现线程安全,其中segment继承自ReentrantLock。JDK1.8采用CAS+Synchronized保证线程安全。
(3)锁的粒度:原来是对需要进行数据操作的Segment加锁,现调整为对每个数组元素加锁(Node)。
(4)链表转化为红黑树:定位结点的hash算法简化会带来弊端,Hash冲突加剧,因此在链表节点数量大于8时,会将链表转化为红黑树进行存储。
(5)查询时间复杂度:从原来的遍历链表O(n),变成遍历红黑树O(logN)。
HashMap和Hashtable的区别
HashMap和HashSet的区别
HashMap和LinkedHashMap的区别
ArrayList和LinkedList的区别
二叉树
树由节点组成,一棵树至少会有一个节点(根节点),二叉树每个节点不能多于两个儿子。
二叉树遍历有三种方式,以上图为例:
先序遍历:先访问根节点,然后访问左节点,最后访问右节点(根->左->右)
13,8,1,6,11,17,15,25,22,27
中序遍历:先访问左节点,然后访问根节点,最后访问右节点(左->根->右)
1,6,8,11,13,15,17,22,25,27
后序遍历:先访问左节点,然后访问右节点,最后访问根节点(左->右->根)
6,1,11,8,15,22,27,25,17,13
红黑树
R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。
红黑树的特性:
(1)每个节点或者是黑色,或者是红色。
(2)根节点是黑色。
(3)每个叶子节点(NIL)是黑色。 [注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点!]
(4)如果一个节点是红色的,则它的子节点必须是黑色的。
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
特性(5),确保没有一条路径会比其他路径长出俩倍。因而,红黑树是相对是接近平衡的二叉树。
红黑树的应用:
红黑树的应用比较广泛,主要是用它来存储有序的数据,它的时间复杂度是O(lgn),效率非常之高。
例如,Java集合中的TreeSet和TreeMap,C++ STL中的set、map,以及Linux虚拟内存的管理,都是通过红黑树去实现的。
为何默认插入的结点为红色?
因为红黑树中黑节点至少是红节点的两倍,因此插入节点的父节点为黑色的概率较大,而此时并不需要作任何调整,因此效率较高