程序运行时,内存是如何分配的?
Jvm中的内存划分JVM 中的内存可以划分为若干个不同的数据区域,主要分为:程序计数器、虚拟机栈、本地方法栈、堆、方法区。
程序计数器java本身是多线程的,当某一线程被CPU挂起后,需要记录程序执行的位置,这个时候就需要用到程序计数器。方便CPU重新执行此线程时,知道从哪行指令开始执行。这就是程序计数器的作用。
注意:1、在JVM中,对于程序计数器没有规定任何OutOfMemoryError的情况。2、线程私有的,每条线程内部都有一个私有程序计数器。它的生命周期随着线程的创建而创建,随着线程的结束而死亡。3、当一个线程正在执行一个Java方法的时候,这个计数器记录的是正在执行的虚拟机字节码指令的地址。如果正在执行的是Native方法,这个计数器值则为空(Undefined)。
虚拟机栈虚拟机栈是线程私有的,与线程的生命周期同步。在java的虚拟机规范中,定义了两种异常:1、StackOverflowError:当线程请求栈深度超出虚拟机栈所允许的深度时抛出。2、OutOfMemoryError:当Java虚拟机动态扩展到无法申请足够内存时抛出。
JVM是基于栈的解释器执行的, ...
如何在工作中快速成长?致工程师的十条建议。
前言
本文是我最近刚看完的一本《阿里工程师的自我修养》书中的部分内容,我做了简单的梳理。侵删。
思考脑与反射脑简单介绍下什么是思考脑和反射脑。思考脑管理性,反射脑管直觉,存储脑管记忆,直觉依赖习惯,用直觉做出反应,快速,但未必正确;思考脑管理性,理性依赖逻辑,缓慢,但更加正确。
有科学家通过研究,发现一个人一天的行为中,5%是非习惯性的,用思考脑的逻辑驱动,95%是习惯性的,用反射脑的直觉驱动,决定我们一生的,永远是95%的反射脑(习惯),而不是5%的思考脑(逻辑)。回想自己的一天,大部分的判断和观点是不是都是靠直觉,靠习惯的,什么情况下才会用思考脑?是不是一个人的时候用思考脑比较多,而在多人对话场景中要快只能靠直觉和反射,而给别人好与不好的印象往往是在对话场景中建立起来的,可想而知,反射出来的观点或行为对我们而言是多么重要。
习以为常把95%中的低质量习惯反射,训练成逻辑后的高质量习惯反射需要有很多的时间保障。但对于处理互联网时代的我们,我们对电子设备的依赖程度已经达到了形影不离的地步。甚至上厕所的那几分钟,也是形影不离。对习惯的认知,关键在于换种说法:“把改变玩手机的习惯,用 ...
算法复杂度
算法复杂度分为时间复杂度和空间复杂度。其作用:时间复杂度是指执行算法所需要的计算工作量;而空间复杂度是指执行这个算法所需要的内存空间。
时间复杂度一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数f(n),进而分析f(n)随n的变化情况并确定T(n)的数量级。这里用”O”来表示数量级,给出算法的时间复杂度。 T(n)=O(f(n));它表示随着问题规模的n的增大,算法的执行时间的增长率和f(n)的增长率相同,这称作算法的渐进时间复杂度,简称时间复杂度。而我们一般讨论的是最坏时间复杂度,这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,分析最坏的情况以估算算法指向时间的一个上界。
时间复杂度的分析方法:1、时间复杂度就是函数中基本操作所执行的次数2、一般默认的是最坏时间复杂度,即分析最坏情况下所能执行的次数3、忽略掉常数项4、关注运行时间的增长趋势,关注函数式中增长最快的表达式,忽略系数5、计算时间复杂度是估算随着n的增长函数执行次数的增长趋势6、递归算法的时间复杂度为:递归总次数 * 每次递归中基本操作所执行的次数
常用的时间复杂度有以下七种, ...
红黑树
红黑树和平衡二叉树的思想是类似的,都是在插入过程中对二叉排序树进行调整,从而提升性能,它的增删改查均可以在O(lg n)内完成。
定义红黑树是一棵二叉排序树。且满足以下特点:
节点是红色或黑色。
根节点是黑色。
每个叶子节点都是黑色的空节点(NIL节点)。
每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
下图就是一棵简单的红黑树示例:示例中每个结点最后都是一个NIL结点,它是黑色的,不过我们画图时通常会省略它。所以下文以及后续文章中绘制时都会省略NIL结点,大家记得还有它就可以。
实现原理红黑树的插入与删除和AVL树类似,也是每插入一个结点,都检查是否破坏了树的结构,然后进行调整。红黑树每个结点插入时默认都为红色,这样做可以降低黑高,也可以减少调整的次数。
插入元素红黑树的概念理解起来较为复杂,我们以一个简单的示例,看看如何构造一棵红黑树。
现有数组int[] a = {1, 10, 9, 2, 3, 8, 7, 4, 5, 6};我们要将其变为一棵红黑树。
首先插入1 ...
树组与链表
数组在java中,数组定义为一种基本类型,其可以通过下标获取到对应位置的数据。那么这种结构的数据,在内存中是怎么存放的呢?
正如上图所示,数组在内存中是一段连续的存储单元,每个数据依次放在每个单元中。分析这种结构,我们可以得出以下几个结论:
创建一个数组,必须声明其长度,以在内存中寻找合适的一段连续存储单元。这也意味着数组的大小是固定的,我们无法动态调整其大小。
想要获取数组中第i个元素,其时间复杂度是O(1),因为可以根据其地址直接找到它。同理修改也是。
数组对查询表现一般,要想查找一个元素,需要遍历,时间复杂度为O(n)。
因为地址连续,想要在数组中插入一个元素是复杂的,因为从插入位置起,后边的所有元素都需要向后移动一位。同理删除也是,只是移动方向为向前。并且,当数组存满时,就无法继续插入了。
因为数组要占据一整块内存,有可能产生许多的碎片,也可能因为找不到合适的内存块,而导致存储失败。
总结起来就是:数组大小固定,查找迅速,增删复杂,需要完整的内存块,容易产生碎片。
链表链表是一种离散存储结构,其在内存中存储不是连续的,每个数据元素都通过一个指针指向其下一 ...
平衡二叉树
二叉排序树很好的平衡了插入与查找的效率,但不平衡的二叉排序树效率大打折扣。今天介绍的AVL树就是一种解决此问题的方案。
定义平衡二叉树,是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1。它是一种高度平衡的二叉排序树。意思是说,要么它是一棵空树,要么它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子BF (Balance Factor),那么平衡二叉树上所有结点的平衡因子只可能是-1、0和1。
如下图就不是一棵AVL树,因为结点18的左子树高度为2,右子树高度为0,高度差大于1。
但通过一定的步骤调整之后,可以将其转为一棵平衡二叉树,如下图:
实现原理平衡二叉树构建的基本思想就是在构建二叉排序树的过程中,每当插入一个结点时,先检查是否因插入而破坏了树的平衡性,若是,则找出最小不平衡子树。在保持二叉排序树特性的前提下,调整最小不平衡子树中各结点之间的链接关系,进行相应的旋转,使之成为新的平衡子树。最小不平衡子树是指距离插入结点最近的,且平衡因子的绝对值大于1 的结点为根的子树。
下面通 ...
二叉排序树
解决查询速度慢的方案除了哈希表外,还可以使用二叉排序树。我们知道,查询慢主要是因为不知道元素的位置,使用hash函数映射虽然解决了问题,但其并不稳定,当出现大量的哈希碰撞后其表现更像一个链表,查询速度大大降低。
二叉排序树的方案则是使元素有序,这样便可以使用二分法进行查找了,虽然效率相比hash函数低一些,但可以通过AVL树、红黑树等增加稳定性。
HashMap在JDK1.8的实现中,就结合了哈希表的高效和红黑树的稳定,我们之后会详细分析其实现。
定义二叉排序树(Binary Sort Tree),又称为二叉查找树。它或者是一棵空树,或者是具有下列性质的二叉树:
若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值
若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值
它的左、右子树也分别为二叉排序树
如下就是一棵简单的二叉排序树:当对这棵树进行中序遍历时,其结果将按照从小到大排序。
查询操作二叉排序树的查找时间复杂度为O(lg n),查找使用二分法。要在上图中找到元素37,只需要四次操作即可。
首先,找到根元素22,37比22大,所以淘汰左子树,再找到35, ...
哈希表
无论是数组还是链表,其对数据的查询表现都比较无力,要想知道一个元素是否在数组或链表中,只能从前向后挨个对比。在后续将会分析的二叉排序树中,还会将数据排序以进行二分查找,将时间复杂度从O(n)降低到O(lg n)。
出现这个问题的根源在于,我们没有办法直接根据一个元素找到它存储的位置,那有没有办法消除这个对比的过程呢?哈希表就是解决查询问题的一种方案。
什么是哈希表通俗来讲,哈希表是通过关键字key来获取数据的一种数据结构。它把关键字映射成表中的位置来获取元素,这种映射称为hash函数。
因为不同的key类型不一样,可能是int,可能是string…但内存地址不会以这些对象也寻址,它会通过hash算法将其转换成int从而完成数据的存储。hash函数需要保证的是对于相同的key,其计算结果总是相同的。
这个过程类似查字典,如果要查一个字,我们不会从第一页到最后一页挨着看,这将需要很长的时间,而是根据其发音先在拼音表中找到对应的页数,直接定位到对应的页即可。当然,由于有许多发音一致的汉字,所以我们可能依然需要逐个对比,但这复杂度就小太多了。
哈希表的过程就和上述例子一样,我们通过key经 ...
树与二叉树
数组与链表是用来解决一对一的问题,而一对多的问题则需要树来解决。
树的定义树是N的节点的有限集。N=0时称为空树,在一个非空树中:
有且只有一个根()节点。
当n>1 时,其余结点可分为m (m>0) 个互不相交的有限集T1 、T2、……、Tm,其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。
下图就是一个树:
节点分类树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree) 。度为0的结点称为叶结点(Leaf) 或终端结点;度不为0 的结点称为非终端结点或分支结点。除根结点之外,分支结点也称为内部结点。树的度是树内各结点的度的最大值。
如下图所示,A结点为根节点,G、H、I、J、F为叶节点,其余节点则为内部节点,此树的度为3。
节点间的关系结点的子树的根称为该结点的孩子(Child),相应地,该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。结点的祖先是从根到该结点所经分支上的所有结点。反之,以某结点为根的子树中的任一结点都称为该结点的子孙。
深度结点的层次(Leve ...
Activity的启动模式
概述上篇我稍微介绍了关于activity的生命周期的知识点,今天我们来谈一下activity的启动模式,这也是一个面试常客。下面容我慢慢道来。
什么情况下会用到启动模式?举个简单的例子,来推送通知之后,我们点击推送跳转页面,如果我们一次来了10个推送,那么我们会先后打开10个页面。但是这10个页面是同一个。这种情况下,我们就需要通过启动模式去解决。
Activity的LaunchMode关于activity的启动模式,目前总共有四种:standard、singleTop、singleTask和singleInstance,下面我们来简单介绍下,四个启动模式的具体含义是什么:
standard:标准模式。这是Android模式的启动模式,所以对这个词陌生也算正常。每次启动一个activity都会创建该实例,不管当前activity是否存在。也就是说可以有多个相同的activity在栈中重叠。也就是上述例子的情况下。
singleTop:栈顶复用模式。在这种模式,如果当前activity已经位于栈顶,此时,当前activity将不再重新创建。同时它的onNewIntent方法会被调用。此 ...