滴滴-测试开发面经（二）

1、堆栈空间分配

栈（操作系统）：由操作系统自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈。

堆（操作系统）：一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收，分配方式倒是类似于链表。

2、堆栈缓存方式

栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放。

堆则是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些。

3、效率比较

栈由系统自动分配，速度较快。但程序员是无法控制的。

堆是由new分配的内存，一般速度比较慢，而且容易产生内存碎片,不过用起来最方便。

4、存储内容

栈：在函数调用时，在大多数的C编译器中，参数是由右往左入栈的，然后是函数中的局部变量。注意静态变量是不入栈的。

当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向函数的返回地址，也就是主函数中的下一条指令的地址，程序由该点继续运行。

堆：一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。

String 类中的属性value为byte数组，被private，final修饰

由此可以知道String的三个不可变特性

①底层是数组，代表String类的长度不可变；

②final修饰，代表数组地址不可变，内存引用不可变；

③private修饰，表示属性私有，数组中的内容不能被修改，只能在本类中访问；

String str=new String(“abc”);创建了几个对象？

在类加载时“abc"将会在常量池中被创建，其次调用new时，JVM命令将会调用String的构造函数。同时引用常量池中"abc"字符串，在堆内存中创建一个String对象！

什么时候方法不能被重写

①，父类中用final修饰方法，代表这个方法不能被覆盖；

②，父类中用static修饰方法，这个方法属于静态方法，而重写只适用于实例方法；

③，父类中private修饰方法，也不能 重写，因为私有子类看不到。

1、Integer是int的包装类，int则是java的一种基本数据类型 

2、Integer变量必须实例化后才能使用，而int变量不需要 

3、Integer实际是对象的引用，当new一个Integer时，实际上是生成一个指针指向此对象；而int则是直接存储数据值 

4、Integer的默认值是null，int的默认值是0

延伸： 

关于Integer和int的比较 

1、由于Integer变量实际上是对一个Integer对象的引用，所以两个通过new生成的Integer变量永远是不相等的（因为new生成的是两个对象，其内存地址不同）。

Integer i = new Integer(100);

Integer j = new Integer(100);

System.out.print(i == j); //false

2、Integer变量和int变量比较时，只要两个变量的值是向等的，则结果为true（因为包装类Integer和基本数据类型int比较时，java会自动拆包装为int，然后进行比较，实际上就变为两个int变量的比较）

Integer i = new Integer(100);

int j = 100；

System.out.print(i == j); //true

3、非new生成的Integer变量和new Integer()生成的变量比较时，结果为false。（因为 ①当变量值在-128~127之间时，非new生成的Integer变量指向的是java常量池中的对象，而new Integer()生成的变量指向堆中新建的对象，两者在内存中的地址不同；②当变量值在-128~127之间时，非new生成Integer变量时，java API中最终会按照new Integer(i)进行处理（参考下面第4条），最终两个Interger的地址同样是不相同的）

Integer i = new Integer(100);

Integer j = 100;

System.out.print(i == j); //false

4、对于两个非new生成的Integer对象，进行比较时，如果两个变量的值在区间-128到127之间，则比较结果为true，如果两个变量的值不在此区间，则比较结果为false

Integer i = 100;

Integer j = 100;

System.out.print(i == j); //true

Integer i = 128;

Integer j = 128;

System.out.print(i == j); //false

对于第4条的原因： 

java在编译Integer i = 100 ;时，会翻译成为Integer i = Integer.valueOf(100)；，而java API中对Integer类型的valueOf的定义如下：

public static Integer valueOf(int i){

    assert IntegerCache.high >= 127;

    if (i >= IntegerCache.low && i <= IntegerCache.high){

        return IntegerCache.cache[i + (-IntegerCache.low)];

    }

    return new Integer(i);

}

java对于-128到127之间的数，会进行缓存，Integer i = 127时，会将127进行缓存，下次再写Integer j = 127时，就会直接从缓存中取，就不会new了。

数组

一、数组的特点

1.在内存中，数组是一块连续的区域

2.数组需要预留空间

在使用前需要提前申请所占内存的大小，这样不知道需要多大的空间，就预先申请可能会浪费内存空间，即数组空间利用率低

ps：数组的空间在编译阶段就需要进行确定，所以需要提前给出数组空间的大小（在运行阶段是不允许改变的）

3.在数组起始位置处，插入数据和删除数据效率低。

插入数据时，待插入位置的的元素和它后面的所有元素都需要向后搬移

删除数据时，待删除位置后面的所有元素都需要向前搬移

4.随机访问效率很高，时间复杂度可以达到O(1)

因为数组的内存是连续的，想要访问那个元素，直接从数组的首地址处向后偏移就可以访问到了

5.数组开辟的空间，在不够使用的时候需要扩容，扩容的话，就会涉及到需要把旧数组中的所有元素向新数组中搬移

6.数组的空间是从栈分配的

二、数组的优点

随机访问性强，查找速度快，时间复杂度为O(1)

三、数组的缺点

1.头插和头删的效率低，时间复杂度为O(N)

2.空间利用率不高

3.内存空间要求高，必须有足够的连续的内存空间

4.数组空间的大小固定，不能动态拓展

链表

一、链表的特点

1.在内存中，元素的空间可以在任意地方，空间是分散的，不需要连续

2.链表中的元素都会两个属性，一个是元素的值，另一个是指针，此指针标记了下一个元素的地址

每一个数据都会保存下一个数据的内存的地址，通过此地址可以找到下一个数据

3.查找数据时效率低,时间复杂度为O(N)

因为链表的空间是分散的，所以不具有随机访问性，如要需要访问某个位置的数据，需要从第一个数据开始找起，依次往后遍历，直到找到待查询的位置，故可能在查找某个元素时，时间复杂度达到O(N)

4.空间不需要提前指定大小，是动态申请的，根据需求动态的申请和删除内存空间，扩展方便，故空间的利用率较高

5.任意位置插入元素和删除元素效率较高，时间复杂度为O(1)

6.链表的空间是从堆中分配的

二、链表的优点

1.任意位置插入元素和删除元素的速度快，时间复杂度为O(1)

2.内存利用率高，不会浪费内存

3.链表的空间大小不固定，可以动态拓展

三、链表的缺点

随机访问效率低，时间复杂度为0(N)

综上：

对于想要快速访问数据，不经常有插入和删除元素的时候，选择数组

对于需要经常的插入和删除元素，而对访问元素时的效率没有很高要求的话，选择链表