先是自我介绍，然后问了一些问题，最后是了解了一下我的实习情况 ## 1、快排的原理及其优化 > 参考自： [快速排序的三种方式以及快排的优化](https://blog.csdn.net/lvyibin890/article/details/79044068) 快排的原理答上来了，**寻找一个基准，将这个基准放到正确的位置上，左边比他大，右边比他小，然后两边采用分治将他们也排好序** 快排要怎么优化呢？ ### 基准值的选取 基准值有三种选取方法， 这里列出他们的优劣 1. 固定位置选取基准：一般的快排的基准值都是选取未排序数组中的第一个或者最后一个基准值。当数组本身是倒序的时候，快排的复杂度就会退化为O(n*n) 2. 随机选取基准：为了避免上面当本身数组是倒序时时间复杂度的退化情况，可以采取随机选取基准的方法。当数组趋于有序时，时间复杂度仍为log(n)。但是当数组中所有的元素相等时，时间仍然会退化至n*n。一般的时间复杂度是O(n * log(n)) 3. 三数取中法选取基准值：取第一个数，最后一个数，第（N/2）个数即中间数，三个数中数值中间的那个数作为基准值。采用三数取中法很好的解决了很多特殊的问题，但对于很多重复的序列，效果依然不好。 ### 排序过程的优化 为了解决基准值没有办法解决的一些问题，这里对排序的过程也进行优化 1. 当待排序序列的长度分割到一定大小后，使用插入排序。 对于待排序的序列长度很小或是基本趋于有序时，排序的效率还是插排好。 自定义截止范围：序列长度N=10。当待排序的序列长度被分割到10时，采用快排而不是插排。 2. 在一次排序后，可以将与基准值相等的数放在一起，在下次分割时可以不考虑这些数。  这种聚集与基准值相等的值的优化方法，在解决数据冗余的情况下非常有用，提高的效率也是非常多。 3. 优化递归操作 ## 2、内存中堆和栈的区别 > 参考自： [栈内存和堆内存的区别（一个笔试题的一部分）](https://blog.csdn.net/richerg85/article/details/19175133) 首先数据结构上和存储的内容上的区别是清楚的，在这里就不重复阐述了 那堆和栈在内存中有什么区别呢？ 1. 程序内存的分配 栈：由编译器自动分配和释放，存放函数的参数、局部变量、临时变量、函数返回地址等 堆：一般有程序员分配和释放，如果没有手动释放，在程序结束时可能由操作系统自动释放（这个针对java那样的有回收机制的语言而说的，对于c/c++,这样的必须要手动释放开辟的堆内存），稍有不慎会引起内存泄漏。 2. 申请后系统的响应 栈：只要栈的剩余空间大于所申请的空间，系统将为程序提供内存，否则将报异常提示栈溢出。 堆：在记录空闲内存地址的链表中寻找一个空间大于所申请空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序。另外，对于大多数系统会在这块内存空间的首地址出记录本次分配空间的大小，这样代码中的delete才能正确释放本内存空间。系统会将多余的那部分重新空闲链表中。 3. 申请大小限制 栈：在Windows下，**栈是向低地址扩展的数据结构**，是一块连续的内存的区域。这句话的意思是栈顶的地址和栈的最大容量是系统预先规定好的，在 WINDOWS下，栈的大小是2M（也有的说是1M，总之是一个编译时就确定的常数），如果申请的空间超过栈的剩余空间时，将提示overflow。因此，能从栈获得的空间较小。 堆：**堆是向高地址扩展的数据结构，是不连续的内存区域。**这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大小受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大。 4. 分配效率 栈：由系统自动分配，速度较快。但程序员是无法控制的。 堆：由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。 另外，在WINDOWS下，最好的方式是用VirtualAlloc分配内存，不是在堆，也不是在栈是直接在进程的地址空间中保留一快内存，虽然用起来最不方便。但是速度快，也最灵活 5. 存储内容 栈：在栈中，第一个进栈的是主函数下一条指令的地址，然后是函数的各个参数，在大多数编译器中，参数是由右往左入栈，然后是函数中的局部变量。注意，静态变量不入栈。出栈则刚好顺序相反。 堆：一般在堆的头部用一个字节存放堆的大小，具体内容由程序员安排。 ## 3、进程和线程的区别 之前总结过这一部分的内容，详见WXG零面总结 这里我只回答出他们的概念，而没有从数据共享、资源消耗等方面回答。还是有点紧张，下次注意 ## 4、链表和数组的区别 我回答了这几点： + 数组允许随机访问，链表不行 + 链表在插入数据的时候更加快速，但是删除和添加到队尾的效率较慢 其实不是很全面，这里重新总结一下 **不同：链表是链式存储结构，数组是顺序存储结构** 链表通过指针来连接元素与元素， 而数组是把所有元素按顺序存储，使用下标访问 链表的插入删除元素相对数组较为简单，不需要移动元素，且较为容易实现长度扩充，但是寻找某个元素较为困难； 数组寻找某个元素较为简单，但插入与删除比较复杂，由于最大长度需要再编程一开始时指定，故当达到最大长度时，扩充长度不如链表方便。 **相同：两种结构均可实现数据的顺序存储，构造出来的模型呈线性结构。** ## 5、引用和指针的区别 这个是C++里面的内容，这里就不展开说了。 > 参考资料： [C++ 引用和指针的区别](https://blog.csdn.net/wang371372/article/details/82178139) ### 联系 指针是指向一块内存地址的变量，这个变量**可以指向其他地址**； 引用是一个变量的别名，**只能是一个变量的别名**。一个变量的引用可以转为指向它的指针。 ### 不同 1. 初始化不同，引用使用时必须初始化，且只能指向一个变量，初始化后不能指向其他变量；指针使用时不必初始化，可以指向nullptr,初始化后仍可以改变指向的地址。 2. 作为函数参数传递时，引用不需要内存拷贝，所以也就不需要申请内存，因此当函数参数传递时，很多时候使用&或者const&传递参数节省内存。 3. 作为函数参数传递时，如果想改变传递进函数参数的原始变量的值，引用改变后改变原始变量，而指针的值改变后并不会改变原始变量，因为它只是一份内存副本，如果想达到改变的效果，使用**。 4. 引用的++ 是变量本身的运算，而指针的++，是内存地址的++。 5. 如果返回动态内存分配的对象或者内存，必须使用指针，引用可能引起内存泄漏。 6. 不要返回局部变量引用，返回对象的引用最好const变量。 7. 操作符<< 和 >> =返回引用，而操作符+-/*的返回对象不能是引用。 ## 6、PUT和POST的区别 这里我回答错了，我答的是PUT是对访问实体资源本身的修改，而POST只是表单的修改。其实不是这样的 他们的真正区别如下： > [post和put的区别](https://blog.csdn.net/xcc_2269861428/article/details/80433382) GET，PUT，DELETE都是幂等操作，而POST不是，以下进行分析： 首先GET请求很好理解，对资源做查询多次，此实现的结果都是一样的。 PUT请求的幂等性可以这样理解，将A修改为B，它第一次请求值变为了B，再进行多次此操作，最终的结果还是B，与一次执行的结果是一样的，所以PUT是幂等操作。 同理可以理解DELETE操作，第一次将资源删除后，后面多次进行此删除请求，最终结果是一样的，将资源删除掉了。 POST不是幂等操作，因为有可能存在这么一种情况，一次请求添加一份新资源，二次请求则添加了两份新资源，多次请求可能会产生不同的结果，因此POST不是幂等操作。 ## 7、gc的机制和原理 > [Java -- 深入浅出GC自动回收机制](https://www.cnblogs.com/wjtaigwh/p/6635484.html) > [Java系列笔记(3) - Java 内存区域和GC机制](https://www.cnblogs.com/zhguang/p/3257367.html) GC：Garbage Collection，垃圾回收器，用来释放没有用的对象所占用的内存空间 Java不像C++那样有delete或者free方法来释放对象的内存，而是通过GC自动地定时地回收没有被使用的对象的空间，这样降低了产生内存溢出和内存泄漏的可能性。但是一旦出现了内存溢出和内存泄漏，却又不了解虚拟机是怎么分配内存的，那么定位错误和排查错误将会是一个很困难的事情。 Java内存分配和回收的机制概括的说，就是：**分代分配，分代回收。** Java对象根据存活的事件被划分为：**年轻代（Young Generation）、年老代（Old Generation）、永久代（Permanent Generation，也就是方法区）。** ### 年轻代（Young Generation） 年轻代的内存区域又可以分为3个区域：Eden区和两个存活区（Survivor 0 、Survivor 1）。 年轻代中的GC活动可以描述为以下几点： 1. 绝大多数刚创建的对象会被分配在Eden区（大对象可以直接被创建在年老代），其中的大多数对象很快就会消亡（IBM的研究表明，98%的对象都是很快消亡的）。Eden区是连续的内存空间，因此在其上分配内存极快； 2. 程序开始运行之后，最初一次Eden区满时，执行Minor GC（Yong GC），将消亡的对象清理掉，并将剩余的对象复制到一个空的存活区，此处假设为Survivor0（此时，Survivor1是空白的，两个Survivor总是至少有一个是空白的）； 3. 下次Eden区满了，再执行一次Minor GC，将消亡的对象清理掉，将存活的对象复制到Survivor1中，然后清空Eden区； 4. 将Survivor0中消亡的对象清理掉，将其中可以晋级的对象晋级到Old区，将存活的对象也复制到Survivor1区，然后清空Survivor0区； 5. 当两个存活区切换了几次（HotSpot虚拟机默认15次，用-XX:MaxTenuringThreshold控制，大于该值进入老年代，但这只是个最大值，并不代表一定是这个值）之后，仍然存活的对象（其实只有一小部分，比如，我们自己定义的对象），将被复制到老年代。 从上面的过程可以看出，Eden区是连续的空间，而两个Survivor区至少有一个为空。经过一次GC，其中一个Survivor肯定会持有经过GC之后存活的对象。那么其他两个区的内容就不再需要了，可以直接清空。到下一次GC时，两个Survivor区角色互换。这种分配内存和清理内存的效率都极高，这种GC方式就是著名的 **“停止-复制（Stop-and-copy）”清理法（将Eden区和一个Survivor中仍然存活的对象拷贝到另一个Survivor中）** 但是这不代表停止-复制方法很高效，他只在这种情况下高效。如果老年代也采用停止-复制，那么效率将会极低。（思考为什么？） #### 拓展 在Eden区，HotSpot虚拟机使用了两种技术来加快内存分配。分别是bump-the-pointer和TLAB（Thread-Local Allocation Buffers），这两种技术的做法分别是：由于Eden区是连续的，因此bump-the-pointer技术的核心就是跟踪最后创建的一个对象，在对象创建时，只需要检查最后一个对象后面是否有足够的内存即可，从而大大加快内存分配速度；而对于TLAB技术是对于多线程而言的，将Eden区分为若干段，每个线程使用独立的一段，避免相互影响。TLAB结合bump-the-pointer技术，将保证每个线程都使用Eden区的一段，并快速的分配内存。 ### 老年代（Old Generation） 对象如果在年轻代存活了足够长的时间而没有被清理掉（即在几次Young GC后存活了下来），则会被复制到年老代。年老代的空间一般比年轻代大（存活时间长），比较稳定，能存放更多的对象，在年老代上发生的GC次数也比年轻代少。　　 如果对象比较大（比如长字符串或大数组），Young空间不足，则大对象会直接分配到老年代上（大对象可能触发提前GC，应少用，更应避免使用短命的大对象）。 当年老代内存不足时，将执行Major GC，也叫 Full GC。但是因为老年代空间大、对象大小也偏大，所以如果采用停止-复制方法，那么花费的事件和空间与年轻代相比那将是效率极低的。这里介绍几种老年代GC算法。 1. Mark-Sweep（标记-清除）算法 这是最基础的垃圾回收算法，之所以说它是最基础的是因为它最容易实现，思想也是最简单的。标记-清除算法分为两个阶段：标记阶段和清除阶段。标记阶段的任务是**标记出所有存活的对象**，清除阶段就是回收没有标记的对象所占用的空间。  优点：实现容易 缺点：在多次回收之后，内存空间不连续，容易产生内存碎片，内存利用率降低。 2. Copying（复制）算法 为了解决Mark-Sweep算法的缺陷，Copying算法就被提了出来。它将可用内存按容量划分为大小相等的两块，每次只使用其中的一块。当这一块的内存用完了，就将还存活着的对象复制到另外一块上面，然后再把已使用的内存空间一次清理掉，这样一来就不容易出现内存碎片的问题。  这个有点像年轻代的停止-复制算法。但是这样也会带来比较大的缺陷 优点：不会产生碎片 缺点：空间利用率低，相比标记-清除算法回收时间长（老年代对象多、空间大） 3. Mark-Compact（标记-整理）算法 为了解决Copying算法的缺陷，充分利用内存空间，提出了Mark-Compact算法。该算法标记阶段和Mark-Sweep一样，但是在完成标记之后，它不是直接清理可回收对象，**而是将存活对象都向一端移动，然后清理掉端边界以外的内存。**  优点：空间利用率高，不会产生碎片，回收时间较短 缺点：实现较为复杂 这种算法是一般JVM中老年代使用的算法 ### 永久代（方法区） 永久代的回收有两种：常量池中的常量，无用的类信息，常量的回收很简单，没有引用了就可以被回收。对于无用的类进行回收，必须保证3点： + 类的所有实例都已经被回收 + 加载类的ClassLoader已经被回收 + 类对象的Class对象没有被引用（即没有通过反射引用该类的地方） 永久代的回收并不是必须的，可以通过参数来设置是否对类进行回收。 ### 扩展：可达性分析算法 > 参考资料： [可达性算法、Java引用 详解](https://www.jianshu.com/p/8f5fa8288d9b) 在Java中，是通过可达性分析（Reachability Analysis）来判定对象是否存活的。该算法的基本思路就是通过一些被称为引用链（GC Roots）的对象作为起点，从这些节点开始向下搜索，搜索走过的路径被称为（Reference Chain)，当一个对象到GC Roots没有任何引用链相连时（即从GC Roots节点到该节点不可达），则证明该对象是不可用的。  在java中，可以作为GC root的对象包括以下几种： + 虚拟机栈（栈帧中的本地变量表）中引用的对象 + 方法区中类静态属性引用的对象 + 方法区中常量引用的对象 + 本地方法栈中JNI（即一般说的Native方法）引用的对象 ### 扩展：Java中的引用 从可达性算法中可以看出，判断对象是否可达时，与“引用”有关。那么什么情况下可以说一个对象被引用，引用到底代表什么？ 在JDK1.2之后，Java对引用的概念进行了扩充，可以将引用分为以下四类： + 强引用（Strong Reference) 在代码中的普遍存在的，类似于`Object obj = new Object();`这样的引用。 只要强引用存在，GC将永远不会收集被引用对象。哪怕是OOM。 + 软引用（Soft Reference) 软引用是用来描述一些有用但并不是必需的对象，在Java中用`java.lang.ref.SoftReference`类来表示。 对于软引用关联着的对象，只有在内存不足的时候JVM才会回收该对象。因此，这一点可以很好地用来解决OOM的问题 ``` SoftReference<String> sr = new SoftReference<String>(new String("hello")); // 创建一个软引用 ``` + 弱引用（Weak Reference) 弱引用也是用来描述非必需对象的，当JVM进行垃圾回收时，无论内存是否充足，都会回收被弱引用关联的对象。 在java中，用`java.lang.ref.WeakReference`类来表示。 ``` WeakReference<String> sr = new WeakReference<String>(new String("hello")); // 创建一个弱引用 ``` + 虚引用（Phantom Reference) 虚引用和前面的软引用、弱引用不同，它并不影响对象的生命周期。在java中用`java.lang.ref.PhantomReference`类表示。 如果一个对象与虚引用关联，则跟没有引用与之关联一样，在任何时候都可能被垃圾回收器回收。 ### 扩展：GC种类 上面的是一些常见的垃圾收集算法，垃圾收集算法是内存回收的理论基础，而垃圾收集器就是内存回收的具体实现。下面有几种创建的垃圾收集器，用户可以根据自己的需求组合出新年代和老年代使用的收集器。下面是常见的划分办法 新生代GC ：串行GC(SerialGC)、并行回收GC(ParallelScavenge)和并行GC(ParNew) 串行GC：在整个扫描和复制过程采用单线程的方式来进行，适用于单CPU、新生代空间较小及对暂停时间要求不是非常高的应用上，是client级别默认的GC方式，可以通过-XX:+UseSerialGC来强制指定。 并行回收GC：在整个扫描和复制过程采用多线程的方式来进行，适用于多CPU、对暂停时间要求较短的应用上，是server级别默认采用的GC方式，可用-XX:+UseParallelGC来强制指定，用-XX:ParallelGCThreads=4来指定线程数。 并行GC：与老年代的并发GC配合使用。 老年代GC：串行GC(Serial MSC)、并行GC(Parallel MSC)和并发GC(CMS)。 串行GC（Serial MSC）：client模式下的默认GC方式，可通过-XX:+UseSerialGC强制指定。每次进行全部回收，进行Compact，非常耗费时间。 并行GC（Parallel MSC）：吞吐量大，但是GC的时候响应很慢：server模式下的默认GC方式，也可用-XX:+UseParallelGC=强制指定。可以在选项后加等号来制定并行的线程数。 并发GC（CMS）：响应比并行gc快很多，但是牺牲了一定的吞吐量。 ## 6、一道理解错的算法题 剑指Offer第55道面试题。八说了，那么简单却理解错了，都是泪 <br /> <br /> <br /> <br /> <div align="right"> Chen Sicong 搬运时间：2019年8月2日 22:26:39 </div>