面试基本知识点总结

1、       关于Singleton模式

合理的实现Singleton模式要求考虑到多线程情况以及时间效率。

1)        多线程但工作效率差

2)        多线程工作效率高（同步锁加前后两次判断），这里主要考虑到加锁操作也是一个非常耗时的。

2、       Java自带的类中那些应用到了快速排序和平衡二叉排序

Java自带排序操作函数：Arrays.sort(数组）、Collections.sort(集合）

1)      Arrays.sort()是java自带的排序函数，排序Object的时候都是用合并排序，排序primitive（int，float等原型数据）的时候用的是快速排序。对于对象的排序，稳定性很重要，而且优化之后的归并排序其时间复杂度也在O（nlog(n)）。对象数组中保存的只是对象的引用，这样多次移位并不会造成额外的开销，但是，对象数组对比较次数一般比较敏感，有可能对象的比较比单纯数的比较开销大很多。归并排序在比较次数方面比快速排序做得更好，这也是选择它作为对象排序的一个重要原因之一。

排序优化：实现中快排和归并都采用递归方式，而在递归的底层，也就是待排序的数组长度小于7时，直接使用冒泡排序，而不再递归下去。

Arrays.sort()除可以传入原型类型数组之外，还可以传入Object[]数组；或者传入实现了Comparator的object[].Comparator其实就是一个比较器，规定了对象的比较策略。如下：

快速排序的优化：

1、 当待排序的数组中的元素个数较少时，源码中的阀值为7，采用的是插入排序。尽管插入排序的时间复杂度为0(n^2)，但是当数组元素较少时，插入排序优于快速排序，因为这时快速排序的递归操作影响性能。

2、 较好的选择了划分元（基准元素）。能够将数组分成大致两个相等的部分，避免出现最坏的情况。例如当数组有序的的情况下，选择第一个元素作为划分元，将使得算法的时间复杂度达到O(n^2).

选择划分元策略：

          i.              当数组大小为 size=7 时 ，取数组中间元素作为划分元。int n=m>>1;(此方法值得借鉴)

        ii.              当数组大小 7<size<=40时，取首、中、末三个元素中间大小的元素作为划分元。

iii.      当数组大小 size>40 时 ，从待排数组中较均匀的选择9个元素，选出一个伪中数做为划分元。

3、 普通的快速排序算法，经过一次划分后，将划分元排到素组较中间的位置，左边的元素小于划分元，右边的元素大于划分元，而没有将与划分元相等的元素放在其附近

2)      Collections.sort

先查看一段源码：

可以看到，Collections.sort方法的本质实现还是Arrays.sort(),当T类型为对象时，则需要实现Comparable接口，采用MergeSort().

3、       排序算法对比和优化

冒泡排序算法时间复杂度是O(n^2)，稳定排序；

选择排序算法时间复杂度是O(n^2)，不稳定排序；

插入排序算法时间复杂度是O(n^2)，稳定排序；

快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n^2)。

堆排序算法时间复杂度是O(nlogn)，不稳定排序；

归并排序算法时间复杂度是O(nlogn)，稳定排序。

快速排序的优化在于划分元的选择策略上，这一点在第二部分有讲述。

归并排序和快速排序都涉及递归操作，当数组元素比较少时，插入排序的效率是更高的，所以可以考虑在递归的最后一步采用插入排序实现。

4、        跳跃链表Skip List

Skip List是一种随机化的数据结构，基于并联的链表，其效率可比拟于二叉查找树（对于大多数操作需要O(log n)平均时间）。基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得 名)。所有操作都以对数随机化的时间进行。Skip List可以很好解决有序链表查找特定值的困难。

一个跳表，应该具有以下特征：

1)  一个跳表应该有几个层（level）组成；

2)  跳表的第一层包含所有的元素；

3)  每一层都是一个有序的链表；

4)  如果元素x出现在第i层，则所有比i小的层都包含x；

5)  第i层的元素通过一个down指针指向下一层拥有相同值的元素；

6)  在每一层中，-1和1两个元素都出现(分别表示INT_MIN和INT_MAX)；

7)  Top指针指向最高层的第一个元素。

构建有序链表

           

的一个跳跃表如下：

skip List构造步骤

1)   给定一个有序的链表。

2)   选择连表中最大和最小的元素，然后从其他元素中按照一定算法（随机）随即选出一些元素，将这些元素组成有序链表。这个新的链表称为一层，原链表称为其下一层

3)   为刚选出的每个元素添加一个指针域，这个指针指向下一层中值同自己相等的元素。Top指针指向该层首元素

4)   重复2、3步，直到不再能选择出除最大最小元素以外的元素。

在选定更高一层元素时候，可以采用随机的方法，也可以采用固定的概率P。每个更高层都充当下面列表的"快速跑道"，这里在层 i 中的元素按某个固定的概率 p 出现在层 i+1 中。要查找一个目标元素，起步于头元素和顶层列表，并沿着每个链表搜索，直到到达小于或的等于目标的最后一个元素。通过跟踪起自目标直到到达在更高列表中出现的元素的反向查找路径，在每个链表中预期的步数显而易见是 1/p。所以查找的总体代价是 O(log1/p n / p)，当p 是常数时是 O(log n)。通过选择不同 p 值，就可以在查找代价和存储代价之间作出权衡。

5、       Java一些内部机制

Java的内部机制主要包括：内存管理和内存释放等处理，java类加载和初始化等。

1)  内存管理和内存释放等处理

分配：内存的分配是由程序完成的，程序员需要通过关键字new 为每个对象申请内存空间 (基本类型除外)，所有的对象都在堆 (Heap)中分配空间。
    释放：对象的释放是由垃圾回收机制决定和执行的，这样做确实简化了程序员的工作。但同时，它也加重了JVM的工作。因为，GC（Garbage Collection）为了能够正确释放对象，GC必须监控每一个对象的运行状态，包括对象的申请、引用、被引用、赋值等，GC都需要进行监控。 

下面我们再来讨论一下内存泄露的问题，内存泄漏有两种情况。一种情况如在C/C++语言中的，在堆中的分配的内存，在没有将其释放掉的时候，就将所有能访问这块内存的方式都删掉（如指针重新赋值），这是在C编程中经常容易犯的错误即忘记内存的释放；另一种情况则是在内存对象明明已经不需要的时候，还仍然保留着这块内存和它的访问方式（引用）。第一种情况，在Java中已经由于垃圾回收机制的引入，得到了很好的解决。所以，Java中的内存泄漏，主要指的是第二种情况。为了避免第二种方式造成的内存泄露，在使用中，应该注意的问题有：

在不涉及复杂数据结构的一般情况下，Java的内存泄露表现为一个内存对象的生命周期超出了程序需要它的时间长度。我们有时也将其称为“对象游离”。 要避免这种情况下的内存泄露，要求我们以C/C++的内存管理思维来管理自己分配的内存。第一，是在声明对象引用之前，明确内存对象的有效作用域。在一个函数内有效的内存对象，应该声明为local变量，与类实例生命周期相同的要声明为实例变量……以此类推。第二，在内存对象不再需要时，记得手动将其引用置空。

Java中有几种不同的引用方式，它们分别是：强引用、软引用、弱引用和虚引用。这几种引用方式对于GC回收机制具有不同的效果，具体如下：

强引用

在此之前我们介绍的内容中所使用的引用都是强引用，如Object object = new Object();这是使用最普遍的引用。如果一个对象具有强引用，那就类似于必不可少的生活用品，垃圾回收器绝不会回收它。当内存空 间不足，Java虚拟机宁愿抛出OutOfMemoryError错误，使程序异常终止，也不会靠随意回收具有强引用的对象来解决内存不足问题。

软引用（SoftReference）

SoftReference 类的一个典型用途就是用于内存敏感的高速缓存cache。SoftReference 的原理是：在保持对对象的引用时保证在 JVM 报告内存不足情况之前将清除所有的软引用。关键之处在于，垃圾收集器在运行时可能会（也可能不会）释放软可及对象。对象是否被释放取决于垃圾收集器的算法 以及垃圾收集器运行时可用的内存数量。

弱引用（WeakReference）

WeakReference 类的一个典型用途就是规范化映射（canonicalized mapping）。另外，对于那些生存期相对较长而且重新创建的开销也不高的对象来说，弱引用也比较有用。关键之处在于，垃圾收集器运行时如果碰到了弱可及对象，将释放 WeakReference 引用的对象。然而，请注意，垃圾收集器可能要运行多次才能找到并释放弱可及对象。

虚引用（PhantomReference）

PhantomReference 类只能用于跟踪对被引用对象即将进行的收集。同样，它还能用于执行 pre-mortem 清除操作。PhantomReference 必须与 ReferenceQueue 类一起使用。需要 ReferenceQueue 是因为它能够充当通知机制。当垃圾收集器确定了某个对象是虚可及对象时，PhantomReference 对象就被放在它的 ReferenceQueue 上。将 PhantomReference 对象放在 ReferenceQueue 上也就是一个通知，表明 PhantomReference 对象引用的对象已经结束，可供收集了。这使您能够刚好在对象占用的内存被回收之前采取行动。Reference与ReferenceQueue的配合使用。

2)  java类加载和初始化

java 类的加载主要有以下几点原则：对实体的创建或者对static成员的访问都会触发类的加载，类的加载是按照“子类->基类->根基类”的顺序进行的，类的加载只进行一次，加载之后新实体类的创建不会触发类的重新加载，因为这时类已经处于内存之中。

初始化的进行则是按照“根基类->基类->子类”的顺序进行，因为子类的访问可能依赖基类成员变量，这个顺序非常重要。

3)  java内存管理

在java中，有java程序、虚拟机、操作系统三个层次，其中java程序与虚拟机交互，而虚拟机与操作系统间交互！这就保证了java程序的平台无关性！

a)   程序运行前：JVM向操作系统请求一定的内存空间，称为初始内存空间！程序执行过程中所需的内存都是由java虚拟机从这片内存空间中划分的。

b)   程序运行中：java程序一直向java虚拟机申请内存，当程序所需要的内存空间超出初始内存空间时，java虚拟机会再次向操作系统申请更多的内存供程序使用！

c)   内存溢出：程序接着运行，当java虚拟机已申请的内存达到了规定的最大内存空间，但程序还需要更多的内存，这时会出现内存溢出的错误！

    JVM 会把申请的内存从逻辑上划分为三个区域，即：方法区、堆与栈。 

a)   方法区：方法区默认最大容量为64M，Java虚拟机会将加载的java类存入方法区，保存类的结构（属性与方法），类静态成员等内容。

b)   堆：默认最大容量为64M，堆存放对象持有的数据，同时保持对原类的引用。可以简单的理解为对象属性的值保存在堆中，对象调用的方法保存在方法区。

c)   栈：栈默认最大容量为1M，在程序运行时，每当遇到方法调用时，Java虚拟机就会在栈中划分一块内存称为栈帧（Stack frame），栈帧中的内存供局部变量（包括基本类型与引用类型）使用，当方法调用结束后，Java虚拟机会收回此栈帧占用的内存。 

     如图所示，java对象的数据是存放在堆中的，栈则是存放引用和基本数据类型。

6、       递归算法时间复杂度的计算

递归算法的时间复杂度我们可以采用递归树来计算。

在引入递归树之前可以考虑一个例子：

　　T(n) = 2T(n/2) + n²

　　迭代2次可以得：

　　T(n) = n² + 2(2T(n/4) + (n/2) ²)

　　还可以继续迭代，将其完全展开可得：

　　T(n) = n² + 2((n/2) ² + 2((n/2²)² + 2((n/2³) ² + 2((n/2⁴) ² +…+2((n/2ⁱ) ² + 2T(n/2^{i + 1})))…))))　　……(1)

　　而当n/2ⁱ⁺¹ == 1时，迭代结束。

　　将(1)式小括号展开，可得：

　　T(n) = n² + 2(n/2)² + 2²(n/2²) ² + … + 2ⁱ(n/2ⁱ)² + 2ⁱ⁺¹T(n/2ⁱ⁺¹)

　　这恰好是一个树形结构，由此可引出递归树法。

 

　　图中的(a)(b)(c)(d)分别是递归树生成的第1,2,3,n步。每一节点中都将当前的自由项n²留在其中，而将两个递归项T(n/2) + T(n/2)分别摊给了他的两个子节点，如此循环。

　　图中所有节点之和为:

　　[1 + 1/2 + (1/2)² + (1/2)³ + … + (1/2)ⁱ] n² = 2n²

　　可知其时间复杂度为O(n²)

　　

　　可以得到递归树的规则为：

　　(1) 每层的节点为T(n) = kT(n / m) + f(n)中的f(n)在当前的n/m下的值；

　　(2) 每个节点的分支数为k；

　　(3)每层的右侧标出当前层中所有节点的和。

　　再举个例子：

　　T(n) = T(n/3) + T(2n/3) + n

　　其递归树如下图所示：

　　

　　可见每层的值都为n，从根到叶节点的最长路径是：

　　

　　因为最后递归的停止是在(2/3)^kn == 1.则

　　　　　　

　　于是

　　　　

　　即T(n) = O(nlogn)　

下面我们可以来考察一下归并排序的时间复杂度：O(nlogn)。

7、       单链表相关算法

1)        单链表倒置

如图所示，借助辅助指针，采用倒插法实现：

2)        求链表的倒数第K个节点，如果K大于链表长度则返回NULL

采用一种比较经典的思想：两个游标指针，两个指针相差K个节点，同时移动，直到后面那个指针遍历完整个链表。

3)        不知道单链表节点前驱的情况下，删除该节点

方法就是将该节点的后继结点中的值数据拷到本节点中，然后删掉后继节点。删除节点的本质其实还是删除节点中的数值，这个要注意。

4)        求单链表的中间节点，偶数个节点时返回中间两个节点的前一个

同样采用两个游标的方式，游标p按照步长1移动，游标q按照步长2移动，直到游标q遍历完整个链表。

5)        判断单链表是否有环，并求出环开始的节点；如果没有环，就返回NULL

同样采用两个游标的方式，游标p按照步长1移动，游标q按照步长2移动，如果q能够追上p则说明他们存在环，若q到达了终点，那就说明没有环的存在。

环的长度计算，当p，q相遇之后，记下相遇的点，然后继续让p移动，再次回到该点时计算移动的步数，这就是环的长度。

6)         判断两个单链表是否相交，如果相交则返回交点的指针，否则返回NULL

如果两个链表相交，那么，在这个相交的节点之后所有的节点都是两个链表共有的，抓住这一点。求交点思路有些巧妙：在判断是否存在交点遍历两链表的时候，我们可以顺便分别计算两链表的长度，然后计算其长度差d，再分别从短链表和长链表的第d个节点开始遍历并判断两者是否相等，第一个相等的节点指针就是交点指针。

7)        从尾到头打印链表

8)         

8、       C语言类型和类型转换的问题

以上是C语言中数据类型的取值范围等信息，在类型转换中，低精度向高精度转换这里不用赘言，高精度向低精度转换则要注意了，会自动截取多余部分。

负数在C语言里面采用补码形式表示，最高位为符号位。Int -1为0xFFFFFFFF，+1取反加1所得。Unsigned int = -1,则是OxFFFFFFFF-1 = 2³²-1-1 = 4294967295.对于unsigned int类型，负数会自动转换正数。

Java基本类型占用字节数

1.整型

类型              存储需求     bit数    取值范围      备注

int                 4字节           4*8

short             2字节           2*8    －32768～32767

long              8字节           8*8

byte              1字节           1*8     －128～127

2.浮点型

类型              存储需求     bit数    取值范围      备注

float              4字节           4*8                  float类型的数值有一个后缀F(例如：3.14F)

double          8字节           8*8                       没有后缀F的浮点数值(如3.14)默认为double类型

3.char类型

类型              存储需求     bit数     取值范围      备注

char              2字节          2*8

4.boolean类型

类型              存储需求    bit数    取值范围      备注

boolean        1字节          1*8      false、true

9、       数据结构中具有重要作用的树结构

这里主要讲述一些数据结构中的二叉树、二叉线索树、二叉排序树、二叉平衡树、B-树、B+树、红黑树、键树等。