首页 文章 精选 留言 我的

精选列表

搜索[面试],共4912篇文章
优秀的个人博客,低调大师

[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) image 队列:先进先出(FIFO) image 1. 栈的 java 实现 import java.util.Arrays; public class Stack { private int size = 0; //栈顶位置 private int[] array; public Stack(){ this(10); } public Stack(int init) { if(init <= 0){ init = 10; } array = new int[init]; } /** * 入栈操作 * @param item 入栈的元素 */ public void push(int item){ if(size == array.length){ array = Arrays.copyOf(array, size*2); //扩容操作 } array[size++] = item; } /** * 获取栈顶元素,但栈顶元素不出栈 * @return 栈顶元素 */ public int peek(){ if(size == 0){ //空栈 throw new IndexOutOfBoundsException("栈是空的"); } return array[size-1]; } /** * 出栈,同时获取栈顶元素 * @return */ public int pop(){ int item = peek(); //获取栈顶元素 size--; //直接使元素个数减1,不用清除元素,下次入栈会覆盖旧元素的值 return item; } /** * 判断栈是否已满 * @return */ public boolean isFull(){ return size == array.length; } /** * 判断栈是否为空 * @return */ public boolean isEmpty(){ return size == 0; } public int getSize(){ return size; } } 2. 队列的 java 实现 public class ArrayQueue { private final Object[] queue; //声明一个数组 private int head; private int tail; /** * 初始化队列 * @param capacity 队列长度 */ public ArrayQueue(int capacity){ this.queue = new Object[capacity]; } /** * 入队 * @param o 入队元素 * @return 入队成功与否 */ public boolean put(Object o){ if(head == (tail+1)%queue.length){ //说明队满 return false; } queue[tail] = o; tail = (tail+1)%queue.length; //tail标记后移一位 return true; } /** * 返回队首元素,但不出队 * @return */ public Object peak() { if(head==tail){ //队空 return null; } return queue[head]; } /** * 出队 * @return 出队元素 */ public Object pull(){ if(head==tail){ return null; } Object item = queue[head]; queue[head] = null; return item; } /** * 判断是否为空 * @return */ public boolean isEmpty(){ return head == tail; } /** * 判断是否为满 * @return */ public boolean isFull(){ return head == (tail+1)%queue.length; } /** * 获取队列中的元素个数 * @return */ public int getsize(){ if(tail>=head){ return tail-head; }else{ return (tail+queue.length)-head; } } } 3. 用两个栈实现队列 剑指offer:用两个栈实现队列 LeetCode:Implement Queue using Stacks class MyQueue { Stack<Integer> input = new Stack<Integer>(); Stack<Integer> output = new Stack<Integer>(); /** Push element x to the back of queue. */ public void push(int x) { input.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { peek(); return output.pop(); } /** Get the front element. */ public int peek() { if(output.isEmpty()){ while(!input.isEmpty()) output.push(input.pop()); } return output.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return input.isEmpty() && output.isEmpty(); } } 4. 用队列实现栈 LeetCode:Implement Stack using Queues class MyStack { Queue<Integer> q1 = new LinkedList<Integer>(); Queue<Integer> q2 = new LinkedList<Integer>(); /** Push element x onto stack. */ public void push(int x) { if(q1.isEmpty()){ q1.add(x); for(int i = 0; i < q2.size(); i++){ q1.add(q2.poll()); } }else{ q2.add(x); for(int i = 0; i < q1.size(); i++){ q2.add(q1.poll()); } } } /** Removes the element on top of the stack and returns that element. */ public int pop() { return q1.isEmpty() ? q2.poll() : q1.poll(); } /** Get the top element. */ public int top() { return q1.isEmpty() ? q2.peek() : q1.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return q1.isEmpty() && q2.isEmpty(); } } 5. 包含min函数的栈 剑指offer:包含min函数的栈 定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。 class MinStack { Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> temp = new Stack<Integer>(); public void push(int x) { stack.push(x); if(temp.isEmpty() || temp.peek() >= x) temp.push(x); } public void pop() { int x = stack.pop(); int min = temp.peek(); if(x == min) temp.pop(); } public int top() { return stack.peek(); } public int getMin() { return temp.peek(); } } 6. 栈的压入、弹出序列 剑指offer:栈的压入、弹出序列 输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。(注意:这两个序列的长度是相等的) import java.util.ArrayList; import java.util.Stack; public class Solution { public boolean IsPopOrder(int [] pushA, int [] popA) { if(pushA.length != popA.length || pushA.length == 0 || popA.length == 0) return false; Stack<Integer> stack = new Stack<>(); int index = 0; for(int i = 0; i < pushA.length; i++){ stack.push(pushA[i]); while(!stack.empty() && stack.peek() == popA[index]){ stack.pop(); index++; } } return stack.empty(); } }

优秀的个人博客,低调大师

2018 年最常见的 Python 面试题 & 答案

Q 1:Python 有哪些特点和优点? 作为一门编程入门语言,Python 主要有以下特点和优点: 可解释 具有动态特性 面向对象 简明简单 开源 具有强大的社区支持 当然,实际上 Python 的优点远不止如此,可以阅读该文档,详细了解: https://data-flair.training/blogs/python-tutorial/ Q 2:深拷贝和浅拷贝之间的区别是什么? 答:深拷贝就是将一个对象拷贝到另一个对象中,这意味着如果你对一个对象的拷贝做出改变时,不会影响原对象。在 Python 中,我们使用函数 deepcopy() 执行深拷贝,导入模块 copy,如下所示: 1 >> > import copy 2 >> > b=copy.deepcopy(a) 而浅拷贝则是将一个对象的引用拷贝到另一个对象上,所以如果我

优秀的个人博客,低调大师

9道前端面试题及答案,赶紧收藏!

1、什么是W3C标准? WEB标准不是某一个标准,而是一系列标准的集合。网页主要由三部分组成:结构(Structure)、表现(Presentation)和行为(Behavior)。对应的标准也分三方面:结构化标准语言主要包括XHTML和XML,表现标准语言主要包括CSS,行为标准主要包括对象模型(如W3C DOM)、ECMAScript等。 2、bootstrap响应式原理 是通过栅格系统和媒体查询实现的 // 小屏幕(平板,大于等于 768px)@media (min-width: @screen-sm-min) { ... }// 中等屏幕(桌面显示器,大于等于 992px)@media (min-width: @screen-md-min) { ... }// 大屏幕(大桌面显示器,大于等于 1200... 3、HTML/XHTM的区别 XHTML 与 HTML 4.01 标准没有太多的不同。 XHTML 元素必须被正确地嵌套。 XHTML 元素必须被关闭。 标签名必须用小写字母。 XHTML 文档必须拥有根元素。 【如果大家对程序员,web前端感兴趣,想要学习的,关注一下小编吧。我是一名前端开发程序员,现在在网上授课教前端,每晚都会在群内免费直播。从最基础的HTML+CSS+JS到移动端HTML5到各种框架都有整理,送给每一位前端小伙伴,这里是小白聚集地,欢迎初学和进阶中的小伙伴。加群:731771211。前端学习必备公众号ID:mtbcxx】 4、页面构架和布局 布局可以是编码方面的,也可以是视觉方面的。 编码方面的涉及到语义化标签(也包含了div+css)布局、iframe框架(特殊地方使用)布局和表格布局(只用于一些特殊的地方,不推荐全站使用),具体你可以百度下了解学习下相关知识。 如果是视觉交互方面的,就比较多了,每年都会有新的设计布局,高级一点的比如视差类型布局,全屏布局,瀑布流,无缝拼图布局等,这些都不局限于传统的布局方式;传统电子商务、信息类的大多采用单栏、两栏或者三栏布局,还有更多栏布局;分辨率相关的宽屏布局和窄屏布局,感应式布局。太多的选择了,要学习的东西也比较多,要慢慢了解啦。还有更多的布局需要慢慢摸索和体验。我把我知道的说了。 至于手机端,例举一些:竖排列表、横排方块、九宫格、TAB切换式、手风琴布局(有多个分类及其内容同时展示)、抽屉/侧边栏、标签场景式),因为屏幕小,要增加用户体验都可以根据具体情况用不同的布局方式。 5、BootStrap学习笔记,优缺点总结 优点: BT的优势之一就是可以根据用户屏幕尺寸调整页面,使其在各个尺寸上都表现良好。 BT预先定义了很多CSS类,使用的时候直接给class赋予对应的类名即可,如text-left,text-align,.table等。最有代表性的就是btn类,BT定义了一个.bt的基础类,如果还想要其他样式可以在这个基础类上进行扩展,实现不同的视觉效果。 BT的JavaScript插件非常丰富,既可以用现成的也可以自己扩充,BT提供了一个集成板的BT.js您可以直接拿过来使用也可以单个使用引入*.js即可。 不足: 对IE兼容也存在不小的问题,BT将所有的元素盒模型都设置成了border-box,这是IE混杂模式下的盒模型,光这点就导致了不能兼容IE。此外还用到了大量的H5标签以及CSS3语法,这些语法标签兼容性方面同样存在不小的问题,当然网上存在很多兼容IE的办法,但需要引入其他文件,有些还不小,势必导致加载速度变慢,影响用户体验。 BT对IE6,7的兼容性肯定不好,对IE8的支持也需要一些额外的文件。 IE8的媒体查询需要response.js的配合才能实现 BT 不支持 IE 古老的兼容模式。为了让 IE 浏览器运行最新的渲染模式下,建议将此 标签加入到你的页面中: 按 F12 键打开 IE 的调试工具,就可以看到 IE 当前的渲染模式是什么。 BT属于前端UI库,可以快速搭建前端页面,以及设计响应式界面,还可以使用saas重新设计组件, 【如果大家对程序员,web前端感兴趣,想要学习的,关注一下小编吧。我是一名前端开发程序员,现在在网上授课教前端,每晚都会在群内免费直播。从最基础的HTML+CSS+JS到移动端HTML5到各种框架都有整理,送给每一位前端小伙伴,这里是小白聚集地,欢迎初学和进阶中的小伙伴。加群:731771211。前端学习必备公众号ID:mtbcxx】 6、JQeury学习笔记,优缺点总结 优点: jQuery实现脚本与页面的分离,是操作DOM的首选js库。 最少的代码做最多的事情 最少的代码做最多的事情,这是jQuery的口号,而且名副其实。使用它的高级selector,开发者只需编写几行代码就能实现令人惊奇的效果。开发者无需过于担忧浏览器差异,它除了还完全支持Ajax,而且拥有许多提高开发者编程效率的其它抽象概念。jQuery把JavaScript带到了一个更高的层次。以下是一个非常简单的示例: 代码如下: $("p.neat").addClass("ohmy").show("slow"); 通过以上简短的代码,开发者可以遍历“neat”类中所有的 元素,然后向其增加“ohmy”类,同时以动画效果缓缓显示每一个段落。开发者无需检查客户端浏览器类型,无需编写循环代码,无需编写复杂的动画函数,仅仅通过一行代码就能实现上述效果。 性能 在大型JavaScript框架中,jQuery对性能的理解最好。尽管不同版本拥有众多新功能,其最精简版本只有18KB大小,这个数字已经很难再减少。jQuery的每一个版本都有重大性能提高。 插件 基于jQuery开发的插件目前已经有大约数千个。开发者可使用插件来进行表单确认、图表种类、字段提示、动画、进度条等任务。 节省开发者学习时间 当然要想真正学习jQuery,开发者还是需要投入一点时间,尤其是如果你要编写大量代码或自主插件的话,更是如此。但是,开发者可以采取“各个击破”的方式,而且jQuery提供了大量示例代码,入门是一件非常容易的事情。 不足: 不能向后兼容 插件兼容性。 jQuery的稳定性 在大型框架中,jQuery核心代码库对动画和特效的支持相对较差。 7、”高内聚 ,低耦合“到底是什么意思? ‘高内聚,低耦合’是相对于代码而言,一个项目中: 每个模块之间相互联系的紧密程度,模块之间联系越紧密,则耦合性越高,模块的独立性就越差!反之同理; 一个模块中各个元素之间的联系的紧密程度,如果各个元素(语句、程序段)之间的联系程度越高,则内聚性越高,即‘高内聚’ ! 如:一个项目中有20个方法调用良好,但是要修改了其中一个,另外的19个都要进行修改,这就是高耦合!独立性太差! 现在的软件结构设计,都会要求“高内聚,低耦合”,来保证软件的高质量!mark! 8、对前后端联合开发 的技术原理(Ajax、Json)有一定认识,理解DOM、Xml概念, 熟悉前后台交互方式。 Ajax异步交互原理:Ajax其核心有JavaScript、XMLHTTPRequest、DOM对象组成,通过XmlHttpRequest对象来向服务器发异步请求,从服务器获得数据,然后用JavaScript来操作DOM而更新页面。 Json:一般我用的比较多的是通过AJAX异步来获取JSON数据。 DOM:文档对象模型,一个网页中所有的东西都是dom节点,根节点是,它可以无线嵌套。用来获取或设置文档中标签的属性,例如获取或者设置input表单的value值。 BOM:浏览器对象模型。用来获取或设置浏览器的属性、行为,例如:新建窗口、获取屏幕分辨率、浏览器版本号等。 XML:被设计用来传输和存储数据,被设计用来格式化和显示数据。仅仅是纯文本。 -前后台交互方式: 9、GET和POST请求的区别 GET提交的数据会放在URL之后,以?分割URL和传输数据,参数之间以&相连,如EditPosts.aspx?name=test1&id=123456. POST方法是把提交的数据放在HTTP包的Body中. GET提交的数据大小有限制(因为浏览器对URL的长度有限制),而POST方法提交的数据没有限制. GET方式需要使用Request.QueryString来取得变量的值,而POST方式通过Request.Form来获取变量的值。 GET方式提交数据,会带来安全问题,比如一个登录页面,通过GET方式提交数据时,用户名和密码将出现在URL上,如果页面可以被缓存或者其他人可以访问这台机器,就可以从历史记录获得该用户的账号和密码. 【如果大家对程序员,web前端感兴趣,想要学习的,关注一下小编吧。我是一名前端开发程序员,现在在网上授课教前端,每晚都会在群内免费直播。从最基础的HTML+CSS+JS到移动端HTML5到各种框架都有整理,送给每一位前端小伙伴,这里是小白聚集地,欢迎初学和进阶中的小伙伴。加群:731771211。前端学习必备公众号ID:mtbcxx】

优秀的个人博客,低调大师

学习Java基础知识,打通面试关~十三锁机制

静态创建线程池 我们平常使用的大部分还是依靠java中自带的静态工厂产生的线程池。先了解下自带的线程池。 newFixedThreadPool(int numThreads) 该线程池会在初始化的指定线程数量。具有以下的特点1.在任何时刻都是最多有numThreads的线程数量活动。如果超过限制会在LinkedBlockingQueue中等待。 2.当达到核心线程数的时候,线程数不在继续增加。3.有工作线程退出,新的工作线程被创建来达到设置的线程数。 Executors.newFixedThreadPool(1); //源码实现 public static ExecutorService newFixedThreadPool(int nThreads) { return new ThreadPoolExecutor(nThreads, nThreads, 0L, TimeUnit.MILLISECONDS, new LinkedBlockingQueue<Runnable>()); } newCachedThreadPool 该线程池是一个可以用来缓存的线程池。1.尝试缓存使用过的线程。2.没有缓存的线程池时,就会使用工厂方法创建线程池,最大的容量理论上是Integer.MAX_VALUE。这个跟服务器的配置有关。所以如果过来大量的线程任务,那么该线程池会在瞬间创建多个线程来执行工作。3.时间上多余的线程超过60秒会被终止移除缓存中。4.内部使用的SynchronousQueue实现的队列,该队列在实现的时候没有容量。适合来做交换的工作。 Executors.newCachedThreadPool(); //源码实现 public static ExecutorService newCachedThreadPool() { return new ThreadPoolExecutor(0, Integer.MAX_VALUE, 60L, TimeUnit.SECONDS, new SynchronousQueue<Runnable>()); } newSingleThreadExecutor 该线程池是用来设置单个的线程池,使用的队列是无界队列。因为提交的任务只要一个是能活动的,剩下的是放到无界队列中。队列是先进先出的。那么执行顺序是有序的。 Executors.newSingleThreadExecutor(); //源码 public static ExecutorService newSingleThreadExecutor() { return new FinalizableDelegatedExecutorService (new ThreadPoolExecutor(1, 1, 0L, TimeUnit.MILLISECONDS, new LinkedBlockingQueue<Runnable>())); } newWorkStealingPool 工作线程,该线程是在jdk1.8以后新增加的.使用的是ForkJoinPool创建线程池。该任务执行没有顺序。需要考虑到硬件的cpu核心数。 Executors.newWorkStealingPool(); public static ExecutorService newWorkStealingPool() { return new ForkJoinPool (Runtime.getRuntime().availableProcessors(), //默认使用的是硬件的cpu数目 ForkJoinPool.defaultForkJoinWorkerThreadFactory, null, true); } Executors.newWorkStealingPool(10); public static ExecutorService newWorkStealingPool(int parallelism) { return new ForkJoinPool (parallelism, // 使用的是自定义的核心数 ForkJoinPool.defaultForkJoinWorkerThreadFactory, null, true); } newSingleThreadScheduledExecutor()与newScheduledThreadPool(int poolSize) 周期性的调度执行任务的线程池。 单个执行。 Executors.newSingleThreadScheduledExecutor(); public static ScheduledExecutorService newSingleThreadScheduledExecutor() { return new DelegatedScheduledExecutorService (new ScheduledThreadPoolExecutor(1)); } //核心周期执行的线程数 Executors.newScheduledThreadPool(10); public static ScheduledExecutorService newScheduledThreadPool(int corePoolSize) { return new ScheduledThreadPoolExecutor(corePoolSize); } 了解其java内部的静态线程池,并且在程序中使用其策略。当然在这种我们没有看到的是线程池的拒绝策略。无界队列和有界队列,核心数的与最大的核心数的设置,这些不同。那么我们的执行拒绝策略也是不同的。在接下里的文章我们会具体了解拒绝策略。 原文发布时间为:2018-07-09本文作者:mengrui本文来自云栖社区合作伙伴“LuckQI”,了解相关信息可以关注“LuckQI”。

优秀的个人博客,低调大师

关于Java锁机制面试官会怎么问

乐观锁与悲观锁 悲观锁:总是假设最坏的情况,每次去拿数据的时候都认为别人会修改,所以每次在拿数据的时候都会上锁,这样别人想拿这个数据就会阻塞直到它拿到锁。传统的关系型数据库里边就用到了很多这种锁机制,比如行锁,表锁等,读锁,写锁等,都是在做操作之前先上锁。再比如Java里面的同步原语synchronized关键字的实现也是悲观锁。 乐观锁:顾名思义,就是很乐观,每次去拿数据的时候都认为别人不会修改,所以不会上锁,但是在更新的时候会判断一下在此期间别人有没有去更新这个数据,可以使用版本号等机制。乐观锁适用于多读的应用类型,这样可以提高吞吐量,像数据库提供的类似于write_condition机制,其实都是提供的乐观锁。在Java中java.util.concurrent.atomic包下面的原子变量类就是使用了乐观锁的一种实现方式CAS实现的。 乐观锁的一种实现方式-CAS(Compare and Swap 比较并交换): 锁存在的问题 Java在JDK1.5之前都是靠synchronized关键字保证同步的,这种通过使用一致的锁定协议来协调对共享状态的访问,可以确保无论哪个线程持有共享变量的锁,都采用独占的方式来访问这些变量。这就是一种独占锁,独占锁其实就是一种悲观锁,所以可以说 synchronized 是悲观锁。 悲观锁机制存在以下问题: 在多线程竞争下,加锁、释放锁会导致比较多的上下文切换和调度延时,引起性能问题。 一个线程持有锁会导致其它所有需要此锁的线程挂起。 如果一个优先级高的线程等待一个优先级低的线程释放锁会导致优先级倒置。 对比于悲观锁的这些问题,另一个更加有效的锁就是乐观锁。其实乐观锁就是:每次不加锁而是假设没有并发冲突而去完成某项操作,如果因为并发冲突失败就重试,直到成功为止。 乐观锁 乐观锁( Optimistic Locking)在上文已经说过了,其实就是一种思想。相对悲观锁而言,乐观锁假设认为数据一般情况下不会产生并发冲突,所以在数据进行提交更新的时候,才会正式对数据是否产生并发冲突进行检测,如果发现并发冲突了,则让返回用户错误的信息,让用户决定如何去做。 上面提到的乐观锁的概念中其实已经阐述了它的具体实现细节:主要就是两个步骤:冲突检测和数据更新。其实现方式有一种比较典型的就是 Compare and Swap ( CAS )。 CAS CAS是乐观锁技术,当多个线程尝试使用CAS同时更新同一个变量时,只有其中一个线程能更新变量的值,而其它线程都失败,失败的线程并不会被挂起,而是被告知这次竞争中失败,并可以再次尝试。 CAS 操作中包含三个操作数 —— 需要读写的内存位置(V)、进行比较的预期原值(A)和拟写入的新值(B)。如果内存位置V的值与预期原值A相匹配,那么处理器会自动将该位置值更新为新值B。否则处理器不做任何操作。无论哪种情况,它都会在 CAS 指令之前返回该位置的值。(在 CAS 的一些特殊情况下将仅返回 CAS 是否成功,而不提取当前值。)CAS 有效地说明了“ 我认为位置 V 应该包含值 A;如果包含该值,则将 B 放到这个位置;否则,不要更改该位置,只告诉我这个位置现在的值即可。 ”这其实和乐观锁的冲突检查+数据更新的原理是一样的。 这里再强调一下,乐观锁是一种思想。CAS是这种思想的一种实现方式。 JAVA对CAS的支持:在JDK1.5 中新增 java.util.concurrent (J.U.C)就是建立在CAS之上的。相对于对于 synchronized 这种阻塞算法,CAS是非阻塞算法的一种常见实现。所以J.U.C在性能上有了很大的提升。 以 java.util.concurrent 中的 AtomicInteger 为例,看一下在不使用锁的情况下是如何保证线程安全的。主要理解 getAndIncrement 方法,该方法的作用相当于 ++i 操作。 在没有锁的机制下,字段value要借助volatile原语,保证线程间的数据是可见性。这样在获取变量的值的时候才能直接读取。然后来看看 ++i 是怎么做到的。getAndIncrement 采用了CAS操作,每次从内存中读取数据然后将此数据和 +1 后的结果进行CAS操作,如果成功就返回结果,否则重试直到成功为止。而 compareAndSet 利用JNI(Java Native Interface)来完成CPU指令的操作: 那么比较this == expect,替换this = update,compareAndSwapInt实现这两个步骤的原子性呢? 参考CAS的原理。 CAS原理:CAS通过调用JNI的代码实现的。而compareAndSwapInt就是借助C来调用CPU底层指令实现的。下面从分析比较常用的CPU(intel x86)来解释CAS的实现原理。下面是sun.misc.Unsafe类的compareAndSwapInt()方法的源代码: 如上面源代码所示,程序会根据当前处理器的类型来决定是否为cmpxchg指令添加lock前缀。如果程序是在多处理器上运行,就为cmpxchg指令加上lock前缀(lock cmpxchg)。反之,如果程序是在单处理器上运行,就省略lock前缀(单处理器自身会维护单处理器内的顺序一致性,不需要lock前缀提供的内存屏障效果)。 CAS缺点: ABA问题:比如说一个线程one从内存位置V中取出A,这时候另一个线程two也从内存中取出A,并且two进行了一些操作变成了B,然后two又将V位置的数据变成A,这时候线程one进行CAS操作发现内存中仍然是A,然后one操作成功。尽管线程one的CAS操作成功,但可能存在潜藏的问题。如下所示: 现有一个用单向链表实现的堆栈,栈顶为A,这时线程T1已经知道A.next为B,然后希望用CAS将栈顶替换为B:head.compareAndSet(A,B);在T1执行上面这条指令之前,线程T2介入,将A、B出栈,再pushD、C、A,此时堆栈结构如下图,而对象B此时处于游离状态: 此时轮到线程T1执行CAS操作,检测发现栈顶仍为A,所以CAS成功,栈顶变为B,但实际上B.next为null,所以此时的情况变为: 其中堆栈中只有B一个元素,C和D组成的链表不再存在于堆栈中,平白无故就把C、D丢掉了。从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用,并且当前标志是否等于预期标志,如果全部相等,则以原子方式将该引用和该标志的值设置为给定的更新值。 循环时间长开销大: 自旋CAS(不成功,就一直循环执行,直到成功)如果长时间不成功,会给CPU带来非常大的执行开销。如果JVM能支持处理器提供的pause指令那么效率会有一定的提升,pause指令有两个作用,第一它可以延迟流水线执行指令(de-pipeline),使CPU不会消耗过多的执行资源,延迟的时间取决于具体实现的版本,在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突(memory order violation)而引起CPU流水线被清空(CPU pipeline flush),从而提高CPU的执行效率。 只能保证一个共享变量的原子操作: 当对一个共享变量执行操作时,我们可以使用循环CAS的方式来保证原子操作,但是对多个共享变量操作时,循环CAS就无法保证操作的原子性,这个时候就可以用锁,或者有一个取巧的办法,就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i=2,j=a,合并一下ij=2a,然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性,你可以把多个变量放在一个对象里来进行CAS操作。 CAS与Synchronized的使用情景 1、对于资源竞争较少(线程冲突较轻)的情况,使用synchronized同步锁进行线程阻塞和唤醒切换以及用户态内核态间的切换操作额外浪费消耗cpu资源;而CAS基于硬件实现,不需要进入内核,不需要切换线程,操作自旋几率较少,因此可以获得更高的性能。 2、对于资源竞争严重(线程冲突严重)的情况,CAS自旋的概率会比较大,从而浪费更多的CPU资源,效率低于synchronized。 补充:synchronized在jdk1.6之后,已经改进优化。synchronized的底层实现主要依靠Lock-Free的队列,基本思路是自旋后阻塞,竞争切换后继续竞争锁,稍微牺牲了公平性,但获得了高吞吐量。在线程冲突较少的情况下,可以获得和CAS类似的性能;而线程冲突严重的情况下,性能远高于CAS。 concurrent包的实现 由于java的CAS同时具有 volatile 读和volatile写的内存语义,因此Java线程之间的通信现在有了下面四种方式: A线程写volatile变量,随后B线程读这个volatile变量。 A线程写volatile变量,随后B线程用CAS更新这个volatile变量。 A线程用CAS更新一个volatile变量,随后B线程用CAS更新这个volatile变量。 A线程用CAS更新一个volatile变量,随后B线程读这个volatile变量。 Java的CAS会使用现代处理器上提供的高效机器级别原子指令,这些原子指令以原子方式对内存执行读-改-写操作,这是在多处理器中实现同步的关键(从本质上来说,能够支持原子性读-改-写指令的计算机器,是顺序计算图灵机的异步等价机器,因此任何现代的多处理器都会去支持某种能对内存执行原子性读-改-写操作的原子指令)。同时,volatile变量的读/写和CAS可以实现线程之间的通信。把这些特性整合在一起,就形成了整个concurrent包得以实现的基石。如果我们仔细分析concurrent包的源代码实现,会发现一个通用化的实现模式: 首先,声明共享变量为volatile; 然后,使用CAS的原子条件更新来实现线程之间的同步; 同时,配合以volatile的读/写和CAS所具有的volatile读和写的内存语义来实现线程之间的通信。 AQS,非阻塞数据结构和原子变量类(java.util.concurrent.atomic包中的类),这些concurrent包中的基础类都是使用这种模式来实现的,而concurrent包中的高层类又是依赖于这些基础类来实现的。从整体来看,concurrent包的实现示意图如下: JVM中的CAS(堆中对象的分配) Java调用new object()会创建一个对象,这个对象会被分配到JVM的堆中。那么这个对象到底是怎么在堆中保存的呢? 首先,new object()执行的时候,这个对象需要多大的空间,其实是已经确定的,因为java中的各种数据类型,占用多大的空间都是固定的(对其原理不清楚的请自行Google)。那么接下来的工作就是在堆中找出那么一块空间用于存放这个对象。 在单线程的情况下,一般有两种分配策略: 指针碰撞:这种一般适用于内存是绝对规整的(内存是否规整取决于内存回收策略),分配空间的工作只是将指针像空闲内存一侧移动对象大小的距离即可。 空闲列表:这种适用于内存非规整的情况,这种情况下JVM会维护一个内存列表,记录哪些内存区域是空闲的,大小是多少。给对象分配空间的时候去空闲列表里查询到合适的区域然后进行分配即可。 但是JVM不可能一直在单线程状态下运行,那样效率太差了。由于在给一个对象分配内存的时候不是原子性的操作,至少需要以下几步:查找空闲列表、分配内存、修改空闲列表等等,这是不安全的。解决并发时的安全问题也有两种策略: CAS:实际上虚拟机采用CAS配合上失败重试的方式保证更新操作的原子性,原理和上面讲的一样。 TLAB:如果使用CAS其实对性能还是会有影响的,所以JVM又提出了一种更高级的优化策略:每个线程在Java堆中预先分配一小块内存,称为本地线程分配缓冲区(TLAB),线程内部需要分配内存时直接在TLAB上分配就行,避免了线程冲突。只有当缓冲区的内存用光需要重新分配内存的时候才会进行CAS操作分配更大的内存空间。 虚拟机是否使用TLAB,可以通过-XX:+/-UseTLAB参数来进行配置(jdk5及以后的版本默认是启用TLAB的)。 原文发布时间为:2018-07-05本文来自云栖社区合作伙伴“Java架构沉思录”,了解相关信息可以关注“Java架构沉思录”。

优秀的个人博客,低调大师

java面试-深入理解JVM(三)——垃圾收集策略详解

Java虚拟机的内存模型分为五个部分,分别是:程序计数器、Java虚拟机栈、本地方法栈、堆、方法区。 这五个区域既然是存储空间,那么为了避免Java虚拟机在运行期间内存存满的情况,就必须得有一个垃圾收集者的角色,不定期地回收一些无效内存,以保障Java虚拟机能够健康地持续运行。 这个垃圾收集者就是平常我们所说的“垃圾收集器”,那么垃圾收集器在何时清扫内存?清扫哪些数据?这就是接下来我们要解决的问题。 程序计数器、Java虚拟机栈、本地方法栈都是线程私有的,也就是每条线程都拥有这三块区域,而且会随着线程的创建而创建,线程的结束而销毁。那么,垃圾收集器在何时清扫这三块区域的问题就解决了。 此外,Java虚拟机栈、本地方法栈中的栈帧会随着方法的开始而入栈,方法的结束而出栈,并且每个栈帧中的本地变量表都是在类被加载的时候就确定的。因此以上三个区域的垃圾收集工作具有确定性,垃圾收集器能够清楚地知道何时清扫这三块区域中的哪些数据。 然而,堆和方法区中的内存清理工作就没那么容易了。堆和方法区所有线程共享,并且都在JVM启动时创建,一直得运行到JVM停止时。因此它们没办法根据线程的创建而创建、线程的结束而释放。 堆中存放JVM运行期间的所有对象,虽然每个对象的内存大小在加载该对象所属类的时候就确定了,但究竟创建多少个对象只有在程序运行期间才能确定。方法区中存放类信息、静态成员变量、常量。类的加载是在程序运行过程中,当需要创建这个类的对象时才会加载这个类。因此,JVM究竟要加载多少个类也需要在程序运行期间确定。因此,堆和方法区的内存回收具有不确定性,因此垃圾收集器在回收堆和方法区内存的时候花了一些心思。 堆内存的回收 1. 如何判定哪些对象需要回收? 在对堆进行对象回收之前,首先要判断哪些是无效对象。我们知道,一个对象不被任何对象或变量引用,那么就是无效对象,需要被回收。一般有两种判别方式: 引用计数法每个对象都有一个计数器,当这个对象被一个变量或另一个对象引用一次,该计数器加一;若该引用失效则计数器减一。当计数器为0时,就认为该对象是无效对象。 可达性分析法所有和GC Roots直接或间接关联的对象都是有效对象,和GC Roots没有关联的对象就是无效对象。GC Roots是指: Java虚拟机栈所引用的对象(栈帧中局部变量表中引用类型的变量所引用的对象) 方法区中静态属性引用的对象 方法区中常量所引用的对象 本地方法栈所引用的对象PS:注意!GC Roots并不包括堆中对象所引用的对象!这样就不会出现循环引用。 两者对比:引用计数法虽然简单,但存在一个严重的问题,它无法解决循环引用的问题。因此,目前主流语言均使用可达性分析方法来判断对象是否有效。 2. 回收无效对象的过程 当JVM筛选出失效的对象之后,并不是立即清除,而是再给对象一次重生的机会,具体过程如下: 判断该对象是否覆盖了finalize()方法 若已覆盖该方法,并该对象的finalize()方法还没有被执行过,那么就会将finalize()扔到F-Queue队列中; 若未覆盖该方法,则直接释放对象内存。 执行F-Queue队列中的finalize()方法虚拟机会以较低的优先级执行这些finalize()方法们,也不会确保所有的finalize()方法都会执行结束。如果finalize()方法中出现耗时操作,虚拟机就直接停止执行,将该对象清除。 对象重生或死亡如果在执行finalize()方法时,将this赋给了某一个引用,那么该对象就重生了。如果没有,那么就会被垃圾收集器清除。 注意:强烈不建议使用finalize()函数进行任何操作!如果需要释放资源,请使用try-finally。因为finalize()不确定性大,开销大,无法保证顺利执行。 方法区的内存回收 我们知道,如果使用复制算法实现堆的内存回收,堆就会被分为新生代和老年代,新生代中的对象“朝生夕死”,每次垃圾回收都会清除掉大量的对象;而老年代中的对象生命较长,每次垃圾回收只有少量的对象被清除掉。 由于方法区中存放生命周期较长的类信息、常量、静态变量,因此方法区就像是堆的老年代,每次垃圾收集的只有少量的垃圾被清除掉。 方法区中主要清除两种垃圾:1. 废弃常量2. 废弃的类 1. 如何判定废弃常量? 清除废弃的常量和清除对象类似,只要常量池中的常量不被任何变量或对象引用,那么这些常量就会被清除掉。 2. 如何废弃废弃的类? 清除废弃类的条件较为苛刻:1. 该类的所有对象都已被清除2. 该类的java.lang.Class对象没有被任何对象或变量引用只要一个类被虚拟机加载进方法区,那么在堆中就会有一个代表该类的对象:java.lang.Class。这个对象在类被加载进方法区的时候创建,在方法区中该类被删除时清除。3. 加载该类的ClassLoader已经被回收 垃圾收集算法 现在我们知道了判定一个对象是无效对象、判定一个类是废弃类、判定一个常量是废弃常量的方法,也就是知道了垃圾收集器会清除哪些数据,那么接下来介绍如何清除这些数据。 1. 标记-清除算法 首先利用刚才介绍的方法判断需要清除哪些数据,并给它们做上标记;然后清除被标记的数据。 分析:这种算法标记和清除过程效率都很低,而且清除完后存在大量碎片空间,导致无法存储大对象,降低了空间利用率。 2. 复制算法 将内存分成两份,只将数据存储在其中一块上。当需要回收垃圾时,也是首先标记出废弃的数据,然后将有用的数据复制到另一块内存上,最后将第一块内存全部清除。 分析:这种算法避免了碎片空间,但内存被缩小了一半。而且每次都需要将有用的数据全部复制到另一片内存上去,效率不高。 解决空间利用率问题:在新生代中,由于大量的对象都是“朝生夕死”,也就是一次垃圾收集后只有少量对象存活,因此我们可以将内存划分成三块:Eden、Survior1、Survior2,内存大小分别是8:1:1。分配内存时,只使用Eden和一块Survior1。当发现Eden+Survior1的内存即将满时,JVM会发起一次MinorGC,清除掉废弃的对象,并将所有存活下来的对象复制到另一块Survior2中。那么,接下来就使用Survior2+Eden进行内存分配。 通过这种方式,只需要浪费10%的内存空间即可实现带有压缩功能的垃圾收集方法,避免了内存碎片的问题。 但是,当一个对象要申请内存空间时,发现Eden+Survior中剩下的空间无法放置该对象,此时需要进行Minor GC,如果MinorGC过后空闲出来的内存空间仍然无法放置该对象,那么此时就需要将对象转移到老年代中,这种方式叫做“分配担保”。 什么是分配担保?当JVM准备为一个对象分配内存空间时,发现此时Eden+Survior中空闲的区域无法装下该对象,那么就会触发MinorGC,对该区域的废弃对象进行回收。但如果MinorGC过后只有少量对象被回收,仍然无法装下新对象,那么此时需要将Eden+Survior中的所有对象都转移到老年代中,然后再将新对象存入Eden区。这个过程就是“分配担保”。 3. 标记-整理算法 在回收垃圾前,首先将所有废弃的对象做上标记,然后将所有未被标记的对象移到一边,最后清空另一边区域即可。 分析:它是一种老年代的垃圾收集算法。老年代中的对象一般寿命比较长,因此每次垃圾回收会有大量对象存活,因此如果选用“复制”算法,每次需要复制大量存活的对象,会导致效率很低。而且,在新生代中使用“复制”算法,当Eden+Survior中都装不下某个对象时,可以使用老年代的内存进行“分配担保”,而如果在老年代使用该算法,那么在老年代中如果出现Eden+Survior装不下某个对象时,没有其他区域给他作分配担保。因此,老年代中一般使用“标记-整理”算法。 4. 分代收集算法 将内存划分为老年代和新生代。老年代中存放寿命较长的对象,新生代中存放“朝生夕死”的对象。然后在不同的区域使用不同的垃圾收集算法。 Java中引用的种类 Java中根据生命周期的长短,将引用分为4类。 1. 强引用 我们平时所使用的引用就是强引用。A a = new A();也就是通过关键字new创建的对象所关联的引用就是强引用。只要强引用存在,该对象永远也不会被回收。 2. 软引用 只有当堆即将发生OOM异常时,JVM才会回收软引用所指向的对象。软引用通过SoftReference类实现。软引用的生命周期比强引用短一些。 3. 弱引用 只要垃圾收集器运行,软引用所指向的对象就会被回收。弱引用通过WeakReference类实现。弱引用的生命周期比软引用短。 4. 虚引用 虚引用也叫幽灵引用,它和没有引用没有区别,无法通过虚引用访问对象的任何属性或函数。一个对象关联虚引用唯一的作用就是在该对象被垃圾收集器回收之前会受到一条系统通知。虚引用通过PhantomReference类来实现。

优秀的个人博客,低调大师

java面试-深入理解JVM(八)——类加载的时机

类的生命周期 一个类从加载进内存到卸载出内存为止,一共经历7个阶段:加载——>验证——>准备——>解析——>初始化——>使用——>卸载 其中,类加载包括5个阶段:加载——>验证——>准备——>解析——>初始化 在类加载的过程中,以下3个过程称为连接:验证——>准备——>解析 因此,JVM的类加载过程也可以概括为3个过程:加载——>连接——>初始化 C/C++在运行前需要完成预处理、编译、汇编、链接;而在Java中,类加载(加载、连接、初始化)是在程序运行期间完成的。在程序运行期间进行类加载会稍微增加程序的开销,但随之会带来更大的好处——提高程序的灵活性。Java语言的灵活性体现在它可以在运行期间动态扩展,所谓动态扩展就是在运行期间动态加载和动态连接。 类加载的时机 1. 类加载过程中每个步骤的顺序 我们已经知道,类加载的过程包括:加载、连接、初始化,连接又分为:验证、准备、解析,所以说类加载一共分为5步:加载、验证、准备、解析、初始化。 其中加载、验证、准备、初始化的开始顺序是依次进行的,这些步骤开始之后的过程可能会有重叠。而解析过程会发生在初始化过程中。 2. 类加载过程中“初始化”开始的时机 JVM规范中只定义了类加载过程中初始化过程开始的时机,加载、连接过程都应该在初始化之前开始(解析除外),这些过程具体在何时开始,JVM规范并没有定义,不同的虚拟机可以根据具体的需求自定义。 初始化开始的时机: 在运行过程中遇到如下字节码指令时,如果类尚未初始化,那就要进行初始化:new、getstatic、putstatic、invokestatic。这四个指令对应的Java代码场景是: 通过new创建对象; 读取、设置一个类的静态成员变量(不包括final修饰的静态变量); 调用一个类的静态成员函数。 使用java.lang.reflect进行反射调用的时候,如果类没有初始化,那就需要初始化; 当初始化一个类的时候,若其父类尚未初始化,那就先要让其父类初始化,然后再初始化本类; 当虚拟机启动时,虚拟机会首先初始化带有main方法的类,即主类; 3. 主动引用 与 被动引用 JVM规范中要求在程序运行过程中,“当且仅当”出现上述4个条件之一的情况才会初始化一个类。如果间接满足上述初始化条件是不会初始化类的。其中,直接满足上述初始化条件的情况叫做主动引用;间接满足上述初始化过程的情况叫做被动引用。那么,只有当程序在运行过程中满足主动引用的时候才会初始化一个类,若满足被动引用就不会初始化一个类。 4. 被动引用的场景示例 示例一 public class Fu{ public static String name = "柴毛毛"; static{ System.out.println("父类被初始化!"); } } public class Zi{ static{ System.out.println("子类被初始化!"); } } public static void main(String[] args){ System.out.println(Zi.name); } 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 输出结果:父类被初始化!柴毛毛原因分析:本示例看似满足初始化时机的第一条:当要获取某一个类的静态成员变量的时候如果该类尚未初始化,则对该类进行初始化。但由于这个静态成员变量属于Fu类,Zi类只是间接调用Fu类中的静态成员变量,因此Zi类调用name属性属于间接引用,而Fu类调用name属性属于直接引用,由于JVM只初始化直接引用的类,因此只有Fu类被初始化。 示例二 public class A{ public static void main(String[] args){ Fu[] arr = new Fu[10]; } } 1 2 3 4 5 输出结果:并没有输出“父类被初始化!”原因分析:这个过程看似满足初始化时机的第一条:遇到new创建对象时若类没被初始化,则初始化该类。但现在通过new要创建的是一个数组对象,而非Fu类对象,因此也属于间接引用,不会初始化Fu类。 示例三 public class Fu{ public static final String name = "柴毛毛"; static{ System.out.println("父类被初始化!"); } } public class A{ public static void main(String[] args){ System.out.println(Fu.name); } } 1 2 3 4 5 6 7 8 9 10 11 12 输出结果:柴毛毛原因分析:本示例看似满足类初始化时机的第一个条件:获取一个类静态成员变量的时候若类尚未初始化则初始化类。但是,Fu类的静态成员变量被final修饰,它已经是一个常量。被final修饰的常量在Java代码编译的过程中就会被放入它被引用的class文件的常量池中(这里是A的常量池)。所以程序在运行期间如果需要调用这个常量,直接去当前类的常量池中取,而不需要初始化这个类。 5. 接口的初始化 接口和类都需要初始化,接口和类的初始化过程基本一样,不同点在于:类初始化时,如果发现父类尚未被初始化,则先要初始化父类,然后再初始化自己;但接口初始化时,并不要求父接口已经全部初始化,只有程序在运行过程中用到当父接口中的东西时才初始化父接口。

优秀的个人博客,低调大师

Java中方法重写的两个面试

1:方法重写和方法重载的区别?方法重载能改变返回值类型吗? 方法重写: 在子类中,出现和父类中一模一样的方法声明的现象。(包含方法名、参数列表和返回值类型都一样) 方法重载: 同一个类中,出现的方法名相同,参数列表不同,与返回值类型无关的现象。 方法重载能改变返回值类型,因为它和返回值类型无关。 Override:方法重写 Overload:方法重载 2:this关键字和super关键字分别代表什么?以及他们各自的使用场景和作用。 this: 代表当前类的对象引用。 super:代表父类存储空间的标识。(可以理解为父类的引用,通过这个东西可以访问父类的成员。) 应用场景: 成员变量: this.成员变量 super.成员变量 构造方法: this(...) super(...) 成员方法: this.成员方法 super.成员方法我的GitHub地址: https://github.com/heizemingjun 我的博客园地址: http://www.cnblogs.com/chenmingjun 我的蚂蚁笔记博客地址: http://blog.leanote.com/chenmingjun Copyright ©2018 黑泽明军 【转载文章务必保留出处和署名,谢谢!】

资源下载

更多资源
优质分享App

优质分享App

近一个月的开发和优化,本站点的第一个app全新上线。该app采用极致压缩,本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

Nacos

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称,一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集,帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Spring

Spring

Spring框架(Spring Framework)是由Rod Johnson于2002年提出的开源Java企业级应用框架,旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念,提供核心容器、应用上下文、数据访问集成等模块,支持整合Hibernate、Struts等第三方框架,其适用范围不仅限于服务器端开发,绝大多数Java应用均可从中受益。

Sublime Text

Sublime Text

Sublime Text具有漂亮的用户界面和强大的功能,例如代码缩略图,Python的插件,代码段等。还可自定义键绑定,菜单和工具栏。Sublime Text 的主要功能包括:拼写检查,书签,完整的 Python API , Goto 功能,即时项目切换,多选择,多窗口等等。Sublime Text 是一个跨平台的编辑器,同时支持Windows、Linux、Mac OS X等操作系统。